Эффективные строковые алгоритмы в модели потока данных : диссертация на соискание ученой степени кандидата физико-математических наук : 05.13.17

1 Введение 4
1.1 Предварительные сведения . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1 Строки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Асимптотические оценки сложности . . . . . . . . . . . . . 6
1.1.3 Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.4 Хэш Карпа–Рабина . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.5 Словари . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.6 Принцип Яо . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.7 Модель потока данных . . . . . . . . . . . . . . . . . . . . . 10
1.2 Обзор диссертации . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2.1 Цели и задачи диссертации . . . . . . . . . . . . . . . . . . 12
1.2.2 Основные методы исследования . . . . . . . . . . . . . . . 12
1.2.3 Структура диссертации и организация текста . . . . . . . . 12
1.2.4 Апробация и публикации . . . . . . . . . . . . . . . . . . . 13
1.2.5 Основные результаты диссертации . . . . . . . . . . . . . . 13

2 Палиндромы в потоках 17
2.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Нижние оценки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Алгоритмы реального времени . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Аддитивная погрешность . . . . . . . . . . . . . . . . . . . 21
2.3.2 Мультипликативная погрешность ≤ 1 . . . . . . . . . . . 22
2.3.3 Мультипликативная погрешность > 1 . . . . . . . . . . . 27

3 Повторы и обратные повторы в потоках 32
3.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Сведение к сжатым повторам . . . . . . . . . . . . . . . . . . . . . 35
3.4 Поиск наибольшего обратного повтора . . . . . . . . . . . . . . . . 37
3.5 Поиск наибольшего повтора . . . . . . . . . . . . . . . . . . . . . . 44
3.6 Нижние оценки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 Максимальные периодические подстроки в потоках 50
4.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Определения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3 Инструменты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.1 Хэши, фреймы, чекпойнты . . . . . . . . . . . . . . . . . . 53
4.3.2 Видимые периодические строки . . . . . . . . . . . . . . . 54
4.3.3 Свежие и чёрствые вхождения . . . . . . . . . . . . . . . . 56
4.3.4 Структуры данных . . . . . . . . . . . . . . . . . . . . . . . 57
4.4 Алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4.1 Удаление чекпойнтов . . . . . . . . . . . . . . . . . . . . . . 59
4.4.2 Обновление групп . . . . . . . . . . . . . . . . . . . . . . . 60
4.4.3 Обнаружение периодических подстрок . . . . . . . . . . . . 61
4.4.4 Обновление списка отслеживания . . . . . . . . . . . . . . 64

Заключение 68

Список литературы 70

Список иллюстраций 75

Итоги выполненного исследования
В диссертации рассмотрены задачи поиска основных регулярных структур в
строках в модели потока данных. Представим краткое резюме по каждой из трёх
основных глав и сформулируем связанные открытые проблемы для дальнейшего
исследования.
Отметим, что все разработанные нами алгоритмы являются рандомизи-
рованными алгоритмами типа Монте-Карло, т.е. решают задачи с высокой
вероятностью, используя детерминированный объём памяти за детерминиро-
ванное время. При этом доказано, что другие типы алгоритмов для решения
поставленных задач требуют как минимум линейных затрат памяти, а значит,
непригодны для потоковой модели.

Палиндромы в потоках
Для задачи LPS о наибольшем палиндроме в модели потока данных мы предста-
вили алгоритмы реального времени для приближенного решения с аддитивной
и мультипликативной погрешностью. При этом объём памяти, используемый
представленными алгоритмами, асимптотически точно совпадает с имеющимися
нижними оценками при большинстве значений параметров задачи. Таким обра-
зом, вопрос о вычислительной сложности задачи LPS в модели потока данных
разрешён.
Отдельно можно отметить введённую функцию времени жизни (ttl), ко-
торая показала себя удобным инструментом и для решения задачи о поиске
максимальных периодических подстрок (approxRuns).

Повторы и обратные повторы в потоках
Мы показали, что задача поиска наибольшего повтора(LRS) и задача поиска
наибольшего обратного повтора(LRRS) в модели потока данных могут быть
решены только с использованием приближенных алгоритмов типа Монте-Карло.
И доказали нижнюю оценку в Ω( log min{|Σ|, }) бит памяти для приближения
ответа с аддитивной погрешностью .
Для обеих задач представлены алгоритмы типа Монте-Карло, близкие к
реальному времени, использующие ( + ) слов памяти, где — аддитивная
ошибка приближения. При этом используемая
√ память точно совпадает с нижни-
ми оценками при условиях = ( ) и |Σ| = Ω( 0.01 ). Алгоритмы основаны
на суффиксных деревьях, что весьма необычно для потоковой модели.

Максимальные периодические подстроки в потоках
Мы доказали, что в потоковой модели не существует алгоритма, точно находя-
щего все максимальные периодические подстроки и сформулировали прибли-
женную версию задачи (approxRuns).
Для приближенной задачи мы представили алгоритм типа Монте-Карло,
близкий к реальному времени, и использующий ( log ) слов памяти.

Перспективы дальнейшей разработки темы
В задаче поиска наибольшего повтора(LRS) и задаче поиска наибольшего обрат-
ного повтора(LRRS) в модели потока данных открытыми остаются вопросы о
нижней оценке на необходимую память для приближения
√ с мультипликативной
ошибкой, а также с аддитивной ошибкой = Ω( ). Кроме того, открыт вопрос
о потоковом алгоритме с мультипликативной ошибкой.
В задаче приближенного поиска всех максимальных периодических подстрок
в потоках открытым остаётся вопрос о нижней оценке на необходимую память.

[1] Alon N., Matias Y., Szegedy M. The space complexity of approximating the
frequency moments // Journal of Computer and system sciences. –– 1999. ––
Vol. 58, no. 1. –– P. 137–147.