LZW-Komprimierung (Algorithmus 5.11)

So geht’s: Beim Öffnen läuft abraLZW.txt mit ABRACADABRABRABRA, das Beispiel unter Listing 5.41. compress(): Im Eingabeband ist der längste Präfix s grün, den longestPrefixOf() gefunden hat. Orange umrandet ist das nächste Zeichen, mit dem s als neue Folge in die Tabelle kommt. Darunter wachsen die Codewörter mit, blau sind die für ganze Folgen. Rechts steht die Codetabelle mit den gelernten Folgen ab 101 (hex). Die Einzelzeichen 00 bis FF und 100 für das Dateiende sind nicht aufgeführt. expand(): Dieselben Codewörter werden wieder gelesen, das aktuelle ist orange. Die Tabelle entsteht dabei noch einmal, jeder Eintrag einen Schritt später als beim Komprimieren. „ababLZW.txt“ zeigt die knifflige Situation: Codewort 103 kommt an, bevor der Dekodierer es eingetragen hat. Die App zeigt das rot. Rechts unten steht die Konsole wie im Buch, mit dem HexDump. Eigene Texte dürfen ASCII-Zeichen ohne Umlaute enthalten. Wiederholungen lohnen sich, z. B. TOBEORNOTTOBEORTOBEORNOT.

Erklärung

LZW-Komprimierung (Algorithmus 5.11), Klasse LZW (Lempel-Ziv-Welch). Das Gegenstück zu Huffman [52]: Huffman gibt einzelnen Zeichen Codes unterschiedlicher Länge. LZW gibt dagegen ganzen, sich wiederholenden Zeichenfolgen Codes fester Länge, und zwar 12 Bit.

Grundidee:

• Eine Codetabelle startet mit allen 256 Einzelzeichen.
• Beim Lesen wird immer die längste Zeichenfolge gesucht, die schon in der Tabelle steht, und deren Code ausgegeben.
• Danach kommt diese Folge plus das nächste Zeichen als neuer Eintrag in die Tabelle.
• Die Tabelle wird nicht mitgeschickt. Der Dekodierer baut sie beim Lesen genauso wieder auf. Bei Huffman musste der Trie dagegen mitgeschickt werden.

Konstanten:

• R = 256: Eingabezeichen (8 Bit).
• L = 4096 = 2^12: Anzahl möglicher Codewörter.
• W = 12: Breite eines Codeworts in Bit.
• Codewort R (hex 100) steht für Dateiende, neue Einträge beginnen bei R + 1 (hex 101).

compress() (Listing 5.41):

• Die Codetabelle ist ein TST [47] mit Integer als Wert. Gewählt wurde er wegen longestPrefixOf() aus [46]: genau die Operation, die LZW braucht.
• Schleife:
  • s = st.longestPrefixOf(input): längster bekannter Anfang der Resteingabe.
  • Seinen Code mit 12 Bit ausgeben.
  • Ist noch Eingabe übrig und die Tabelle nicht voll: s plus nächstes Zeichen mit dem nächsten freien Code eintragen.
  • Eingabe um s kürzen.
• Am Ende Codewort R für Dateiende.

Ablauf ABRACADABRABRABRA (eigene Nachrechnung, passt zum HexDump):

• Der HexDump 04 10 42 05 20 41 … ergibt in 3er-Gruppen gelesen genau 041 042 052 041 043 041 044 101 103 102 108 041 100.
• 13 Codewörter × 12 Bit sind 156 Bit. Es werden 160 ausgegeben, weil close() auf volle Bytes auffüllt.
• Unkomprimiert wären es 17 × 8 = 136 Bit. Bei so kurzen Texten lohnt LZW sich also nicht. Der Gewinn kommt erst bei langen Eingaben, wenn die Tabelle lange Folgen enthält.

expand() (Listing 5.42):

• Hier reicht ein einfaches String[] als Tabelle, denn man schlägt jetzt vom Code zum String nach, also über den Arrayindex.
• Einzelzeichen eintragen, Platz R für Dateiende freihalten.
• Schleife:
  • Aktuellen String val ausgeben.
  • Nächstes Codewort lesen, bei R Schluss.
  • s = st[codeword].
  • Neuen Eintrag anlegen: val + erstes Zeichen von s.
  • val = s.
• Der Dekodierer läuft dem Kodierer einen Schritt hinterher. Das letzte Zeichen eines neuen Eintrags (das Vorausschauzeichen) kennt er erst, wenn er das nächste Codewort gelesen hat.

Die knifflige Situation, if (i == codeword):

• Manchmal liest der Dekodierer ein Codewort, das er selbst noch gar nicht eingetragen hat. Der Kodierer hat es im Schritt davor angelegt und sofort benutzt.
• Beispiel ABABABA:
  • Kodierer gibt aus: 041 (A), 042 (B), 101 (AB) und legt dabei ABA = 103 an.
  • Dann gibt er 103 (ABA) aus.
  • Der Dekodierer hat beim Lesen von 103 erst bis 102 eingetragen.
• Lösung: Der fehlende Eintrag muss val plus ein Zeichen sein. Dieses Zeichen ist das erste Zeichen des nächsten Strings, und der beginnt selbst mit val. Also ist s = val + val.charAt(0), hier AB + A = ABA.
• Das ist der Fehler, den das Buch als „subtil“ bezeichnet: Er tritt nur bei solchen Wiederholungsmustern auf und wird leicht übersehen.

Kosten und Grenzen:

• Komprimieren und Dekomprimieren in Zeit etwa proportional zur Eingabelänge. Jedes Eingabezeichen wird im TST bzw. Array nur einmal angefasst.
• Nach 4096 Einträgen ist die Tabelle voll. Dann werden keine neuen Folgen mehr gelernt, auch wenn sich die Daten ändern.
• Verbesserungen laut Buch (Übungen): Codewortbreite variabel wachsen lassen, die Tabelle bei Bedarf leeren und neu aufbauen.

Huffman vs. LZW:

Kapitel 5 komplett:

• Algorithmus 5.1: LSD-Sortierverfahren [43]
• Algorithmus 5.2: MSD-Sortierverfahren [44]
• Algorithmus 5.3: 3-Wege-Quicksort für Strings [45]
• Algorithmus 5.4: Trie-Symboltabelle [46]
• Algorithmus 5.5: TST-Symboltabelle [47]
• Algorithmus 5.6: Knuth-Morris-Pratt [48]
• Algorithmus 5.7: Boyer-Moore [49]
• Algorithmus 5.8: Rabin-Karp [50]
• Algorithmus 5.9: Reguläre Ausdrücke mit NEA [51]
• Algorithmus 5.10: Huffman-Komprimierung [52]
• Algorithmus 5.11: LZW-Komprimierung [53]