LCP-Array

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 „Vorlage:Lang“ (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) benutzt, in der es als Hgt-Array bezeichnet wurde.

Definition

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

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

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

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

Beispiel

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

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

i	1	2	3	4	5	6	7	8	9	10	11	12
H[i]	$\mathrm{\perp }$	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 $O(n^2)$. Enthält ein Text beispielsweise $n$ gleiche Zeichen, so müssten insgesamt $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 $i$ und $j$ sind aufeinanderfolgende Werte im Suffixarray und $T^i$ und $T^j$ haben ein gemeinsames Präfix von $h$ Zeichen. Die Suffixe $T^{i+1}$ und $T^{j+1}$ besitzen dann $h-1$ gemeinsame Zeichen. Allerdings müssen $i+1$ und $j+1$ im Suffixarray nicht nebeneinander stehen; es kann durchaus Suffixe geben, die lexikographisch zwischen $T^{i+1}$ und $T^{j+1}$ liegen. Angenommen $k$ sei der Wert, der vor dem Wert $i+1$ im Suffixarray steht. Dann müssen $T^{i+1}$ und $T^k$ wegen der lexikographischen Sortierung der Suffixe mindestens $h-1$ gemeinsame Zeichen haben (denn $k$ liegt im Suffixarray zwischen $i+1$ und $j+1$), das heißt, es würde reichen die beiden Suffixe ab dem $h$-ten Zeichen miteinander zu vergleichen.

Für diesen Ansatz wird das inverse Suffixarray $A^{-1}$ benötigt, um herauszufinden, an welcher Stelle ein bestimmter Wert in $A$ vorkommt. Bei $A^{-1}$ handelt es sich um die inverse Permutation von $A$, das heißt $A^{-1}[i]$ gibt an, an welcher Stelle im Suffixarray $A$ der Wert $i$ 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 $h$ maximal den Wert $n$ annehmen kann. Da $h$ in jedem Schritt nur um 1 dekrementiert wird, wird die innere While-Schleife höchstens $O(n)$ mal ausgeführt. Es ergibt sich somit eine Gesamtlaufzeit von $O(n)$.

Der oben vorgestellte Ansatz stammt von Kasai et al. (2001) und ist der erste veröffentlichte Algorithmus, der das LCP-Array in linearer Zeit berechnet. Manzini (2004) 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: Während der ursprüngliche Algorithmus durch nicht sequentielle Zugriffe auf die Arrays für entsprechend lange Texte bis zu $4n$ Cache-Misses verursacht (nämlich in den Zeilen 3, 9, 10 und 12), kommt der φ-Algorithmus mit nur $3n$ 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).

Gog & Ohlebusch (2011) 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

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

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

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

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

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

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

Literatur

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