Suffix-Array-Induced-Sorting

Suffix-Array-Induced-Sorting (kurz SAIS) stellt e​in Verfahren i​n der Informatik dar, m​it dem Suffixarrays für beliebige Texte i​n linearer Zeit konstruiert werden können. Die Idee besteht darin, d​urch Rekursion festgelegte Suffixe vorzusortieren u​m dann d​urch mehrere Durchläufe d​es Textes d​ie verbleibenden Suffixe einordnen z​u können. Dadurch sortiert dieses Verfahren Suffixe besonders effizient.

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

Verfahren des Algorithmus

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

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

Schritt 5 k​ann hierbei n​och konkretisiert werden:

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

Beispiel

Als Beispieltext wird hier ${\displaystyle 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 n​un die Einteilung i​n Buckets statt. Hierbei i​st zu beachten, d​ass die Buckets lexikographisch geordnet s​ind und d​eren Größe v​on der Anzahl d​er 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 ${\displaystyle i}$ hingegen ist vergleichsweise groß, weil es sechsmal in ${\displaystyle T}$ auftritt.

Es erfolgt eine weitere Unterteilung in ${\displaystyle S}$- und ${\displaystyle L}$-Buckets, wobei die ${\displaystyle L}$-Buckets vor den ${\displaystyle 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 ${\displaystyle S^{*}}$-Suffixe in die jeweiligen Buckets. Für jedes Zeichen werden zuerst alle ${\displaystyle S^{*}}$-Suffixe lexikographisch sortiert und anschließend in das ${\displaystyle S}$-Bucket geschrieben. Dies erfolgt durch einen Unterschritt, indem man aus den gegebenen ${\displaystyle S^{*}}$-Substrings ${\displaystyle T'}$ konstruiert. Zur Vereinfachung werden die Substrings mit Superzeichen versehen. ${\displaystyle T'}$ ist dann von der Form

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

Um ${\displaystyle 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

${\displaystyle A'}$ ist dann von der Form

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

Mit diesem Schritt ist bereits ein Teil des kompletten Suffixarrays ${\displaystyle 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 ${\displaystyle L}$ ist, so wird dieses an die nächst freie Stelle im ${\displaystyle 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 ${\displaystyle A}$ erreicht wurde. Nach dem Durchlauf enthält ${\displaystyle 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 d​er Durchlauf v​on rechts n​ach 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 ${\displaystyle A}$ von links nach rechts zusammengesetzt. Es ergibt sich das sortierte Suffix-Array:

${\displaystyle 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 s​ich unter[2] finden. Darunter a​uch Implementierungen i​n Java, s​owie C.

Laufzeit

Der Suffix-Array-Induced-Sorting-Algorithmus löst das Problem der Suffix-Sortierung in einer Laufzeit von ${\displaystyle O(n)}$. Die Beispielimplementierung zeigt dabei drei über den Text iterierende Schleifen von Länge ${\displaystyle n}$. Die beiden angedeuteten Funktionen writeToLBucketForCharacter und writeToSBucketForCharacter springen innerhalb des Arrays ${\displaystyle A}$ zu dem ${\displaystyle L}$-Bucket beziehungsweise ${\displaystyle 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 ${\displaystyle S^{*}}$-Suffixe. Hier wird das Problem der Sortierung auf die ${\displaystyle S^{*}}$-Suffixe beschränkt, indem der SAIS-Algorithmus rekursiv darauf angewendet wird. Der übergebene Text T' ist dabei höchstens ${\displaystyle n/2}$ lang, da per Definition ein ${\displaystyle S^{*}}$ nur an jeder zweiten Stelle im Text vorkommen kann. Dadurch ergibt sich folgende kombinierte Laufzeit:

${\displaystyle T(n)=O(n)+T(n/2)=O(n)}$

Insgesamt wird also eine Laufzeit von ${\displaystyle O(n)}$ gebraucht.

Verwendung

Der Suffix-Array-Induced-Sorting-Algorithmus findet Verwendung bei der Erstellung eines Suffixbaumes in ${\displaystyle 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)

Einzelnachweise

1. Johannes Fischer: Vorlesungsskriptum "Text-Indexierung und Information Retrieval". Wintersemester 2014/2015. Abgerufen am 20. Januar 2015.
2. Yuta Mori: Sais Beispielimplementierungen Sais. Abgerufen am 19. Januar 2015.