Suffix-Array

Kurz: Ein Suffix-Array ist eine sortierte Liste aller Endstücke (Suffixe) eines Textes. Mit ihm findet man jedes Teilwort per Binärsuche.

Genauer: Für den Text banana sind die Suffixe banana, anana, nana, ana, na, a. Man speichert nur ihre Startpositionen in alphabetischer Reihenfolge: [5, 3, 1, 0, 4, 2].

Im Detail

• Suche: Ein Muster der Länge m wird per Binärsuche über die Suffixe gefunden, in O(m log n).
• Aufbau: Naiv durch Sortieren in O(n² log n). Gute Algorithmen (SA-IS, Prefix-Doubling) schaffen O(n) bis O(n log n).
• Gegen Suffix-Bäume: Etwas langsamer, aber deutlich weniger Speicher.
• Zusatz LCP-Array: Speichert die gemeinsame Präfixlänge benachbarter Suffixe und ermöglicht weitere Abfragen, etwa den längsten wiederholten Teilstring.
• Einsatz: Bioinformatik (Genomsuche), Burrows-Wheeler-Transformation in bzip2, Plagiatserkennung, Volltextindizes.
• Vergleich: Für wiederholte Suchen im selben Text lohnt sich der Index. Einmalige Suche erledigt KMP oder Boyer-Moore.

Siehe auch: Invertierter Index