Beispielimplementierung des LZW-Algorithmus in Java

Allgemein

Im Rahmen meines Studiums (Software-Engineering) durfte ich im letzten Präsenzblock die Vorlesung Multimedia besuchen. Dort haben wir auch den Lempel-Ziv-Welch-Algorithmus angesprochen, einen bekannten Algorithmus zur Entropiekodierung. Um die ganze Theorie dahinter (so viel ist es aber eigentlich gar nicht) besser zu verstehen, habe ich eine kleine Implementierung des Algorithmus in Java erstellt. Wen es interessiert, das Progrämmchen gibt es hier zum Download: Beispielimplementierung des LZW-Algorithmus in Java.

Das Ergebnis des Programms für den String, der auch in der Wikipedia verwendet wird, ist im folgenden Screenshot zu sehen.

Beispielaufruf des LZW-Algorithmus in Java

Über Stefan

Polyglot Clean Code Developer

4 Kommentare

  1. Rapha
    2. Februar 2010 um 22:41:12

    Wenn man sich nur mal den erzeugten Code anguckt: Daraus kann nie und nimmer mehr auf den Originaltext geschlossen werden.
    Auch wenn der Artikel schon etwas älter ist, richtig ist er nicht.

  2. Stefan
    2. Februar 2010 um 23:25:53

    Sorry Rapha, aber das stimmt nicht. Der erzeugte Code kann sehr wohl mit Hilfe des Wörterbuchs korrekt zum Ausgangswort entschlüsselt werden:

     1 => L
 2 => Z
 3 => W
10 => LZ
 4 => 7
 5 => 8
13 => LZ7
usw.

    Schreibt man alle Werte rechts der Pfeile hintereinander, erhält man das Ausgangswort.

  3. Kai
    15. Juli 2011 um 23:37:41

    Nur das dann irgendwie nichts gespart wurde, wenn das Wörterbuch noch mit gespeichert werden muss.

  4. Stefan
    16. Juli 2011 um 22:57:40

    Naja, der LZW lohnt sich erst ab einer gewissen Größe der zu komprimierenden Daten und wird natürlich umso effektiver, je mehr Wiederholungen in diesen Daten auftreten.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks: 

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax