Драгоценности стрингологии - Jewels of Stringology

Драгоценности стрингологии: текстовые алгоритмы это книга о алгоритмы за сопоставление с образцом в струны и связанные с этим проблемы. Это было написано Максим Крочмор и Войцех Риттер, и опубликовано World Scientific в 2003 году.

Темы

Первые темы книги - это две основные алгоритмы поиска по строкам для поиска точно совпадающих подстроки, то Алгоритм Кнута – Морриса – Пратта и Алгоритм поиска строки Бойера – Мура. Затем он описывает суффиксное дерево, индекс для быстрого поиска совпадающих подстрок и два алгоритма его построения. Другие темы в книге включают строительство детерминированные конечные автоматы для распознавания образов, обнаружения повторяющихся образов в строках, алгоритмов сопоставления строк в постоянном пространстве и сжатие без потерь струн. Приблизительное соответствие строк покрыт в нескольких вариантах, включая редактировать расстояние и проблема самой длинной общей подпоследовательности. Книга завершается расширенными темами, включая двумерное сопоставление с образцом, параллельные алгоритмы сопоставления с образцом, кратчайшая общая задача суперструны, параметризованное сопоставление с образцом и повторяющийся код обнаружение, и Алгоритм Рабина – Карпа.^[1]

Аудитория и прием

Книга написана для аудитории, знакомой с проектированием и анализом алгоритмов, но не обязательно знакомой со строковыми алгоритмами.^[1] Рецензент Рольф Кляйн предполагает, что эта целевая аудитория может быть узкой, поскольку он оценивает книгу как слишком сложную для многих студентов, но не дает такой глубины экспертам, как предыдущая книга тех же авторов. Текстовые алгоритмы (1994).^[2]

Обозреватель Шошана Маркус пишет, что алгоритмы, выбранные для включения в книгу, «элегантны, но фундаментальны», но часто игнорируются в более общих учебниках по алгоритмам. Она пишет, что сама книга должна стать ценным справочником для исследователей в этой области и что ее также можно использовать в качестве дополнения к материалам курса бакалавриата или магистратуры по алгоритмам.^[1] Рецензент Рикардо Баеза-Йейтс предполагает, что в книге отсутствует методы параллельного программирования на битовом уровне отражает его склонность к теоретическим, а не практическим методам, но, тем не менее, согласуется с его пригодностью для аспирантуры.^[3]

Рекомендации

1. Маркус, Шошана (сентябрь 2015 г.), "Обзор Драгоценности стрингологии" (PDF), Новости ACM SIGACT, 46 (3): 11–14, Дои:10.1145/2818936.2818940, S2CID  29751366
2. Кляйн, Рольф, zbMATH, Zbl  1078.68151
3. Баеза-Йейтс, Рикардо (2005), Математические обзоры, МИСТЕР  2012571