// Tunstall-kodning – optimal variabel-til-fasts længde-komprimering
Mapper sekvenser med variabel længde til koder med fast længde.
Ordbogen bygges ud fra symbolernes sandsynlighedsfordeling.
Koder med fast længde gør dekodning enkel og hurtig.
Tunstall-kodning bygger en ordbog af sekvenser med variabel længde, som maps til binære koder med fast længde. Man starter med enkelte symboler og udvider iterativt den mest sandsynlige sekvens ved at tilføje hvert symbol i alfabetet. Resultatet er en optimal variabel-til-fast længde-kode, hvor de mest sandsynlige sekvenser får deres egne kodeord.
Tekst: 'aabaa' med P(a)=0.8, P(b)=0.2 Ordbogsopbygning (3-bit koder): Initial: a, b Udvid 'a': aa, ab Udvid 'aa': aaa, aab Udvid 'ab': aba, abb Endelig ordbog (8 koder): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Kodning: 'aabaa' → 001 100 (aab + aa)
Tunstall-kodning er en entropikodningsmetode med variabel-til-fast længde. I modsætning til Huffman (fast-til-variabel) mapper Tunstall sekvenser af variabel længde til kodeord med fast længde, hvilket gør den ideel til applikationer der kræver konstant bitrate.
Huffman: fast input → variabel output (f.eks. 'a' → '0', 'b' → '10'). Tunstall: variabel input → fast output (f.eks. 'aa' → '000', 'ab' → '001'). Tunstall er bedre til hardware og synkronisering, men opnår typisk lidt lavere komprimeringsgrad.
Start med enkelte symboler. Gentag: 1) Find sekvensen med højest sandsynlighed, 2) Fjern den og tilføj alle mulige forlængelser med ét symbol, 3) Fortsæt indtil den ønskede ordbogs-størrelse (2^n for n-bit koder) er nået.
Tunstall-kodning bruges i tale-komprimering, billedkodning og situationer hvor der kræves fast bitrate. Den er særligt nyttig i hardware-implementeringer og realtids-systemer, hvor koder med variabel længde ville gøre tidsstyring vanskelig.