Suffixarray

Ein Suffixarray ist in der Informatik ein Array, das die Suffixe einer Zeichenkette in lexikographischer Reihenfolge angibt.

Beispiel

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

i	1	2	3	4	5	6	7	8	9	10	11	12
${\displaystyle S[i]}$	a	b	r	a	c	a	d	a	b	r	a	$

Dieser String hat zwölf Suffixe, die auch durch ihre Startposition i in ${\displaystyle S}$ beschrieben werden können:

Suffix	i
abracadabra$	1
bracadabra$	2
racadabra$	3
acadabra$	4
cadabra$	5
adabra$	6
dabra$	7
abra$	8
bra$	9
ra$	10
a$	11
$	12

Der leere String ist lexikografisch kleiner als jedes Suffix von ${\displaystyle S}$. Daher ist der Endmarker $ per Konvention ebenfalls lexikografisch kleiner als jedes andere Zeichen im String. Somit können alle Suffixe lexikografisch sortiert werden:

Suffix	i
$	12
a$	11
abra$	8
abracadabra$	1
acadabra$	4
adabra$	6
bra$	9
bracadabra$	2
cadabra$	5
dabra$	7
ra$	10
racadabra$	3

Als Array dargestellt ergibt sich {$, a$, abra$, …}.

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 abracadabra$ lautet das Suffixarray somit ${\displaystyle A}$={12,11,8,1,4,6,9,2,5,7,10,3}: Das Suffix „a“ bzw. „a$“ beginnt am elften Zeichen, „abra“ beim achten und so weiter.

Der Endmarker $ ist nützlich, wenn mehrere Strings kombiniert werden. Beispielsweise ist in ${\displaystyle S'}$=abracadabra$mississippi$ sofort klar, dass der Text aus den beiden Strings abracadabra und mississippi 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 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 ${\displaystyle O(n\log n)}$ Vergleiche benötigt. Da der Vergleich zweier Suffixe ${\displaystyle O(n)}$ Zeit benötigt, beträgt die komplette Laufzeit dieses Verfahrens ${\displaystyle O(n^{2}\log n)}$. Weiter entwickelte Algorithmen verbessern dies auf ${\displaystyle O(n\log n)}$, 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 ${\displaystyle \log _{2}n}$ Schritten ist jedes Suffix vollständig richtig sortiert und der Suffixarray fertig aufgebaut. Jeder Teilschritt ist in Zeit ${\displaystyle O(n)}$ möglich, so dass sich die Gesamtlaufzeit ${\displaystyle O(n\log n)}$ ergibt.[1]

Zu dieser Klasse gehören der klassische Suffixarray-Algorithmus von Manber und Myers[2] sowie der in der Praxis deutlich effizientere Algorithmus von Larsson und Sadakane.[3]

Rekursive Algorithmen

Diese Algorithmenklasse wird erst seit 2003 erforscht. Der Zeichen des Strings ${\displaystyle S}$ 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 ${\displaystyle S}$ abgelesen werden.

Durch geschickte Wahl von x und y haben die meisten dieser Algorithmen eine Laufzeit von ${\displaystyle O(n)}$. Da Rekursion in der Praxis teuer ist, sind sie jedoch nicht immer zu bevorzugen.[1]

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 ${\displaystyle S}$ 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 ${\displaystyle O(n^{2}\log n)}$ in der Praxis meist schneller als rekursive Algorithmen sind. Auch benötigen sie im Allgemeinen deutlich weniger Speicherplatz als andere Algorithmen.[1]

Der derzeit schnellste Algorithmus dieser Klasse ist der Suffix-Array-Induced-Sorting-Algorithmus (kurz SAIS) von Nong, Zhang und Chan[4]. Er benötigt lediglich eine Laufzeit in ${\displaystyle O(n)}$. Der SAIS-Algorithmus erweist sich auch in der Praxis als sehr schnell, wenn bei der Implementierung verschiedene Effekte wie z. B. Cache-Misses berücksichtigt werden.[5]

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)

Eine exakte Suchanfrage besteht aus einem Suchmuster ${\displaystyle P}$, das in einem Text ${\displaystyle T}$ gesucht werden soll. Eine Textstelle zählt nur dann als exaktes Vorkommen von ${\displaystyle P}$, wenn jedes Zeichen der Textstelle mit ${\displaystyle P}$ ü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 ${\displaystyle P}$ in ${\displaystyle T}$ vor?"), Anzahlanfragen ("Wie oft kommt ${\displaystyle P}$ in ${\displaystyle T}$ vor?") und Aufzählungsanfragen ("An welchen Stellen kommt ${\displaystyle P}$ in ${\displaystyle T}$ vor?") unterschieden, wobei Entscheidungsanfragen ggf. mithilfe von Anzahlanfragen und Anzahlanfragen mit Aufzählungsanfragen beantwortet werden können[6].

Um die Anzahl der exakten Vorkommen von ${\displaystyle P}$ zu bestimmen, müssen im Suffixarray zu ${\displaystyle T}$ alle Suffixe gesucht werden, die mit ${\displaystyle P}$ 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 ${\displaystyle P}$ beginnen. Mithilfe der binären Suche können diese jeweils in ${\displaystyle O(m\cdot \log n)}$ gefunden werden, wobei ${\displaystyle m}$ im Folgenden für die Länge von ${\displaystyle P}$ und ${\displaystyle n}$ für die Länge von ${\displaystyle T}$ steht. Die Anzahl der Vorkommen von ${\displaystyle P}$ ist dann gleich der Anzahl der Suffixe, die in diesem Block liegen. Damit kann die Anzahl der Vorkommen insgesamt in ${\displaystyle O(m\cdot \log n)}$ 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 ${\displaystyle O(m\cdot \log n+\vert O_{P}\vert )}$, wobei ${\displaystyle \vert O_{P}\vert }$ für die Anzahl der Vorkommen von ${\displaystyle P}$ in ${\displaystyle T}$ steht[7].

Verfeinerte Verfahren können unter Zuhilfenahme von weiteren Datenstrukturen bessere Laufzeiten erzielen. Wenn das sogenannte LCP-Array (englisch longest common prefix) zu ${\displaystyle T}$ bestimmt und eine geeignete RMQ-Datenstruktur (englisch range minimum query) zu dem LCP-Array konstruiert wurde, können Entscheidungs- sowie Anzahlanfragen in ${\displaystyle O(m)}$ und Aufzählungsanfragen in ${\displaystyle O(m+\vert O_{P}\vert )}$ beantwortet werden[8].

Konstruktion eines Suffixbaums

Das Suffixarray eines Texts ${\displaystyle T}$ wird häufig als Zwischenschritt benutzt, um den zugehörigen Suffixbaum in Linearzeit zu konstruieren[9]. 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[10]. 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[11]. 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 Suffixbäumen zu reduzieren[2]. 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 ${\displaystyle O(n\log n)}$ bis ${\displaystyle O(n^{2}\log n)}$ haben[3][12]. Die ersten garantierten Linearzeit-Algorithmen (d. h. solche mit Worst Case-Laufzeit ${\displaystyle O(n)}$) sind erst seit 2003 bekannt[13][14]. Seit 2004 ist bekannt, dass Suffixarrays jedes Problem mit der gleichen Zeitkomplexität wie Suffixbäume lösen können[15]. 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[16][17]. 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: Simple linear work suffix array construction. (PDF; 193 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, uni-ulm.de
• Klaus-Bernd Schürmann, Jens Stoye: An incomplex algorithm for fast suffix array construction. (PDF; 204 kB) In: Proceedings of ALENEX, 2005.

Weblinks

Commons: Suffix array – Sammlung von Bildern, Videos und Audiodateien

• Beispiel zur Verwendung von Suffixarrays für die Suche von Wörtern in einem Wörterbuch

Einzelnachweise

1. Simon J. Puglisi, W.F. Smyth, Andrew H. Turpin: A Taxonomy of Suffix Array Construction Algorithms. In: ACM Computing Surveys (CSUR) 39.2 (2007)
2. 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)
3. J.N. Larsson, K. Sadakane: Faster suffix sorting. In Tech rep. LU-CS-TR:99-214, Dep. of Computer Science, Lund University, Schweden (1999)
4. Nong Ge, Sen Zhang, Wai Hong Chan: Two Efficient Algorithms for Linear Time Suffix Array Construction. In: IEEE Transactions on Computers 60, no. 10 (October 2011), S. 1471–1484.
5. Nataliya Timoshevskaya, Wu-chun Feng: 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.
6. Enno Ohlebusch: Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 116.
7. Enno Ohlebusch: Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 120–125.
8. Enno Ohlebusch: Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 117–118.
9. Enno Ohlebusch: Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 113–114.
10. Enno Ohlebusch: Bioinformatics Algorithms. Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, Bremen 2013, ISBN 978-3-00-041316-2, S. 130.
11. Juha Kärkkäinen: Fast BWT in small space by blockwise suffix sorting. In: Theoretical Computer Science. Band 387, Nr. 3, 2007, S. 251 (PDF; 227KB)
12. S. Burkhardt, J. Kärkkäinen: Fast lightweight suffix array construction and checking. In: Proceedings of the 14th Annual Symposium CPM 2003
13. P. Ko, S. Aluru: Space efficient linear time construction of suffix arrays. In: Proceedings of the 14th Annual Symposium CPM 2003
14. Juha Kärkkäinen, Peter Sanders: Simple linear work suffix array construction. (PDF; 193 kB) In_ Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03). LNCS 2719, Springer, 2003, S. 943–955
15. M.I. Abouelhoda, S. Kurtz, E. Ohlebusch: Replacing suffix trees with suffix arrays. In J. Disc. Algor. 2, 1, 2004, S. 53–86
16. 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
17. G. Navarro, V. Mäkinen: Compressed full-text indexes. In_ ACM Comput. Serv., 39, 1.2, 2007