// Tunstall-Codierung – optimale variabel-zu-festlängige Kompression
Ordnet Sequenzen variabler Länge Codes mit fester Länge zu.
Das Wörterbuch wird aus der Wahrscheinlichkeitsverteilung der Symbole aufgebaut.
Codes fester Länge ermöglichen eine einfache und schnelle Dekodierung.
Die Tunstall-Codierung erstellt ein Wörterbuch aus Folgen variabler Länge, die auf binäre Codes fester Länge abgebildet werden. Ausgehend von Einzelsymbolen wird iterativ die wahrscheinlichste Sequenz gewählt und durch alle möglichen Erweiterungen um ein Symbol ersetzt. So entsteht ein optimaler variabel-zu-festlängiger Code, bei dem wahrscheinliche Sequenzen eigene Codewörter erhalten.
Text: 'aabaa' mit P(a)=0.8, P(b)=0.2 Wörterbuchaufbau (3-Bit-Codes): Initial: a, b Erweitere 'a': aa, ab Erweitere 'aa': aaa, aab Erweitere 'ab': aba, abb Endgültiges Wörterbuch (8 Codes): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Kodierung: 'aabaa' → 001 100 (aab + aa)
Tunstall-Codierung ist ein Entropie-Codierverfahren mit variabler Eingabe- und fester Ausgabelänge. Anders als bei Huffman (fest-zu-variabel) ordnet Tunstall Folgen variabler Länge Codewörtern fester Länge zu und ist damit ideal für Anwendungen mit konstantem Ausgaberatenbedarf.
Huffman: feste Eingabe → variable Ausgabe (z. B. 'a' → '0', 'b' → '10'). Tunstall: variable Eingabe → feste Ausgabe (z. B. 'aa' → '000', 'ab' → '001'). Tunstall ist besser für Hardware und Synchronisation geeignet, erreicht aber meist etwas geringere Kompressionsraten.
Man beginnt mit Einzelsymbolen. Dann wiederholt man: 1) Finde die Sequenz mit der höchsten Wahrscheinlichkeit, 2) entferne sie und füge alle möglichen Erweiterungen um ein Symbol hinzu, 3) fahre fort, bis die gewünschte Wörterbuchgröße (2^n für n-Bit-Codes) erreicht ist.
Tunstall-Codierung wird in Sprachkompression, Bildkodierung und überall dort eingesetzt, wo eine feste Bitrate erforderlich ist. Sie ist besonders nützlich in Hardware-Implementierungen und Echtzeitsystemen, in denen variable Codewortlängen das Timing erschweren würden.