Вопрос по java, data-structures, algorithm, tree, substring – Как найти самую длинную общую подстроку, используя деревья?

13

Самая длинная распространенная проблема подстрок в соответствии с вики может быть решена с помощью дерева суффиксов.
Отвики:

The longest common substrings of a set of strings can be found by building a generalised suffix tree for the strings, and then finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it

Я не понимаю этого.
Пример: если у меня есть:
ABCDE а такжеXABCZ
тогда дерево суффиксов (некоторые ветви изXABCZ опущено из-за пробела):
enter image description here

Самая длинная общая подстрокаABC но это не я не вижу, как здесь помогает описание вики.
ABC это не самые глубокие внутренние узлы с листовыми узлами.
Любая помощь, чтобы понять, как это работает?

@twalberg: Да, вы правы. 2 синие ветви будут одним. Но в таком случае, как я могу их программно найти? Мне не понятно, как помогает описание вики Cratylus
ABC is not the deepest internal nodes with leaf nodes.  Нет, но азбукаis самый длинныйcommon Строка узлов в любом месте дерева. Следующие самые длинныеB-C а такжеD-E, с двумя узлами каждый. Robert Harvey♦
даABC самая длинная общая строка Но я не понимаю, как описание вики поможет мне найти его программно Cratylus
Вы должны прочитать другую вики:en.wikipedia.org/wiki/Generalised_suffix_tree, Есть, вероятно, некоторые лучшие (более понятные) ресурсыhere, Смотрите такжеstackoverflow.com/questions/969448/… Robert Harvey♦
@ user384706 - Я думаю, что отчасти проблема в том, что это неправильное дерево суффиксов. У вас должна быть только одна ветвь, которая запускает root-A-B-C, и C будет иметь двух дочерних элементов: D-E и Z. Аналогично для остальных ветвей. То, что у вас есть, это просто список суффиксов, на которые все корневые узлы указывают. twalberg

Ваш Ответ

2   ответа
4

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

@LouisWasserman: Хорошо. Я согласен. Но в этом случае, т. Е. Имея 2 объединенных узла, как программно найти самую длинную общую подстроку, используя описание вики? Я застрял на этом Cratylus
Я не уверен, что следую за тобой здесь. Если строка была:ABCDBEF тогда будет подразделение подB заBCDBEF а такжеBEF но для этого примера, т.е.ABCDE Неужели у нас нет ветки для каждого возможного суффикса? Cratylus
В приведенной вами примерной диаграмме должен быть не более одного дочернего элемента корня, помеченного как «A». Вы должны были объединить эти два узла.
@LouisWasserman: Действительно почему?A это префикс вABCDE, Зачем нужен дочерний узел root, которыйA? Cratylus
Весь смысл дерева суффиксов состоит в том, чтобы объединить совпадающие префиксы суффиксов в одни и те же корни. Там должна быть одна ветка от корня, которая идетABCи затем этот последний узел должен иметь двух детей, одинX и одинDE.
7

Это то, что я получаю, когда запускаю & quot; ABCDE $ XABCZ & quot; через мой код.

Suffix Tree code:

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, очевидно.

Суффикс Три-код:

└── null
    ├── A
    │   └── B
    │       └── C
    │           ├── D
    │           │   └── (E) ABCDE
    │           └── (Z) ABCZ
    ├── B
    │   └── C
    │       ├── D
    │       │   └── (E) BCDE
    │       └── (Z) BCZ
    ├── C
    │   ├── D
    │   │   └── (E) CDE
    │   └── (Z) CZ
    ├── D
    │   └── (E) DE
    ├── (E) E
    ├── X
    │   └── A
    │       └── B
    │           └── C
    │               └── (Z) XABCZ
    └── (Z) Z

В (не компактном) суффиксе три найдите самые глубокие внутренние узлы, которые имеют листовые узлы из всех строк.

Надеюсь, поможет.

Да, это свернуто, но разрушение означает слияние, например & Quot; DE & Quot; в один узел. Однако все суффиксные деревья объединяют «CDE $». и "CZ $" в одну "C" узел с "DE $" ветвь и "Z $" ветвь - но свернутое суффиксное дерево будет обрабатывать & quot; DE $ & quot; как один узел, и дерево без суффиксов будет обрабатывать & quot; DE $ & quot; как три узла, по одному на каждого персонажа.
@ user384706 Да, это свернутое дерево. Числа - это просто идентификаторы узлов, ничего не нужно отметить. Я также создал три суффикса, если вы заинтересованы. Я добавил это к ответу.
Является ли это "свернутым"? суффикс дерево? Также, каковы числа, например(20) или же(24) так далее? Cratylus
@ user384706 Я обновляю свой ответ

Похожие вопросы