// Tunstall-koding â optimal komprimering fra variabel til fast lengde
Mapper sekvenser med variabel lengde til koder med fast lengde.
Ordboken bygges ut fra sannsynlighetsfordelingen til symbolene.
Koder med fast lengde gjør dekoding enkel og rask.
Tunstall-koding bygger opp en ordbok av sekvenser med variabel lengde som mappes til binÌre koder med fast lengde. Man starter med enkeltsymboler og utvider iterativt sekvensen med høyest sannsynlighet ved ü legge til hvert symbol i alfabetet. Resultatet er en optimal variabel-til-fast lengde-kode der mer sannsynlige sekvenser für egne kodeord.
Tekst: 'aabaa' med P(a)=0.8, P(b)=0.2 Ordboksbygging (3-bits koder): Initial: a, b Utvid 'a': aa, ab Utvid 'aa': aaa, aab Utvid 'ab': aba, abb Endelig ordbok (8 koder): aaa â 000 aab â 001 aba â 010 abb â 011 aa â 100 ab â 101 a â 110 b â 111 Koding: 'aabaa' â 001 100 (aab + aa)
Tunstall-koding er en entropikodemetode med variabel inngangslengde og fast utgangslengde. I motsetning til Huffman (fast til variabel) mapper Tunstall sekvenser med variabel lengde til kodeord med fast lengde, noe som er ideelt for applikasjoner som krever 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 for maskinvare og synkronisering, men gir vanligvis noe lavere kompresjonsgrad.
Start med enkeltsymboler. Gjenta: 1) finn sekvensen med høyest sannsynlighet, 2) fjern den og legg til alle mulige utvidelser med ett symbol, 3) fortsett til ønsket ordbokstørrelse (2^n for nâbits koder) er nĂĽdd.
Tunstall-koding brukes i tale-komprimering, bildekoding og andre situasjoner der man trenger fast utdatahastighet. Den er sÌrlig nyttig i maskinvareimplementasjoner og sanntidssystemer der variable kodelengder gjør timing vanskelig.