Книги по строковым [закрытым] алгоритмам
5 ответов
Я удивлен, что никто не упомянул отличную книгу Дэна Гасфилда Алгоритмы на строках, деревьях и последовательностях, которая охватывает строковые алгоритмы более подробно, чем кому-либо может понадобиться. Она очень помогла мне в проекте по секвенированию белков, над которым я работал несколько лет назад. Прочитав эту книгу, вы узнаете:
- Наивное сопоставление строк
- Алгоритмы на основе препроцессора (Бойер-Мур, Кнут-Моррис-Пратт)
- Алгоритмы регекса
- Карп-Рабин и подобные методы
- Методы суффиксного дерева (метод Укконена и др.)
- Выравнивание последовательностей (расстояние Левенштейна и сходство строк, а также множественное выравнивание последовательностей)
- Применение в секвенировании ДНК, предсказании генов и других областях.
Это не рекомендация книги, а эта библиотека и site - это библиотека, которая предлагает множество эффективных реализаций алгоритмов сопоставления строк:
http://www.dcs.shef.ac.uk/~sam/simmetrics.html
Он также предоставляет ссылки на дальнейшее обучение для каждого и где каждый из них лучше всего применим.
CLR имеет некоторые алгоритмы обработки строк, но это не специфично для них.
Including:
- Knuth-Morris-Pratt
- Rabin-Karp
- matching by finite automata
- edit distance
TRE - это библиотека с открытым исходным кодом, которая реализует приблизительное сопоставление. На странице О программе есть несколько интересных подсказок о том, как это работает, хотя я не уверен, что она обеспечивает тот вид глубокого анализа, который вам нужен. Исходный код, вероятно, более информативен с этой точки зрения.