// Tunstall-kodning – optimal komprimering från variabel till fast längd
Mappar sekvenser med variabel längd till koder med fast längd.
Ordboksbaserad kodning där ordlistan byggs från symbolernas sannolikhetsfördelning.
Koder med fast längd gör avkodningen enkel och snabb.
Tunstall‑kodning bygger upp en ordlista över sekvenser med variabel längd som mappas till binära koder med fast längd. Man börjar med enskilda symboler och utökar iterativt den mest sannolika sekvensen genom att lägga till varje symbol i alfabetet. Resultatet är en optimal variabel‑till‑fast‑kodsättning där mer sannolika sekvenser får egna kodord.
Text: 'aabaa' med P(a)=0.8, P(b)=0.2 Uppbyggnad av ordlista (3‑bits koder): Initialt: a, b Utöka 'a': aa, ab Utöka 'aa': aaa, aab Utöka 'ab': aba, abb Slutlig ordlista (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 är en entropikodningsmetod där indata har variabel längd och utdata har fast längd. Till skillnad från Huffman‑kodning (fast→variabel) mappar Tunstall sekvenser med variabel längd till kodord med fast längd, vilket är idealiskt när man behöver en konstant bithastighet.
Huffman: fast indata → variabel utdata (t.ex. 'a' → '0', 'b' → '10'). Tunstall: variabel indata → fast utdata (t.ex. 'aa' → '000', 'ab' → '001'). Tunstall är bättre för maskinvara och synkronisering, men ger vanligtvis något lägre kompressionsgrad.
Man börjar med enskilda symboler. Sedan upprepar man: 1) hittar sekvensen med högst sannolikhet, 2) tar bort den och lägger till alla möjliga utökningar med ett symbol, 3) fortsätter tills önskad ordlistestorlek (2^n för n‑bits kod) uppnås.
Tunstall‑kodning används i röstkomprimering, bildkodning och andra sammanhang där man behöver fast utdatahastighet. Den är särskilt användbar i maskinvaruimplementationer och realtidssystem där koder med variabel längd skulle göra tidsstyrningen mer komplex.