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 oder Lempel-Ziv 77 ordnet die Tunstall-Kodierung einem Quellensymbol mit variabler Länge, die konkrete Länge wird durch die Auftrittswahrscheinlichkeiten der einzelnen Quellensymbole bestimmt und in einem Suchbaum abgelegt, 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 9 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 12 Zeichen langen Zeichenfolge drei mal vor, was einer Auftrittswahrscheinlichkeit von 3/12 entspricht.

Für den ersten Iterationsschritt und den Aufbau des Suchbaums werden die einzelnen Auftrittswahrscheinlichkeiten aller 9 Quellsymbole bestimmt und diese 9 Symbole mit je einem Codesymbol der Länge von \lceil \log_2(9) \rceil = 4 Bits codiert. Die Schreibweise \lceil \cdot \rceil steht für die sogenannte Gauß-Klammer. Beispielsweise ist, wie in der Abbildung dargestellt, dem Symbol 'h' das Codewort w3 = "0010" zugeordnet.

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/12, und alle Wahrscheinlichkeiten für das Symbol l gefolgt von einem der 9 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:

{1 \over 3} \cdot {3 \over 12} = {1 \over 12}

Daraus folgen in Summe 17 verschiedene Codewörter welche mit \lceil \log_2(17) \rceil = 5 Bits codiert werden. Das Verfahren stoppt dann, wenn die Anzahl der Codewörter eine Anfangs festgelegte Grenze erreicht bzw. überschritten hat. Würde die Tunstall-Kodierung in diesem Beispiel nach dem zweiten Iterationsschritt mit einem Umfang von 17 Codewörtern beendet werden, würde die Zeichenfolge "hello, world" Tunstall-kodiert folgende binäre Codefolge darstellen, darunter sind die zugeordneten Quellsymbole angegeben:

01010 01011 00001 00000 01100 01101 01110 00000 01111 00011
  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).