Жемчужины стрингологии
«Жемчужины стрингологии: текстовые алгоритмы» — это книга об сопоставления алгоритмах строк и с образцом связанных с ними проблемах. Он был написан Максимом Крошмором и Войцехом Риттером и опубликован World Scientific в 2003 году.
Темы
[ редактировать ]Первые темы книги — это два основных алгоритма поиска строк для поиска точно совпадающих подстрок : алгоритм Кнута-Морриса-Пратта и алгоритм поиска строк Бойера-Мура . Затем он описывает суффиксное дерево , индекс для быстрого поиска совпадающих подстрок и два алгоритма его построения. Другие темы в книге включают построение детерминированных конечных автоматов для распознавания образов, обнаружение повторяющихся шаблонов в строках, алгоритмы сопоставления строк в постоянном пространстве и без потерь сжатие строк . Приблизительное сопоставление строк рассматривается в нескольких вариантах, включая расстояние редактирования и самую длинную общую проблему подпоследовательности . Книга завершается более сложными темами, включая двумерное сопоставление с образцом, параллельные алгоритмы сопоставления с образцом, задачу о кратчайшей общей суперстроке , параметризованное сопоставление с образцом и повторяющегося кода обнаружение , а также алгоритм Рабина-Карпа . [1]
Аудитория и прием
[ редактировать ]Книга написана для аудитории, знакомой с разработкой и анализом алгоритмов, но не обязательно знакомой со строковыми алгоритмами. [1] Рецензент Рольф Кляйн предполагает, что эта целевая аудитория может быть узкой, поскольку он оценивает книгу как слишком сложную для многих студентов, но не дающую такой глубины экспертам, как более ранняя книга тех же авторов « Текстовые алгоритмы» (1994). [2]
Рецензент Шошана Маркус пишет, что алгоритмы, выбранные для включения в книгу, «элегантны, но фундаментальны», но их часто упускают из виду в учебниках по более общим алгоритмам. Она пишет, что сама книга должна стать ценным справочником для исследователей в этой области и что ее также можно использовать в качестве дополнения к материалам курсов по алгоритмам для студентов или аспирантов. [1] Рецензент Рикардо Баеза-Йейтс предполагает, что отсутствие в книге методов параллельного программирования на уровне битов отражает ее уклон в сторону теоретических, а не практических методов, но, тем не менее, согласен с ее пригодностью для аспирантуры. [3]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Маркус, Шошана (сентябрь 2015 г.), «Обзор драгоценностей стрингологии » (PDF) , ACM SIGACT News , 46 (3): 11–14, doi : 10.1145/2818936.2818940 , S2CID 29751366
- ^ Кляйн, Рольф, zbMATH , Zbl 1078.68151
{{citation}}: CS1 maint: периодическое издание без названия ( ссылка ) - ^ Баеза-Йейтс, Рикардо (2005), Математические обзоры , MR 2012571
{{citation}}: CS1 maint: периодическое издание без названия ( ссылка )