Quelltext der Seite Suffixarray

Ein '''Suffixarray''' ist in der [[Informatik]] ein [[Feld (Datentyp)|Array]], das die [[Suffix]]e einer [[Zeichenkette]] in [[lexikographisch]]er Reihenfolge angibt.

== Beispiel ==
Betrachte den String <math>S</math>=<code>abracadabra</code> der Länge 11. Da auch der leere String ein gültiges Suffix ist, fügen wir an das Ende von <math>S</math> den Endmarker <code>$</code> hinzu, um den leeren String bzw. das Ende von <math>S</math> ausdrücken zu können. Der String mit den zugehörigen Positionen seiner Zeichen lautet also:

{| class="wikitable"
|-
! i
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12
|- style="text-align:center"
! <math>S[i]</math>
| a || b || r || a || c || a || d || a || b || r || a || $
|}

Dieser String hat zwölf Suffixe, die auch durch ihre Startposition <code>i</code> in <math>S</math> beschrieben werden können:

{| class="wikitable"
!style="text-align:left"| Suffix !!style="text-align:left"| i
|- class="odd"
|style="text-align:right"| <code>abracadabra$</code> || 1
|- class="even"
|style="text-align:right"| <code>bracadabra$</code> || 2
|- class="odd"
|style="text-align:right"| <code>racadabra$</code> || 3
|- class="even"
|style="text-align:right"| <code>acadabra$</code> || 4
|- class="odd"
|style="text-align:right"| <code>cadabra$</code> || 5
|- class="even"
|style="text-align:right"| <code>adabra$</code> || 6
|- class="odd"
|style="text-align:right"| <code>dabra$</code> || 7
|- class="even"
|style="text-align:right"| <code>abra$</code> || 8
|- class="odd"
|style="text-align:right"| <code>bra$</code> || 9
|- class="even"
|style="text-align:right"| <code>ra$</code> || 10
|- class="odd"
|style="text-align:right"| <code>a$</code> || 11
|- class="even"
|style="text-align:right"| <code>$</code> || 12
|}

Der leere String ist lexikografisch kleiner als jedes Suffix von <math>S</math>. Daher ist der Endmarker <code>$</code> per Konvention ebenfalls lexikografisch kleiner als jedes andere Zeichen im String. Somit können alle Suffixe lexikografisch sortiert werden:

{| class="wikitable"
!style="text-align:left"| Suffix !!style="text-align:left"| i
|- class="odd"
| <code>$</code> || 12
|- class="even"
| <code>a$</code> || 11
|- class="even"
| <code>abra$</code> || 8
|- class="odd"
| <code>abracadabra$</code> || 1
|- class="even"
| <code>acadabra$</code> || 4
|- class="odd"
| <code>adabra$</code> || 6
|- class="even"
| <code>bra$</code> || 9
|- class="odd"
| <code>bracadabra$</code> || 2
|- class="even"
| <code>cadabra$</code> || 5
|- class="odd"
| <code>dabra$</code> || 7
|- class="even"
| <code>ra$</code> || 10
|- class="odd"
| <code>racadabra$</code> || 3
|}

Als Array dargestellt ergibt sich <code>{$, a$, abra$, …}</code>.

Wenn der Originalstring bekannt ist, kann jedes Suffix platzsparend durch den Index seines ersten Zeichens spezifiziert werden. Das Suffixarray ist ein Array dieser Indizes in lexikographischer Reihenfolge. Für den String <code>abracadabra$</code> lautet das Suffixarray somit <math>A</math>=<code>{12,11,8,1,4,6,9,2,5,7,10,3}</code>: Das Suffix „a“ bzw. „a$“ beginnt am elften Zeichen, „abra“ beim achten und so weiter.
<!--
{| class="wikitable"
! i
| 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12
|-
! <math>A[i]</math>
| 12 || 11 || 8 || 1 || 4 || 6 || 9 || 2 || 5 || 7 || 10 || 3
|-
|
|    ||    ||   || a ||   ||   ||   ||   ||   ||   ||    ||
|-
|
|    ||    ||   || b ||   ||   ||   || b ||   ||   ||    ||
|-
|
|    ||    ||   || r ||   ||   ||   || r ||   ||   ||    || r
|-
|
|    ||    ||   || a || a ||   ||   || a ||   ||   ||    || a
|-
|
|    ||    ||   || c || c ||   ||   || c || c ||   ||    || c
|-
|
|    ||    ||   || a || a || a ||   || a || a ||   ||    || a
|-
|
|    ||    ||   || d || d || d ||   || d || d || d ||    || d
|-
|
|    ||    || a || a || a || a ||   || a || a || a ||    || a
|-
|
|    ||    || b || b || b || b || b || b || b || b ||    || b
|-
|
|    ||    || r || r || r || r || r || r || r || r ||  r || r
|-
|
|    ||  a || a || a || a || a || a || a || a || a ||  a || a
|-
|
|  $ || $  || $ || $ || $ || $ || $ || $ || $ || $ ||  $ || $
|-
|}
-->

Der Endmarker <code>$</code> ist nützlich, wenn mehrere Strings kombiniert werden. Beispielsweise ist in <math>S'</math>=<code>abracadabra$mississippi$</code> sofort klar, dass der Text aus den beiden Strings <code>abracadabra</code> und <code>mississippi</code> besteht. Wenn nur ein String betrachtet wird, kann dieses Suffix übergangen werden: Da der leere String lexikographisch immer vor allen anderen sortiert wird, geht in diesem Fall keine Information verloren.

== Algorithmen ==
Es gibt eine Vielzahl an [[Algorithmus|Algorithmen]], um aus einem gegebenen Text der Länge ''n'' ein Suffixarray zu konstruieren. Die dabei verwendeten Methoden zur Suffix-Sortierung lassen sich grob in drei Klassen einteilen: Iterative, Rekursive und Induzierte Sortierung.

=== Iterative Teilsortierung ===

Der einfachste Weg besteht darin, einen effizienten vergleichsbasierten Sortieralgorithmus zu verwenden, der höchstens <math>O(n \log n)</math> Vergleiche benötigt. Da der Vergleich zweier Suffixe <math>O(n)</math> Zeit benötigt, beträgt die komplette Laufzeit dieses Verfahrens <math>O(n^2 \log n)</math>. Weiter entwickelte Algorithmen verbessern dies auf <math>O(n \log n)</math>, indem sie die Ergebnisse von Teilvergleichen ausnutzen und somit redundante Vergleiche vermeiden.

Dazu wird zunächst nur der erste Buchstabe jedes Suffixes betrachtet und daraus ein vorläufiger Suffixarray aufgebaut, der Suffixe mit gleichem Anfangsbuchstaben noch nicht untereinander sortiert hat. Suffixe mit unterschiedlichen Anfangsbuchstaben sind aber bereits in der richtigen Reihenfolge enthalten. In einem zweiten Schritt wird jede Gruppe von Suffixen mit gleichem Anfangsbuchstaben so sortiert, dass sie bezüglich der ersten beiden Anfangsbuchstaben korrekt sortiert sind. Der dritte Schritt sortiert alle Suffixgruppen mit zwei gleichen Anfangsbuchstaben so, dass sie bezüglich der ersten vier richtig sortiert sind, der vierte Schritt so, dass sie bezüglich der ersten acht richtig sortiert sind, und so weiter. Nach <math>\log_2 n</math> Schritten ist jedes Suffix vollständig richtig sortiert und der Suffixarray fertig aufgebaut. Jeder Teilschritt ist in Zeit <math>O(n)</math> möglich, so dass sich die Gesamtlaufzeit <math>O(n \log n)</math> ergibt.<ref name="puglisi07taxonomy">Simon J. Puglisi, W.F. Smyth, Andrew H. Turpin: ''A Taxonomy of Suffix Array Construction Algorithms''. In: ''ACM Computing Surveys (CSUR)'' 39.2 (2007)</ref>

Zu dieser Klasse gehören der klassische Suffixarray-Algorithmus von Manber und Myers<ref name="mm90">U. Manber, G.W. Myers: ''Suffix arrays: A new method for on-line string searches''. In ''Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms'' (1990)</ref> sowie der in der Praxis deutlich effizientere Algorithmus von Larsson und Sadakane.<ref name="ls99">J.N. Larsson, K. Sadakane: ''Faster suffix sorting''. In ''Tech rep. LU-CS-TR:99-214'', Dep. of Computer Science, Lund University, Schweden (1999)</ref>

=== Rekursive Algorithmen ===

Diese Algorithmenklasse wird erst seit 2003 erforscht. Die Zeichen des Strings <math>S</math> werden dazu in zwei Zeichenketten ''x'' und ''y'' aufgeteilt. Anschließend wird der Algorithmus rekursiv auf ''x'' aufgerufen. Mit dem dadurch berechneten Suffixarray von ''x'' kann der Suffixarray von ''y'' effizient berechnet („induziert“) werden. Da die Aufteilung in ''x'' und ''y'' bekannt ist, kann daraus der Suffixarray von <math>S</math> abgelesen werden.

Durch geschickte Wahl von ''x'' und ''y'' haben die meisten dieser Algorithmen eine Laufzeit von <math>O(n)</math>. Da Rekursion in der Praxis teuer ist, sind sie jedoch nicht immer zu bevorzugen.<ref name="puglisi07taxonomy" />

=== Induzierte Sortierung ===

Auch hier wird mit einem bereits berechneten Suffixarray einer Zeichenkette ''x'' der Suffixarray einer Zeichenkette ''y'' effizient berechnet (induziert). Anstelle einer rekursiven Arbeitsweise kann beispielsweise der String <math>S</math> mehrfach in verschiedenen Richtungen durchlaufen werden. Dabei werden die Zeichen in ''x'' bzw. ''y'' klassifiziert, teilweise sortiert und in einem späteren Schritt auf Basis anderer Teilergebnisse weitersortiert. Die Algorithmen dieser Klasse sind sehr divers. Fast alle haben jedoch gemeinsam, dass sie trotz einer häufig schlechten Worst Case-Laufzeit von <math>O(n^2 \log n)</math> in der Praxis meist schneller als rekursive Algorithmen sind. Auch benötigen sie im Allgemeinen deutlich weniger Speicherplatz als andere Algorithmen.<ref name="puglisi07taxonomy" />

Der derzeit schnellste Algorithmus dieser Klasse ist der [[Suffix-Array-Induced-Sorting|{{lang|en|Suffix-Array-Induced-Sorting}}-Algorithmus]] (kurz SAIS) von Nong, Zhang und Chan.<ref name="SAIS">Nong Ge, Sen Zhang, Wai Hong Chan: T''wo Efficient Algorithms for Linear Time Suffix Array Construction''. In: ''IEEE Transactions on Computers 60'', no. 10 (October 2011), S. 1471–1484.</ref> Er benötigt lediglich eine Laufzeit in <math>O(n)</math>. Der SAIS-Algorithmus erweist sich auch in der Praxis als sehr schnell, wenn bei der Implementierung verschiedene Effekte wie z.&nbsp;B. Cache-Misses berücksichtigt werden.<ref name="timoshevskaya">Nataliya Timoshevskaya, Wu-chun Feng: [http://synergy.cs.vt.edu/pubs/papers/timoshevskaya-saisopt-iccabs14.pdf ''SAIS-OPT: On the characterization and optimization of the SA-IS algorithm for suffix array construction''.] In: ''2014 IEEE 4th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS)'', 2014.</ref>

== Anwendungen ==
Nach der Konstruktion kann das Suffixarray als Index des Texts verwendet werden, um nachfolgende Operationen effizient durchzuführen. Zu diesen Operationen zählen unter anderem Suchanfragen und Kompressionsverfahren.

=== Exakte Suchanfragen (String Matching) ===
{{Siehe auch|String Matching}}
Eine exakte Suchanfrage besteht aus einem Suchmuster <math>P</math>, das in einem Text <math>T</math> gesucht werden soll. Eine Textstelle zählt nur dann als exaktes Vorkommen von <math>P</math>, wenn jedes Zeichen der Textstelle mit <math>P</math> übereinstimmt. Damit unterscheiden sich diese Anfragen von den nicht exakten Anfragen, bei denen eine festgelegte Anzahl an abweichenden Zeichen erlaubt ist. Es wird bei den exakten Suchanfragen zwischen Entscheidungsanfragen ("Kommt <math>P</math> in <math>T</math> vor?"), Anzahlanfragen ("Wie oft kommt <math>P</math> in <math>T</math> vor?") und Aufzählungsanfragen ("An welchen Stellen kommt <math>P</math> in <math>T</math> vor?") unterschieden, wobei Entscheidungsanfragen ggf. mithilfe von Anzahlanfragen und Anzahlanfragen mit Aufzählungsanfragen beantwortet werden können.<ref name="ohlebusch_bioinformatics-S116">Enno Ohlebusch: ''Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction.'' Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 116.</ref>

Um die Anzahl der exakten Vorkommen von <math>P</math> zu bestimmen, müssen im Suffixarray zu <math>T</math> alle Suffixe gesucht werden, die mit <math>P</math> beginnen. Da das Suffixarray sortiert ist, liegen diese Suffixe alle direkt hintereinander und bilden einen Block. Daher reicht es aus, den lexikographisch kleinsten und den lexikographisch größten Suffix zu bestimmen, die mit <math>P</math> beginnen. Mithilfe der binären Suche können diese jeweils in <math>O(m \cdot \log n)</math> gefunden werden, wobei <math>m</math> im Folgenden für die Länge von <math>P</math> und <math>n</math> für die Länge von <math>T</math> steht. Die Anzahl der Vorkommen von <math>P</math> ist dann gleich der Anzahl der Suffixe, die in diesem Block liegen. Damit kann die Anzahl der Vorkommen insgesamt in <math>O(m \cdot \log n)</math> bestimmt werden. Wenn zusätzlich die Ausgabe der Anfangspositionen aller exakten Vorkommen gefordert ist, müssen stattdessen die Werte des Suffixarrays in dem Block zurückgegeben werden. Die Laufzeit hierfür beträgt <math>O(m \cdot \log n + \vert O_P\vert )</math>, wobei <math>\vert O_P\vert</math> für die Anzahl der Vorkommen von <math>P</math> in <math>T</math> steht.<ref name="ohlebusch_bioinformatics-S120-125">Enno Ohlebusch: ''Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction.'' Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 120–125.</ref>

Verfeinerte Verfahren können unter Zuhilfenahme von weiteren Datenstrukturen bessere Laufzeiten erzielen. Wenn das sogenannte [[LCP-Array]] (englisch longest common prefix) zu <math>T</math> bestimmt und eine geeignete [[Range Minimum Query|RMQ-Datenstruktur]] (englisch range minimum query) zu dem LCP-Array konstruiert wurde, können Entscheidungs- sowie Anzahlanfragen in <math> O( m )</math> und Aufzählungsanfragen in <math>O(m + \vert O_P\vert )</math> beantwortet werden.<ref name="ohlebusch_bioinformatics-S117-118">Enno Ohlebusch: ''Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction.'' Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 117–118.</ref>

=== Konstruktion eines Suffixbaums ===
Das Suffixarray eines Texts <math>T</math> wird häufig als Zwischenschritt benutzt, um den zugehörigen [[Suffixbaum]] in Linearzeit zu konstruieren.<ref name="ohlebusch_bioinformatics-S113-114">Enno Ohlebusch: ''Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction.'' Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 113–114.</ref> Der Suffixbaum kann anschließend ebenfalls als Index genutzt werden, um Suchanfragen zu beantworten.

=== Kompression ===
Verschiedene Kompressionsverfahren können unter Einsatz des Suffixarrays effizient umgesetzt werden. So kann die Faktorisierung der [[LZ77]]-Komprimierung in Linearzeit implementiert werden.<ref name="ohlebusch_bioinformatics-S130">Enno Ohlebusch: ''Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction.'' Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 130.</ref> Darüber hinaus kann man aus einem bestehenden Suffixarray mit sehr geringem Aufwand die [[Burrows-Wheeler-Transformation]] des Textes errechnen.
Dazu wird nacheinander für jedes Suffix des Suffixarrays das Zeichen bestimmt, das im Text genau eine Position vor dem Suffix steht, und in einem Array abgelegt<ref name="kärkkäinen-bwt">Juha Kärkkäinen: ''Fast BWT in small space by blockwise suffix sorting.'' In: ''Theoretical Computer Science.'' Band 387, Nr. 3, 2007, S. 251 ([http://www.sciencedirect.com/science/article/pii/S0304397507005245/pdf?md5=63fe82c3005930879b1b2eaceadb55c6&pid=1-s2.0-S0304397507005245-main.pdf PDF; 227KB])</ref>. Das resultierende Array ist dann identisch zur Burrows-Wheeler-Transformation des Textes und kann beispielsweise für das [[bzip2]]-Kompressionsverfahren verwendet werden.

== Geschichte ==
Suffixarrays wurden ursprünglich 1990 von [[Gene Myers]] und [[Udi Manber]] entwickelt, um den Speicherverbrauch im Vergleich zu [[Suffixbaum|Suffixbäumen]] zu reduzieren.<ref name="mm90" /> Nachdem einige Jahre keine signifikanten Erkenntnisse auftraten, sind Suffixarrays seit ca. 2000 ein beliebtes Forschungsthema. Seitdem wurde eine Vielzahl von Konstruktionsalgorithmen entwickelt, die zahlreiche wünschenswerte Eigenschaften aufweisen.

Seit 1999 existieren Algorithmen, die in den meisten Anwendungsfällen schneller als die existierenden Linearzeitalgorithmen sind, schlimmstenfalls jedoch einen Zeitbedarf im Bereich <math>O(n \log n)</math> bis <math>O(n^2 \log n)</math> haben<ref name="ls99" /><ref name="bk03">S. Burkhardt, J. Kärkkäinen: ''Fast lightweight suffix array construction and checking''. In: ''Proceedings of the 14th Annual Symposium CPM 2003''</ref>.
Die ersten garantierten Linearzeit-Algorithmen (d.&nbsp;h. solche mit Worst Case-Laufzeit <math>O(n)</math>) sind erst seit 2003 bekannt.<ref name="ka05">P. Ko, S. Aluru: ''Space efficient linear time construction of suffix arrays''. In: ''Proceedings of the 14th Annual Symposium CPM 2003''</ref><ref name="ks03">Juha Kärkkäinen, Peter Sanders: [http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf ''Simple linear work suffix array construction''.] (PDF; 193&nbsp;kB) In_ ''Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03)''. LNCS 2719, Springer, 2003, S. 943–955</ref>
Seit 2004 ist bekannt, dass Suffixarrays jedes Problem mit der gleichen Zeitkomplexität wie [[Suffixbaum|Suffixbäume]] lösen können.<ref name="ako04">M.I. Abouelhoda, S. Kurtz, E. Ohlebusch: ''Replacing suffix trees with suffix arrays''. In ''J. Disc. Algor. 2'', 1, 2004, S. 53–86</ref> Spätestens seit diesem Zeitpunkt sind Suffixarrays daher für fast alle Suffix- und Stringsortierungsaufgaben das Mittel der Wahl.

Ab 2005 wurde neben der Konstruktion auch die effiziente Speicherung von Suffixarrays betrachtet. Neben reinen Suffixarrays können nun auch komprimierte Suffixarrays effizient konstruiert und verwendet werden.<ref name="gv05">R. Grossi, J. Vitter: ''Compressed suffix arrays and suffix trees with applications to text indexing and string matching''. In ''SIAM J. Comput. '' 35.2, 2005, S. 378–407</ref><ref name="nm07">G. Navarro, V. Mäkinen: ''Compressed full-text indexes''. In_ ''ACM Comput. Serv.'', 39, 1.2, 2007</ref>
Auch für auf der [[Burrows-Wheeler-Transformation]] basierende komprimierte Volltext-Indizes sind sie nützlich.

== Literatur ==
* Udi Manber, Gene Myers: ''Suffix arrays: a new method for on-line string searches''. In: ''SIAM Journal on Computing'', Volume 22, Issue 5, Oktober 1993, S. 935–948.
* Pang Ko, Srinivas Aluru: ''Space efficient linear time construction of suffix arrays''. In: ''Combinatorial Pattern Matching (CPM 03)''. LNCS 2676, Springer, 2003, S. 203–210.
* Juha Kärkkäinen, Peter Sanders: [http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf ''Simple linear work suffix array construction''.] (PDF; 193&nbsp;kB) In: ''Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP ’03)''. LNCS 2719, Springer, 2003, S. 943–955.
* Enno Ohlebusch: ''Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction''. Oldenbusch, Bremen 2013, [http://www.uni-ulm.de/in/theo/m/ohlebusch/book-bioinformatics-algorithms.html uni-ulm.de]
* Klaus-Bernd Schürmann, Jens Stoye: [http://www.techfak.uni-bielefeld.de/~stoye/dropbox/alenex2005final.pdf ''An incomplex algorithm for fast suffix array construction''.] (PDF; 204&nbsp;kB) In: ''Proceedings of ALENEX'', 2005.

== Weblinks ==
{{Commonscat|Suffix array}}
* [http://kodira.de/2012/12/einfach-erklart-suffixarray/ Beispiel zur Verwendung von Suffixarrays für die Suche von Wörtern in einem Wörterbuch]

== Einzelnachweise ==
<references />

[[Kategorie:Datenstruktur]]
[[Kategorie:Kombinatorische Optimierung]]
[[Kategorie:Suffix (Informatik)|!Suffixarray]]