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örterbuch nach der längsten übereinstimmenden 
                                         Zeichenkette mit dem Vorschaupuffer;
     if Eine Übereinstimmung wurde gefunden; then
         Gib das Tripel (Versatz zum Rand des Wörterbuch, 
                         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örterbuchs der Länge 12 und einem Vorschaupuffer der Länge 9. In der ganz rechten Spalte findet sich von oben nach unten gelesen die Ausgabe des Algorithmus (0, 0, a ), (1, 1, c ), (3, 4, b ), (3, 3, a ) und (12, 3, Ende). Die Position ist relativ zum rechten Rand des Wörterbuchs angegeben, dies muss bei der Decodierung genau so geschehen.

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 Ende \Longrightarrow  (3, 3, a )
5 a a c a a c a b c a b a a a c Ende \Longrightarrow  (12, 3, Ende)
fertig

Das erste gesehene Zeichen ist unbekannt, sodass das erste a mit (0, 0, a ) aufgenommen wird. In der 2. Zeile kann das a bereits aus dem Wörterbuch 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 ist im Beispiel durch grünen Text auf rotem Grund dargestellt. Zeile 4 und 5 sind äquivalent zu den ersten beiden zu behandeln, mit der Ausnahme, dass im letzten Tripel ein Ende-Marker 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 (der direkte Nachfolger des LZ77) benötigt für die Rekonstruktion des Textes das initiale Wörterbuch (was aber meist das triviale Wörterbuch ist, in dem jedes Einzeichen-Symbol sortiert einmal vorkommt) und war bis ins Jahr 2004 teilweise durch Patente geschützt. Ein großer Nachteil des LZ77 ist jedoch, dass er allein insbesondere bei kleinen oder nicht natürlichsprachlichen Texten wenig komprimiert oder gar die Datenmenge vergrößert. Dies wird im angegebenen Beispiel deutlich, da der originale Text 16 Zeichen beinhaltet und die Komprimierung 15 Zeichen benötigt, was nur 1 Zeichen Ersparnis bedeutet. Er eignet sich ähnlich wie die Burrows-Wheeler-Transformation oder Move to front-Coder sehr gut als Preprozessor, um mittels anderen Kompressionsverfahren wie z. B. einer Huffman-Kodierung Daten effektiv zu komprimieren.

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 length > 0; then
         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;
     end if
     Gib symbol aus;
 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 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1
1 \Longrightarrow  (0, 0, a ) leer a
2 \Longrightarrow  (1, 1, c ) leer a a c
3 \Longrightarrow  (3, 4, b ) leer a a c a a c a b
4 \Longrightarrow  (3, 3, a ) leer a a c a a c a b c a b a
5 \Longrightarrow  (12, 3, Ende) a a c a a c a b c a b a a a c Ende
fertig

Ist der erste Eintrag eines Tripels gleich 0, wird der letzte Eintrag im Tripel an den Text angehängt (siehe Zeile 1). In Zeile 2 mit der Eingabe (1, 1, c ), wird bereits der erste Eintrag des rekonstruierten Textes aus Zeile 1 (erste Eintrag des Tripels für Position 1 und die zweite Eintrag des Tripels für die Länge 1) wieder verwendet und anschließend das Zeichen c hinten angehängt. In Zeile 3 ist die Länge der wieder verwendeten Zeichenkette länger als die gespeicherten Daten 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 Ende-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))
     end if
     if len = 0; then 
         pos <- i
     end if
     if i + len > n; then
         print factor(pos, len, 'Ende')
     else
         print factor(pos, len, x[i+len])
     end if
     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]
     end while
     PSV[i] <- j
 end for

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)
 end while

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 linear 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