Почему мы не используем дерево префиксов (trie) для поиска самой длинной общей подстроки?

Недавно я узнаю, как использовать дерево для решения самой длинной общей проблемы подстроки. Узнав из Вики и других онлайн-ресурсов, я обнаружил, что мы должны использовать дерево суффиксов, чтобы найти самую длинную общую подстроку.

Как сказано в вики:

Самые длинные общие подстроки набора строк можно найти, построив обобщенное дерево суффиксов для строк, а затем найдя самые глубокие внутренние узлы, которые имеют конечные узлы из всех строк в поддереве под ним.

Как сказал Джастин:

String = ABCDE$XABCZ$
    End of word character 1 = $
    └── (0)
        ├── (20) $
        ├── (22) ABC
        │   ├── (15) DE$
        │   └── (23) Z$
        ├── (24) BC
        │   ├── (16) DE$
        │   └── (25) Z$
        ├── (26) C
        │   ├── (17) DE$
        │   └── (27) Z$
        ├── (18) DE$
        ├── (19) E$
        ├── (21) XABCZ$
        └── (28) Z$

В (компактном) дереве суффиксов вам нужно найти самый глубокий внутренний узел (узлы), у которого есть конечные узлы из всех строк. Если у вас есть несколько узлов на одной глубине, вам нужно сравнить длину строки, представленной этим узлом. то есть ABC, BC и C имеют одинаковую глубину, поэтому вам нужно сравнить длину строк ABC, BC и C, чтобы увидеть, какая из них длиннее; который, очевидно, ABC.

Здесь я подумал, что процесс поиска самых глубоких внутренних узлов, у которых есть листовые узлы из всех строк, на самом деле является процессом поиска самого длинного общего префикса всех суффиксов из всех строк.

Итак, вот вопрос: почему бы нам не построить дерево префиксов, в котором будут храниться все суффиксы из всех строк? Затем мы можем искать дерево префиксов, чтобы найти самый длинный общий префикс этих суффиксов. Я не могу сказать разницу между этими двумя. Может ли кто-нибудь дать мне некоторые подсказки, почему мы используем дерево суффиксов вместо дерева префиксов для решения этой проблемы?


string algorithm trie longest-substring suffix-tree
person JoJo    schedule 23.09.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Дерево суффиксов требует только O(N) времени и места для строки длиной N. Вот почему с его помощью можно решить самую длинную общую задачу о подстроке за линейное время.
Добавление всех достаточностей строки к дереву требует O(N^2) времени и места в худшем случае.

Таким образом, ваша идея добавления всех суффиксов всех строк в дерево на самом деле верна, но неэффективна по сравнению с решением с деревом суффиксов.

person kraskevich    schedule 23.09.2014

arrow_upward
0
arrow_downward

Trie используется для словаря. Он не хранит суффиксы.

person Gigamegs    schedule 23.09.2014
comment
но мы могли бы построить trie со всеми суффиксами всех строк, верно? Означает ли это, что дерево со всеми суффиксами и всеми строками похоже на дерево суффиксов? - person JoJo; 23.09.2014
comment
Позвольте мне пояснить: вы можете построить суффиксное дерево НАВЕРХУ дерева. Это наивно, но работает. Алгоритм ukkonen быстрее. В дереве обычно нет суффиксов:stackoverflow.com/questions/13893950/. - person Gigamegs; 23.09.2014