|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Nozhenko 2:5020/175.1 08 Jul 2003 01:41:20
To : Dmitriy Krylov
Subject : Хитрый поиск подстроки
--------------------------------------------------------------------------------
SN>>> Эта "свертка" называется суффиксным деревом. Она дает ответ
SN>>> одновременно на оба вопроса (о существовании и позиции подстроки)
SN>>> за время, не большее пропорционального длине подстроки.
IB>> А где можно про это прочитать? Может, это как-то соответствует широко
IB>> известным алгоритмам поиска (БМ, КМП)?
DK> У Кнута есть алгоритм "Луч". Hа основе него - суффиксное дерево.
DK> Дерево Кнута можно использовать для хранения словаря.
DK> Есть алгоритм, позволяющий определить, принадлежит ли
DK> слово словарю или нет.
DK> В дереве Кнута дуги размечены буквами алфавита. Вершины помечаются
DK> признаком "принадлежит словарю/не принадлежит словарю".
DK> Пусть мы находимся в некоторой вершине дерева (начинаем с корня).
DK> Берем очередную (начиная с первой) букву слова, если дуга с
DK> этой буквой есть, переходим к соответствующей вершине и
DK> повторяем процесс. После того, как букв в слове не остается
DK> смотрим метку вершины - если "принадлежит словарю", значит
DK> слово принадлежит словарю.
DK> Отсюда очевиден способ построения дерева и модификация до
DK> суффиксного дерева.
А вот насчет очевидности способа построения нужно заметить, что это как раз
один из тех случаев, когда кнутовский талмуд страдает несовременностью, т.к.
эффективные алгоритмы для работы с суффиксными деревьями появились гораздо позже
него.
DK> Минус этих деревьев, как было уже отмечено, - очень большой размер
DK> требуемой для хранения дерева памяти.
И притом мало подходит для работы с данными загружаемыми в оперативную память
по частям с медленных носителей. Hо есть большой плюс: само существование
подобной структуры и алгоритмов ее обработки с известными характеристиками
упрощает теоретические выкладки при рассмотрении других алгоритмов.
Serge
PS. Желающим почитать про это подробнее могу порекомендовать пойти в Интернет,
набрать "suffix tree" в любом поисковике, после чего желаю приятного
времяпровождения. ;-)
--- Golded 2.41+
* Origin: Moccoletto (2:5020/175.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
