Suffix-Array-Induced-Sorting

Grundidee und Zweck

Suffix-Array-Induced-Sorting, kurz SAIS, ist ein Verfahren der Informatik zur Konstruktion eines Suffixarrays für einen beliebigen Text T. Ein Suffix T^i ist der Teiltext, der an Index i beginnt. Das Suffixarray A enthält die Startindizes aller Suffixe in lexikographisch sortierter Reihenfolge. SAIS ist besonders effizient, weil es einige Suffixe rekursiv vorsortiert und daraus die übrigen Suffixe durch mehrere Durchläufe des Arrays einordnet. Die Konstruktion benötigt insgesamt eine Laufzeit von O(n), wobei n die Textlänge ist.

Zunächst werden die Suffixe in zwei Typen eingeteilt. Ein Suffix erhält den Typ S (smaller), wenn das nachfolgende Suffix lexikographisch größer ist. Andernfalls erhält es den Typ L (larger). Ein S-Suffix wird mit S* markiert, wenn sein Vorgänger-Suffix lexikographisch größer ist. Diese speziell markierten S*-Suffixe bilden die Grundlage der rekursiven Vorsortierung.

Ablauf des Verfahrens

Das Suffixarray wird in Buckets aufgeteilt. Ein Bucket ist ein zusammenhängendes Intervall in A, in dem alle Suffixe mit demselben Anfangszeichen liegen. Die Buckets werden lexikographisch nach ihren Zeichen angeordnet. Jedes Bucket wird außerdem in einen L- und einen S-Bereich unterteilt; innerhalb eines Zeichen-Buckets stehen die L-Buckets vor den S-Buckets.

Der eigentliche Ablauf besteht aus drei wesentlichen Phasen:

• Zuerst werden die S*-Suffixe lexikographisch sortiert und in ihre jeweiligen S-Buckets eingetragen. Dazu werden die S*-Substrings zu Superzeichen zusammengefasst. Aus diesen Superzeichen entsteht ein neuer Text T'. Für T' wird rekursiv ein Suffixarray A' berechnet. Aus A' lässt sich anschließend die Reihenfolge der S*-Suffixe im ursprünglichen Text T durch Rücktransformation der Indizes bestimmen.
• Danach wird A von links nach rechts durchsucht. Wird an Position i ein bereits eingetragenes Suffix gefunden und ist T^{A[i]-1} vom Typ L, wird der Index A[i]-1 an die nächste freie Stelle im L-Bucket des Zeichens T[A[i]-1] geschrieben.
• Zum Schluss wird A von rechts nach links durchsucht. Ist T^{A[i]-1} vom Typ S, wird A[i]-1 an die nächste freie Stelle im S-Bucket des Zeichens T[A[i]-1] geschrieben. Die Eintragung erfolgt dabei von rechts nach links.

Durch diese sogenannten induzierten Eintragungen werden aus den bereits sortierten S*-Suffixen schrittweise auch die übrigen L- und S-Suffixe an die richtigen Stellen gesetzt.

Beispiel mit immissiissippi$

Als Beispiel dient der Text T = immissiissippi$. Das Dollarzeichen am Ende kennzeichnet das Ende der Zeichenkette. Der Text hat die Indizes 1 bis 15. Die Typklassifikation lautet:

• Index 1: S
• Index 2: L
• Index 3: L
• Index 4: S*
• Index 5: L
• Index 6: L
• Index 7: S*
• Index 8: S
• Index 9: L
• Index 10: L
• Index 11: S*
• Index 12: L
• Index 13: L
• Index 14: L
• Index 15: S*

Die lexikographisch geordneten Buckets gehören zu den Zeichen $, i, m, p und s. Ihre Größen richten sich nach der Häufigkeit der Zeichen im Text. Der Bucket für $ ist besonders klein, weil dieses Zeichen nur einmal vorkommt; der Bucket für i ist vergleichsweise groß, weil i sechsmal in T vorkommt. In jedem Bucket stehen die L-Bereiche vor den S-Bereichen.

Die S*-Suffixe beginnen an den Indizes 4, 7, 11 und 15. Für ihre Sortierung werden die S*-Substrings mit Superzeichen bezeichnet. Dabei gilt T' = [D,B,C,A], mit A = 15, B = 7, C = 11 und D = 4. Nach der Vergabe von Indizes an die Superzeichen ergibt sich für den rekursiven Text das Suffixarray A' = [4,2,3,1]. In dieser Darstellung entsprechen 4 = A, 2 = BCA, 3 = CA und 1 = DBCA.

Die so gewonnene Reihenfolge wird in die ursprünglichen Buckets übertragen. Die anschließenden Durchläufe von links nach rechts und von rechts nach links tragen die L- beziehungsweise S-Suffixe induziert ein. Das vollständig sortierte Suffixarray lautet schließlich:

A = [15,14,7,1,11,4,8,3,2,13,12,6,10,5,9].

Pseudocode, Laufzeit und Verwendung

Die Beispielimplementierung sais(T,A) bestimmt die Typen durch einen Durchlauf von i = n bis 1. Wenn T[i] >lex T[i+1] gilt, wird typ[i] auf L gesetzt; ist typ[i+1] vom Typ S, wird dieses Suffix zusätzlich als S* markiert. Andernfalls wird typ[i] auf S gesetzt.

Anschließend werden die S*-Bereiche erkannt und durch CharacterFor(begin,end) zu Superzeichen in T' zusammengefasst. Sind alle Zeichen in T' verschieden, kann A' durch countingSort(T') berechnet werden. Andernfalls wird sais(T',A') rekursiv aufgerufen. Danach werden in einer Schleife von k = 1 bis n die L-Suffixe mit writeToLBucketForCharacter und in einer Schleife von l = n bis 1 die S-Suffixe mit writeToSBucketForCharacter in A eingetragen.

Für die Laufzeit nennt der Artikel drei über den Text iterierende Schleifen der Länge n. Die rekursive Eingabe T' ist höchstens n/2 lang, weil ein S* per Definition nur an jeder zweiten Stelle im Text vorkommen kann. Daher gilt:

T(n) = O(n) + T(n/2) = O(n).

Die Bucket-Funktionen suchen jeweils die nächste freie Stelle im passenden L- oder S-Bucket. In einer naiven Implementierung kann innerhalb eines Buckets bis zu n-mal geprüft werden, ob eine freie Stelle vorhanden ist; für die angegebene Gesamtlaufzeit O(n) wird die Bucket-Verarbeitung entsprechend effizient organisiert.

SAIS wird außerdem bei der Erstellung eines Suffixbaumes in O(n) Zeit verwendet. Zwischen dem ursprünglichen Text und dem fertigen Suffixbaum bildet der Algorithmus jedoch nur einen Teilschritt.