Ich bereite mich gerade auf eine letzte Klausur für dieses Semester vor, und bin auf den Lempel-Ziv-Welch Kompressionsalgorithmus gestoßen. Da dieser relativ „einfach“ aussah, wollte ich ihn zum besseren Verständnis in Python implementieren.

Die Theorie

Der Zempel-Ziv-Welch (LZW) Algorithmus kann bzw. wurde zur Datenkompression eingesetzt, wobei ein Wörterbuch genutzt wird, um öfters vorkommende Zeichenketten wiederzuerkennen und wiederzubenutzen. Der Algorithmus ist verlustfrei, d.h man kann die komplette Nachricht ohne Verluste später wiederherstellen. Der Algorithmus funktioniert theoretisch so:

Eingabe: - S Zeichenkette, die komprimiert werden soll
Ausgabe: - W Wörterbuch, C Codebuch
Algorithmus:
Initialisiere Wörterbuch W mit Zeichen von 0-255.
While ( S ist nicht leer ) do
    Finde längste Zeichenkette s in W, die mit dem Anfang von S übereinstimmt
    Füge Index von s in W zu C hinzu.
    Entferne s vom Anfang von S.
    Füge s konkateniert mit dem ersten Zeichen von S zu W hinzu.
[Entferne von W die ersten 256 Einträge]
Gib das Wörterbuch W und Codebuch C aus.

Da das Wörterbuch W bis zum 256. Eintrag immer gleich ist, habe ich am Ende die Optimierung, diese vor der Ausgabe zu entfernen, vorgekommen.

Ein Beispiel

Damit man den Pseudocode besser verstehen kann, werde ich ein kurzes Beispiel zeigen. Wir möchten die folgende Zeichenkette komprimieren:

aaaabbaaabaaaabaabbaaaabaaab

Längste Zeichenkette s in W	Angabe ins Codebuch	Eintrag im Wörterbuch W	Resttsring S
a	97	W[256] := aa	aaabbaaabaaaabaabbaaaabaaab
aa	256	W[257] := aaa	abbaaabaaaabaabbaaaabaaab
a	97	W[258] := ab	bbaaabaaaabaabbaaaabaaab
b	98	W[259] := bb	baaabaaaabaabbaaaabaaab
b	98	W[260] := ba	aaabaaaabaabbaaaabaaab
aaa	257	W[261] := aaab	baaaabaabbaaaabaaab
ba	260	W[262] := baa	aaabaabbaaaabaaab
aaab	261	W[263] := aaaba	aabbaaaabaaab
aa	256	W[264] := aab	bbaaaabaaab
bb	259	W[265] := bba	aaaabaaab
aaa	257	W[266] := aaaa	abaaab
ab	258	W[267] := aba	aaab
aaab	261	–	–

Fast man die Ergebnisse zusammen, erhält man folgendes Resultat:

Dictoniary:['aa', 'aaa', 'ab', 'bb', 'ba', 'aaab', 'baa', 'aaaba', 'aab', 'bba', 'aaaa', 'aba']
Code: [97, 256, 97, 98, 98, 257, 260, 261, 256, 259, 257, 258, 261]

 Der Code

Der Code wird bestimmt wieder einmal nicht der Schönste sein, und kann bestimmt noch optimiert werden ;)

#!/usr/bin/python2.7

#Wörterbuch initialisieren (Zeichen 0-255)
def initDic():
    Dic = []
    for i in xrange(0,256):
        Dic.append(chr(i))
    return Dic

#Von hinten nach vorne, da hinten die längeren Zeichenketten sind
def find_in_dic(stri,dic):
    for i in xrange(len(dic)-1,0,-1):
        if(stri.find(dic[i],0)==0):
            return [dic[i],dic.index(dic[i])]

#Hauptfuntion
def LZW(str_input):

    dic = initDic()
    code = []

    while (len(str_input) <> 0):
        part, dictpos = find_in_dic(str_input,dic)     
        str_input = str_input[len(part):] #Vom Anfang n stellen entfernen
        code.append(dictpos)
        if(str_input <> ""):
            dic.append(part+str_input[0])
    del dic[0:256] #Konstanten Bestandteil entfernen
    return [dic, code]

def test():
    to_compress = "aaaabbaaabaaaabaabbaaaabaaab"
    dic, code = LZW(to_compress)
    print "Dictoniary:" + str(dic)
    print "Code: " + str(code)

test()

Ihr müsst einfach den Code abspeichern, und danach mit python2.7 ausführen. Wenn Ihr die Datei „LZW.py“ nennt, dann sieht ein Aufruf folgendermaßen aus:

python2.7 LZW.py

Der Algorithmus komprimiert umso besser, umso öfter gleiche Zeichenketten in dem zu komprimierenden String vorhanden sind. Es ist dann nämlich zu erwarten, dass man öfter auf das Wörterbuch zurückgreifen kann, und nicht neue Einträge anlegen muss.

Decompression

Ich wurde von einem Kollegen angesprochen, dass mit dem bisher beschriebenen Teil des Algorithmus noch nicht alles abgedeckt sei. Man kann nämlich nur aus dem Codebuch den Originaltext wiederherstellen.

Das funktioniert, indem man das initiale Wörterbuch initialisiert und dort nacheinander die Codes aus dem Codebuch nachschaut. Das Zeichen an dem entsprechenden Index gibt man aus, und fügt den Code konkateniert mit dem ersten Buchstaben des Folgecodes in das Wörterbuch ein.

Unser Pythonscript erweitern wir also um die folgende Funktion:

def LZWUncompress(codebook):

    dic = initDic()

    lastcode = codebook[0]
    del codebook[0]

    output = dic[lastcode]

    for code in codebook:
        if code < len(dic):
            dic.append(dic[lastcode]+dic[code][0])
        else:
            dic.append(dic[lastcode]+dic[lastcode][0])
        output = output + dic[code]
        lastcode = code
    print dic
    return output

Der „else“-Zweig wird für den Fall genutzt, dass zwei gleiche Codes nacheinander im Codebuch stehen. Als Eingabe erhält diese Funktion ein Codebuch. Wer das Script testen möchte, der kann die test()-Funktion entsprechend anpassen:

def test():
    to_compress = "aaaabbaaabaaaabaabbaaaabaaab"
    dic, code = LZW(to_compress)
    print "Teststring: " + to_compress
    print "Dictoniary:" + str(dic)
    print "Code: " + str(code)
    print "Decoded: " + LZWUncompress(code)

~ Sebastian