Komplettes Suffix-Array

Question

Ein Suffix-Array indiziert alle Suffixe für eine bestimmte Liste von Zeichenfolgen. Was ist jedoch, wenn Sie versuchen, alle möglichen eindeutigen Teilzeichenfolgen zu indizieren?Ich bin ein bisschen neu in diesem Bereich, daher hier ein Beispiel dafür, was ich meine:

Gegeben die Zeichenfolge

abcd

Ein Suffix-Array indiziert (zumindest nach meinem Verständnis)

(abcd,bcd,cd,d)

Ich möchte (alle Teilzeichenfolgen) indizieren

(abcd,bcd,cd,d,abc,bc,c,ab,b,a)

Ist ein Suffix-Array das, wonach ich suche?Wenn ja, was mache ich, um alle Teilzeichenfolgen zu indizieren?Wenn nicht, wo soll ich suchen?Wofür würde ich auch googeln, um "alle Teilzeichenfolgen" mit "Suffix-Teilzeichenfolgen" zu vergleichen?

Answer 1

Das Suffix-Array macht das, was Sie bereits benötigen, da jeder Teilstring ein Präfix eines der Suffixe ist. Insbesondere in Anbetracht Ihres Suffix-Arrays

abcd bcd CD d

und nehmen Sie an, Sie suchen nach der Teilzeichenfolge "bc". Dann können Sie dies finden, indem Sie nach allen Suffixen suchen, die mit "bc" beginnen (in diesem Fall gibt es nur eine, "bcd"). Da ein Suffix-Array lexikografisch sortiert ist, entspricht das Auffinden aller Suffixe, die ein bestimmtes Präfix gemeinsam haben, einer binären Suche im gesamten Suffix-Array. Das Ergebnis ist ein fortlaufender Bereich von Einträgen des Suffix-Arrays.

Es gibt jedoch optimierte Suchmethoden, bei denen das Suffix-Array mit zusätzlichen Datenstrukturen kombiniert wird, z. B. das LCP-Array (Longest-Common Prefix) oder Wavelet-Bäume. Eine Beschreibung solcher Methoden finden Sie in der Umfrage von Navarro aus dem Jahr 2007 (DOI 10.1145 / 1216370.1216372).

Um die folgenden Kommentare zu berücksichtigen, schlage ich vor, jedes Suffix mit der Anzahl der Teilzeichenfolgen zu kombinieren, die es darstellt . In einem einfachen Beispiel wie dem oben genannten wäre dies

4 abcd
3 bcd
2 bc
1 d

weil beispielsweise das erste Suffix "abcd" die 4 Teilzeichenfolgen "a", "ab", "abc", "abcd" darstellt. In einem komplexeren Beispiel, beispielsweise für die Zeichenfolge "abcabxdabe", wären die ersten beiden Einträge des Suffix-Arrays

10 abcabxdabe
1 abe

weil der zweite Eintrag Teilzeichenfolgen "a", "ab" und "abe" darstellt, aber "a" und "ab" auch durch den ersten Eintrag dargestellt werden.

Wie berechnet man die Anzahl der Teilzeichenfolgen, die ein Eintrag darstellt? -> Die Länge des Suffix abzüglich der Länge des längsten Präfixes, das es mit dem vorherigen Suffix gemeinsam hat. Z.B. im Beispiel "abe" ist dies 3 (seine Länge) minus 2 (die Länge von "ab", dem längsten Präfix, das es mit dem vorherigen Eintrag teilt). Diese Zahlen können also in einem Durchgang über das Suffix-Array generiert werden, und noch schneller, wenn Sie auch das LCP-Array (Longest-Common Prefix) generiert haben.

Der nächste Schritt wäre, akkumulierte Zählungen zu generieren:

10 abcabxdabe
11 abe
16 abxdabe
...

und dann einen effizienten Weg finden, um die akkumulierten Zählungen zu nutzen. Z.B. Wenn Sie den 13. Teilstring lexikografisch erhalten möchten, müssen Sie den ersten Eintrag finden, dessen akkumulierte Anzahl größer oder gleich 13 ist. Das wäre oben "16 abxdabe". Entfernen Sie dann das Präfix, das es mit dem vorherigen Eintrag teilt (ergibt "xdabe"), und springen Sie dann zur Position nach dem 2. Zeichen (da der vorherige Eintrag die Anzahl 11 und 13-11== 2 angesammelt hat), sodass Sie " abxd "als 13. Teilzeichenfolge lexikographisch.

Answer 2

Wie bereits beantwortet wurde, sind Teilzeichenfolgen Präfixe von Suffixen.Manchmal möchten Sie vielleicht in die andere Richtung gehen und Suffixe von Präfixen erhalten.

Darüber hinaus ist unklar, wonach Sie mit "einzigartigen Teilzeichenfolgen" suchen.Ich würde vorschlagen, dass Sie die Wörter nachschlagen: Typ, Token, Maximum, Supermaximal.Sie sollten keine Probleme haben, diese in der Literatur zu Suffix-Arrays zu finden.

Answer 3

Sie sollten eine Variation von 'Trie' verwenden.Wenn Sie über ABCD verfügen, erstellen Sie im Wesentlichen einen Baum, bei dem die Pfade zusammengeführt werden: root-> A-> B-> C-> D, root-> B-> C-> D, root-> C-> D und root-> D.Führen Sie nun an jedem Knoten eine Liste der Stellen, an denen der String root -> .-> .-> Knoten beobachtet wurde.