Ich versuche gerade aus der Theorie der LZW Komprimierung, wie sie z.B.
hier beschrieben ist:
https://de.m.wikipedia.org/wiki/Lempel-Ziv-Welch-Algorithmus
eine praktische Umsetzung in PHP zu erarbeiten, weil ich diese Sprache
ein wenig kann. (Und nein, ich bin kein Student und das ist auch keine
Hausaufgabe)
Die Theorie vom LZW klingt eigentlich recht simpel und ich würde sie
hier nur in Teilen zitieren um abzuprüfen das ich es richtig verstanden
hab.
Der LZW Algorithmus basiert auf der Theorie das sich in einem Datenstrom
wiederholende Sequenzen durch Zeiger auf eine Codetabelle übertragen
lassen anstelle der Daten selbst, wodurch eine Kompression erreicht
wird. Dabei wird die Codetabelle selbst nicht übertragen, Kodierer und
Dekodierer bauen diese Idempotent aus dem Datenstrom auf. Jeder Sequenz
wird dabei ein 9 bis 12 Bit breiter Code zugeteilt, wodurch sich
theoretisch bis zu 4096 verschiedene Sequenzen erkennen und übertragen
lassen.
Frage: Im Ausgangsstrom wird jeder Code also 2 Byte belegen, ausser man
arbeitet hier mit Bitshifting, richtig?
Die Codetabelle wird zunächst mit allen Grundsequenzen, also den Zeichen
0x00 bis 0xFF initialisiert:
1 | $dict = array();
|
2 | for ($i=0; $i <= 255; $i++) {
|
3 | $dict[] = chr($i);
|
4 | }
|
Danach habe ich ein Array bei dem der Index der Code ist und sein Wert
die Sequenz.
Vom Eingangsstrom wird immer ein Zeichen (Byte) nach dem anderen in
einen Puffer eingelesen bis eine neue Sequenz gefunden wird, welche dann
an die Codetabelle angefügt wird.
Also ich nehme mal diesen Eingangsstrom an "LZWLZ78LZ77LZCLZMWLZAP". Das
erste Zeichen ist "L" und kommt in der Codetabelle aufgrund der
Initialisierung vor. Eine Suche nach diesem Zeichen in der Codetabelle
würde also einen Treffer finden. In dem Fall müsste man laut Algo
solange weitersuchen bis man eine noch unbekannte Sequenz findet, also
das nächste Zeichen an den Suchpuffer (ich nehme hier $searchpattern)
anfügen und erneut suchen. Nun wird nach "LZ" gesucht, was noch nicht in
der Codetabelle vorhanden ist und wir landen in der "else" Bedingung:
1 | $searchpattern = '';
|
2 | while ($inp_char = fread($uncompressed_fh, 1))
|
3 | {
|
4 | $pattern = $pattern . $inp_char;
|
5 | if (in_array($pattern, $dict, true)) {
|
6 | # pattern found in dict
|
7 | } else {
|
8 | # new pattern, not in dict
|
9 | $dict[] = $searchpattern;
|
10 | fput($compressed_fh, pack("v", count($dict)));
|
11 | }
|
12 | }
|
Nun soll laut Algo der Code dieser neuen Sequenz in den Ausgangsstrom
geschrieben werden, also: "<256>" bzw. in Hex-Bytes (big endian)
ausgedrückt: "0x01 0x00".
Woher aber weiss den Dekodierer das in der Codetabelle auf Index 256 die
Sequenz "LZ" liegt?