Suffix-Array-Induced-Sorting

Beispiel für das Sortieren der Suffix Arrays für den Text immissiissippi$

Suffix-Array-Induced-Sorting (kurz SAIS) stellt ein Verfahren in der Informatik dar, mit dem Suffixarrays für beliebige Texte in linearer Zeit konstruiert werden können. Die Idee besteht darin, durch Rekursion festgelegte Suffixe vorzusortieren um dann durch mehrere Durchläufe des Textes die verbleibenden Suffixe einordnen zu können. Dadurch sortiert dieses Verfahren Suffixe besonders effizient.

Verfahren des Algorithmus

Im Folgenden wird der Algorithmus für einen Text $T$ angewendet, der ein Suffixarray $A$ konstruiert. Mit $T^{i}$ wird das Suffix von $T$ ab Index $i$ angegeben.

1. Klassifiziere alle Suffixe im Text mit $S$ (smaller) oder $L$ (larger), in dem der Text von rechts nach links durchlaufen wird. Ein Zeichen beziehungsweise Suffix wird hierbei als $S$ klassifiziert, wenn das nachfolgende Suffix lexikographisch größer ist, sonst als $L$.
2. Kennzeichne ein Suffix vom Typ $S$ mit $S^{*}$, wenn dessen Vorgänger lexikographisch größer ist
3. Teile $A$ in Buckets auf. Buckets stellen hier Intervalle in $A$ dar, in denen alle Suffixe mit dem gleichen jeweiligen Zeichen beginnen.
4. Teile die Buckets in $S$- und $L$-Buckets auf. Innerhalb eines oberen Buckets stehen die $L$-Buckets vor den $S$-Buckets.
5. Sortiere die $S^{*}$-Suffixe lexikographisch und schreibe sie in ihre jeweiligen $S$-Buckets.
6. Scanne $A$ von links nach rechts. Falls an Stelle $i$ ein Suffix vorhanden ist und $T^{A[i]-1}$ vom Typ $L$ ist, dann schreibe $A[i]-1$ an die nächste freie Stelle im Typ-$L$-Bucket für den Buchstaben $T[A[i]-1]$.
7. Scanne von rechts nach links. Falls an Stelle $i$ ein Suffix vorhanden ist und $T^{A[i]-1}$ vom Typ $S$ ist, dann schreibe $A[i]-1$ an die nächste freie Stelle im Typ-$S$-Bucket für den Buchstaben $T[A[i]-1]$ von rechts nach links.

Schritt 5 kann hierbei noch konkretisiert werden:

1. Sortiere die $S^{*}$-Substrings und ordne diesen dann Superzeichen zu. Erzeuge daraus Text $T'$.
2. Berechne Suffixarray $A'$ für $T'$ rekursiv.
3. Aus $A'$ folgt dann die Sortierung der $S^{*}$-Suffixe $\rightarrow$ Rücktransformation der Indizes von $T'$ nach $T$.

Beispiel

Als Beispieltext wird hier $T={\text{immissiissippi}}\$$ genommen, das Dollarzeichen am Ende symbolisiert das Ende der Zeichenkette. Die zugehörige Klassifizierung ergibt folgende Zuweisungen:

Index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
T	i	m	m	i	s	s	i	i	s	s	i	p	p	i	$
Typ	S	L	L	S*	L	L	S*	S	L	L	S*	L	L	L	S*

Nach erfolgter Klassifizierung findet nun die Einteilung in Buckets statt. Hierbei ist zu beachten, dass die Buckets lexikographisch geordnet sind und deren Größe von der Anzahl der jeweils vorkommenden Zeichen abhängt.

Index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
T	i	m	m	i	s	s	i	i	s	s	i	p	p	i	$
Typ	S	L	L	S*	L	L	S*	S	L	L	S*	L	L	L	S*
Buckets	$	i						m		p		s

Es ist zu erkennen, dass der Bucket für das Dollarzeichen ziemlich klein ist, weil dieses Zeichen nur einmal im Text vorkommt. Der Bucket für das Zeichen $i$ hingegen ist vergleichsweise groß, weil es sechsmal in $T$ auftritt.

Es erfolgt eine weitere Unterteilung in $S$- und $L$-Buckets, wobei die $L$-Buckets vor den $S$-Buckets stehen.

Index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
T	i	m	m	i	s	s	i	i	s	s	i	p	p	i	$
Typ	S	L	L	S*	L	L	S*	S	L	L	S*	L	L	L	S*
Buckets	$	i						m		p		s
Bucket-Typ	S	L	S					L		L		L

Nun erfolgt die Einordnung der $S^{*}$-Suffixe in die jeweiligen Buckets. Für jedes Zeichen werden zuerst alle $S^{*}$-Suffixe lexikographisch sortiert und anschließend in das $S$-Bucket geschrieben. Dies erfolgt durch einen Unterschritt, indem man aus den gegebenen $S^{*}$-Substrings $T'$ konstruiert. Zur Vereinfachung werden die Substrings mit Superzeichen versehen. $T'$ ist dann von der Form

$T'=[D,B,C,A]$, wobei $A=15$, $B=7$, $C=11$ und $D=4$. Die Superzeichen $A$ bis $D$ stehen hier für die jeweiligen $S^{*}$-Suffixe.

Um $A'$ generieren zu können, werden den Superzeichen Indizes zugewiesen. Anschließend wird lexikographisch sortiert.

Index	1	2	3	4
T'	D	B	C	A
Stelle in T	4	7	11	15

$A'$ ist dann von der Form

$A'=[4,2,3,1]$, wobei $4=A$, $2=BCA$, $3=CA$ und $1=DBCA$.

Mit diesem Schritt ist bereits ein Teil des kompletten Suffixarrays $A$ vorsortiert, dieser kann nun in die Buckets eingefügt werden:

Index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
T	i	m	m	i	s	s	i	i	s	s	i	p	p	i	$
Typ	S	L	L	S*	L	L	S*	S	L	L	S*	L	L	L	S*
Buckets	$	i						m		p		s
Bucket-Typ	S	L	S					L		L		L
	15		7	11	4

Jetzt erfolgt ein Durchlauf der Buckets von links nach rechts, wird hierbei ein Suffix einer entsprechenden Stelle gefunden, dessen Vorgänger-Suffix vom Typ $L$ ist, so wird dieses an die nächst freie Stelle im $L$-Bucket des jeweiligen Zeichens geschrieben.

Index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
T	i	m	m	i	s	s	i	i	s	s	i	p	p	i	$
Typ	S	L	L	S*	L	L	S*	S	L	L	S*	L	L	L	S*
Buckets	$	i						m		p		s
Bucket-Typ	S	L	S					L		L		L
	15		7	11	4
		14

Dieser Vorgang wird so oft wiederholt, bis das Ende von $A$ erreicht wurde. Nach dem Durchlauf enthält $A$ folgende Suffixe:

Index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
T	i	m	m	i	s	s	i	i	s	s	i	p	p	i	$
Typ	S	L	L	S*	L	L	S*	S	L	L	S*	L	L	L	S*
Buckets	$	i						m		p		s
Bucket-Typ	S	L	S					L		L		L
	15		7	11	4
		14						3				6	10
									2	13				5
											12

Jetzt erfolgt der Durchlauf von rechts nach links:

Index	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
T	i	m	m	i	s	s	i	i	s	s	i	p	p	i	$
Typ	S	L	L	S*	L	L	S*	S	L	L	S*	L	L	L	S*
Buckets	$	i						m		p		s
Bucket-Typ	S	L	S					L		L		L
	15		7	11	4
		14						3				6	10
									2	13				5
											12				9
							8
						4
					11
				1

Zuletzt werden die sortierten Suffixe in $A$ von links nach rechts zusammengesetzt. Es ergibt sich das sortierte Suffix-Array:

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

Beispielimplementierung (Pseudocode)

sais(T,A)
for i = n to 1 do
    if (T[i] >lex T[i+1])
        typ[i] <- L
        if (typ[i+1] = S) typ[i+1] = S*
    else
        typ[i] <- S

begin <- {}
for j = 1 to n do
       if (typ[j] = S*)
         if (begin = {})
           begin <- j
	 else
           end <- p
           T’[q] <- CharacterFor(begin,end)
           q <- q + 1
           begin <- end

If (everyCharacterInT’IsUnique(T’))
	A <- countingSort(T’)
        return A
else
        A <- sais(T’,A)

for k = 1 to n do
	if (A[k] != {})
	  if (typ[A[k]-1] = L)
	    A <- writeToLBucketForCharacter(T[A[k]-1])

for l = n to 1 do
	if (A[l] != {})
	  if (typ[A[l]-1] = S)
	    A <- writeToSBucketForCharacter(T[A[l]-1])

return A

Weitere Implementierungen lassen sich unter finden. Darunter auch Implementierungen in Java sowie C.

Laufzeit

Der Suffix-Array-Induced-Sorting-Algorithmus löst das Problem der Suffix-Sortierung in einer Laufzeit von $O(n)$. Die Beispielimplementierung zeigt dabei drei über den Text iterierende Schleifen von Länge $n$. Die beiden angedeuteten Funktionen writeToLBucketForCharacter und writeToSBucketForCharacter springen innerhalb des Arrays $A$ zu dem $L$-Bucket beziehungsweise $S$-Bucket für das angegebene Zeichen. Innerhalb des Buckets wird in einer naiven Implementierung maximal n-mal geprüft werden müssen, ob ein freier Platz im Bucket vorhanden ist, um einen freien Platz zu finden.

Interessant ist das Sortieren der $S^{*}$-Suffixe. Hier wird das Problem der Sortierung auf die $S^{*}$-Suffixe beschränkt, indem der SAIS-Algorithmus rekursiv darauf angewendet wird. Der übergebene Text T' ist dabei höchstens $n/2$ lang, da per Definition ein $S^{*}$ nur an jeder zweiten Stelle im Text vorkommen kann. Dadurch ergibt sich folgende kombinierte Laufzeit:

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

Insgesamt wird also eine Laufzeit von $O(n)$ gebraucht.

Verwendung

Der Suffix-Array-Induced-Sorting-Algorithmus findet Verwendung bei der Erstellung eines Suffixbaumes in $O(n)$ Zeit. Dabei bildet er nur einen Teilschritt zwischen dem Text und dem entstandenen Suffixbaum.

Siehe auch

• Suffixarray

Literatur

• Ge Nong, Sen Zhang, Wai Hong Chan: Two Efficient Algorithms for Linear Time Suffix Array Construction. IEEE Trans. Computers 60(10): 1471–1484 (2011)