Книги по строковым алгоритмам
Там были многочисленные посты по строковым алгоритмам:
- Алгоритм поиска статей с похожим текстом,
- Аналог Строкового алгоритма,
- Эффективный алгоритм сопоставления строк
Однако никакой общей литературы не было упомянуто.
Может ли кто-нибудь порекомендовать книгу (-ы), в которой будут тщательно изучаться различные алгоритмы строк? Тема, которая представляет особый интерес, - это приблизительное сопоставление строк [такие вещи, как предложенные Google исправленные варианты строки поиска:) ].
Большое спасибо за совет.
5 ответов
Я удивлен, что никто не упомянул превосходную книгу Дэна Гусфилда " Алгоритмы на строках, деревьях и последовательностях", которая описывает строковые алгоритмы более подробно, чем, возможно, понадобится кому-либо. Это очень помогло мне в проекте по секвенированию белков, над которым я работал несколько лет назад. Прочитав эту книгу, вы узнаете:
- Наивное соответствие строк
- Основанные на препроцессоре алгоритмы (Бойер Мур, Кнут-Моррис-Пратт)
- Алгоритмы сопоставления регулярных выражений
- Карп-Рабин и аналогичные методы
- Методы суффиксного дерева (метод Укконена и др.)
- Выравнивание последовательностей (расстояние Левенштейна и сходство строк, а также множественное выравнивание последовательностей)
- Приложения для секвенирования ДНК, предсказания генов и других областей.
Это не рекомендация книги, но эта библиотека и сайт - это библиотека, которая предлагает множество эффективных реализаций алгоритма сопоставления строк:
http://www.dcs.shef.ac.uk/~sam/simmetrics.html
Он также предоставляет ссылки на дальнейшее обучение для каждого и где каждый лучше всего подходит.
У CLR есть некоторые алгоритмы обработки строк, но они не специфичны для них.
В том числе:
- Кнут-Морриса-Пратта
- Рабина-Карпа
- сопоставление конечными автоматами
- редактировать расстояние
TRE - это библиотека с открытым исходным кодом, которая реализует приблизительное сопоставление. На странице " О программе" есть несколько интересных советов о том, как это работает, хотя я не уверен, что она обеспечивает тот вид углубленного анализа, который вы ищете. Исходный код, вероятно, более поучителен с этой точки зрения.