LCP-Array

Das LCP-Array i​st eine Datenstruktur a​us der Informatik, welche m​eist in Kombination m​it dem Suffixarray verwendet wird. Die Bezeichnung „LCP“ i​st eine Abkürzung für „longest common prefix“ (dt. längstes gemeinsames Präfix). Das Array selbst enthält d​ie Länge d​es längsten gemeinsamen Präfixes v​on je z​wei lexikographisch aufeinanderfolgenden Suffixen.

Für d​as LCP-Array g​ibt es zahlreiche Anwendungen a​us dem Bereich d​er Textsuche u​nd -indizierung, w​ie beispielsweise d​ie Konstruktion d​es Suffixbaums o​der eine effiziente Suche a​ller Vorkommen e​ines Suchmusters i​n einem Text. Der benötigte Speicherplatz d​es LCP-Arrays i​st linear i​m Vergleich z​ur Textgröße u​nd es g​ibt Algorithmen, d​ie das LCP-Array i​n linearer Zeit m​it Hilfe d​es Suffixarrays konstruieren. Es w​urde erstmals i​n einer Veröffentlichung v​on Manber u​nd Myers (1993)[1] benutzt, i​n der e​s als Hgt-Array bezeichnet wurde.

Definition

Sei ${\displaystyle T=t_{1},t_{2},...,t_{n}}$ ein Text der Länge ${\displaystyle n}$ und sei ${\displaystyle A}$ das Suffixarray über dem Text ${\displaystyle T}$. Außerdem bezeichne ${\displaystyle T^{i}}$ das Suffix ${\displaystyle t_{i},t_{i+1},...,t_{n}}$ und ${\displaystyle lcp(s,t)}$ die Länge des längsten gemeinsamen Präfixes der beiden Strings ${\displaystyle s}$ und ${\displaystyle t}$.

Das LCP-Array ${\displaystyle H}$ ist ein Array der Größe ${\displaystyle n}$, wobei die einzelnen Felder wie folgt definiert sind:

${\displaystyle H[i]={\begin{cases}{\text{undefiniert}},&{\text{für }}i=1\\lcp(T^{A[i-1]},T^{A[i]}),&{\text{für }}2\leq i\leq n\end{cases}}}$

Das Suffixarray ${\displaystyle A}$ enthält eine lexikographische Sortierung aller Suffixe von ${\displaystyle T}$. Etwas informeller ausgedrückt bezieht sich ein Eintrag das LCP-Array immer auf zwei lexikographisch aufeinanderfolgende Suffixe von ${\displaystyle T}$ und beschreibt die Länge des längsten gemeinsamen Präfixes der betrachteten Suffixe. Der Wert von ${\displaystyle H[1]}$ ist undefiniert, weil ${\displaystyle T^{A[1]}}$ bereits das lexikographisch kleinste Suffix von ${\displaystyle T}$ ist und keinen Vorgänger besitzt.

Beispiel

Betrachte den Text ${\displaystyle T={\text{mississippi}}\$}$.

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 ${\displaystyle T}$ 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 ${\displaystyle T}$ 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 ${\displaystyle H}$ 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 ${\displaystyle H[10]}$ die bei ${\displaystyle A[10]}$ und ${\displaystyle A[9]}$ beginnenden Suffixe miteinander verglichen: Das längste gemeinsame Präfix von ${\displaystyle T^{A[10]}=T^{4}={\text{sissippi}}\$}$ und ${\displaystyle T^{A[9]}=T^{7}={\text{sippi}}\$}$ ist ${\displaystyle {\text{si}}}$ und hat damit eine Länge von 2. Dementsprechend ist ${\displaystyle H[10]=2}$. Die restlichen Werte des LCP-Arrays können auf die gleiche Weise berechnet werden. Der Wert von ${\displaystyle H[1]}$ bleibt dabei undefiniert, da es kein Suffix gibt, das lexikographisch vor ${\displaystyle T^{A[1]}=T^{12}=\$}$ liegt. Das LCP-Array für den Text ${\displaystyle T}$ sieht wie folgt aus:

i	1	2	3	4	5	6	7	8	9	10	11	12
H[i]	${\displaystyle \bot }$	0	1	1	4	0	0	1	0	2	1	3

Berechnung

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 ${\displaystyle O(n^{2})}$. Enthält ein Text beispielsweise ${\displaystyle n}$ gleiche Zeichen, so müssten insgesamt ${\displaystyle 1+2+3+...+(n-1)=O(n^{2})}$ Vergleiche getätigt werden.

Ein effizienterer Ansatz basiert auf der Grundidee, die LCP-Einträge in Textreihenfolge zu berechnen. Angenommen ${\displaystyle i}$ und ${\displaystyle j}$ sind aufeinanderfolgende Werte im Suffixarray und ${\displaystyle T^{i}}$ und ${\displaystyle T^{j}}$ haben ein gemeinsames Präfix von ${\displaystyle h}$ Zeichen. Die Suffixe ${\displaystyle T^{i+1}}$ und ${\displaystyle T^{j+1}}$ besitzen dann ${\displaystyle h-1}$ gemeinsame Zeichen. Allerdings müssen ${\displaystyle i+1}$ und ${\displaystyle j+1}$ im Suffixarray nicht nebeneinander stehen; es kann durchaus Suffixe geben, die lexikographisch zwischen ${\displaystyle T^{i+1}}$ und ${\displaystyle T^{j+1}}$ liegen. Angenommen ${\displaystyle k}$ sei der Wert, der vor dem Wert ${\displaystyle i+1}$ im Suffixarray steht. Dann müssen ${\displaystyle T^{i+1}}$ und ${\displaystyle T^{k}}$ wegen der lexikographischen Sortierung der Suffixe mindestens ${\displaystyle h-1}$ gemeinsame Zeichen haben (denn ${\displaystyle k}$ liegt im Suffixarray zwischen ${\displaystyle i+1}$ und ${\displaystyle j+1}$), das heißt, es würde reichen die beiden Suffixe ab dem ${\displaystyle h}$-ten Zeichen miteinander zu vergleichen.

Für diesen Ansatz wird das inverse Suffixarray ${\displaystyle A^{-1}}$ benötigt, um herauszufinden, an welcher Stelle ein bestimmter Wert in ${\displaystyle A}$ vorkommt. Bei ${\displaystyle A^{-1}}$ handelt es sich um die inverse Permutation von ${\displaystyle A}$, das heißt ${\displaystyle A^{-1}[i]}$ gibt an, an welcher Stelle im Suffixarray ${\displaystyle A}$ der Wert ${\displaystyle i}$ steht.

Es ergibt s​ich 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 ${\displaystyle h}$ maximal den Wert ${\displaystyle n}$ annehmen kann. Da ${\displaystyle h}$ in jedem Schritt nur um 1 dekrementiert wird, wird die innere While-Schleife höchstens ${\displaystyle O(n)}$ mal ausgeführt. Es ergibt sich somit eine Gesamtlaufzeit von ${\displaystyle O(n)}$.

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 ${\displaystyle 4n}$ Cache-Misses verursacht (nämlich in den Zeilen 3, 9, 10 und 12), kommt der φ-Algorithmus mit nur ${\displaystyle 3n}$ Cache-Misses aus.

Die o​ben genannten Algorithmen benutzen für d​ie Berechnung d​es LCP-Arrays e​in bereits vorhandenes Suffixarray. Es g​ibt Algorithmen, d​ie das LCP-Array gleichzeitig m​it dem Suffix-Array berechnen. Der z​ur Zeit schnellste Linearzeit-Algorithmus stammt v​on Fischer (2011).[5]

Gog & Ohlebusch (2011)[6] h​aben zwei Algorithmen veröffentlicht, d​ie im Worst-Case e​ine quadratische Laufzeit haben, a​ber in d​er Praxis schneller sind, a​ls die o​ben erwähnten Linearzeit-Algorithmen.

Beschleunigung der Textsuche mit Hilfe des LCP-Arrays

Mit dem Suffixarray kann das Vorkommen eines Musters ${\displaystyle P}$ der Länge ${\displaystyle m}$ in einem Text ${\displaystyle T}$ der Länge ${\displaystyle n}$ mit Hilfe von binärer Suche bestimmt werden. Da die Suffixe im Suffixarray lexikographisch sortiert sind, genügen ${\displaystyle O(\log {n})}$ Vergleiche, um das lexikographisch kleinste (bzw. größte) Suffix zu finden, welches ${\displaystyle P}$ enthält. Für jeden Vergleich müssen dabei bis zu ${\displaystyle m}$ Zeichen verglichen werden, wodurch dieses Verfahren eine Laufzeit von ${\displaystyle O(m\log {n})}$ besitzt.

Mit Hilfe des LCP-Arrays lässt sich die Laufzeit auf ${\displaystyle O(m+\log {n})}$ verbessern, indem verhindert wird, dass bei jedem Schritt der binären Suche das Muster ${\displaystyle P}$ erneut von Beginn an gelesen werden muss.

Bei jedem Schritt der binären Suche liegt eine linke Intervallgrenze ${\displaystyle l}$, eine rechte Intervallgrenze ${\displaystyle r}$ und ein mittleres Element ${\displaystyle m}$ vor. Dabei wird ${\displaystyle P}$ mit dem lexikographisch ${\displaystyle A[m]}$-ten Suffix (also mit ${\displaystyle T^{A[m]}}$) 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 ${\displaystyle P}$ lexikographisch kleiner als ${\displaystyle T^{A[m]}}$ ist – der andere Fall ist analog. Sei ${\displaystyle k=lcp(P,T^{A[m]})}$ die Länge des längsten gemeinsamen Präfixes der beiden Strings. Das heißt, dass das ${\displaystyle k+1}$-te Zeichen von ${\displaystyle P}$ lexikographisch kleiner als das von ${\displaystyle T^{A[m]}}$ ist.

Das neue Intervall besitzt die Grenzen ${\displaystyle l}$ und ${\displaystyle m}$ und das mittlere Element ${\displaystyle m'}$. Sei ${\displaystyle k'=lcp(T^{A[m]},T^{A[m']})}$ die Länge des längsten gemeinsamen Präfixes zwischen dem alten und dem neuen mittleren Element. Es folgt eine Fallunterscheidung:

• ${\displaystyle k<k'}$: Das ${\displaystyle k+1}$-te Zeichen der Suffixe ${\displaystyle T^{A[m]}}$ und ${\displaystyle T^{A[m']}}$ ist gleich. Daher muss ${\displaystyle P}$ auch lexikographisch kleiner als ${\displaystyle T^{A[m']}}$ sein und die binäre Suche kann ohne weitere Vergleiche in der linken Intervallhälfte fortgesetzt werden.
• ${\displaystyle k>k'}$: Wegen ${\displaystyle m'<m}$ ist das Suffix ${\displaystyle T^{A[m']}}$ lexikographisch kleiner als das Suffix ${\displaystyle T^{A[m]}}$. Das bedeutet, dass das ${\displaystyle k'+1}$-te Zeichen von Suffix ${\displaystyle T^{A[m']}}$ kleiner als das ${\displaystyle k'+1}$-te Zeichen von Suffix ${\displaystyle T^{A[m]}}$ sein muss. Da ${\displaystyle T^{A[m]}}$ und ${\displaystyle P}$ ein gemeinsames Präfix von mindestens ${\displaystyle k'+1}$ Zeichen haben, folgt hier, dass ${\displaystyle T^{A[m']}}$ lexikographisch kleiner ist als P und die binäre Suche wird in der rechten Hälfte fortgesetzt.
• ${\displaystyle k=k'}$: ${\displaystyle P}$ und ${\displaystyle T^{A[m']}}$ haben ein gemeinsames Präfix von mindestens ${\displaystyle k}$ Zeichen. Hier müssen beide Strings verglichen werden, wobei der Vergleich erst beim ${\displaystyle k+1}$-ten Zeichen beginnen muss.

Durch das beschriebene Verfahren ist es bei der binären Suche niemals notwendig bereits gelesene Zeichen von ${\displaystyle P}$ nochmals zu lesen. Das Verfahren stammt von Manber und Myers[1]. Da sich im LCP-Array nur die ${\displaystyle lcp}$-Werte für lexikographisch aufeinanderfolgende Suffixe befinden, wird im Folgenden noch gezeigt, wie sich beliebige ${\displaystyle lcp}$-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 ${\displaystyle T^{A[i]},T^{A[j]}}$, betrachtet man alle Suffixe, die lexikographisch dazwischen liegen: Falls zwei aufeinanderfolgende Suffixe ein längestes gemeinsames Präfix der Länge ${\displaystyle k}$ besitzen, so können ${\displaystyle T^{A[i]}}$ und ${\displaystyle T^{A[j]}}$ wegen der lexikographischen Sortierung kein längeres gemeinsames Präfix haben. Der Wert ${\displaystyle lcp(T^{A[i]},T^{A[j]})}$ entspricht daher genau dem Minimum über den LCP-Einträgen ${\displaystyle H[i+1],...,H[j]}$. Dieses Minimum lässt sich mit geeigneten Verfahren für Range Minimum Queries in konstanter Zeit finden.[8]

Literatur

• Enno Ohlebusch Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, 2013, Kapitel 4.

Einzelnachweise

1. Udi Manber, Gene Myers: Suffix Arrays: A New Method for On-Line String Searches. In: SIAM Journal on Computing. 22, Nr. 5, 1993, S. 935. doi:10.1137/0222058.
2. Kasai, T. et al.: Linear-Time Longest-Common-Prefix Computation in Suffix. In: Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, 2001.
3. Manzini, Giovanni: Two Space Saving Tricks for Linear Time LCP Array Computation. In: Lecture Notes in Computer Science, Volume 3111, Seite 372, 2004.
4. 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.
5. Fischer, Johannes: Inducing the LCP-Array. In: Lecture Notes in Computer Science, Volume 6844, Seite 374–385, 2011.
6. 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.
7. 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.
8. 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.