LINUX.ORG.RU

suffix tree vs trie

 


0

1

Можно взять исходный текст, развернуть его и построить suffix tree за линейное время. Поиск соответственно по 'перевернутым' строкам в суффиксном дереве. Зачем тогда нужно префиксное дерево?

Ответ на: комментарий от fmap

Забыл добавить: под префиксным деревом я имею ввиду сжатое (компактное) префиксное дерево

nerdogeek
() автор топика
Ответ на: комментарий от d_Artagnan

Так и сжатое суффиксное дерево для перевернутой строки будет не хуже для поиска 'перевернутого' слова в ней

nerdogeek
() автор топика

Может быть дело в том что prefix tree не нужно перестраивать для добавления нового слова в строку?

nerdogeek
() автор топика
Ответ на: комментарий от nerdogeek

Тип того. И вроде как есть различие в их назначении: префиксные - для словаря, суффиксные - для нахождения подстрок (наидлиннейшей подстроки)

d_Artagnan ★★
()

Trie — это то, что по-русски обычно называют бором, и оно хранит множество образцов, а suffix tree — это его сжатая версия, построенная на всех суффиксах одной строки (хотя можно засунуть и несколько). Для его построения за линию переворачивать ничего не нужно.

Из trie делают автомат для поиска всех вхождений множества образцов в текст — алгоритм Ахо-Корасик

BlackHawk
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.