Аннотация

Курс «Алгоритмы на строках» предназначен для ознакомления студентов с широко используемыми на практике алгоритмами различных типов поиска в строках. В курсе приводятся описание алгоритмов, обоснование их корректности и оценка сложности. Производится сравнительный анализ алгоритмов для различных ситуаций. Помимо теоретической части рассматриваются вопросы реализации алгоритмов.

Область применения приводимых в курсе алгоритмов не ограничена строковыми объектами и является очень широкой. Например, алгоритмы нечёткого поиска используются при исследовании последовательностей нуклеотидов в ДНК, фильтрации спама, поиска мелодий по звуковым фрагментам и во многих других областях.

Программа курса

I. Поиск точного вхождения подстрок

Алгоритм Рабина-Карпа

Алгоритм Кнута-Морриса-Пратта

Алгоритм Бойера-Мура

модификация Хорспула

турбо-вариант

быстрый вариант

Алгоритм обращения сегмента

турбо-вариант

Алгоритм «сдвиг-ИЛИ»

Алгоритм Ченга-Лоулера

II. Регулярные выражения

Недетерминированные конечные автоматы

Детерминированные конечные автоматы

III. Поиск множества подстрок

Алгоритм суффиксных деревьев

Алгоритм Ахо-Корасика

Алгоритм Комменца-Уолтера

IV. Нечёткий поиск в тексте и словаре

Алгоритм Селлера

Расстояние Левенштейна, алгоритм Вагнера-Фишера

Расстояние Левенштейна-Дамерау

Алгоритм Bitap с модификациями

Алгоритм расширения выборки

Суффиксные деревья

Метод N-грамм

Хеширование по сигнатуре

BK-деревья

V. Поиск наибольшей общей подпоследовательности

Алгоритм Вагнера-Фишера

Алгоритм Хиршберга

Алгоритм Шанта-Шиманского

Алгоритм Машека-Патерсона

Алгоритм Укконена

Параллельный алгоритм

Литература

Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн, Алгоритмы: построение и анализ, 2-е издание, глава 32.
D. Gusfield, Algorithms on Strings, Trees and Sequences — Computer Science and Computational Biology.
Под. ред. J. Leeuwen, Handbook of Theoretical Computer Science — Algorithms and Complexity, глава 5.

Ссылки

C. Charras, T. Lecroq, Exact String Matching Algorithms, http://igm.univ-mlv.fr/~lecroq/string/
R. Cox, Regular Expression Matching can be Simple and Fast, http://swtch.com/~rsc/regexp/regexp1.html
G. Navarro, A Guided Tour to Approximate String Matching, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.96.7225&rep=rep1&type=pdf
G. Navarro, R. Baeza-Yates, E. Sutineny, J. Tarhioz, Indexing Methods for Approximate String Matching, http://www.dcc.uchile.cl/~gnavarro/ps/deb01.pdf
S. Kurtz, Fundamental Algorithms for a Declarative Pattern Matching System, http://www.techfak.uni-bielefeld.de/web/files/StefanKurtzDiss.pdf
http://algolist.manual.ru/search/
http://itman.narod.ru/articles/articles_fz_search.html
http://aho-corasick.narod.ru/
http://habrahabr.ru/blogs/algorithm/114997/