LZ77-Kompressor-Demo

Beobachte, wie das Sliding Window von links nach rechts wandert: Bei jedem Schritt sucht es den längsten Rückverweis im Suchfenster und erzeugt ein Token (Offset, Länge, Literal).

Rechenbeispiel — LZ77-Kompressor-Demo

Vorschau	[0..7] "abracada"
Erzeugte Tokens: 1 von 6	5.18×
Ausgabe-Tokens	(0,0,'a')

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Ein größeres Fenster hilft weniger, als es kostet 🖖

Es scheint offensichtlich, dass ein größeres Suchfenster besser komprimiert, denn mehr Vorgeschichte bedeutet mehr Chancen auf einen Treffer. Der Haken ist, dass jeder einzelne Zeiger irgendwohin in diesem Fenster adressieren können muss, sodass eine Verbreiterung das Distanzfeld für jede ausgegebene Referenz verlängert — auch für die Tausenden, die nur wenige Bytes zurückgreifen mussten. Verdoppelt man das Fenster, kommt bei allen ein Bit hinzu, ob es einen längeren Treffer einbrachte oder nicht. Dieser Kompromiss ist der Grund, weshalb DEFLATE, der Algorithmus in ZIP, PNG und gzip, sich auf 32 KB festlegte und dort jahrzehntelang blieb: weit genug zurück für echte Wiederholungen in gewöhnlichem Text, nah genug, dass die Offsets günstig bleiben.

Kopieren statt wiederholen 🖖

Trifft der Algorithmus auf Text, den er schon gelesen hat, schreibt er ihn nicht noch einmal aus. Stattdessen notiert er kurz: „Gehe Versatz Zeichen zurück und kopiere Länge Zeichen.“ Jedes Token hat hier die Form (offset, length, literal): einen Rückverweis und ein neues Zeichen. Text mit vielen Wort- oder Musterwiederholungen schrumpft stark; bereits zufällige Daten lassen sich dagegen kaum komprimieren.

Wenn ein Token zur langen Folge wird 🖖

Ein Treffer kann nur ein Zeichen zurückverweisen und trotzdem mehr Zeichen kopieren, als dort schon existieren. Bei offset 1 kopiert der Decoder jedes Byte sofort, während er es schreibt, sodass ein einziges Token wie (1, 5, ...) aus einem einzelnen a das Wort aaaaaa entfaltet. So ergibt sich die klassische Lauflängenkodierung gratis aus LZ77 — die „Kopie" überlappt Text, der noch erzeugt wird. Probiere das wiederholende Beispiel, um zu sehen, wie ein Trefferbereich über die aktuelle Position hinausreicht.

Aufgabe vollständig gelöst

Sechs Token von "abracadabra" mit einem Suchfenster von 16 Zeichen 5 Schritte
Das Bedienfeld zeigt nach einem Token 5,18× an. Berechnen Sie, was es nach allen sechs zeigt. Die Eingabe lautet "abracadabra", das Suchfenster umfasst 16 Zeichen und der Vorausschaupuffer 8.
1. Ein Token besteht aus drei Feldern fester Breite, sodass seine Kosten von den beiden Einstellungen und nicht von den Daten bestimmt werden. Der Offset muss jede Position im Fenster adressieren können, die Länge jeden Wert bis zur Puffergröße, und das Literal ist ein rohes Byte.
  
  $⌈ lo g_{2} (W + 1)⌉ + ⌈ lo g_{2} (B + 1)⌉ + 8 = ⌈ lo g_{2} 17 ⌉ + ⌈ lo g_{2} 9 ⌉ + 8 = 5 + 4 + 8 = 17 bits$
2. Der Kodierer tastet von links nach rechts ab und nimmt die längste Übereinstimmung, die das Fenster bietet. Vor den ersten drei Zeichen liegt noch nichts, sodass 'a', 'b' und 'r' jeweils ein ganzes Token kosten, um einmal ausgegeben zu werden. Erst das letzte Token lohnt sich und kopiert "abra" ab Position 0.
  
  $(0, 0, a) (0, 0, b) (0, 0, r) (3, 1, c) (5, 1, d) (7, 4, \emptyset)$
3. Das Verhältnis auf dem Bedienfeld ist ein fortlaufender Wert und teilt die gesamte Eingabe durch die bisher erzeugte Ausgabe. Nach einem Token stellt es elf Zeichen siebzehn Bit gegenüber, weshalb es so hoch beginnt.
  
  $\frac{11 \times 8}{1 \times 17} = \frac{88}{17} = 5.18 \times$
4. Sechs Token zu je siebzehn Bit ergeben 102 Bit gegenüber einer Eingabe von 88. Die Kodierung ist größer als das, was sie kodiert.
  
  $\frac{11 \times 8}{6 \times 17} = \frac{88}{102} = 0.86 \times$
5. Die Schwelle zur Rentabilität ist eine einzige Division. Ein Token kostet 17 Bit und kauft eine Anzahl von Zeichen im Wert von jeweils 8 Bit, sodass das Verfahren nur dann gewinnt, wenn das durchschnittliche Token mehr als 17/8 Zeichen voranschreitet — und von diesen sechs tut dies nur das letzte.
  
  $\frac{N}{T} > \frac{17}{8} = 2.125, \frac{N}{T} = \frac{11}{6} = 1.83$
Antwort

Das Bedienfeld zeigt nach dem ersten Token 5,18× und nach dem sechsten 0,86× an: dieselbe Zeichenkette, dieselbe Kodierung, auf gegenüberliegenden Seiten von 1,0. Der merkenswerte Wert ist 2,125 Zeichen pro Token, was genau der Tokenbreite geteilt durch acht entspricht, und er ist das einzige Kriterium dafür, ob LZ77 bei einer gegebenen Eingabe hilft. Er bewertet auch einen Stellparameter, der kostenlos wirkt. Die Erweiterung des Suchfensters auf 64 fügt jedem Offset-Feld zwei Bit hinzu, und bei dieser Zeichenkette findet sich überhaupt keine längere Übereinstimmung — die Zerlegung bleibt dieselben sechs Token —, sodass das Verhältnis auf 0,77× fällt. Jede Verdopplung der Reichweite kostet ein weiteres Bit pro Token, ob genutzt oder nicht.

$\frac{N}{T} > \frac{⌈ lo g _{2} ( W + 1 )⌉ + ⌈ lo g _{2} ( B + 1 )⌉ + 8}{8}$

Lernpfad

Kompression von Hand

Führt zu Burrows-Wheeler

Quellen (1)

The algorithm, and the offset-1 trick block 3 turns on: J. Ziv and A. Lempel, "A universal algorithm for sequential data compression." IEEE Transactions on Information Theory 23(3), 337–343, 1977.

Vom 42Math-Team · Aktualisiert 2026-08-17

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

abracadabra → 6 Tokens - „abracadabra“: 6 Token für 11 Zeichen. Das letzte greift 7 Stellen zurück und kopiert 4 Zeichen, also das gesamte „abra“ mit einem einzigen Verweis.
aabaabaabaab → 3 Tokens - „aabaabaabaab“: 4 Token für 12 Zeichen. Eines davon greift nur 3 Stellen zurück und kopiert 7 Zeichen, sodass der Treffer über das gerade geschriebene Zeichen hinausläuft. Lauflängencodierung gibt es hier nebenbei.
the quick brown fox → 16 Tokens - „the quick brown fox“: 16 Token für 19 Zeichen. Der längste Treffer besteht aus einem einzigen Buchstaben. Bei einem so kurzen Text gibt es fast nichts, worauf sich zurückverweisen lässt.
ATGATCGATCG → 5 Tokens - „ATGATCGATCGATCG“: 6 Token für 15 Basen. Der fünfte Verweis greift 4 Stellen zurück und kopiert 7 Zeichen, wobei er sich selbst überlappt: ATCG wiederholt sich mit einer kürzeren Periode als der Treffer, den der Verweis auffüllt.