// Codifica Tunstall – compressione ottimale da variabile a lunghezza fissa
Mappa sequenze di lunghezza variabile in codici a lunghezza fissa.
Il dizionario è costruito usando la distribuzione di probabilità dei simboli.
I codici a lunghezza fissa consentono una decodifica semplice e veloce.
La codifica Tunstall costruisce un dizionario di sequenze a lunghezza variabile che vengono mappate in codici binari a lunghezza fissa. Partendo da simboli singoli, estende iterativamente la sequenza con probabilità maggiore aggiungendo ogni simbolo dell'alfabeto. Si ottiene così un codice variabile-a-fisso ottimale in cui le sequenze più probabili hanno i propri codeword.
Testo: 'aabaa' con P(a)=0.8, P(b)=0.2 Costruzione del dizionario (codici a 3 bit): Iniziale: a, b Espandi 'a': aa, ab Espandi 'aa': aaa, aab Espandi 'ab': aba, abb Dizionario finale (8 codici): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Codifica: 'aabaa' → 001 100 (aab + aa)
La codifica Tunstall è un metodo di codifica entropica da variabile a lunghezza fissa. A differenza di Huffman (fisso a variabile), Tunstall mappa sequenze di lunghezza variabile in codeword a lunghezza fissa, risultando ideale per applicazioni che richiedono un flusso in uscita a bitrate costante.
Huffman: input fisso → output variabile (es. 'a' → '0', 'b' → '10'). Tunstall: input variabile → output fisso (es. 'aa' → '000', 'ab' → '001'). Tunstall è migliore per hardware e sincronizzazione, ma in genere ottiene rapporti di compressione leggermente inferiori.
Si parte da simboli singoli. Poi si ripete: 1) trovare la sequenza con probabilità più alta, 2) rimuoverla e aggiungere tutte le estensioni possibili con un simbolo, 3) continuare fino a raggiungere la dimensione di dizionario desiderata (2^n per codici a n bit).
La codifica Tunstall è usata nella compressione vocale, nella codifica di immagini e in scenari che richiedono un'uscita a bitrate fisso. È particolarmente utile in implementazioni hardware e sistemi in tempo reale, dove i codici a lunghezza variabile complicherebbero la temporizzazione.