Huffman-Kodierung mit Python erstellen

Mit Python kann man sich ziemlich leicht eine Huffman-Kodierung ermitteln lassen. Eine Huffman-Kodierung ist eine präfixfreie Kodierung von Zeichen in Binärdarstellung mit variabler Länge. Dabei werden häufigere Buchstaben mit kürzeren Symbolen kodiert. Eine solche Kodierung wird üblicherweise für jeden Text neu ermittelt, da sie nur für den jeweiligen Text optimal ist. Würde man sie aber z.B. über die gesamte deutsche Sprache kalibrieren, hätte das e eine sehr kurze Binärkodierung.

Um dies zu erreichen, muss man sich einen Baum anlegen, der die seltensten Buchstaben an den Blättern und die häufigsten nah an der Wurzel hat. Dies kann man ziemlich leicht mit einer PriorityQueue erreichen, da diese immer die kleinsten Prioritäten zuerst zurückgibt.

Legen wir uns aber zuerst eine einfache Klasse zur Verwaltung des Baumes an:

class Node(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.char = ""
        self.frequency = 0

Unsere Klasse kann eine Häufigkeit speichern, ein linkes Tochterelement und ein rechtes Tochterelement. Wegen der binären Kodierung sind die Bäume auch binär, deshalb werden nur linke und rechte Kindelemente benötigt. Ein Huffman-Baum ist dazu auch immer vollständig (d.h. ein Knoten ist entweder Blatt oder hat zwei Kindelemente), dies spielt bei der Implementierung aber eigentlich keine Rolle.

Zunächst muss man sich eine PriorityQueue anlegen und dann alle bisherigen Zeichen dort abspeichern. Der Einfachheit halber habe ich direkt welche im Programm vorgegeben:

chars = {"a": 10, "b": 2, "c": 3}

queue = Queue.PriorityQueue()

for key, value in chars.items():
    node = Node()
    node.char = key
    node.frequency = value
    queue.put((value, node))

Diese Liste wird nun so lange abgearbeitet, bis sie nur noch ein einziges Element enthält (die Wurzel des Baumes). Dabei werden jeweils die zwei Knoten mit der geringsten Häufigkeit zu einem virtuellen Knoten (ohne Zeichen) zusammengefasst und dieser wird selbst wieder in die Liste gegeben (damit er selbst auch im Baum eingetragen werden kann).

while queue.qsize() > 1:
    newNode = Node()

    if (queue.qsize() <= 1):
        break
  
    _, x = queue.get()
    _, y = queue.get()
    newNode.left = x
    newNode.right = y
    newNode.frequency = x.frequency + y.frequency
    queue.put((newNode.frequency, newNode))

Nun kann man auf den Baum zugreifen, indem man sich das letzte Element aus der Liste zurückgeben lässt. Natürlich will man zum Testen aber auch gerne sehen, wie die Buchstaben nun kodiert sind. Dazu kann man sich eine kleine Methode schreiben:

def printTree(node, code = ""):
    if (node.left == None and node.right == None):
        print("%s: %s" % (node.char, code))
    else:
        printTree(node.left, code + "0")
        printTree(node.right, code + "1")

Diese nimmt das Wurzelelement des Baumes entgegen und prüft, ob der Knoten keine Kindelemente mehr hat. Ein Knoten mit Kindelementen ist ein virtueller Knoten und braucht deshalb nicht ausgegeben zu werden. Da Huffman-Bäume vollständig sind, ist eine Prüfung darauf, ob ein linkes oder rechtes Kindelement existiert nicht mehr nötig. Für jedes Kindelement wird – und das ist wichtig – eine Ziffer an die Kodierung angehängt. So erhält jedes echte Zeichen eine eindeutige Binärzahl zugeordnet.

Der Ablauf für obiges Programm gibt schließlich aus:

b: 00
c: 01
a: 1