Суффиксные деревья для представления длинных строк (например, 4 тома "Война и мир" Л.Н.Толстого) - это достаточно новая алгоритмическая техника, первые публикации относятся к 1975 году. Но только после 2000-х возник востребованный интерес к этой технике, а с 2010-х - учебные курсы в разнообразных технических университетах ... и стали массово мучить студентов курсовыми заданиями на эту тему.
Одна из самых ранних и обстоятельных переводных книг на этот предмет была вот эта (её во множестве выложено в Интернет для свободного скачивания):
Одна из самых ранних и обстоятельных переводных книг на этот предмет была вот эта (её во множестве выложено в Интернет для свободного скачивания):
Такой всплеск интереса объясняется тем, что а). возник огромный спрос на поиск контекста в поисковых системах в интернет + б). потому что были предложены за прошедшее время алгоритмы построения суффиксных деревьев с алгоритмической сложностью O(n).
Появление суффиксных деревьев и некоторых подобных алгоритмов быстрого поиска - это революция в поиске контекста! Но неприятность состоит в том, что предлагаемые алгоритмы сложности O(n) достаточно мудрёны в своих описаниях. Но, с другой стороны, сами эти алгоритмы - это внутренняя кухня технологии. Один раз реализовав эти алгоритмы (а тем более, "завернув" их внутрь класса C++, например), использовать суффиксные деревья, в самых разных целях, можно без всякого вникания в эту внутренню кухню построения деревьев.
Обсуждения по теме, готовые реализации 2-х из числа самых популярных - алгоритм Укконена и упрощённый алгоритм Вейнера, а также их применение для поиска контекста в строке (что само по себе тоже не тривиальная задача) см. здесь: суффиксные деревья и поиск в строке. Там же, кроме кода, и примеры применительно к поиску в строке. Хотя приложения суффиксного дерева к символьным переменным гораздо шире, чем просто нахождение совпадений ... об этом см. в книге.
P.S. Меня очень удивляет статистика просмотров разных тем здесь в блоге: вот эта тема относительно суффиксных деревьев и контекстного поиска в строке вызывает минимальный интерес, а это фундаментальные достижения в IT последних 10-15 лет ... Дональд Кнут в своих толстенных книжках высказывал квалифицированную догадку, что такие алгоритмы не существуют в природе и не будут найдены никогда - и вот на же тебе!
И это при том, рядом, что совершенно проходные замечания здесь в блоге, или старые темы, которые и актуальность уже потеряли от времени - они вызывают максимальный интерес и наибольшее число прочтений.
Неисповедимы пути твои, Господи...
Появление суффиксных деревьев и некоторых подобных алгоритмов быстрого поиска - это революция в поиске контекста! Но неприятность состоит в том, что предлагаемые алгоритмы сложности O(n) достаточно мудрёны в своих описаниях. Но, с другой стороны, сами эти алгоритмы - это внутренняя кухня технологии. Один раз реализовав эти алгоритмы (а тем более, "завернув" их внутрь класса C++, например), использовать суффиксные деревья, в самых разных целях, можно без всякого вникания в эту внутренню кухню построения деревьев.
Обсуждения по теме, готовые реализации 2-х из числа самых популярных - алгоритм Укконена и упрощённый алгоритм Вейнера, а также их применение для поиска контекста в строке (что само по себе тоже не тривиальная задача) см. здесь: суффиксные деревья и поиск в строке. Там же, кроме кода, и примеры применительно к поиску в строке. Хотя приложения суффиксного дерева к символьным переменным гораздо шире, чем просто нахождение совпадений ... об этом см. в книге.
P.S. Меня очень удивляет статистика просмотров разных тем здесь в блоге: вот эта тема относительно суффиксных деревьев и контекстного поиска в строке вызывает минимальный интерес, а это фундаментальные достижения в IT последних 10-15 лет ... Дональд Кнут в своих толстенных книжках высказывал квалифицированную догадку, что такие алгоритмы не существуют в природе и не будут найдены никогда - и вот на же тебе!
И это при том, рядом, что совершенно проходные замечания здесь в блоге, или старые темы, которые и актуальность уже потеряли от времени - они вызывают максимальный интерес и наибольшее число прочтений.
Неисповедимы пути твои, Господи...
Комментариев нет:
Отправить комментарий