> tunstall | variabel | fast <
// Tunstall-kodning – optimal variabel-til-fasts længde-komprimering
V2F-kodning
Mapper sekvenser med variabel længde til koder med fast længde.
Sandsynlighedsbaseret
Ordbogen bygges ud fra symbolernes sandsynlighedsfordeling.
Nem dekodning
Koder med fast længde gør dekodning enkel og hurtig.
>> tekniske detaljer
Hvordan Tunstall-kodning virker:
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.
Tunstall-eksempel:
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)
Hvorfor bruge Tunstall-kodning?:
- ▸Uddata med fast længde
- ▸Simpel implementering af dekoder
- ▸Ingen synkroniseringsproblemer
- ▸Velegnet til hardware-implementering
- ▸Optimal for hukommelsesløse kilder
>> ofte stillede spørgsmål
Hvad er Tunstall-kodning?
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.
Tunstall vs. Huffman-kodning?
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.
Hvordan bygges ordbogen?
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.
Hvor bruges Tunstall-kodning?
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.