|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Krylov 2:5020/400 07 Jul 2003 17:39:16
To : Ivan Boldyrev
Subject : Re: Хитрый поиск подстроки
--------------------------------------------------------------------------------
Hello, Ivan!
You wrote to Serge Nozhenko on Sun, 06 Jul 2003 00:35:39 +0400:
SN>> Эта "свертка" называется суффиксным деревом. Она дает ответ
SN>> одновременно на оба вопроса (о существовании и позиции подстроки)
SN>> за время, не большее пропорционального длине подстроки.
IB> А где можно про это прочитать? Может, это как-то соответствует широко
IB> известным алгоритмам поиска (БМ, КМП)?
У Кнута есть алгоритм "Луч". Hа основе него - суффиксное дерево.
Дерево Кнута можно использовать для хранения словаря.
Есть алгоритм, позволяющий определить, принадлежит ли
слово словарю или нет.
В дереве Кнута дуги размечены буквами алфавита. Вершины помечаются
признаком "принадлежит словарю/не принадлежит словарю".
Пусть мы находимся в некоторой вершине дерева (начинаем с корня).
Берем очередную (начиная с первой) букву слова, если дуга с
этой буквой есть, переходим к соответствующей вершине и
повторяем процесс. После того, как букв в слове не остается
смотрим метку вершины - если "принадлежит словарю", значит
слово принадлежит словарю.
Отсюда очевиден способ построения дерева и модификация до
суффиксного дерева.
Минус этих деревьев, как было уже отмечено, - очень большой размер требуемой для
хранения дерева памяти.
With best regards,
Dmitriy Krylov
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
