LCP-Array – einfach erklärt

Grundidee und Definition

Das LCP-Array ist eine Datenstruktur der Informatik, die meist zusammen mit einem Suffixarray verwendet wird. „LCP“ steht für „longest common prefix“, also „längstes gemeinsames Präfix“. Ein Präfix ist ein zusammenhängender Anfang eines Strings. Das LCP-Array speichert für jeweils zwei lexikographisch aufeinanderfolgende Suffixe eines Textes die Länge ihres längsten gemeinsamen Präfixes.

Sei T = t₁, t₂, …, tₙ ein Text der Länge n und A das Suffixarray von T. Das Suffix Tⁱ ist definiert als tᵢ, tᵢ₊₁, …, tₙ. Mit lcp(s,t) wird die Länge des längsten gemeinsamen Präfixes zweier Strings s und t bezeichnet. Das LCP-Array H hat die Größe n und ist definiert durch:

H[i] = undefiniert für i = 1, H[i] = lcp(Tᴬ⁽ⁱ⁻¹⁾, Tᴬ⁽ⁱ⁾) für 2 ≤ i ≤ n.

Das Suffixarray A enthält alle Suffixe von T in lexikographischer Reihenfolge. Daher bezieht sich H[i] immer auf das Suffix an der Stelle A[i] und dessen Vorgänger an der Stelle A[i−1]. H[1] ist undefiniert, weil das lexikographisch kleinste Suffix keinen Vorgänger besitzt.

Das LCP-Array benötigt im Verhältnis zur Textgröße linearen Speicherplatz. Es wird unter anderem zur Konstruktion von Suffixbäumen und zur effizienten Suche aller Vorkommen eines Musters in einem Text eingesetzt.

Beispiel mit „mississippi“

Betrachtet wird der Text T = „mississippi“$. Das zusätzliche Zeichen $ markiert das Textende; der Text hat damit die Länge 12. Die Zeichen an den Positionen 1 bis 12 sind:

m, i, s, s, i, s, s, i, p, p, i, $.

Das Suffixarray speichert die Anfangspositionen der Suffixe in lexikographischer Reihenfolge. Für diesen Text lautet es:

A = (12, 11, 8, 5, 2, 1, 10, 9, 7, 4, 6, 3).

Das erste Suffix ist also T¹² = „$“, das zweite T¹¹ = „i$“, danach folgen unter anderem T⁸ = „ippi$“, T⁵ = „issippi$“ und T² = „ississippi$“.

Das LCP-Array vergleicht jeweils benachbarte Suffixe in dieser Sortierung. Für H[10] werden beispielsweise die Suffixe an den Positionen A[10] = 4 und A[9] = 7 verglichen: T⁴ = „sissippi$“ und T⁷ = „sippi$“. Ihr längstes gemeinsames Präfix ist „si“ und hat die Länge 2. Deshalb gilt H[10] = 2.

Das vollständige LCP-Array lautet:

H = (⊥, 0, 1, 1, 4, 0, 0, 1, 0, 2, 1, 3).

Der Wert ⊥ an der ersten Stelle steht für „undefiniert“. Die übrigen Werte geben jeweils die Länge des gemeinsamen Anfangs der beiden benachbarten Suffixe an.

Berechnung in linearer Zeit

Eine direkte Berechnung vergleicht jedes Paar lexikographisch aufeinanderfolgender Suffixe Zeichen für Zeichen. Im ungünstigsten Fall benötigt dieses Verfahren O(n²) Zeit. Enthält ein Text beispielsweise n gleiche Zeichen, entstehen insgesamt 1 + 2 + 3 + … + (n−1) = O(n²) Vergleiche.

Der effizientere Ansatz berechnet die LCP-Werte in Textreihenfolge. Haben die Suffixe Tⁱ und Tʲ ein gemeinsames Präfix der Länge h, dann haben Tⁱ⁺¹ und Tʲ⁺¹ mindestens h−1 gemeinsame Zeichen. Diese beiden verschobenen Suffixe müssen im Suffixarray nicht benachbart sein. Wegen der lexikographischen Ordnung gilt jedoch: Steht ein Suffix Tᵏ zwischen ihnen, besitzt Tⁱ⁺¹ mit Tᵏ ebenfalls mindestens h−1 gemeinsame Zeichen. Deshalb müssen beim nächsten Vergleich höchstens die Zeichen ab Position h neu geprüft werden.

Dafür wird das inverse Suffixarray A⁻¹ benötigt. Es ist die inverse Permutation von A; A⁻¹[i] gibt an, an welcher Stelle i im Suffixarray A steht. Der Algorithmus von Kasai et al. (2001) arbeitet im Wesentlichen so:

Zuerst wird für jede Position i der Rang A⁻¹[i] im Suffixarray bestimmt.
H[1] wird auf 0 gesetzt und eine Variable h mit 0 initialisiert.
Für jede Textposition i wird geprüft, ob das zugehörige Suffix im Suffixarray einen Vorgänger besitzt.
Der Vorgänger ist j = A[A⁻¹[i] − 1]. Die beiden Suffixe Tⁱ und Tʲ werden ab dem bereits bekannten gemeinsamen Präfix verglichen.
Solange T[i+h] = T[j+h] gilt, wird h um 1 erhöht. Danach wird H[A⁻¹[i]] = h gespeichert und h auf max(0, h−1) gesetzt.

Die Laufzeit ist O(n). Die Variable h kann insgesamt höchstens bis n anwachsen und wird zwischen zwei Schritten nur um 1 verringert; deshalb wird die innere While-Schleife insgesamt höchstens O(n)-mal ausgeführt.

Manzini (2004) entwickelte eine verbesserte Version, die neben Text, Suffixarray und LCP-Array keinen zusätzlichen Speicher benötigt. Der φ-Algorithmus von Kärkkäinen, Manzini und Puglisi reduziert die Zahl der Cache-Misses bei langen Texten von bis zu 4n auf 3n. Es gibt außerdem Verfahren, die LCP-Array und Suffixarray gleichzeitig berechnen; der zur Zeit der Darstellung schnellste Linearzeit-Algorithmus stammt von Fischer (2011). Die Algorithmen von Gog und Ohlebusch (2011) haben im Worst Case zwar quadratische Laufzeit, sind in der Praxis aber schneller als die genannten Linearzeit-Verfahren.

Beschleunigte Mustersuche

Mit einem Suffixarray kann ein Suchmuster P der Länge m in einem Text T der Länge n durch binäre Suche gefunden werden. Weil die Suffixe lexikographisch sortiert sind, reichen O(log n) Vergleiche, um das lexikographisch kleinste beziehungsweise größte Suffix zu bestimmen, das P enthält. Werden bei jedem Vergleich bis zu m Zeichen geprüft, beträgt die Laufzeit O(m log n).

Das LCP-Array verbessert diese Laufzeit auf O(m + log n). Bereits gelesene Zeichen des Musters P müssen bei der binären Suche nicht erneut vom Anfang an verglichen werden. Sei k = lcp(P, Tᴬ⁽ᵐ⁾) die Länge des gemeinsamen Präfixes von P und dem Suffix in der Mitte des aktuellen Intervalls. Ist P lexikographisch kleiner als dieses Suffix, wird im linken Teilintervall weitergesucht; der andere Fall ist analog.

Für das neue mittlere Element m′ sei k′ = lcp(Tᴬ⁽ᵐ⁾, Tᴬ⁽ᵐ′⁾). Dann gelten drei Fälle:

Ist k < k′, stimmen die Suffixe auch an der für P entscheidenden Stelle k+1 überein. P ist daher ebenfalls kleiner als das neue mittlere Suffix; die Suche kann ohne weitere Vergleiche in der linken Hälfte fortgesetzt werden.
Ist k > k′, ist das neue mittlere Suffix wegen m′ < m an der Stelle k′+1 kleiner als das bisherige mittlere Suffix. Da P mit dem bisherigen Suffix mindestens k′+1 Zeichen gemeinsam hat, ist das neue Suffix kleiner als P. Die Suche wird in der rechten Hälfte fortgesetzt.
Ist k = k′, müssen P und das neue mittlere Suffix verglichen werden. Der Vergleich beginnt erst beim Zeichen k+1.

Allgemeine LCP-Werte zweier Suffixe lassen sich durch eine Range Minimum Query über dem LCP-Array bestimmen. Für Tᴬ⁽ⁱ⁾ und Tᴬ⁽ʲ⁾ mit i < j betrachtet man die Einträge H[i+1], …, H[j]. Es gilt:

lcp(Tᴬ⁽ⁱ⁾, Tᴬ⁽ʲ⁾) = min(H[i+1], …, H[j]).

Der Grund ist, dass zwei Suffixe kein längeres gemeinsames Präfix besitzen können als ein Paar aufeinanderfolgender Suffixe zwischen ihnen. Mit geeigneten Verfahren für Range Minimum Queries kann dieses Minimum in konstanter Zeit berechnet werden.