„Suffix-Array-Induced-Sorting“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen
[ungesichtete Version][gesichtete Version]
← Zum vorherigen Versionsunterschied
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
MerlBot (Diskussion | Beiträge)
1.885.939 Bearbeitungen
InternetArchiveBot hat 1 Archivlink(s) ergänzt und 0 Link(s) als defekt/tot markiert.) #IABot (v2.0.9.5
 
(26 dazwischenliegende Versionen von 13 Benutzern werden nicht angezeigt)
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[[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 SuffixArraySuffixarray <math>A</math> konstruiert. Mit <math>T^{i}</math> wird ein einzelnesdas ZeichenSuffix 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 ZeichenSuffix lexikographisch größer ist, sonst als <math>L</math>.
#Kennzeichne alleein SuffixeSuffix vom Typ <math>S</math> mit <math>S^{*}</math>, wenn derendessen Vorgänger lexikographisch größer sindist
#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 lexikograpischlexikographisch 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 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>-SuffixeSubstrings und ordne diesen dann Superzeichen zu. Erzeuge daraus Text <math>T'</math>.
#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>.
 
== Beispiel ==
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 ⟶ 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*
|}
 
 
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 ⟶ 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*
|-
| 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 sechs malsechsmal 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 ⟶ 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*
|-
| Buckets
| $
|colspan="6"| i
|colspan="2"| m
|colspan="2"| p
|colspan="4"| s
|-
| Bucket-Typ
Zeile 82 ⟶ 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 übergebengeschrieben. Dies erfolgt durch einen Unterschritt, indem man aus den gegebenen <math>S^{*}</math>-SuffixenSubstrings <math>T'</math> konstruiert. Zur Vereinfachung werden die SuffixeSubstrings 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.
 
{| class="wikitable" style="text-align:center"
Zeile 96 ⟶ 91:
| T' || D || B || C || A
|-
| Stelle in T || 4 || 7 || 11 || 15
|}
 
Zeile 111 ⟶ 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*
|-
| Buckets
| $
|colspan="6"| i
|colspan="2"| m
|colspan="2"| p
|colspan="4"| s
|-
| Bucket-Typ
Zeile 130 ⟶ 125:
|
| 15
|
| 7
| 11
Zeile 140 ⟶ 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 ⟶ 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*
|-
| Buckets
| $
|colspan="6"| i
|colspan="2"| m
|colspan="2"| p
|colspan="4"| s
|-
| Bucket-Typ
Zeile 168 ⟶ 162:
|
| 15
|
| 7
| 11
Zeile 186 ⟶ 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 ⟶ 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*
|-
| Buckets
| $
|colspan="6"| i
|colspan="2"| m
|colspan="2"| p
|colspan="4"| s
|-
| Bucket-Typ
Zeile 215 ⟶ 208:
|
| 15
|
| 7
| 11
Zeile 255 ⟶ 248:
|-
|}
 
 
Jetzt erfolgt der Durchlauf von rechts nach links:
Zeile 265 ⟶ 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*
|-
| Buckets
| $
|colspan="6"| i
|colspan="2"| m
|colspan="2"| p
|colspan="4"| s
|-
| Bucket-Typ
Zeile 284 ⟶ 276:
|
| 15
|
| 7
| 11
Zeile 360 ⟶ 352:
|-
|}
 
 
Zuletzt werden die sortierten Suffixe in <math>A</math> von links nach rechts zusammengesetzt. Es ergibt sich das sortierte Suffix-Array:
Zeile 368 ⟶ 359:
== Beispielimplementierung (Pseudocode) ==
 
<syntaxhighlight lang="pascal" line="1">
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)
Zeile 392 ⟶ 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 ⟶ 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 | 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:
 
<math>T(n) = O(n) + T(n/2) = O(n)</math>
Zeile 420 ⟶ 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 entstandendementstandenen Suffixbaum.
 
== Siehe auch ==
Zeile 426 ⟶ 417:
 
== Literatur ==
* Ge Nong, Sen Zhang, Wai Hong Chan: Two Efficient Algorithms for Linear Time Suffix Array Construction. IEEE Trans. Computers 60(10): 1471-14841471–1484 (2011)
 
== Einzelnachweise ==
<references />
 
<!--Keine Artikelkategorien auf Benutzerseiten!
{{SORTIERUNG:SuffixArrayInducedSorting}}
[[Kategorie:Algorithmus]]
-->

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

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 angewendet, der ein Suffixarray konstruiert. Mit wird das Suffix von ab Index angegeben.[1]

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

Schritt 5 kann hierbei noch konkretisiert werden:

  1. Sortiere die -Substrings und ordne diesen dann Superzeichen zu. Erzeuge daraus Text .
  2. Berechne Suffixarray für rekursiv.
  3. Aus folgt dann die Sortierung der -Suffixe Rücktransformation der Indizes von nach .

Beispiel

Als Beispieltext wird hier 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 hingegen ist vergleichsweise groß, weil es sechsmal in auftritt.

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

, wobei , , und . Die Superzeichen bis stehen hier für die jeweiligen -Suffixe.

Um 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

ist dann von der Form

, wobei , , und .

Mit diesem Schritt ist bereits ein Teil des kompletten Suffixarrays 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 ist, so wird dieses an die nächst freie Stelle im -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 erreicht wurde. Nach dem Durchlauf enthält 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 von links nach rechts zusammengesetzt. Es ergibt sich das sortierte Suffix-Array:

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 . Die Beispielimplementierung zeigt dabei drei über den Text iterierende Schleifen von Länge . Die beiden angedeuteten Funktionen writeToLBucketForCharacter und writeToSBucketForCharacter springen innerhalb des Arrays zu dem -Bucket beziehungsweise -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 -Suffixe. Hier wird das Problem der Sortierung auf die -Suffixe beschränkt, indem der SAIS-Algorithmus rekursiv darauf angewendet wird. Der übergebene Text T' ist dabei höchstens lang, da per Definition ein nur an jeder zweiten Stelle im Text vorkommen kann. Dadurch ergibt sich folgende kombinierte Laufzeit:

Insgesamt wird also eine Laufzeit von gebraucht.

Verwendung

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

Siehe auch

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. 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
Quelle: https://de.wikipedia.org/w/index.php?title=Suffix-Array-Induced-Sorting&diff=cur&oldid=138168414&diff-type=inline