Tunstall-Kodierung
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
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 dreimal 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.
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:
Daraus folgen in Summe 15 verschiedene Codewörter welche mit Bits codiert werden koennen. Die Schreibweise 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 folgende Abbildung:
| 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
- Martin Bossert: Angewandte Informationstheorie. (PDF; 815 kB) Skript zur Vorlesung. (Nicht mehr online verfügbar.) Universität Ulm, April 2007, archiviert vom Original; abgerufen am 5. April 2013.
Einzelnachweise
- Brian Parker Tunstall: Synthesis of noiseless compression codes. Georgia Institute of Technology, Dezember 1967.
- Variable to fixed Length Source Coding - Tunstall Codes. (PDF; 715 kB) Massachusetts Institute of Technology, Oktober 1994, abgerufen am 5. April 2013.