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

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

Ответ 1

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

banana
anana
nana
ana
na
a

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

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

Этот ответ также выполняет замечательную работу, объясняющую вариант этой структуры данных.

Ответ 2

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

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

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

Ответ 3

Разница очень проста. Дерево суффикса имеет меньше "dummy" узлов, чем суффикс trie. Эти фиктивные узлы являются одиночными символами, которые увеличивают операцию поиска в дереве