Huffman-Kodierung

Kompression von Text mit Beispielcode in Python

Die Huffman-Codierung bildet die Grundlage fĂŒr die Kompression (und Dekompression) von Daten. In diesem Beitrag geht es um die entsprechende Datenstruktur (den Huffman-Baum) mit den zugehörigen Algorithmen (Aufbau des Baums, Kompression und Dekompression). Dabei soll es ausschliesslich um Text (und nicht um BinĂ€rdaten) gehen, womit sich die ganzen VorgĂ€nge leicht veranschaulichen lassen.

AuftretenshÀufigkeit und Komprimierbarkeit

Als Ausgangslage soll der Text „abracadabra“ dienen. Der Buchstabe ‚a‘ kommt darin ganze fĂŒnf mal vor, die Buchstaben ‚c‘ und ‚d‘ jedoch je nur einmal. Diesen Umstand macht sich die Huffman-Codierung zu Nutze, indem hĂ€ufig vorkommende Zeichen mit kurzen Bitsequenzen codiert werden, wĂ€hrend die selteneren Zeichen lĂ€ngere Bitsequenzen erfordern.

ZunÀchst wird die HÀufigkeiten der Buchstaben gezÀhlt:

Aufbau des Huffman-Baums

Als nĂ€chstes soll der Kodierungsbaum aufgebaut werden. Dies geschieht „von unten“, d.h. man fĂ€ngt bei den seltensten Zeichen an. Hierzu muss die Liste aufsteigend nach HĂ€ufigkeit und Zeichen sortiert werden:

Die einzelnen Zeichen mit HÀufigkeit bilden die BlÀtter des Baums:

Ausgangslage: FĂŒnf lose BlĂ€tter

Nun sollen je zwei BlĂ€tter zu einem Ast zusammengefĂŒgt werden. Der Ast enthĂ€lt einerseits eine Liste der darunter kodierten Zeichen, andererseits die Summe der ZeichenhĂ€ufigkeit. Die BlĂ€tter ‚c‘ und ‚d‘ werden also zu einem Knoten zusammengefasst:

Schritt 1: Zwei BlÀtter werden zu einem Knoten verbunden

Die Knoten werden erneut nach den gleichen Kriterien sortiert:

Zwar haben ‚b‘ einerseits und ‚c‘/‚d‘ zusammen andererseits die gleiche HĂ€ufigkeit, aber es soll auch alphabetisch sortiert werden, damit die Reihenfolge immer wohldefiniert ist. Das Blatt fĂŒr ‚b‘ und der Knoten fĂŒr „cd“ werden zu einem neuen Knoten „bcd“ zusammengefĂŒgt:

Schritt 2: Der Baum wÀchst asymmetrisch

Erneut wird die Liste sortiert:

Und das Spiel kann weitergefĂŒhrt werden, bis alle Knoten in den Baum integriert worden sind:

Schritt 3: Der Baum wÀchst und wÀchst

Und schliesslich:

Schritt 4: Der finale Baum

Kompression durch Huffman-Kodierung

Dem geneigten Betrachter dĂŒrften die Nullen (an der jeweils linken) und Einsen (an der jeweils rechten Kante) aufgefallen sein. Diese dienen der eigentlichen Kodierung des Textes. Man nehme eine leere Liste [], den ersten Buchstaben des zu kodierenden Textes (‚a‘ von „abracadabra“) und beginne beim obersten Knoten. Da der Baum fĂŒr diese Zeichenfolge aufgebaut worden ist, mĂŒssen alle Buchstaben im Wurzelknoten vorhanden sein. Nun wird das Zeichen ‚a‘ in den beiden Unterknoten gesucht. Da dieses Zeichen im linken Unterknoten zu finden ist, wird die 0 der Liste hinzugefĂŒgt: [0].

Gleichermassen wird mit dem Zeichen ‚b‘ verfahren, das mit der Bitfolge [1 1 0] kodiert wird. Die Liste ist nun auf [0 1 1 0] angewachsen. Damit sind zwei Buchstaben mit vier Bits kodiert worden.

Bevor nun die ganze Zeichenfolge „abracadabra“ abgearbeitet wird, was spĂ€ter mit einem Python-Programm erfolgt, soll an dieser Stelle die Dekodierung ausgehend von der Bitfolge [0 1 1 0] versucht werden.

Dekompression durch Huffman-Dekodierung

Der Vorgang beginnt beim Wurzelknoten mit der leeren Zeichenfolge „“. Dem ersten Bit folgend gelangt man zum Knoten ‚a‘, der zugleich ein Blatt ist. So wird der Zeichenkette dieses ‚a‘ hinzugefĂŒgt: „a“.

Es bleibt die Bitfolge [1 1 0], mit der wiederum beim Wurzelknoten begonnen werden soll. Es werden nacheinander die Knoten „bcdr“, „bcd“ und schliesslich ‚b‘ besucht. Das ging gut: die Bitfolge war beim Erreichen des Blattes erschöpft, und das ‚b‘ kann der Zeichenkette hinzugefĂŒgt werden, die nun „ab“ lautet.

Das Prinzip sollte also verstanden sein. Der ganze Vorgang des Baum-Aufbaus, der Kodierung und Dekodierung wird automatisiert, wozu Python zum Einsatz kommen soll.

Implementierung in Python

ZunĂ€chst einmal wird eine Datenstruktur fĂŒr den Baum benötigt, bzw. fĂŒr dessen Knoten (Nodes). Neben einer Liste von Zeichen und dem Gewicht werden auch Referenzen auf Unterknoten links und rechts benötigt. So ein Node liesse sich als Klasse oder Dictionary umsetzen; eine namedtuple ist hierfĂŒr ein guter Kompromiss:

from collections import namedtuple

Node = namedtuple('Node', 'chars weight left right')

left = False
right = True

Die Variablen left und right sind Aliase fĂŒr die Bits 0 und 1 (bzw. True und False), die spĂ€ter zum Einsatz kommen werden.

Aufbau des Baumes

Im ersten Schritt können die BlĂ€tter (Leaves) als je ein Node pro Buchstabe erstellt werden. Hierzu mĂŒssen die AuftretenshĂ€ufigkeiten im urpsrĂŒnglichen Text gezĂ€hlt werden:

def count_frequencies(text):
    freqs = {}
    for c in text:
        freqs[c] = freqs.get(c, 0) + 1
    return [Node([c], n, None, None) for c, n in freqs.items()]

In einem Dictionary namens freqs wird die HÀufigkeit pro Buchstabe gezÀhlt. mit einer list comprehension wird daraus eine Reihe von Knoten erzeugt; jeweils mit Zeichen und Anzahl; jedoch noch ohne Referenzen links und rechts.

Im nÀchsten Schritt soll der eigentliche Baum anhand der Frequenz-BlÀtter aufgebaut werden:

def build_tree(freqs):
    def sortkey(node):
        return (node[1], node[0])
    nodes = sorted(freqs, key=sortkey)
    while (len(nodes) > 1):
        a = nodes[0]
        b = nodes[1]
        c = Node(sorted(a.chars + b.chars), a.weight + b.weight, a, b)
        nodes = sorted([c] + nodes[2:], key=sortkey)
    return nodes[0]

Die Hilfsfunktion sortkey sortiert die Knoten aufsteigend nach HÀufigkeit und Zeichen(folge). Solange es mehr als einen Knoten in der Liste gibt, werden die Knoten mit den jeweils geringsten Frequenzen paarweise kombiniert. Dabei werden die Zeichen als Strings zusammengehÀngt, und die Gewichte (HÀufigkeiten) aufaddiert. Die Liste mit den Knoten wird neu erstellt, sodass die beiden Kinder daraus verschwinden und nur noch ihr gemeinsamer Eltern-Knoten darin auftaucht. Sobald die Liste nur noch aus dem Wurzelknoten besteht, ist der Baum fertig aufgebaut.

Kodierung

FĂŒr die eigentliche Kodierung soll ein spezieller Datentyp namens BitStream aus dem entsprechenden Package (bitsream) zum Einsatz kommen:

from bitstream import BitStream

def encode(text, tree):
    bits = BitStream()
    for c in text:
        bits.write(encode_char(c, tree))
    return bits

Jedes Zeichen im Text soll anhand des Baumes und der Hilfsfunktion encode_char kodiert werden. Diese ist folgendermassen implementiert:

def encode_char(c, tree):
    path = []
    if len(tree.chars) == 1 and c == tree.chars[0]:
        # leaf
        return path
    elif c in tree.chars:
        # node
        if c in tree.left.chars:
            return path + [left] + encode_char(c, tree.left)
        elif c in tree.right.chars:
            return path + [right] + encode_char(c, tree.right)
        else:
            raise ValueError(f'{c} not found in left/right branch of {tree}')
    else:
        raise ValueError(f'{c} not found in {tree}')

Der Baum wird von oben nach unten durchlaufen. Der dabei beschrittene Pfad wird in der Liste path als Bitfolge festgehalten. Handelt es sich beim aktuell besuchten Knoten um ein Blatt (ein Zeichen, das dem zu kodierenden entspricht), ist die Bitfolge komplett. Bei Knoten mit mehreren Zeichen und Kindern muss der richtige Pfad eingeschlagen werden, indem das zu kodierende Zeichen in den beiden Kindern links und rechts gesucht wird.

Die eigentliche Kodierung kann nun anhand der bereitgestellten API erfolgen:

if __name__ == '__main__':
    text = 'abracadabra'
    freqs = count_frequencies(text)
    tree = build_tree(freqs)
    encoded = encode(text, tree)
    print(f'Compressed "{text}" as {encoded} in {len(encoded)} bits.')

Und so wird es ausgefĂŒhrt:

$ ./huffman.py
Compressed "abracadabra" as 01101001110011110110100 in 23 bits.



12 Zeichen in 23 (Huffman) statt 96 (ASCII) Bits: nicht schlecht!

Dekodierung

Das bringt aber nur etwas, wenn man das wieder rĂŒckgĂ€ngig machen kann. Hierzu wird eine Funktion zur Dekodierung benötigt:

def decode(bits, tree):
    text = ''
    bits = bits.copy()
    while len(bits):
        char, bits = decode_next(bits, tree)
        text += char
    return text

Begonnen wird mit einem leeren Text; die Bitfolge wird kopiert, damit das Original erhalten bleibt. Das jeweils nĂ€chste Zeichen wird mit decode_next dekodiert, wonach eine kĂŒrzere Bitfolge verbleibt:

def decode_next(bits, tree):
    if len(tree.chars) == 1:
        # leaf
        return tree.chars[0], bits
    elif len(bits):
        # node
        bit = bits.read(bool, 1)[0]
        if bit is left:
            return decode_next(bits, tree.left)
        else:
            return decode_next(bits, tree.right)
    else:
        raise ValueError('bits consumed prematurely')

VerfĂŒgt der jeweilige (Unter)baum (tree) nur noch ĂŒber ein einziges Zeichen, ist ein Blatt erreicht, und das Zeichen kann mit der verbleibenden Bitfolge zurĂŒckgegeben werden. Sind jedoch mehrere Zeichen im Ast zu finden und noch Bits vorhanden, wird der Bitfolge das nĂ€chste Bit entnommen, welches uns in die linke oder rechte Richtung herabschickt, wozu decode_next rekursiv aufgerufen wird.

Die vorher erstellte (kodierte) Bitfolge wird folgendermassen dekodiert:

if __name__ == '__main__':
    # 

    encoded = encode(text, tree)
    # 

    decoded = decode(encoded, tree)
    print(f'Decompressed {encoded} as "{text}".')

Auch das funktioniert:

$ ./huffman.py


Decompressed 01101001110011110110100 as "abracadabra".

Und jetzt?

Jetzt mĂŒsste nur noch ein Dateiformat gefunden werden, in die sich die Bitfolge zusammen mit dem Kodierungsbaum effizient abspeichern liesse. Doch dieses Problem ist durch gzip, bzip2, xz usw. schon gelöst. Hier soll es ja nur um das VerstĂ€ndnis gehen.

Das ganze, ausfĂŒhrbare Programm steht als GitHub Gist zur VerfĂŒgung. Eine alternative Implementierung in Erlang kann die kodierte Bitfolge inkl. Huffman-Baum in einer Datei ablegen und auch wieder daraus herauslesen und dekodieren.