Math
Codice di Huffman
Una coda ordinata di frequenze diventa un albero di codici prefisso. Seleziona un simbolo per seguirne i bit e le unioni.
Cosa succede
Ogni passo unisce i due pesi minori. I rami 0 e 1 formano il codice dalla radice al simbolo. Selezionando una lettera si evidenzia il suo percorso. L è la lunghezza media del codice e H è l’entropia. Huffman minimizza L tra i codici prefisso binari dei singoli simboli anche quando L > H. L’uguaglianza vale per probabilità 2^(-k). Il conteggio dei bit esclude la tabella dei codici e le intestazioni.
Equazioni del modulo
Equazioni costruzione: si fondono i due nodi più leggeri, n−1 volte; il codice di un simbolo è il suo cammino dalla radice, sinistra 0, destra 1 L = Σ p(i)·l(i) (bit per simbolo); H = −Σ p(i)·log₂ p(i); la lunghezza del codice l(i) è la profondità della foglia Kraft: ogni codice prefisso ha Σ 2^(−l(i)) ≤ 1, e ogni vettore così è un albero; l'albero di Huffman è pieno, quindi la somma è esattamente 1 H ≤ L < H + 1 sempre; L = H esattamente quando ogni p(i) è una potenza di due l'ottimalità è verificata con una ricerca su TUTTI i vettori di lunghezze ammissibili per Kraft - la ricerca non sa nulla dell'algoritmo frequenze uguali: 2(n − 2^k) simboli ricevono il codice lungo, dove 2^k è la più grande potenza di due sotto n le frequenze di Fibonacci 1, 1, 2, 3, 5, … danno l'albero più sbilanciato: lunghezze n−1, n−1, n−2, …, 1
