LZ77 + Huffman · von Grund auf · Rückweg geprüft
Kompression ist keine Magie, sondern Buchführung: was schon einmal dastand, wird nicht noch einmal geschrieben, sondern als Rückverweis notiert; und was häufig vorkommt, bekommt ein kürzeres Zeichen als was selten vorkommt. Beides passiert unsichtbar. Hier ist es sichtbar — jedes Zeichen ist danach eingefärbt, was es tatsächlich an Bits kostet. Blasse Stellen sind fast umsonst, kräftige sind teuer.
Einfügen und auf „Neu rechnen“ drücken. Alles bleibt im Browser.
—
| Posten | Bits | Anteil |
|---|
LZ77 schaut beim Schreiben zurück: steht die kommende Zeichenfolge schon irgendwo in den letzten 32 768 Zeichen, notiert es statt der Zeichen nur „gehe d zurück und nimm l Stück“. Genau diese Stellen sind hier grün unterstrichen — der Rest musste einzeln geschrieben werden.
Huffman zählt danach, wie oft jedes Symbol vorkommt, und gibt dem häufigsten das kürzeste Codewort. In deutschem Text bekommt „e“ etwa drei bis vier Bit, ein „q“ dagegen zwölf und mehr. Das Histogramm zeigt, wie sich die Wortlängen verteilen.
Der Entpacker muss die Codetabelle kennen, also steht sie vorne mit drin. Naiv abgelegt sind das 162 Byte Fixkosten — bei kurzen Texten mehr als die Daten selbst. Deshalb wird die Tabelle ihrerseits lauflängencodiert und gehuffmant; das drückt sie hier auf 20 bis 70 Byte.
Zwei Prüfungen laufen bei jedem Durchgang: das Entpackte wird Byte für Byte mit
dem Original verglichen, und die Größe wird gegen das im Browser eingebaute
CompressionStream('deflate-raw') gehalten. Ohne beides wäre jede
Zahl hier wertlos.