// Tunstall-codering – optimale compressie van variabele naar vaste lengte
Mapt sequenties met variabele lengte naar codes met vaste lengte.
Het woordenboek wordt opgebouwd op basis van de kansverdeling van symbolen.
Codes met vaste lengte maken decoderen eenvoudig en snel.
Tunstall-codering bouwt een woordenboek van sequenties met variabele lengte die worden toegewezen aan binaire codes met vaste lengte. Beginnend met enkele symbolen wordt de meest waarschijnlijke sequentie herhaaldelijk uitgebreid door elk alfabet-symbool toe te voegen. Dit resulteert in een optimale variabel-naar-vast-lengte code waarbij de meest waarschijnlijke sequenties eigen codewoorden krijgen.
Tekst: 'aabaa' met P(a)=0.8, P(b)=0.2 Woordenboekopbouw (3-bit codes): Initieel: a, b Breid 'a' uit: aa, ab Breid 'aa' uit: aaa, aab Breid 'ab' uit: aba, abb Definitief woordenboek (8 codes): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Codering: 'aabaa' → 001 100 (aab + aa)
Tunstall-codering is een entropie-coderingsmethode van variabele naar vaste lengte. In tegenstelling tot Huffman (vast naar variabel) mapt Tunstall sequenties met variabele lengte naar codewoorden met vaste lengte, waardoor het ideaal is voor toepassingen die een constante uitvoersnelheid vereisen.
Huffman: vaste invoer → variabele uitvoer (bijv. 'a' → '0', 'b' → '10'). Tunstall: variabele invoer → vaste uitvoer (bijv. 'aa' → '000', 'ab' → '001'). Tunstall is beter voor hardware en synchronisatie, maar levert meestal iets lagere compressieverhoudingen op.
Begin met enkele symbolen. Herhaal vervolgens: 1) vind de sequentie met de hoogste waarschijnlijkheid, 2) verwijder deze en voeg alle mogelijke uitbreidingen met één symbool toe, 3) ga door tot de gewenste woordenboekgrootte (2^n voor n‑bit codes) is bereikt.
Tunstall-codering wordt gebruikt in spraakcompressie, beeldcodering en situaties waarin een vaste uitvoersnelheid nodig is. Het is vooral nuttig in hardware-implementaties en realtime systemen waar codes met variabele lengte de timing ingewikkeld maken.