Suffixarray

Grundidee und Darstellung

Ein Suffixarray ist ein Array, das die Suffixe einer Zeichenkette in lexikographischer Reihenfolge angibt. Ein Suffix ist dabei der Teil einer Zeichenkette, der an einer bestimmten Position beginnt und bis zum Ende reicht. Das Array speichert normalerweise nicht die Suffixe selbst, sondern die Indizes ihrer ersten Zeichen. Dadurch lässt sich ein Text platzsparend als Index strukturieren und anschließend effizient durchsuchen oder für Kompressionsverfahren verwenden.

Um auch das Ende eines Strings eindeutig zu behandeln, wird häufig der Endmarker $ angehängt. Er steht für das Ende beziehungsweise das leere Suffix und ist per Konvention lexikographisch kleiner als jedes andere Zeichen. Bei mehreren zusammengefügten Strings, etwa abracadabra$mississippi$, trennt der Endmarker zugleich die einzelnen Texte.

Beispiel mit abracadabra

Für S = abracadabra der Länge 11 wird der Endmarker angefügt: abracadabra$. Es gibt dann zwölf Suffixe, darunter abracadabra$ ab Position 1, abra$ ab Position 8, a$ ab Position 11 und $ ab Position 12.

Lexikographisch sortiert beginnen die Suffixe mit $, a$, abra$, abracadabra$, acadabra$, adabra$, bra$, bracadabra$, cadabra$, dabra$, ra$ und racadabra$. Das zugehörige Suffixarray lautet daher A = {12,11,8,1,4,6,9,2,5,7,10,3}. Beispielsweise bedeutet der Wert 11, dass das Suffix a$ am elften Zeichen beginnt. Ist nur ein einzelner Originalstring relevant, kann das leere Suffix übergangen werden, weil es stets vor allen anderen Suffixen steht.

Konstruktionsalgorithmen

Um für einen Text der Länge n ein Suffixarray zu erzeugen, gibt es drei große Klassen von Verfahren: iterative, rekursive und induzierte Sortierung.

Bei der iterativen Teilsortierung würde ein gewöhnlicher vergleichsbasierter Sortieralgorithmus höchstens O(n log n) Vergleiche benötigen. Da ein Vergleich zweier Suffixe O(n) dauern kann, ergäbe sich insgesamt O(n² log n). Verbesserte Verfahren vermeiden wiederholte Teilvergleiche: Zuerst werden Suffixe nach ihrem ersten Zeichen gruppiert, dann nach den ersten zwei, vier, acht Zeichen und so weiter. Nach log₂n Schritten sind alle Suffixe vollständig sortiert. Jeder Schritt kann O(n) benötigen; insgesamt ergibt sich O(n log n). Zu dieser Klasse gehören der Algorithmus von Manber und Myers sowie der in der Praxis deutlich effizientere Algorithmus von Larsson und Sadakane.

Rekursive Algorithmen teilen den String S in die Zeichenketten x und y. Zuerst wird rekursiv das Suffixarray von x berechnet; daraus wird das Suffixarray von y induziert, also effizient abgeleitet. Aus beiden Teilergebnissen kann das Suffixarray von S bestimmt werden. Bei geeigneter Wahl von x und y erreichen die meisten Verfahren O(n), doch Rekursion kann in der Praxis teuer sein.

Bei der induzierten Sortierung wird ebenfalls aus einem bekannten Suffixarray einer Zeichenkette x dasjenige einer Zeichenkette y abgeleitet. Statt Rekursion wird S zum Beispiel mehrfach in verschiedenen Richtungen durchlaufen; Zeichen werden klassifiziert, teilweise sortiert und anhand weiterer Teilergebnisse weitergeordnet. Diese Algorithmen brauchen meist weniger Speicher und sind praktisch oft schneller als rekursive Verfahren, obwohl ihre Worst-Case-Laufzeit häufig O(n² log n) beträgt. SAIS von Nong, Zhang und Chan benötigt O(n) und ist auch praktisch schnell, wenn etwa Cache-Misses berücksichtigt werden.

Suche, Suffixbäume und Kompression

Nach seiner Konstruktion dient ein Suffixarray als Textindex. Bei einer exakten Suchanfrage wird ein Muster P nur dann an einer Stelle in T gefunden, wenn jedes Zeichen übereinstimmt. Man unterscheidet Entscheidungsanfragen („Kommt P in T vor?“), Anzahlanfragen („Wie oft kommt P in T vor?“) und Aufzählungsanfragen („An welchen Stellen kommt P in T vor?“).

Alle Suffixe von T, die mit P beginnen, liegen im sortierten Suffixarray direkt hintereinander. Sie bilden also einen Block. Mit binärer Suche werden der lexikographisch kleinste und größte passende Suffix bestimmt. Für ein Muster der Länge m und einen Text der Länge n dauern Anzahlanfragen O(m · log n). Für eine Aufzählungsanfrage werden zusätzlich die Arraywerte im Block ausgegeben; ihre Laufzeit ist O(m · log n + |Oₚ|), wobei |Oₚ| die Anzahl der Vorkommen von P in T ist. Mit einem LCP-Array, das für benachbarte Suffixe die Länge ihres längsten gemeinsamen Präfixes speichert, und einer RMQ-Datenstruktur für Bereichsminimum-Anfragen lassen sich Entscheidungs- und Anzahlanfragen in O(m), Aufzählungsanfragen in O(m + |Oₚ|) beantworten.

Ein Suffixarray kann außerdem als Zwischenschritt dienen, um den Suffixbaum eines Textes T in Linearzeit zu konstruieren. Auch der Suffixbaum ist ein Suchindex. Für die Kompression lässt sich die Faktorisierung von LZ77 in Linearzeit umsetzen. Zudem kann aus dem Suffixarray mit geringem Aufwand die Burrows-Wheeler-Transformation bestimmt werden: Für jedes Suffix wird das im Text genau eine Position davor stehende Zeichen in ein Array geschrieben. Dieses Array entspricht der Transformation und kann beispielsweise beim Kompressionsverfahren bzip2 verwendet werden.