LCP-Array – Wikipedia
Das LCP-Array ist eine Datenstruktur aus der Informatik, welche meist in Kombination mit dem Suffixarray verwendet wird. Die Bezeichnung „LCP“ ist eine Abkürzung für „longest common prefix“ (dt. längstes gemeinsames Präfix). Das Array selbst enthält die Länge des längsten gemeinsamen Präfixes von je zwei lexikographisch aufeinanderfolgenden Suffixen.
Für das LCP-Array gibt es zahlreiche Anwendungen aus dem Bereich der Textsuche und -indizierung, wie beispielsweise die Konstruktion des Suffixbaums oder eine effiziente Suche aller Vorkommen eines Suchmusters in einem Text. Der benötigte Speicherplatz des LCP-Arrays ist linear im Vergleich zur Textgröße und es gibt Algorithmen, die das LCP-Array in linearer Zeit mit Hilfe des Suffixarrays konstruieren. Es wurde erstmals in einer Veröffentlichung von Manber und Myers (1993)[1] benutzt, in der es als Hgt-Array bezeichnet wurde.
Definition
[Bearbeiten | Quelltext bearbeiten]Sei ein Text der Länge und sei das Suffixarray über dem Text . Außerdem bezeichne das Suffix und die Länge des längsten gemeinsamen Präfixes der beiden Strings und .
Das LCP-Array ist ein Array der Größe , wobei die einzelnen Felder wie folgt definiert sind:
Das Suffixarray enthält eine lexikographische Sortierung aller Suffixe von . Etwas informeller ausgedrückt bezieht sich ein Eintrag das LCP-Array immer auf zwei lexikographisch aufeinanderfolgende Suffixe von und beschreibt die Länge des längsten gemeinsamen Präfixes der betrachteten Suffixe. Der Wert von ist undefiniert, weil bereits das lexikographisch kleinste Suffix von ist und keinen Vorgänger besitzt.
Beispiel
[Bearbeiten | Quelltext bearbeiten]Betrachte den Text .
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
T[i] | m | i | s | s | i | s | s | i | p | p | i | $ |
Das Suffixarray von repräsentiert die Sortierung der Suffixe des Textes, wobei im Array jeweils der Index des ersten Buchstabens des jeweiligen Suffixes gespeichert wird. Für den Text sieht die Suffixsortierung wie folgt aus:
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
A[i] | 12 | 11 | 8 | 5 | 2 | 1 | 10 | 9 | 7 | 4 | 6 | 3 |
1 | $ | i | i | i | i | m | p | p | s | s | s | s |
2 | $ | p | s | s | i | i | p | i | i | s | s | |
3 | p | s | s | s | $ | i | p | s | i | i | ||
4 | i | i | i | s | $ | p | s | p | s | |||
5 | $ | p | s | i | i | i | p | s | ||||
6 | p | s | s | $ | p | i | i | |||||
7 | i | i | s | p | $ | p | ||||||
8 | $ | p | i | i | p | |||||||
9 | p | p | $ | i | ||||||||
10 | i | p | $ | |||||||||
11 | $ | i | ||||||||||
12 | $ |
Das LCP-Array enthält die Länge des längsten gemeinsamen Präfixes zweier aufeinanderfolgender Suffixe. Es kann konstruiert werden, indem die Suffixe in der Suffixsortierung zeichenweise miteinander verglichen werden. Beispielsweise werden für die Berechnung des Wertes die bei und beginnenden Suffixe miteinander verglichen: Das längste gemeinsame Präfix von und ist und hat damit eine Länge von 2. Dementsprechend ist . Die restlichen Werte des LCP-Arrays können auf die gleiche Weise berechnet werden. Der Wert von bleibt dabei undefiniert, da es kein Suffix gibt, das lexikographisch vor liegt. Das LCP-Array für den Text sieht wie folgt aus:
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
H[i] | 0 | 1 | 1 | 4 | 0 | 0 | 1 | 0 | 2 | 1 | 3 |
Berechnung
[Bearbeiten | Quelltext bearbeiten]Die einfachste Art das LCP-Array zu berechnen wäre (so wie im obigen Beispiel) mit Hilfe des Suffixarrays die lexikographisch aufeinanderfolgenden Suffixe zeichenweise zu vergleichen, um so die Länge des längsten gemeinsamen Präfixes zu berechnen. Allerdings ergibt sich mit diesem Verfahren im schlimmsten Fall eine Laufzeit von . Enthält ein Text beispielsweise gleiche Zeichen, so müssten insgesamt Vergleiche getätigt werden.
Ein effizienterer Ansatz basiert auf der Grundidee, die LCP-Einträge in Textreihenfolge zu berechnen. Angenommen und sind aufeinanderfolgende Werte im Suffixarray und und haben ein gemeinsames Präfix von Zeichen. Die Suffixe und besitzen dann gemeinsame Zeichen. Allerdings müssen und im Suffixarray nicht nebeneinander stehen; es kann durchaus Suffixe geben, die lexikographisch zwischen und liegen. Angenommen sei der Wert, der vor dem Wert im Suffixarray steht. Dann müssen und wegen der lexikographischen Sortierung der Suffixe mindestens gemeinsame Zeichen haben (denn liegt im Suffixarray zwischen und ), das heißt, es würde reichen die beiden Suffixe ab dem -ten Zeichen miteinander zu vergleichen.
Für diesen Ansatz wird das inverse Suffixarray benötigt, um herauszufinden, an welcher Stelle ein bestimmter Wert in vorkommt. Bei handelt es sich um die inverse Permutation von , das heißt gibt an, an welcher Stelle im Suffixarray der Wert steht.
Es ergibt sich folgender Algorithmus:
LCP-Array(T, A, n) for (i=1 to n) { Ainv[A[i]] = i; } H[1] = 0; h = 0; for (i=1 to n) { if (Ainv[i] ≠ 1) { j = A[Ainv[i] - 1] while T[i+h] = T[j+h] h = h + 1 H[Ainv[i]] = h h = max(0, h - 1) } }
Die Laufzeit ist linear, da maximal den Wert annehmen kann. Da in jedem Schritt nur um 1 dekrementiert wird, wird die innere While-Schleife höchstens mal ausgeführt. Es ergibt sich somit eine Gesamtlaufzeit von .
Der oben vorgestellte Ansatz stammt von Kasai et al. (2001)[2] und ist der erste veröffentlichte Algorithmus, der das LCP-Array in linearer Zeit berechnet. Manzini (2004)[3] hat eine verbesserte Version entwickelt, die neben dem eigentlichen Text, dem Suffix-Array und dem LCP-Array keinen zusätzlichen Speicher benötigt. Eine weitere Verbesserung ist der φ-Algorithmus von Kärkkäinen, Manzini und Puglisi:[4] Während der ursprüngliche Algorithmus durch nicht sequentielle Zugriffe auf die Arrays für entsprechend lange Texte bis zu Cache-Misses verursacht (nämlich in den Zeilen 3, 9, 10 und 12), kommt der φ-Algorithmus mit nur Cache-Misses aus.
Die oben genannten Algorithmen benutzen für die Berechnung des LCP-Arrays ein bereits vorhandenes Suffixarray. Es gibt Algorithmen, die das LCP-Array gleichzeitig mit dem Suffix-Array berechnen. Der zur Zeit schnellste Linearzeit-Algorithmus stammt von Fischer (2011).[5]
Gog & Ohlebusch (2011)[6] haben zwei Algorithmen veröffentlicht, die im Worst-Case eine quadratische Laufzeit haben, aber in der Praxis schneller sind, als die oben erwähnten Linearzeit-Algorithmen.
Beschleunigung der Textsuche mit Hilfe des LCP-Arrays
[Bearbeiten | Quelltext bearbeiten]Mit dem Suffixarray kann das Vorkommen eines Musters der Länge in einem Text der Länge mit Hilfe von binärer Suche bestimmt werden. Da die Suffixe im Suffixarray lexikographisch sortiert sind, genügen Vergleiche, um das lexikographisch kleinste (bzw. größte) Suffix zu finden, welches enthält. Für jeden Vergleich müssen dabei bis zu Zeichen verglichen werden, wodurch dieses Verfahren eine Laufzeit von besitzt.
Mit Hilfe des LCP-Arrays lässt sich die Laufzeit auf verbessern, indem verhindert wird, dass bei jedem Schritt der binären Suche das Muster erneut von Beginn an gelesen werden muss.
Bei jedem Schritt der binären Suche liegt eine linke Intervallgrenze , eine rechte Intervallgrenze und ein mittleres Element vor. Dabei wird mit dem lexikographisch -ten Suffix (also mit ) verglichen. Stimmen beide Strings überein, ist die binäre Suche fertig, ansonsten muss entweder in der linken oder rechten Intervallhälfte weitergesucht werden. Wir schauen uns den Fall an, dass lexikographisch kleiner als ist – der andere Fall ist analog. Sei die Länge des längsten gemeinsamen Präfixes der beiden Strings. Das heißt, dass das -te Zeichen von lexikographisch kleiner als das von ist.
Das neue Intervall besitzt die Grenzen und und das mittlere Element . Sei die Länge des längsten gemeinsamen Präfixes zwischen dem alten und dem neuen mittleren Element. Es folgt eine Fallunterscheidung:
- : Das -te Zeichen der Suffixe und ist gleich. Daher muss auch lexikographisch kleiner als sein und die binäre Suche kann ohne weitere Vergleiche in der linken Intervallhälfte fortgesetzt werden.
- : Wegen ist das Suffix lexikographisch kleiner als das Suffix . Das bedeutet, dass das -te Zeichen von Suffix kleiner als das -te Zeichen von Suffix sein muss. Da und ein gemeinsames Präfix von mindestens Zeichen haben, folgt hier, dass lexikographisch kleiner ist als P und die binäre Suche wird in der rechten Hälfte fortgesetzt.
- : und haben ein gemeinsames Präfix von mindestens Zeichen. Hier müssen beide Strings verglichen werden, wobei der Vergleich erst beim -ten Zeichen beginnen muss.
Durch das beschriebene Verfahren ist es bei der binären Suche niemals notwendig bereits gelesene Zeichen von nochmals zu lesen. Das Verfahren stammt von Manber und Myers[1]. Da sich im LCP-Array nur die -Werte für lexikographisch aufeinanderfolgende Suffixe befinden, wird im Folgenden noch gezeigt, wie sich beliebige -Werte effizient berechnen lassen.
Im Allgemeinen lässt sich das längste gemeinsame Präfix von zwei Suffixen mit Hilfe einer Range Minimum Query über dem LCP-Array finden[7]. Für zwei Suffixe , betrachtet man alle Suffixe, die lexikographisch dazwischen liegen: Falls zwei aufeinanderfolgende Suffixe ein längestes gemeinsames Präfix der Länge besitzen, so können und wegen der lexikographischen Sortierung kein längeres gemeinsames Präfix haben. Der Wert entspricht daher genau dem Minimum über den LCP-Einträgen . Dieses Minimum lässt sich mit geeigneten Verfahren für Range Minimum Queries in konstanter Zeit finden.[8]
Literatur
[Bearbeiten | Quelltext bearbeiten]- Enno Ohlebusch Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, 2013, Kapitel 4.
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ a b Udi Manber, Gene Myers: Suffix Arrays: A New Method for On-Line String Searches. In: SIAM Journal on Computing. 22. Jahrgang, Nr. 5, 1993, S. 935, doi:10.1137/0222058.
- ↑ Kasai, T. et al.: Linear-Time Longest-Common-Prefix Computation in Suffix. In: Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, 2001.
- ↑ Manzini, Giovanni: Two Space Saving Tricks for Linear Time LCP Array Computation. In: Lecture Notes in Computer Science, Volume 3111, Seite 372, 2004.
- ↑ Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simon J.: Permuted Longest-Common-Prefix Array. In: Lecture Notes in Computer Science, Volume 5577, Seite 181, 2009.
- ↑ Fischer, Johannes: Inducing the LCP-Array. In: Lecture Notes in Computer Science, Volume 6844, Seite 374–385, 2011.
- ↑ Gog, Simon; Ohlebusch, Enno: Fast and Lightweight LCP-Array Construction Algorithms. In: Proceedings of the Workshop on Algorithm Engineering and Experiments, ALENEX, Seite 25–34, 2011.
- ↑ Fischer, J. and V. Heun: Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In: Combinatorial Pattern Matching. 2006, S. 36–48, doi:10.1007/11780441_5.
- ↑ Fischer, J. and V. Heun: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays. In: SIAM J. Comput. 40 (apr). 2011, S. 465–492, doi:10.1137/090779759.