Суффиксное дерево и попытки. В чем разница?

81

Я читаю о Triesшироко известных деревьях префиксов и Suffix Trees.
Хотя я нашел код для файла, Trieя не могу найти пример для Suffix Tree. Также у меня такое ощущение, что код, строящий a Trie, такой же, как код для a, Suffix Treeс той лишь разницей, что в первом случае мы храним префиксы, а во втором - суффиксы.
Это правда? Может ли кто-нибудь помочь мне прояснить это в моей голове? Пример кода будет большим подспорьем!

algorithm data-structures trie suffix-tree Кратил
источник
1
TL; DR Суффиксное дерево строки - это патриция всех ее суффиксов. Единственная особенность в этом заключается в том, что метки краев являются подстроками исходной строки, поэтому они могут быть представлены в виде пары индексов и занимают только постоянное пространство. По этой же причине его можно построить за линейное время.
Niklas B.

Ответы:

66

Дерево суффиксов можно рассматривать как структуру данных, построенную на основе дерева, в котором вместо простого добавления самой строки в дерево можно также добавить все возможные суффиксы этой строки. Например, если вы хотите проиндексировать строку banana в дереве суффиксов, вы должны построить дерево со следующими строками:

banana
anana
nana
ana
na
a

Как только это будет сделано, вы можете найти любой n-грамм и посмотреть, присутствует ли он в вашей проиндексированной строке. Другими словами, поиск n-грамм - это префиксный поиск всех возможных суффиксов вашей строки.

Это самый простой и медленный способ построить дерево суффиксов. Оказывается, есть много более причудливых вариантов этой структуры данных, которые улучшают как пространство, так и время сборки. Я недостаточно хорошо разбираюсь в этой области, чтобы делать обзор, но вы можете начать с изучения суффиксных массивов или расширенных структур данных этого класса (лекции 16 и 18).

Этот ответ также прекрасно объясняет вариант этой структуры данных.

Зе Блоб
источник
Это то, что я подозревал. Trie используется для построения дерева суффиксов, и поэтому большинство учебников предоставляют код только для попыток. Но это наихудшая реализация, а?
Cratylus
Суффиксные деревья @Cratylus наиболее полезны для очень больших строк (например, для индексации всех работ Шекспира), где пространство O (n ^ 2) и время сборки просто не будут сокращать его. К счастью, эти границы можно немного снизить.
Ze Blob
8

Если вы представите Trie, в которое вы помещаете суффиксы некоторых слов, вы сможете очень легко запросить у него подстроки строки. Это основная идея суффиксного дерева, в основном это суффиксное дерево.

Но, используя этот наивный подход, построение этого дерева для строки размера n будет O (n ^ 2) и потребует много памяти.

Поскольку все записи этого дерева являются суффиксами одной и той же строки, они разделяют большой объем информации, поэтому существуют оптимизированные алгоритмы, позволяющие создавать их более эффективно. Например, алгоритм Укконена позволяет создавать суффиксное дерево в режиме онлайн за время O (n) сложности.

Хуан Лопес
источник
2
То есть вы говорите, что суффиксные деревья и суффиксные попытки - это одно и то же?
batman
1

Отличие очень простое. Суффиксное дерево имеет меньше «фиктивных» узлов, чем суффиксное дерево. Эти фиктивные узлы являются одиночными символами, которые увеличивают поиск в дереве.

любопытный
источник
0

Узлы Trie имеют ссылки на более короткий контекст, а в «Дереве» его нет. Если узлы Tree получают ссылку на более короткий контекст, тогда он обращается к Trie; o)

Стефан Банев
источник