LZ77-Kompressor-Demo

Der LZ77-Komprimierungsalgorithmus eliminiert strukturelle Redundanz, indem er sich wiederholende Datensequenzen durch relative mathematische Zeiger ersetzt. Unter Verwendung eines verschiebbaren Betriebsfensters kodiert es Daten als Längen-Entfernungs-Paare, die auf zuvor verarbeitete Puffer verweisen. Diese deterministische Referenzierung bestimmt die Grundlage der DEFLATE-Protokolle. Der Algorithmus basiert ausschließlich auf der statistischen Wahrscheinlichkeit sich wiederholender Zeichenfolgen und maximiert die Entropiereduzierung, ohne die ursprünglichen mathematischen Informationen grundlegend zu verändern.

Wenn der Algorithmus Text sieht, den er schon gelesen hat, buchstabiert er ihn nicht erneut aus — er notiert kurz: „gehe offset Zeichen zurück und kopiere length davon." Jedes Token ist hier (offset, length, literal): ein Rückverweis plus ein neues Zeichen. Praktisch heißt das: Text voller wiederholter Wörter oder Muster schrumpft stark, während bereits zufällige Daten kaum komprimiert werden.

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.