„Suffix-Array-Induced-Sorting“ – Versionsunterschied

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$ .
Kennzeichne ein Suffix vom Typ $S$ mit $S^{*}$ , wenn dessen Vorgänger lexikographisch größer ist
Teile $A$ in Buckets auf. Buckets stellen hier Intervalle in $A$ dar, in denen alle Suffixe mit dem gleichen jeweiligen Zeichen beginnen.
Teile die Buckets in $S$ - und $L$ -Buckets auf. Innerhalb eines oberen Buckets stehen die $L$ -Buckets vor den $S$ -Buckets.
Sortiere die $S^{*}$ -Suffixe lexikographisch und schreibe sie in ihre jeweiligen $S$ -Buckets.
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]$ .
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:

Sortiere die $S^{*}$ -Substrings und ordne diesen dann Superzeichen zu. Erzeuge daraus Text $T'$ .
Berechne Suffixarray $A'$ für $T'$ rekursiv.
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^[2] 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)

Einzelnachweise

↑ Johannes Fischer: Vorlesungsskriptum "Text-Indexierung und Information Retrieval". Wintersemester 2014/2015. Abgerufen am 20. Januar 2015.
↑ Yuta Mori: Sais Beispielimplementierungen Sais. Archiviert vom Original (nicht mehr online verfügbar) am 26. Juli 2014; abgerufen am 19. Januar 2015. Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/sites.google.com

[JF-1] Johannes Fischer: Vorlesungsskriptum "Text-Indexierung und Information Retrieval". Wintersemester 2014/2015. Abgerufen am 20. Januar 2015.

[sais_impl-2] Yuta Mori: Sais Beispielimplementierungen Sais. Archiviert vom Original (nicht mehr online verfügbar) am 26. Juli 2014; abgerufen am 19. Januar 2015. Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/sites.google.com

[1]

[2]

Land Niedersachsen

„Suffix-Array-Induced-Sorting“ – Versionsunterschied

Aktuelle Version vom 19. Mai 2024, 02:47 Uhr

Inhaltsverzeichnis

Verfahren des Algorithmus

Beispiel

Beispielimplementierung (Pseudocode)

Laufzeit

Verwendung

Siehe auch

Literatur

Einzelnachweise

What are your Feelings

@@ Zeile 1: / Zeile 1: @@
-{{QS-Antrag|26. Januar 2015| [[WP:Wikifizieren]]: [[Hilfe:Sackgasse|wenige Artikellinks]], [[Wikipedia:Kategorien|Kategorien]] fehlen -- [[Benutzer:MerlBot/AutoQS|MerlBot]] 02:45, 26. Jan. 2015 (CET)}}
 [[Datei:sais-bsp.gif|mini|hochkant=2.0|Beispiel für das Sortieren der Suffix Arrays für den Text immissiissippi$]]
-<b>Suffix-Array-Induced-Sorting</b> (kurz SAIS) stellt ein Verfahren in der Informatik dar, mit dem [[Suffixarray]]s 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.
+'''Suffix-Array-Induced-Sorting''' (kurz SAIS) stellt ein Verfahren in der [[Informatik]] dar, mit dem [[Suffixarray]]s für beliebige Texte in linearer Zeit konstruiert werden können. Die Idee besteht darin, durch [[Rekursion]] festgelegte [[Suffix]]e 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 <math>T</math> angewendet, der ein SuffixArray <math>A</math> konstruiert. Mit <math>T^{i}</math> wird ein einzelnes Zeichen von <math>T</math> angegeben. <ref name="JF">Johannes Fischer: Vorlesungsskriptum [http://ls11-www.cs.uni-dortmund.de/fischer/teaching/tir-ws2014| "Text-Indexierung und Information Retrieval"]. Wintersemester 2014/2015. Abgerufen am 20. Januar 2015.</ref>
+Im Folgenden wird der [[Algorithmus]] für einen Text <math>T</math> angewendet, der ein Suffixarray <math>A</math> konstruiert. Mit <math>T^{i}</math> wird das Suffix von <math>T</math> ab Index <math>i</math> angegeben.<ref name="JF">Johannes Fischer: Vorlesungsskriptum [http://ls11-www.cs.uni-dortmund.de/fischer/teaching/tir-ws2014 "Text-Indexierung und Information Retrieval"]. Wintersemester 2014/2015. Abgerufen am 20. Januar 2015.</ref>
-#Klassifiziere alle Suffixe im Text mit <math>S</math> (smaller) oder <math>L</math> (larger), in dem der Text von rechts nach links durchlaufen wird. Ein Zeichen beziehungsweise Suffix wird hierbei als <math>S</math> klassifiziert, wenn das nachfolgende Zeichen lexikographisch größer ist, sonst als <math>L</math>.
+#Klassifiziere alle Suffixe im Text mit <math>S</math> (smaller) oder <math>L</math> (larger), in dem der Text von rechts nach links durchlaufen wird. Ein Zeichen beziehungsweise Suffix wird hierbei als <math>S</math> klassifiziert, wenn das nachfolgende Suffix lexikographisch größer ist, sonst als <math>L</math>.
-#Kennzeichne alle Suffixe vom Typ <math>S</math> mit <math>S^{*}</math>, wenn deren Vorgänger lexikographisch größer sind
+#Kennzeichne ein Suffix vom Typ <math>S</math> mit <math>S^{*}</math>, wenn dessen Vorgänger lexikographisch größer ist
 #Teile <math>A</math> in Buckets auf. Buckets stellen hier Intervalle in <math>A</math> dar, in denen alle Suffixe mit dem gleichen jeweiligen Zeichen beginnen.
 #Teile die Buckets in <math>S</math>- und <math>L</math>-Buckets auf. Innerhalb eines oberen Buckets stehen die <math>L</math>-Buckets vor den <math>S</math>-Buckets.
-#Sortiere die <math>S^{*}</math>-Suffixe lexikograpisch und schreibe sie in ihre jeweiligen <math>S</math>-Buckets.
+#Sortiere die <math>S^{*}</math>-Suffixe lexikographisch und schreibe sie in ihre jeweiligen <math>S</math>-Buckets.
-#Scanne <math>A</math> von links nach rechts. Falls an Stelle <math>i</math> ein Suffix vorhanden ist und <math>T^{A[i] - 1}</math> vom Typ <math>L</math> ist, dann schreibe<math> A[i] - 1</math> an die nächste freie Stelle im Typ-<math>L</math>-Bucket für den Buchstaben <math>T[A[i]-1]</math>.
+#Scanne <math>A</math> von links nach rechts. Falls an Stelle <math>i</math> ein Suffix vorhanden ist und <math>T^{A[i] - 1}</math> vom Typ <math>L</math> ist, dann schreibe <math> A[i] - 1</math> an die nächste freie Stelle im Typ-<math>L</math>-Bucket für den Buchstaben <math>T[A[i]-1]</math>.
 #Scanne von rechts nach links. Falls an Stelle <math>i</math> ein Suffix vorhanden ist und <math>T^{A[i] - 1}</math> vom Typ <math>S</math> ist, dann schreibe <math>A[i] - 1</math> an die nächste freie Stelle im Typ-<math>S</math>-Bucket für den Buchstaben <math>T[A[i]-1]</math> von rechts nach links.
 Schritt 5 kann hierbei noch konkretisiert werden:
-#Sortiere die <math>S^{*}</math>-Suffixe und ordne diesen dann Superzeichen zu. Erzeuge daraus Text <math>T'</math>.
+#Sortiere die <math>S^{*}</math>-Substrings und ordne diesen dann Superzeichen zu. Erzeuge daraus Text <math>T'</math>.
-#Berechne Suffixarray <math>A'</math> für <math>T'</math> rekursiv
+#Berechne Suffixarray <math>A'</math> für <math>T'</math> rekursiv.
-#Aus <math>A'</math> folgt dann die Sortierung der <math>S^{*}</math>-Suffixe <math>\rightarrow</math> Rücktransformation der Indizes von <math>T'</math> nach <math>T</math>
+#Aus <math>A'</math> folgt dann die Sortierung der <math>S^{*}</math>-Suffixe <math>\rightarrow</math> Rücktransformation der Indizes von <math>T'</math> nach <math>T</math>.
 == Beispiel ==
-Als Beispieltext wird hier <math>T = immissiissippi$</math> genommen, das Dollarzeichen am Ende symbolisiert das Ende der Zeichenkette. Die zugehörige Klassifizierung ergibt folgende Zuweisungen:
+Als Beispieltext wird hier <math>T = \text{immissiissippi}\$</math> genommen, das Dollarzeichen am Ende symbolisiert das Ende der Zeichenkette. Die zugehörige Klassifizierung ergibt folgende Zuweisungen:
 {| class="wikitable" style="text-align:center"
@@ Zeile 30: / Zeile 29: @@
 | 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*
+| 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.
@@ Zeile 42: / Zeile 40: @@
 | 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*
+| Typ || S || L || L || S* || L || L || S* || S || L || L || S* || L || L || L || S*
 |-
 | Buckets
 | $
 |colspan="6"| i
 |colspan = "2"| m
 |colspan = "2"| p
 |colspan="4"| 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 <math>i</math> hingegen ist vergleichsweise groß, weil es sechsmal in <math>T</math> auftritt.
-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 <math>i</math> hingegen ist vergleichsweise groß, weil es sechs mal in <math>T</math> auftritt.
 Es erfolgt eine weitere Unterteilung in <math>S</math>- und <math>L</math>-Buckets, wobei die <math>L</math>-Buckets vor den <math>S</math>-Buckets stehen.
@@ Zeile 64: / Zeile 61: @@
 | 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*
+| Typ || S || L || L || S* || L || L || S* || S || L || L || S* || L || L || L || S*
 |-
 | Buckets
 | $
 |colspan="6"| i
 |colspan="2"| m
 |colspan="2"| p
 |colspan="4"| s
 |-
 | Bucket-Typ
@@ Zeile 82: / Zeile 79: @@
 |}
-Nun erfolgt die Einordnung der <math>S^{*}</math>-Suffixe in die jeweiligen Buckets. Für jedes Zeichen werden zuerst alle <math>S^{*}</math>-Suffixe lexikographisch sortiert und anschließend in das <math>S</math>-Bucket übergeben. Dies erfolgt durch einen Unterschritt, indem man aus den gegebenen <math>S^{*}</math>-Suffixen <math>T'</math> konstruiert. Zur Vereinfachung werden die Suffixe mit Superzeichen versehen. <math>T'</math> ist dann von der Form
+Nun erfolgt die Einordnung der <math>S^{*}</math>-Suffixe in die jeweiligen Buckets. Für jedes Zeichen werden zuerst alle <math>S^{*}</math>-Suffixe lexikographisch sortiert und anschließend in das <math>S</math>-Bucket geschrieben. Dies erfolgt durch einen Unterschritt, indem man aus den gegebenen <math>S^{*}</math>-Substrings <math>T'</math> konstruiert. Zur Vereinfachung werden die Substrings mit Superzeichen versehen. <math>T'</math> ist dann von der Form
-<math>T' = [D, B, C, A]</math>, wobei <math>A = 15</math>, <math>B = 7</math>, <math>C = 11</math> und <math>D = 4</math>.
+<math>T' = [D, B, C, A]</math>, wobei <math>A = 15</math>, <math>B = 7</math>, <math>C = 11</math> und <math>D = 4</math>. Die Superzeichen <math>A</math> bis <math>D</math> stehen hier für die jeweiligen <math>S^{*}</math>-Suffixe.
-Um <math>A'</math> generieren zu können werden den Superzeichen Indizes zugewiesen. Anschließend wird lexikographisch sortiert.
+Um <math>A'</math> generieren zu können, werden den Superzeichen Indizes zugewiesen. Anschließend wird lexikographisch sortiert.
 {| class="wikitable" style="text-align:center"
@@ Zeile 96: / Zeile 91: @@
 | T' || D || B || C || A
 |-
 | Stelle in T || 4 || 7 || 11 || 15
 |}
@@ Zeile 111: / Zeile 106: @@
 | 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*
+| Typ || S || L || L || S* || L || L || S* || S || L || L || S* || L || L || L || S*
 |-
 | Buckets
 | $
 |colspan="6"| i
 |colspan="2"| m
 |colspan="2"| p
 |colspan="4"| s
 |-
 | Bucket-Typ
@@ Zeile 130: / Zeile 125: @@
 |
 | 15
 |
 | 7
 | 11
@@ Zeile 140: / Zeile 135: @@
 |}
+Jetzt erfolgt ein Durchlauf der Buckets von links nach rechts, wird hierbei ein Suffix einer entsprechenden Stelle gefunden, dessen Vorgänger-Suffix vom Typ <math>L</math> ist, so wird dieses an die nächst freie Stelle im <math>L</math>-Bucket des jeweiligen Zeichens geschrieben.
-Jetzt erfolgt ein Durchlauf der Buckets von links nach rechts, wird hierbei ein Suffix einer entsprechenden Stelle gefunden, dessen Vorgänger-Suffix vom Typ <math>L</math> ist, so wird dieses an die nächst freie Stelle im <math>L</math>-Bucket des jeweiligen Zeichens geschrieben.
 {| class="wikitable" style="text-align:center"
@@ Zeile 149: / Zeile 143: @@
 | 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*
+| Typ || S || L || L || S* || L || L || S* || S || L || L || S* || L || L || L || S*
 |-
 | Buckets
 | $
 |colspan="6"| i
 |colspan="2"| m
 |colspan="2"| p
 |colspan="4"| s
 |-
 | Bucket-Typ
@@ Zeile 168: / Zeile 162: @@
 |
 | 15
 |
 | 7
 | 11
@@ Zeile 186: / Zeile 180: @@
 |-
 |}
 Dieser Vorgang wird so oft wiederholt, bis das Ende von <math>A</math> erreicht wurde. Nach dem Durchlauf enthält <math>A</math> folgende Suffixe:
@@ Zeile 196: / Zeile 189: @@
 | 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*
+| Typ || S || L || L || S* || L || L || S* || S || L || L || S* || L || L || L || S*
 |-
 | Buckets
 | $
 |colspan="6"| i
 |colspan="2"| m
 |colspan="2"| p
 |colspan="4"| s
 |-
 | Bucket-Typ
@@ Zeile 215: / Zeile 208: @@
 |
 | 15
 |
 | 7
 | 11
@@ Zeile 255: / Zeile 248: @@
 |-
 |}
 Jetzt erfolgt der Durchlauf von rechts nach links:
@@ Zeile 265: / Zeile 257: @@
 | 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*
+| Typ || S || L || L || S* || L || L || S* || S || L || L || S* || L || L || L || S*
 |-
 | Buckets
 | $
 |colspan="6"| i
 |colspan="2"| m
 |colspan="2"| p
 |colspan="4"| s
 |-
 | Bucket-Typ
@@ Zeile 284: / Zeile 276: @@
 |
 | 15
 |
 | 7
 | 11
@@ Zeile 360: / Zeile 352: @@
 |-
 |}
 Zuletzt werden die sortierten Suffixe in <math>A</math> von links nach rechts zusammengesetzt. Es ergibt sich das sortierte Suffix-Array:
@@ Zeile 368: / Zeile 359: @@
 == Beispielimplementierung (Pseudocode) ==
-<syntaxhighlight lang="pascal" line>
+<syntaxhighlight lang="pascal" line="1">
 sais(T,A)
 for i = n to 1 do
-	if (T[i] >lex T[i+1])
+    if (T[i] >lex T[i+1])
-          typ[i] <- L
+        typ[i] <- L
-          if (typ[i+1] = S) typ[i+1] = S*
+        if (typ[i+1] = S) typ[i+1] = S*
-        else
+    else
-          typ[i] <- S
+        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)
@@ Zeile 392: / Zeile 383: @@
         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)
@@ Zeile 408: / Zeile 399: @@
 </syntaxhighlight>
-Weitere Implementierungen lassen sich unter <ref name="sais_impl">Yuta Mori: Sais Beispielimplementierungen {{Internetquelle | url= https://sites.google.com/site/yuta256/sais | titel= Sais | zugriff=2015-01-19}}</ref> finden. Darunter auch Implementierungen in Java, sowie C.
+Weitere Implementierungen lassen sich unter<ref name="sais_impl">Yuta Mori: Sais Beispielimplementierungen {{Internetquelle | url= https://sites.google.com/site/yuta256/sais | titel= Sais | zugriff= 2015-01-19 | archiv-url= https://web.archive.org/web/20140726035234/https://sites.google.com/site/yuta256/sais | archiv-datum= 2014-07-26 | offline= ja | archiv-bot= 2024-05-19 00:47:18 InternetArchiveBot }}</ref> 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 <math>O(n)</math>. Die Beispielimplementierung zeigt dabei drei über den Text iterierende Schleifen von Länge <math>n</math>. Die beiden angedeuteten Funktionen writeToLBucketForCharacter und writeToSBucketForCharacter springen innerhalb des Arrays <math>A</math> zu dem <math>L</math>-Bucket beziehungsweise <math>S</math>-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 <math>S^{*}</math>-Suffixe. Hier wird das Problem der Sortierung auf die <math>S^{*}</math>-Suffixe beschränkt indem der SAIS-Algorithmus rekursiv darauf angewendet wird. Der übergebene Text T' ist dabei höchstens <math>n/2</math> lang, da per Definition ein <math>S^{*}</math> nur an jeder zweiten Stelle im Text vorkommen kann. Dadurch ergibt sich folgende kombinierte Laufzeit:
+Interessant ist das Sortieren der <math>S^{*}</math>-Suffixe. Hier wird das Problem der Sortierung auf die <math>S^{*}</math>-Suffixe beschränkt, indem der SAIS-Algorithmus rekursiv darauf angewendet wird. Der übergebene Text T' ist dabei höchstens <math>n/2</math> lang, da per Definition ein <math>S^{*}</math> nur an jeder zweiten Stelle im Text vorkommen kann. Dadurch ergibt sich folgende kombinierte Laufzeit:
 <math>T(n) = O(n) + T(n/2) = O(n)</math>
@@ Zeile 420: / Zeile 411: @@
 == Verwendung ==
-Der Suffix-Array-Induced-Sorting-Algorithmus findet Verwendung bei der Erstellung eines Suffixbaumes in <math>O(n)</math> Zeit. Dabei bildet er nur einen Teilschritt zwischen dem Text und dem entstandendem Suffixbaum.
+Der Suffix-Array-Induced-Sorting-Algorithmus findet Verwendung bei der Erstellung eines Suffixbaumes in <math>O(n)</math> Zeit. Dabei bildet er nur einen Teilschritt zwischen dem Text und dem entstandenen Suffixbaum.
 == Siehe auch ==
@@ Zeile 426: / Zeile 417: @@
 == 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)
+* 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 ==
 <references />
-<!--Keine Artikelkategorien auf Benutzerseiten!
+{{SORTIERUNG:SuffixArrayInducedSorting}}
 [[Kategorie:Algorithmus]]
--->

„Suffix-Array-Induced-Sorting“ – Versionsunterschied

Aktuelle Version vom 19. Mai 2024, 02:47 Uhr

Verfahren des Algorithmus

Beispiel

Beispielimplementierung (Pseudocode)

Laufzeit

Verwendung

Siehe auch

Literatur

Einzelnachweise

What are your Feelings

Share This Article :