Routinen für LZW-(De-)Komprimierung von binären Daten

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Thomas W.
User
Beiträge: 17
Registriert: Sonntag 9. April 2006, 08:36
Wohnort: Halle (Saale)

Routinen für LZW-(De-)Komprimierung von binären Daten

Beitragvon Thomas W. » Dienstag 25. September 2007, 09:09

Ich habe in einer Datei mehrere Blöcke mit binären Daten, die z.T. LZW kodiert sind. Gibt es eine Routine, der ich in einem String den komprimierten Datenblock übergeben kann und von der ich den unkomprimierten Datenblock zurückbekomme?

Ich habe das Code-Beispiel http://en.wikipedia.org/wiki/Lempel-Ziv-Welch#Python_example gefunden. LZW ist ja eigentlich nicht textspezifisch, ich weiß aber nicht, ob der verwendeten Unicode-Bezug Auswirkung auf binäre Daten hat.
BlackJack

Beitragvon BlackJack » Dienstag 25. September 2007, 09:59

Der Quelltext dort ist auf Unicode beschränkt und kann so nicht für beliebige binäre Daten benutzt werden.

Mal davon abgesehen, das der Quelltext ein einigen Stellen etwas komisch/umständlich aussieht, verstehe ich die Beschränkung auf Unicode dort auch nicht. Da werden im Grunde zwei verschiedene Funktionalitäten vermischt, die man besser getrennt gehalten hätte. Duck typing wird durch manuelle Typprüfungen verhindert und so Sachen wie ``int(256)`` oder ``del buffer`` gleich gefolgt von einer neuen Zuweisung an den Namen, vermitteln den Eindruck als wenn da jemand noch nicht lange Python programmiert.

Edit: Und ich sehe auch nicht warum das in einer Klasse stecken muss. Das sind ganz einfach drei Funktionen.
BlackJack

Beitragvon BlackJack » Dienstag 25. September 2007, 11:36

Und noch ein Nachtrag: Vergiss was ich gesagt habe :-)

UTF-8 kommt ins Spiel weil bei der Kompression nach dem LZW-Verfahren Zahlen herauskommen die grösser als 255 sind, also nicht mehr als Byte darstellbar sind. Der Autor hat dann einfach diese Zahlen zu Unicode-Zeichen gemacht und UTF-8 kodiert um Platz zu sparen weil so die "ein Byte Werte" < 128 wenigstens ein Byte lang bleiben.

Real müsste man sich natürlich eine etwas effizientere Methode einfallen lassen. Bzw. müsstest Du schauen wie das bei Deinen LZW-komprimierten Daten gelöst ist.

Üblich ist wohl, dass immer wenn `chars` aus dem Quelltext eine 2er Potenz überschreitet, ein Bit mehr pro Zahl gespeichert wird. Oder das gleich eine feste Anzahl von Bits pro Zahl genommen wird und wenn die nicht mehr ausreicht das Dictionary und `chars` einfach wieder initialisiert werden. Oder eine Kombination von beidem damit die Bitanzahl pro Zahl nicht "unendlich" steigt und damit den Kompressionseffekt wieder zunichte macht.

Den Quelltext aus dem Artikel habe ich mal ein wenig überarbeitet: http://paste.pocoo.org/show/4497/

Ist immer noch auf "Lesbarkeit" ausgerichtet, also als möglicher Ersatz für Wikipedia. Ansonsten liesse er sich sicher nochmal etwas "pythonischer" formulieren.
Thomas W.
User
Beiträge: 17
Registriert: Sonntag 9. April 2006, 08:36
Wohnort: Halle (Saale)

Beitragvon Thomas W. » Dienstag 25. September 2007, 11:59

BlackJack hat geschrieben:UTF-8 kommt ins Spiel weil bei der Kompression nach dem LZW-Verfahren Zahlen herauskommen die grösser als 255 sind, also nicht mehr als Byte darstellbar sind. Der Autor hat dann einfach diese Zahlen zu Unicode-Zeichen gemacht und UTF-8 kodiert um Platz zu sparen weil so die "ein Byte Werte" < 128 wenigstens ein Byte lang bleiben.

Das ist natürlich auch ein Ansatz.

BlackJack hat geschrieben:Üblich ist wohl, dass immer wenn `chars` aus dem Quelltext eine 2er Potenz überschreitet, ein Bit mehr pro Zahl gespeichert wird.

Das ist bei mir der Fall.

BlackJack hat geschrieben:Den Quelltext aus dem Artikel habe ich mal ein wenig überarbeitet: http://paste.pocoo.org/show/4497/

Danke, ich werde mir den ansehen. Ich werde im Forum Codesnippets (später) mal einstellen, was ich zusammenkopiert/-geschrieben und benutzt habe.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder