Tunstall-Kodierung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Tunstall-Kodierung ist eine Form der verlustfreien Datenkompression und Entropiekodierung, die 1967 von Brian Parker Tunstall in seiner Doktorarbeit am Georgia Institute of Technology entwickelt wurde.[1] Im Gegensatz zu ähnlichen Verfahren wie der Huffman-Kodierung ordnet die Tunstall-Kodierung einem Quellensymbol mit variabler Länge ein Codesymbol mit einer fixen Anzahl von Bits (Stellen) zu.[2]

Verfahren[Bearbeiten]

Suchbaum im ersten Iterationsschritt

Als Beispiel soll die Datencodierung der Zeichenfolge "hello_world" dienen. Zur Vereinfachung sei weiters angenommen, dass der Umfang der Quellsymbole, das sogenannte Alphabet, nur die 8 Symbole {dehlorw_} umfassen soll. In diesem Fall lässt sich die Auftrittswahrscheinlichkeit der einzelnen Zeichen in der zu codierenden Zeichenfolge direkt angeben: Beispielsweise kommt das Zeichen 'l' in der 11 Zeichen langen Zeichenfolge drei mal vor, was einer Auftrittswahrscheinlichkeit von 3/11 entspricht.

Für den ersten Iterationsschritt und den Aufbau des Suchbaums werden die einzelnen Auftrittswahrscheinlichkeiten aller 8 Quellsymbole bestimmt.

Suchbaum im zweiten Iterationsschritt

Durch weitere Iterationsschritte wird die Entropiecodierung verbessert. Im zweiten Iterationsschritt wird aus dem Baum das Blatt mit der höchsten Auftrittswahrscheinlichkeit genommen, in diesem Fall das Symbol l mit 3/11, und alle Wahrscheinlichkeiten für das Symbol l gefolgt von einem der 8 weiteren möglichen Symbole gebildet. Auch in diesem Fall werden die Auftrittswahrscheinlichkeiten der einzelnen Symbole bzw. Symbolfolgen gebildet und absteigend im Baum sortiert, wie in der zweiten Abbildung dargestellt. So beträgt die Auftrittswahrscheinlichkeit der Symbolfolge ll in diesem Beispiel:

  \left({3 \over 11}\right)^2 = {9 \over 121}

Daraus folgen in Summe 15 verschiedene Codewörter welche mit \lceil \log_2(15) \rceil = 4 Bits codiert werden koennen. Die Schreibweise \lceil \cdot \rceil steht für die sogenannte Gauß-Klammer. Beispielsweise ist, wie in der Abbildung dargestellt, dem Symbol 'h' das Codewort w1 = "0000" zugeordnet. Das Verfahren stoppt dann, wenn die Anzahl der Codewörter eine Anfangs festgelegte Grenze erreicht bzw. überschritten hat. Hier ergibt sich also folgendes Woerterbuch:

Wort Code
w1="h" 0000
w2="e" 0001
w3="lh" 0010
w4="le" 0011
w5="ll" 0100
w6="lo" 0101
w7="l_" 0110
w8="lw" 0111
w9="lr" 1000
w10="ld" 1001
w11="o" 1010
w12="_" 1011
w13="w" 1100
w14="r" 1101
w15="d" 1110
1111

Würde die Tunstall-Kodierung in diesem Beispiel nach dem zweiten Iterationsschritt mit einem Umfang von 15 Codewörtern beendet werden, würde die Zeichenfolge "hello_world" Tunstall-kodiert folgende binäre Codefolge darstellen, darunter sind die zugeordneten Quellsymbole angegeben:

0000 0001 0100 1010 1011 1100 1010 1101 1001
 h    e    ll   o    _    w    o    r    ld

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Brian Parker Tunstall: Synthesis of noiseless compression codes. Georgia Institute of Technology, Dezember 1967.
  2. Vorlage:Internetquelle/Wartung/Datum nicht im ISO-FormatVariable to fixed Length Source Coding - Tunstall Codes. Massachusetts Institute of Technology, Oktober 1994, abgerufen am 5. April 2013 (PDF; 715 kB).