Эффективные строковые алгоритмы в модели потока данных
Аннотация
Строка — один из центральных объектов компьютерных наук. Любая последовательность данных может рассматриваться как строка (по- следовательность символов). Такое абстрактное представление, не учитывающее структуру обрабатываемых данных, имеет очень широкую область примене- ний — от поиска в базах данных до анализа структуры ДНК и белков. Раздел компьютерных наук, занимающийся алгоритмами обработки строк, называется стрингология (англ. stringology от string — строка). Название было предложено в 1985 в работе [19]. Этой динамически развивающейся в настоящее время области посвящен ряд монографий [13,15,24,42] и специализированных конференций с высоким уровнем цитируемости: Combinatorial Pattern Matching (CPM), String Processing and Information Retrieval (SPIRE) и др. Задачи, рассматриваемые в стрингологии, можно сгруппировать в несколько кластеров: поиск по образцу (pattern matching), индексирование данных, сжатие данных и алгоритмы на сжа- тых представлениях, а также поиск регулярных структур, таких как повторы, палиндромы, периодические фрагменты и различные их обобщения. Последнему кластеру принадлежат задачи, рассматриваемые в диссертации.
Одной из активно исследуемых областей являются строковые алгоритмы в модели потока данных. В этой модели элементы последовательности данных поступают один за одним и не могут быть сохранены в связи с малым объёмом доступной памяти. Первые работы, рассматривающие подобные ограничения, появились в 1970-е годы [39]. При этом понятие модели потока данных было сформулировано в работе [1], авторы которой получили в 2005 г. премию Гёделя за основополагающие исследования в области потоковых алгоритмов. Интересной особенностью модели потока данных является то, что в ней зачастую удаётся получить нижние оценки на вычислительную сложность задач, в первую очередь на необходимый объём памяти.
Первый значительный результат о строковых алгоритмах в модели потока данных был получен в [40]. В последнее десятилетие модель потока данных является заметным трендом в стрингологии. В настоящей работе рассматриваются строковые задачи, связанные с поиском регулярных структур в потоке данных.
Одной из активно исследуемых областей являются строковые алгоритмы в модели потока данных. В этой модели элементы последовательности данных поступают один за одним и не могут быть сохранены в связи с малым объёмом доступной памяти. Первые работы, рассматривающие подобные ограничения, появились в 1970-е годы [39]. При этом понятие модели потока данных было сформулировано в работе [1], авторы которой получили в 2005 г. премию Гёделя за основополагающие исследования в области потоковых алгоритмов. Интересной особенностью модели потока данных является то, что в ней зачастую удаётся получить нижние оценки на вычислительную сложность задач, в первую очередь на необходимый объём памяти.
Первый значительный результат о строковых алгоритмах в модели потока данных был получен в [40]. В последнее десятилетие модель потока данных является заметным трендом в стрингологии. В настоящей работе рассматриваются строковые задачи, связанные с поиском регулярных структур в потоке данных.