Umsetzung der LZW Kompression in PHP

[Olli Z. (z80freak)]

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:

$dict = array();
for ($i=0; $i <= 255; $i++) {
  $dict[] = chr($i);
}

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:

$searchpattern = '';
while ($inp_char = fread($uncompressed_fh, 1))
{
  $pattern = $pattern . $inp_char;
  if (in_array($pattern, $dict, true)) {
    # pattern found in dict
  } else {
    # new pattern, not in dict
    $dict[] = $searchpattern;
    fput($compressed_fh, pack("v", count($dict)));
  }
}

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?

[Jim M. (turboj)]

Olli Z. schrieb:
> Woher aber weiss den Dekodierer das in der Codetabelle auf Index 256 die
> Sequenz "LZ" liegt?

Weil er vorher die Codes für L und Z gesehen hat, die Du oben in Deiner 
Beschreibung nicht einfach weglassen durftest.

Olli Z. schrieb:
> Frage: Im Ausgangsstrom wird jeder Code also 2 Byte belegen, ausser man
> arbeitet hier mit Bitshifting, richtig?

Da kommt in der Praxis noch ein Huffman Schritt hinterher - aber der 
Ausgangsdatenstrom ist ein Bit Stream, also muss man die Bytes 
praktisch immer auseinander verdüddeln.

[Olli Z. (z80freak)]

Jim M. schrieb:
> Olli Z. schrieb:
>> Woher aber weiss den Dekodierer das in der Codetabelle auf Index 256 die
>> Sequenz "LZ" liegt?
>
> Weil er vorher die Codes für L und Z gesehen hat, die Du oben in Deiner
> Beschreibung nicht einfach weglassen durftest.

Ok. Mal schaun ob ich das so richtig sehen: Der Dekoder müsste zum 
Aufbau des gleichen Dicts auch die Basissequenzen sehen, also im Fall 
von "LZW...." müsste doch "L" unkomprimiert, dann "Z" unkomprimiert 
übertragen werden. Damit bilden dann sowohl Kodierer als auch Dekoder 
das gleiche Dict, nämlich:
...
"L" => 0x4C
..
"Z" => 0x5A
..
"LZ" => 0x100

kommt jetzt irgendwann, irgendwo im Stream nochmal die Bytefolge "LZ" 
vor, sendet der Kodierer 0x100 und der Dekoder ersetzt (expandiert) das 
zu "LZ".

Soweit würde mir das einleuchten.

> Da kommt in der Praxis noch ein Huffman Schritt hinterher - aber der
> Ausgangsdatenstrom ist ein Bit Stream, also muss man die Bytes
> praktisch immer auseinander verdüddeln.
Klingt logisch. Habe ich das richtig verstanden das beim LZW erstmal von 
einem 9-Bit code ausgegangen wird, d.H. der Empfänger weiss das max. 9 
Bit pro empfangenem Code übertragen werden? Also anfangs auch für die 
"unkomprimierten" Grundcodes von "L" und "Z", ...
Irgendwann ist das Dict ja mal voll, sprich bei 9 Bit passen max. 512 
Einträge rein. Das "wissen" aber Kodierer und Dekodierer, weil sie das 
Dict ja quasi parallel gleich aufbauen. In dem Moment wo der letzte 
Dict-Eintrag benutzt wurde, müsste auf 10-Bit codes gewechselt werden, 
was ja auch wiederum beiden klar ist. Dann hat man Luft bis zum 1024ten 
Eintrag. So geht das Spiel weiter bis zum 12-Bit Code, wo, aus mir noch 
unklaren Gründen irgendwie schluß sein soll. Schluß bedeutet dann wohl 
das beide das vorhandene so mühsam aufgebaute Dict wegwerfen und wieder 
von vorn beginnen.

[Fabulierender Schwafelhans (Gast)]

Olli Z. schrieb:
> was ja auch wiederum beiden klar ist. Dann hat man Luft bis zum 1024ten
> Eintrag. So geht das Spiel weiter bis zum 12-Bit Code, wo, aus mir noch
> unklaren Gründen irgendwie schluß sein soll. Schluß bedeutet dann wohl
> das beide das vorhandene so mühsam aufgebaute Dict wegwerfen und wieder
> von vorn beginnen.

Lies den englischen Artikel dann wird es klarer.