Общая характеристика работы 2
Положения, выносимые на защиту 5
Степень достоверности и апробация результатов 6
Основное содержание работы 7
Заключение 15
Список литературы 17
Купить

Актуальность темы. Строка — один из центральных объектов компьютерных наук. Любая последовательность данных может рассматриваться как строка (по­следовательность символов). Такое абстрактное представление, не учитывающее структуру обрабатываемых данных, имеет очень широкую область примене­ний — от поиска в базах данных до анализа структуры ДНК и белков. Раздел компьютерных наук, занимающийся алгоритмами обработки строк, называется стрингология (англ. 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]. В последнее десятилетие модель потока данных яв­ляется заметным трендом в стрингологии. В настоящей работе рассматриваются строковые задачи, связанные с поиском регулярных структур в потоке данных.
Степень разработанности темы исследования. В одной из первых работ в потоковой модели [39] Мунро и Патерсон рассмотрели задачи сортировки потока и вычисления к-ой порядковой статистики, а также медианы как важного частно­го случая. Среди прочих результатов в статье показывается, что для вычисления медианы детерминированному алгоритму требуется линейная память, при этом представлен рандомизированный алгоритм, вычисляющий медиану с высокой вероятностью и использующий память объёмом О Д/n). Вообще, необходимость рандомизированных алгоритмов является характерной чертой модели потока данных.
В ключевой в области работе Алона, Матиаса и Сегеди [1] рассматривалась задача вычисления к-х частотных моментов потока, где к-й частотный момент равен сумме к-х степеней частот встретившихся в потоке символов. В частности, 0-й частотный момент — это количество различных символов, 1-й — это длина потока, 2-й — это квадрат евклидовой нормы вектора частот. В статье показано, что для приближения к-х частотных моментов при к > 6 требуется линейная память. А вот 0-й, 1-й и 2-й моменты могут быть вычислены с логарифмической. При этом 0-й и 2-й моменты могут быть вычислены только приближённо и только с использованием рандомизированных алгоритмов. Рандомизированному алгоритму, вычисляющему точное значение, или детерминированному алгоритму, решающему задачу приближённо, уже понадобится линейная память.
Для задачи приближения количества различных элементов в потоке Бар- Йосеф и др. [5] представили позже более эффективный рандомизированный алгоритм.
Другие интересные результаты, полученные в модели потока данных, отно­сятся к задачам на графах. В этом случае элементы потока рассматриваются как новые или удаляемые рёбра графа. Например, Кейн и др. [26] рассматривали задачу приближённого подсчёта числа вхождений фиксированного подграфа константного размера в большой граф, заданный потоком. Обзор задач на графах в модели потока данных представлен в работе Макгрегора [36].
Изучение алгоритмов на строках в модели потока данных началось со статьи Пората и Пората [40], в которой рассматривалась задача поиска по образцу в модели потока данных. В ней был представлен алгоритм, который предвари­тельно обрабатывает образец, а затем, используя О (logт) памяти (где т это длина образца), обрабатывает каждый символ текста за О (log т), и с высокой вероятностью находит все вхождения образца в текст. И уже через два года Галил и Бреслауэр [8] представили алгоритм реального времени, то есть обраба­тывающий каждый символ потока за О(1), который решает задачу поиска по образцу в полностью потоковой постановке задачи (во входном потоке сначала записан образец и после него через разделитель записан текст) с использованием О (log т) памяти.
Более сложные задачи поиска также рассматриваются в модели потока дан­ных. Один из примеров — это задача поиска с к ошибками. В этой задаче позиция считается вхождением образца, если расстояние Хэмминга между образцом и соответствующей подстрокой текста не превосходит к. Первый результат по этой задаче был представлен в статье [40]. После серии улучшений Клиффорд, Кочумака и Порат [12] представили алгоритм для полностью потоковой версии задачи, использующий память объёмом О (к • poly(log п)) и обрабатывающий один символ потока за О(д/к • poly(log п)). Сходными задачами, рассмотренными в потоковой модели, являются поиск многих образцов [10], приближенный поиск образца [11] и параметризованный поиск образца [25].
Кроме того, в потоковой модели рассматривались задачи поиска регулярных структур в строках. Так, отправной точкой для работы над данной диссертацией послужила статья Беренбринк и др. [6], авторы которой представили потоковые алгоритмы для приближенного поиска палиндромов в строке...
Купить