Können Suffixbäume verwendet werden, um alle gängigen Teilzeichenfolgen zu finden?

Ich versuche, Suffixbäume zu verwenden, um Zeichenfolgenfolgen zu vergleichen. Ich habe Implementierungen / Theorie für das längste häufige Problem mit Unterzeichenfolgen unter Verwendung von Suffixbäumen gefunden. Was ich jedoch suche, ist eine Diskussion des damit verbundenen Problems - "alle gängigen Teilzeichenfolgen". Insbesondere habe ich ein Problem, bei dem ich zuerst den längsten gemeinsamen Teilstring finden muss, dann den nächstlängsten gemeinsamen Teilstring, der die bereits gefundenen lcs-Indizes nicht enthält, und so weiter bis zu einer minimalen Länge. Ist dieses Problem lösbar, indem der Generalized Suffix Tree (GST) nur einmal für die beiden Sequenzen erstellt wird? Ich weiß, dass es gelöst werden kann, indem nach jeder Iteration des Findens und Entfernens des LCS wiederholt eine GST erstellt wird. Aber ich frage mich, ob mir ein ordentlicher Trick fehlt, bei dem in der GST nur einmal gebaut wird.

Ja, Suffixbäume können verwendet werden, um alle gängigen Teilzeichenfolgen zu finden. Ich würde sagen, stattdessen ein Suffix-Array zu verwenden, aber wenn Sie bereits einen Suffix-Baum haben, benötigt das Erstellen eines Suffix-Arrays aus einem Suffix-Baum eine lineare Zeit von DFS. Der Rest meiner Antwort geht also davon aus, dass wir mit einem Suffix-Array arbeiten.

Bei einem gegebenen Text ist ein Suffix-Array für ein Array von ganzen Zahlen im Bereich von bis , das die lexikografische Reihenfolge der Suffixe der Zeichenfolge $ angibt S 0 n n + 1 $S = s_1 , ..., s_n$$S$$0$$n$$n+1$$S$

Wir wollen das Suffix-Array mit den koppeln , den längsten gemeinsamen Präfixen. Wir können das Array von in linearer Zeit konstruieren, wie in der Arbeit von Kasai et al . Suffix-Arrays und ihre lcp-Arrays sind so aneinandergereiht, dass bei einem Index in das lcp-Array gesagt wird, wobei die Indexnummer ist, dann ist der Beginn einer Instanz des gemeinsamen Teilstrings und ist der Startindex der zweiten Instanz. Die Länge ist natürlich der Wert im lcp-Array.L C P s l c p [ k ] k s a [ k ] s a [ k - 1 $LCPs$$LCPs$$lcp[k]$$k$$sa[k]$$sa[k-1]$

Ich habe eine Idee, die funktionieren könnte. Wir beginnen mit einem verallgemeinerten Suffix - Baum für Sequenzen und . Jeder interne Knoten mit Suffixen von und in seinem Teilbaum entspricht einem gemeinsamen Teilstring der Sequenzen. Nennen wir solche Knoten nicht trivial. Die gemeinsame Teilzeichenfolge ist maximal, wenn der entsprechende Knoten keine nicht trivialen untergeordneten Knoten hat. Wenn der Knoten nicht trivial ist, speichern wir die größte Zeichenfolgentiefe eines nicht trivialen Knotens in seinem Teilbaum als . Wenn die Wurzel ist, dann ist die Länge der längsten gemeinsamen Teilzeichenfolge und .T S T v l c s ( v ) r l c s ( r ) S $S$$T$$S$$T$$v$$lcs(v)$$r$$lcs(r)$$S$$T$

Das Aktualisieren des Baums nach dem Löschen eines Teilstrings aus einer der Sequenzen sollte nicht zu schwierig sein. Wir löschen zuerst die Blätter, die den gelöschten Suffixen entsprechen, und aktualisieren ihre Vorfahren bei Bedarf. Dann beginnen wir mit der Verarbeitung der Suffixe vor dem gelöschten Teilstring. Sei der niedrigste nicht triviale Vorfahr des aktuellen Blattes. Wenn die Länge des Suffixes (wir sind Schritte vom Löschen entfernt) und , müssen wir das Suffix an die richtige Position im Baum verschieben und die Vorfahren bei Bedarf aktualisieren. Wenn , sind wir fertig, da wir nicht an Teilbäumen mit trivialen Wurzeln interessiert sind.k k k < l c s ( v ) k ≥ l c s ( v $v$$k$$k$$k < lcs(v)$$k \ge lcs(v)$

Der Gesamtalgorithmus findet wiederholt den längsten gemeinsamen Teilstring von und und löscht eines seiner Vorkommen aus beiden Sequenzen, solange die Länge des LCS groß genug ist.$S$$T$

Es gibt einige technische Details, aber die allgemeine Idee sollte funktionieren.

Beginnen Sie mit dem verketteten Text S $ T , wobei $ nirgends in * oder T vorkommt . Erstellen Sie aus diesem Text einen Suffixbaum / ein Array. Es ist jetzt einfach, diese Suffix-Datenstruktur zu durchlaufen, um alle richtigen maximalen Wiederholungen zu sammeln. Filtern Sie durch Untersuchen des linken Kontexts die nicht linken maximalen Wiederholungen heraus. Diese Filterung nach links könnte unter Verwendung der Burrows-Wheeler-Tabelle wie bei Abouelhoda et al. Implementiert werden, obwohl ich nicht glaube, dass dies notwendig ist. Wiederholungen nur in S oder nur in T.sollte auch an dieser Stelle beseitigt werden. Nicht eliminierte Wiederholungen werden dann in eine Prioritätswarteschlange gestellt, wobei die Priorität durch die Länge definiert wird. Nach dem Durchlaufen kann die endgültige Filterung (zur Eindämmung von Teilzeichenfolgen) durchgeführt werden, da aufgezeichnete Wiederholungen von der Priorität entfernt werden. Angesichts der Verwendung maximaler Phrasen vermute ich jedoch, dass nur sehr wenig von dieser Filterung notwendig wäre.

Dieser Algorithmus ist meine eigene Erfindung. Ich würde es nicht als sehr klug einstufen, aber es sollte funktionieren.

Eine wirklich einfache Lösung: Erstellen Sie einen Suffixbaum für die erste Zeichenfolge und versehen Sie alle Knoten mit . Fügen Sie dann alle Suffixe der zweiten Zeichenfolge . Kommentieren Sie Knoten, die Sie durchlaufen oder mit erstellen . Das Pfad - Label für jeden Knoten, der mit beiden kommentierten ist und ist eine Teilkette von sowohl und . (Siehe zum Beispiel diese Vorlesungsunterlagen, in denen eine schnelle Websuche aufgetaucht ist.)s T t s t S $S$$s$$T$$t$$s$$t$$S$$T$