LZ77

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel behandelt den Datenkompressionsalgorithmus, weitere Bedeutungen unter LZ77 (Begriffsklärung)

LZ77 (Lempel-Ziv 77) [1] ist ein verlustloses Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Es ist ein wörterbuchbasiertes Verfahren, das sich erstmals zunutze macht, dass ganze Sequenzen von Daten mehrfach in einem Datensatz vorkommen. In früher entwickelten Verfahren (z.B. Huffman-Kodierung bzw. Shannon-Fano-Kodierung) wurde ausschließlich die Häufigkeit einzelner Zeichen ausgenutzt (siehe auch Entropiekodierung).

Definition[Bearbeiten]

Die LZ77-Faktorisierung einer Zeichenkette x ist eine Zerlegung in nicht-leere Zeichenketten w_1, w_2, \ldots, w_k, sodass[2]

  • x = w_1 w_2 \cdots w_k und
  • für jedes w_j mit 1 \leq j \leq k gilt:
    • w_j ist ein neuer Buchstabe \alpha, der nicht in w_1 \cdots w_{j-1} auftaucht oder
    • w_j ist die längste Zeichenkette, die mindestens zweimal in w_1 \cdots w_j auftaucht.

Die einzelnen Zeichenketten w_j werden als Faktoren oder Phrasen bezeichnet.

Aus der Definition ist direkt ableitbar, dass w_1 = x[1] ist. Dabei bezeichnet x[i \dots j] die Zeichenkette x, die von der Position i an alle Zeichen aus x bis einschließlich zur Position j enthält. x[i] ist die abkürzende Schreibweise für die Zeichenkette x[i \dots i].

Algorithmus[Bearbeiten]

Die Idee des Algorithmus zur Berechnung der LZ77-Kompression besteht darin, den bereits verarbeiteten Präfix der Zeichenkette als Wörterbuch zu verwenden. Aus implementierungstechnischen Gründen ist die Größe dieses Wörterbuchs in der Praxis beschränkt, um die Dauer der Suche zu beschränken. Es wird deshalb in der Regel ein gleitendes Fenster (engl. sliding window) verwendet, welches sowohl das Wörterbuch als auch den zu betrachtenden Textausschnitt (Vorschaupuffer) begrenzt. Komprimierte Zeichen werden so nach und nach vom Vorschaupuffer in das Wörterbuch verschoben. In der Praxis enthält der Puffer für das Wörterbuch mehrere tausend Zeichen und der Vorschaupuffer für den zu codierenden Ausschnitt der Zeichenkette in etwa 100 Zeichen (teilweise auch weniger).

Der Algorithmus erzeugt als Ausgabe eine Sequenz von Tripeln, mit denen der ursprüngliche Text zurückgewonnen werden kann. Ein Tripel für einen Faktor w_j hat die Form (pos, len, \lambda), wobei

  • pos die Position des vorherigen Vorkommens von w_j in x angibt (bzw. 0, falls kein vorheriges Vorkommen in x existiert),
  • len die nicht-negative Länge des vorherigen Vorkommens von w_j ist (bzw. 0, falls w_j ein neues Zeichen ist)
  • und \lambda der Missmatch-Buchstabe ist, d. h. für j <= k ist \lambda = x[|w_1w_2 \cdots w_{j-1}| + len + 1].

Dabei ist zu beachten, dass bei Verwendung eines Puffers für das Wörterbuch die Position pos einer Zeichenkette relativ zum linken oder rechten Rand des Puffers zu verstehen ist (dies kann je nach Implementierung variieren), neue Zeichen müssen dann mit (0,0, \lambda) eingeführt werden. Durch das Ausgabeformat der Kompression ist die Rekonstruktion des Textes ohne explizites Abspeichern des Wörterbuches möglich.

Pseudocode[Bearbeiten]

Der Pseudocode ist eine Wiedergabe des LZ77-Kompressionsalgorithmus mit gleitendem Fenster.

 while der Vorschaupuffer nicht leer ist do
   durchsuche rückwärts den Wörterbuchpuffer nach der längsten 
      übereinstimmenden Zeichenkette mit dem Vorschaupuffer;
   if eine Übereinstimmung wurde gefunden then
     gib das Tripel (Versatz zum Rand des Wörterbuchpuffers, Länge der gefundenen 
        Zeichenkette, erstes nicht übereinstimmendes Zeichen aus dem Vorschaupuffer) aus;
     verschiebe das Fenster um die Länge+1;
   else
    gib das Tripel (0, 0, erstes Zeichen im Vorschaupuffer) aus;
    verschiebe das Fenster um 1;
   end if
end while

Beispiel[Bearbeiten]

Die Berechnung der LZ77-Faktorisierung wird anhand der Zeichenkette aacaacabcabaaac veranschaulicht.

Die Tabelle zeigt die Berechnung der LZ77-Faktorisierung unter Verwendung eines Wörterbuchpuffers der Größe 12 und einem Vorschaupuffer der Größe 9. In der Spalte ganz rechts findet sich von oben nach unten gelesen die Ausgabe des Algorithmus (0,0,"a") (1,1,"c") (3,4,"b") (3,3,"a") (12,3,"$"). Die Position ist relativ zum rechten Rand des Wörterbuchpuffers angegeben, dies muss bei der Decodierung beachtet werden.

Die Puffer funktionieren nach dem Prinzip des gleitenden Fensters (engl.: sliding window), d. h. der zu komprimierende Datenstrom wird von rechts in die Puffer hineingeschoben. Wie im Algorithmus vermerkt, erfolgt die Verschiebung um die Länge der gefundenen Übereinstimmung im Wörterbuch und eine weitere Position. Dies führt dazu, dass redundante Tripel vermieden werden, da neue Zeichen sonst immer einzeln in das Wörterbuch übernommen werden. Im Beispiel müsste so das dritte Tripel (0,0, "c") mit aufgenommen werden, was die Kompressionsrate allerdings deutlich verschlechtert. Dabei sind die Übereinstimmungen grün und die zu verschiebende Zeichenkette in rot gekennzeichnet. Dabei gilt zu beachten, dass immer ein Zeichen mehr verschoben wird, als in der Übereinstimmung gefunden wurde, um neue Zeichen nicht doppelt codieren zu müssen.

Beispiel für eine LZ77-Kompression mit gleitendem Fenster
Zeile 12 11 10  9  8  7  6  5  4  3  2  1  0  1  2  3  4  5  6  7  8  9 Ausgabe
1 (leer) a a c a a c a b c a \Longrightarrow (0,0,"a")
2 (leer) a a c a a c a b c a b \Longrightarrow (1,1,"c")
3 (leer) a a c a a c a b c a b a a \Longrightarrow (3,4,"b")
4 (leer) a a c a a c a b c a b a a a c (leer) \Longrightarrow (3,3,"a")
5 a a c a a c a b c a b a a a c (leer) \Longrightarrow (12,3,"$")
fertig

Das erste gesehene Zeichen ist unbekannt, sodass das das erste "a" mit (0,0,"a") aufgenommen wird. In der 2. Zeile kann das "a" bereits aus dem Wörterbuchpuffer gelesen werden (grün markiert), sodass "c" als neues Zeichen übernommen wird. In der 3. Zeile ist ein Sonderfall des LZ77-Algorithmus zu sehen, da die übereinstimmende Zeichenkette bis in das Vorschaufenster hineinragt, dies im Beispiel durch grünen Text auf rotem Grund dargestellt. Zeile 4. und 5. sind äquivalent zu den ersten beiden zu behandeln, mit der Ausnahmen, dass im letzten Tripel ein $ als nächstes Zeichen eingeführt wird, da der Text vollständig komprimiert wurde und es kein nächstes Zeichen gibt.

Laufzeitanalyse[Bearbeiten]

Die Laufzeit des Algorithmus wird mit \Theta(n) angegeben, da der Text bei der Kompression nur ein Mal durchlaufen wird. Dies ist möglich, wenn der Vorschau- und Wörterbuchpuffer eine konstante Größe hat und die Suche nach einer übereinstimmenden Zeichenkette bei großen Texten nicht ins Gewicht fällt. In der praktischen Anwendung ist die Implementierung mit einer normalen Suche (ohne zusätzliche Datenstrukturen) eher langsam.

Vor- und Nachteile[Bearbeiten]

Ein großer Vorteil des LZ77 ist, dass er ohne jegliche Kenntnis des Textes komprimieren kann und des Weiteren nicht mit einem Patent belegt ist. Der LZ78 (ein Nachfolger des LZ77) benötigt für die Rekonstruktion des Textes das ursprüngliche Wörterbuch und war bis ins Jahr 2004 teilweise durch Patente geschützt. Ein großer Nachteil ist jedoch, dass er bei kleinen oder nicht natürlichsprachlichen Texten ohne Erweiterungen eine Vergrößerung der gespeicherten Bytes bewirken kann (Speichergröße des Originaltextes im Vergleich zum Speicherverbrauch des komprimierten Textes). Dies wird im angegebenen Beispiel deutlich, da der originale Text 16 Zeichen beinhaltet und die Komprimierung 15 Zeichen benötigt, was nur ein Zeichen Ersparnis bedeutet. Wenn die Kodierung jedoch mittels eines anderen Kompressionsverfahren wie z. B. der Huffman-Kodierung kombiniert wird, lassen sich noch weitere Einsparungen erzielen.

Dekompression[Bearbeiten]

Die Dekompression von LZ77 komprimierten Dateien ist deutlich einfacher als die Kompression, da keine Suche nach übereinstimmenden Zeichenketten stattfinden muss. Die Laufzeit ist linear, und hat genau so viele Schritte wie der Originaltext lang ist, also \Theta(n).

Pseudocode[Bearbeiten]

Der Pseudocode ist eine Wiedergabe des LZ77 Dekompressionsalgorithmus mit gleitendem Fenster.

 for jedes Tripel (offset, length, symbol) 
  if offset = 0 then
    gib symbol aus;
  else
    durchlaufe Rückwärts die bisherige Ausgabe und gib solange 
       Zeichen aus bis eine Länge von length erreicht ist, bei 
       einem Überlauf beginne erneut bei offset;
    gib symbol aus;
 end if
end for

Beispiel[Bearbeiten]

Die Dekompression von LZ77-Codierungen benötigt kein zusätzliches Wörterbuch, die ausgegebenen Tripel sind eindeutig um den Text zu rekonstruieren. Die rot hinterlegten Zellen, sind Zellen die für die Rekonstruktion in der darauffolgenden Zeile verwendet werden.

Beispiel für eine LZ77-Dekompression mit gleitendem Fenster
Zeile Eingabe 12 11 10  9  8  7  6  5  4  3  2  1
1 (0,0,"a") a
2 (1,1,"c") a a c
3 (3,4,"b") a a c a a c a b
4 (3,3,"a") a a c a a c a b c a b a
5 (12,3,"$") aac a a c a b c a b a a a c
fertig

Ist der 1. Eintrag des Tripels 0, wird der letzte Eintrag im Tripel einfach an den Text angehängt (siehe Zeile 1). In der 2. Zeile mit der Eingabe (1,1,"c"), wird bereits der erste Eintrag des rekonstruierten Textes aus der ersten Zeile (erste Stelle im Tripel für Position 1 und die zweite Stelle im Tripel für die Länge 1) wieder verwendet und anschließend das Zeichen c hinten angehängt. In der 3. Zeile ist die Länge der wieder verwendeten Zeichenkette länger als der Speicher im Wörterbuch (Länge 4, aber ab Speicherzelle 3 sind nur 3 Zellen verfügbar), es wird deshalb wieder bei der Startposition (Speicherzelle 3) mit der Ausgabe fortgefahren und ein zusätzliches a ausgegeben. Anschließend wird das b als letzter Eintrag des zu verarbeitenden Tripels angehängt. Die Zeilen 4 und 5 sind analog zu verstehen. Das $ Zeichen wird bei Rekonstruktion ignoriert, da es global als Ende des Textes zu verstehen ist. Der vollständig rekonstruierte Text lautet aacaacabcabaaac.

Effiziente Konstruktion[Bearbeiten]

Für eine Laufzeit-effizientere Berechnung der LZ77-Faktorisierung einer Zeichenkette wird im Folgenden die Faktorisierung auf der kompletten Zeichenkette berechnet und das Prinzip des gleitenden Fensters aufgegeben. Schließlich wird in mehreren Anwendungen (siehe Abschnitt Verwendung) auch die LZ77-Kompression auf der gesamten Zeichenkette verwendet.

Eine bezüglich der Laufzeit effiziente Berechnung der LZ77-Faktorisierung für eine Zeichenkette ist mit Hilfe von zusätzlichen Datenstrukturen möglich. Für eine Zeichenkette x bezeichne SA das Suffixarray und ISA das inverse Suffixarray von x, d. h. es ist ISA[i] = j genau dann, wenn SA[j] = i. Zudem bezeichne lcp(i, j) die Länge des längsten gemeinsamen Präfixes der Zeichenketten x[SA[i]..n] und x[SA[j]..n], wobei n = |x| ist.

Die Berechnung nutzt aus, dass für einen Faktor w_j von x mit |w_j| > 1 für die Bestimmung der Position pos des Tupels nur die Textpositionen SA[NSV[ISA[j]]] und SA[PSV[ISA[j]]] betrachtet werden müssen. Dabei ist NSV[j] = min\{i \in \{j+1, \ldots, n\} \, | \, SA[i] < SA[j] \} (NSV steht für next smaller value) und PSV[j] = max\{i \in \{j+1, \ldots, n\} \, | \, SA[i] < SA[j] \} (PSV steht für previous smaller value)[3].

Pseudocode[Bearbeiten]

Der Algorithmus LZ_Factor(i, psv, nsv) liefert als Rückgabe die Startposition des nächstens Faktors

 Algorithmus LZ_Factor(i, psv, nsv):
   if lcp(i, psv) > lcp(i, nsv) then
     (pos, len) <- (psv, lcp(i, psv))
   else
     (pos, len) <- (nsv, lcp(i, nsv))
   if (len = 0) { pos <- i }
   if i + len > n then
     print factor(pos, len, '$')
   else
     print factor(pos, len, x[i+len])
   return i + max(len, 1)

Die beiden Arrays NSV und PSV können aus dem Suffixarray SA in Linearzeit berechnet werden:

 for i <- i to n+1 do
   j <- i - 1
   while SA[i] < SA[j] do
     NSV[j] <- i
     j <- PSV[j]
   PSV[i] <- j

Abschließend folgt der Algorithmus zur Berechnung der LZ77-Faktorisierung für die Zeichenkette x

 Berechne SA, ISA, NSV und PSV für x
 k <- 1
 while k <= n do
   psv <- SA[PSV[ISA[k]]]
   nsv <- SA[NSV[ISA[k]]]
   k <- LZ_Factor(k, psv, nsv)

Laufzeitanalyse[Bearbeiten]

Die Berechnung der LZ77-Faktorisierung eines Strings ist mit dem Algorithmus in \mathcal{O}(n) Zeit möglich, wobei n = |x| die Länge der Eingabezeichenkette x ist. Die Methode LZ_Factor benötigt \mathcal{O}(1) Zeit, wenn die Berechnung von lcp(i, j) über Range Miminum Queries realisiert wird. Die Berechnung der Arrays NSV und PSV ist in \mathcal{O}(n) Zeit möglich, sodass der gesamte Algorithmus zur Berechnung \mathcal{O}(n) Zeit benötigt (dies setzt eine Linearzeitkonstrukturion des Suffixarrrays voraus)[3].

Vergleich verschiedener Implementierungen[Bearbeiten]

Zur Berechnung der LZ77-Kompression einer Zeichenkette gibt es verschiedene Implementierungen, die sich in der Laufzeit und im Speicherbedarf unterscheiden. Für den Vergleich wird die LZ-Faktorisierung auf der kompletten Zeichenkette x mit der Länge |x| = n betrachtet. Die Analyse des Speicherbedarfs orientiert sich an der Speicherung in 32- oder 64-Bit-Worten. Dabei belege ein Buchstabe des Alphabets \Sigma ein Viertel eines Speicherwortes und ein Integer ein ganzes Speicherwort.[2]

In der folgenden Tabelle sind einige Implementierungen zur Berechnung der LZ77-Faktorisierung mit ihrer Laufzeit, ihrem Speicherbedarf und den verwendeten Datenstrukturen aufgelistet.

Algorithmus von Worst-Case-Laufzeit Speicherbedarf in Wörtern Verwendete Datenstrukturen Bemerkungen
Abouelhoda et al.[4] \Theta(n) 4.25n+ Suffixarray, LCP-Array -
Chen et al.[5][6] \Theta(n) 4.25n+ Suffixarray, LCP-Array -
Chen et al.[5][6] \Theta(n) 3.25n+ Suffixarray, LCP-Array Positions-Array überschreibt Suffix-Array
Chen et al.[5][6] \Theta(n) 3.25n Suffixarray, LCP-Array Positions-Array überschreibt Suffix-Array
Crochemore und Ilie[7] \Theta(n) 3.25n Suffixarray, LCP-Array, LPF-Array LZ77-Ausgabe erfordert keinen zusätzlichen Platz
Crochemore und Ilie[7] \Theta(n) 3n+ Suffixarray, LCP-Array, LPF-Array LZ77-Ausgabe erfordert keinen zusätzlichen Platz, kein Zugriff auf die Zeichenkette x für die LZ77-Kompression notwendig

Einige der in der Tabelle aufgeführten Algorithmen verwenden das LPF-Array (LPF steht für Longest Previous Factor). Das LPF-Array ist wie folgt definiert:[2] Für jede Position i der Zeichenkette x ist LPF[i] definiert als Länge des längsten Faktors von x, der an der Position i beginnt und vor der Position i in x auftaucht, d. h. LPF[i] = max(\{0\} \cup \{l \, | \, x[i \dots i+l-1] \text{ ist ein Faktor von } x[1 \dots i+l-2]\}). Aus dem LPF-Array kann die LZ77-Faktorisierung einer Zeichenkette in linearer Zeit berechnet werden. Das LPF-Array kann unter anderem mit den oben aufgeführten NSV und PSV-Arrays berechnet werden, denn es gilt[3]: LPF[i] = max(lcp(i, SA[NSV[ISA[i]]]), lcp(i, SA[PSV[ISA[i]]]))

Für die Implementierung einiger der in der Tabelle aufgeführten Algorithmen wird ein Stapelspeicher S verwendet, welcher zusätzlichen Speicher benötigt. In der Tabelle ist die Verwendung eines Stacks durch ein an den Speicherbedarf angehängtes + dargestellt. Die Größe des Stapelspeichers ist begrenzt durch |S| = n - dies ist der Fall, wenn die Zeichenkette die Form x = \alpha^n mit \alpha \in \Sigma aufweist. Erwartet ist |S| \in O(\log_{|\Sigma|}n).[2]

Verwendung[Bearbeiten]

Heute wird die LZ77-Kompression u. a. noch auf dem Game Boy Advance und weiteren eingebetteten Systemen verwendet. Mit der Huffman-Kodierung kombiniert, wird LZ77 in dem vielbenutzten Deflate-Algorithmus verwendet, welcher wiederum von sehr bekannten Komprimierungsprogrammen sowie dem Grafikformat PNG genutzt wird. Dass LZ77 mit keinerlei Patenten belegt ist, dürfte wohl der Grund sein, dass das Verfahren heute immer noch dem ein Jahr später veröffentlichten Nachfolger LZ78 vorgezogen wird, der bis ins Jahr 2004 mancherorts in Teilen patentiert war.

In der algorithmischen Verarbeitung von Zeichenketten wird die LZ77-Faktorisierung für die Berechnung von Regelmäßigkeiten in Strings eingesetzt. Dabei wird stets die Faktorisierung auf dem gesamten String betrachtet und nicht nur innerhalb des gleitenden Fensters. Zudem kann die Ausgabe vereinfacht werden, da der ursprüngliche String in den Anwendungen vorliegt und nicht rekonstruiert werden muss. Eine Auswahl von Problemstellungen, bei denen die LZ77-Faktorisierung verwendet werden kann, findet sich in der folgenden Auflistung:

  • Bestimmung von Wiederholungen in Zeichenketten[8][9]: In einer Zeichenkette x wird nach nicht-leeren Teilzeichenketten der Form uu (im engl. als tandem repeat oder square bezeichnet) gesucht.
  • Zeichenketten mit Wiederholungen mit Lücken (engl.: gaps) fester Größe:[10] In einer Zeichenkette x werden alle nicht-leeren Teilzeichenketten der Form uvu mit |u| > 0 und |v| = r für ein gegebenes r gesucht.
  • Maximale Periodizitäten in Zeichenketten[11]: In einer Zeichenkette x wird eine maximale Periodizität gesucht.
    • Eine Periodizität in einer Zeichenkette x ist eine nicht-leerer Zeichenkette der Form p^mq, wobei m \geq 2 und q ein Präfix von p ist. Dabei ist |p| die Periodenlänge.
    • Ein Vorkommen der Periodizität x[i \dots j] mit einer Periodenlänge k ist maximal, wenn
      1. i = 1 ist oder x[i-1 \dots j] keine Periodizität mit Periodenlänge k ist und
      2. j = |x| ist oder x[i \dots j+1] keine Periodizität mit Periodenlänge k ist.

Geschichte[Bearbeiten]

Die Kompressionsgüte ist direkt von der Größe des Lexikons abhängig. Um gute Kompressionsraten zu erhalten, muss das gleitende Fenster daher eine gewisse Mindestgröße erreichen. Da im Algorithmus der zu komprimierende Text mit jedem Eintrag im Lexikon verglichen werden muss (siehe Abschnitt Algorithmus), steigt die zum Komprimieren benötigte Zeit mit der Größe des Fensters stark an. Der LZ77-Algorithmus in Reinform fand daher zunächst wenig Beachtung. James Storer und Thomas Szymanski verbesserten 1982 einige Probleme in dem nun Lempel-Ziv-Storer-Szymanski (LZSS) genannten Algorithmus, der auch von Phil Katz für den weit verbreiteten Deflate-Algorithmus verwertet wurde. Der Vergleich des zu komprimierenden Textes mit allen Einträgen im Lexikon entfällt bei einer effizienten Implementierung wie im Abschnitt zur effizienten Konstruktion, wo immer nur der Vergleich mit maximal zwei Einträgen aus dem Lexikon notwendig ist.

In Reduced Offset Lempel Ziv (ROLZ, auch Lempel Ziv Ross Williams, von Ross Williams, 1991) und dem Lempel-Ziv-Markow-Algorithmus (LZMA, von Igor Pavlov, 1998) fand er bekanntere, moderne Nachfolger.

Verwandte Algorithmen[Bearbeiten]

Literatur[Bearbeiten]

  • Mark Nelson und Jean-Loup Gailly: The Data Compression Book, 1996 (2. Auflage), New York: M&T Books, ISBN 1-55851-434-1
  • Anisa Al-Hafeedh et al.: A Comparison of Index-based Lempel-Ziv LZ77 Factorization Algorithms, 2012. Erschienen in ACM Computing Surveys, Nr. 1, Volume 45, Seiten 5:1-5:17

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Jacob Ziv und Abraham Lempel: A Universal Algorithm for Sequential Data Compression, 1977. Erschienen in IEEE Transactions on Information Theory, Nr. 3, Volume 23, Seiten 337-343 als PDF
  2. a b c d Anisa Al-Hafeedh et al.: A Comparison of Index-based Lempel-Ziv LZ77 Factorization Algorithms, 2012. Erschienen in ACM Computing Surveys, Nr. 1, Volume 45, Seiten 5:1-5:17
  3. a b c Juha Kärkkäinen, Dominik Kempa und Simon J. Puglisi: Linear Time Lempel-Ziv Factorization: Simple, Fast, Small, 2013. Erschienen in CPM 2013, Lecture Notes in Computer Science, Volume 7922, Springer, 2013, ISBN 978-3-642-38904-7
  4. Mohamed I. Abouelhoda, Stefan Kurtz und Enno Ohlebusch: Replacing suffix trees with enhanced suffix arrays, 2004. Erschienen in Journal of Discrete Algorithms, Nr. 1, Volume 2, Seiten 53-86
  5. a b c Gang Chen, Simon J. Puglisi und William F. Smyth: Fast and Practical Algorithms for Computing All the Runs in a String, 2007. Erschienen in Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings, Seiten 307-315
  6. a b c Gang Chen, Simon J. Puglisi und William F. Smyth: Lempel-Ziv Factorization Using Less Time and Space, 2008. Erschienen in Mathematics in Computer Science, Nr. 4, Volume 1, Seiten 605-623
  7. a b Maxime Crochemore und Lucian Ilie: Computing Longest Previous Factor in linear time and applications, 2008. Erschienen in Information Processing Letters, Nr. 2, Volume 106, Seiten 75-80
  8. Maxime Crochemore: Transducers and repititions, 1986. Erschienen in Theoretical Computer Science, Nr. 1, Volume 45, Seiten 63-86
  9. Jens Stoye und Dan Gusfield: Simple and flexible detection of contiguous repeats using a suffix tree, 2002. Erschienen in Theoretical Computer Science, Nr. 1-2, Volume 270, Seiten 843-856
  10. Roman M. Kolpakov und Gregory Kucherov: Finding Repeats with Fixed Gap, 2000. Erschienen in Proceedings of the 7th International Symposium on String Processing and Information Retrieval (SPIRE), IEEE Computer Society, Seiten 162-168
  11. Michael G. Main: Detecting leftmost maximal periodicities, 1989. Erschienen in Discrete Applied Mathematics, Nr. 1-2, Volume 25, Seiten 145-153