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. 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.
Verfahren mini|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 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.
mini|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:
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
Einzelnachweise
Kategorie:Kompressionsalgorithmus Kategorie:Kodierungstheorie