Come Huffman Costruisce il Codice Ottimale
Hamming presenta la codifica di Huffman come un algoritmo greedy che costruisce un codice senza prefissi a lunghezza media minima. L'idea chiave: costruire l'albero dal basso verso l'alto, sempre fondendo i due simboli meno probabili.
La Fase Forward (Costruire)
1. Ordinare tutti i simboli per probabilità, dal più alto al più basso.
2. Prendere i due simboli con la probabilità più bassa. Combinarli in un nuovo meta-simbolo con probabilità = somma dei due.
3. Inserire il meta-simbolo nella sua posizione ordinata.
4. Ripetere fino a quando rimangono solo due simboli.
5. Assegnare 0 e 1 ai due simboli rimanenti.
La Fase Backward (Assegnare Codici)
Annullare le fusioni in ordine inverso: ad ogni divisione, i due simboli che sono stati fusi ricevono gli stessi bit di prefisso del loro genitore combinato, più uno 0 aggiuntivo (un figlio) o 1 (l'altro figlio). L'assegnazione 0/1 è arbitraria — entrambi sono validi.
Perché questo è ottimale: se qualsiasi altro codice avesse una lunghezza media più piccola L', applicando la stessa riduzione forward alla fine si produrrebbero due simboli con lunghezza media inferiore a 1 bit — impossibile per un codice a 2 simboli. Contraddizione.
Tracciamento dell'Algoritmo
Esempio da Hamming: quattro simboli A, B, C, D con p(A)=0,5, p(B)=0,25, p(C)=0,125, p(D)=0,125.
Fase forward:
Passaggio 1: Ordinato: A(0,5), B(0,25), C(0,125), D(0,125). Due più bassi: C, D.
Passaggio 2: Fondere CD con p=0,25. Nuova lista: A(0,5), B(0,25), CD(0,25).
Passaggio 3: Due più bassi: B(0,25), CD(0,25). Fondere BCD con p=0,5.
Passaggio 4: Rimangono due simboli: A(0,5), BCD(0,5). Assegnare A=0, BCD=1.
Fase backward:
BCD → B riceve 10, CD riceve 11. CD → C riceve 110, D riceve 111.
Codice finale: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0,5·1 + 0,25·2 + 0,125·3 + 0,125·3 = 1,75 bit.
Codici Huffman Validi Multipli
Hamming nota due fonti di non-unicità:
1. Assegnazione arbitraria di 0/1. Ad ogni divisione, puoi assegnare 0 a uno qualsiasi dei figli. Scambiare 0 e 1 in tutto dà un codice diverso con L identico.
2. Tie-breaking. Quando due nodi hanno probabilità uguale, uno qualsiasi può essere posizionato 'più in alto' (fuso per primo). Diverse scelte di tie-breaking possono produrre alberi strutturalmente diversi — 'lunghi' vs 'cespugliosi' — con la stessa L ma diverse distribuzioni di lunghezza del codice.
Lungo vs Cespuglioso
Albero lungo (inclinato): un simbolo ad ogni livello di profondità (struttura simile a Fibonacci). Le lunghezze dei codici variano notevolmente: un simbolo riceve un codice breve, altri si estendono a codici più lunghi.
Albero cespuglioso (bilanciato): simboli distribuiti uniformemente su diversi livelli di profondità. Le lunghezze dei codici si raggruppano vicino alla media. Varianza più bassa.
La raccomandazione di Hamming: quando dato una scelta, preferisci l'albero cespuglioso. Stessa L, ma varianza più piccola nelle lunghezze dei codici → tempo di decodifica più uniforme → requisiti di buffer più piccoli nelle applicazioni in tempo reale.
Calcolo della Varianza della Lunghezza del Codice
Varianza della lunghezza dei codici: Var = E[l²] − (E[l])²
Per il codice {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} con p=[0,5, 0,25, 0,125, 0,125]:
E[l] = L = 1,75
E[l²] = 0,5·1² + 0,25·2² + 0,125·3² + 0,125·3² = 0,5 + 1,0 + 1,125 + 1,125 = 3,75
Var = 3,75 − 1,75² = 3,75 − 3,0625 = 0,6875
Un codice cespuglioso alternativo per simboli equiprobabili usa tutti codici di lunghezza 2: L=2, Var=0.
Guadagni di Compressione vs Distribuzione dei Simboli
La regola di Hamming: la codifica di Huffman conviene solo quando le probabilità dei simboli differiscono sostanzialmente.
Probabilità uguali. Se tutti i simboli 2^k hanno probabilità uguale 1/2^k, Huffman produce un codice a blocchi: ogni simbolo riceve lunghezza k. L = H = k. Nessun guadagno rispetto al semplice codice a blocchi.
Probabilità asimmetriche. Se un simbolo domina (p >> 1/2^k per gli altri), Huffman gli assegna un codice molto breve (lunghezza 1 o 2), riducendo drasticamente L.
Il codice virgola (termine di Hamming). Quando ogni probabilità supera 2/3 del totale rimanente, Huffman naturalmente produce: p(s1)→0, p(s2)→10, p(s3)→110, ..., fino a due codici di uguale lunghezza alla fine. Questo è un 'codice virgola': lo 0 finale dopo una serie di 1 agisce come una virgola.
Hamming nota: la compressione dei dati nel mondo reale (backup, archiviazione di file) può ridurre l'archiviazione di più della metà quando la fonte ha probabilità asimmetriche — il testo in inglese è un esempio principale.
Huffman vs Codice a Blocchi: Confronto Numerico
Il secondo esempio di Hamming: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Codice a blocchi: 8 simboli → 3 bit ciascuno → L_block = 3.
Hamming calcola il codice Huffman e riporta L_Huffman ≈ 2,58 bit.
Risparmio: (3 − 2,58)/3 ≈ 14% compressione rispetto alla codifica a blocchi.
Quando le probabilità dei simboli differiscono notevolmente (1/3 vs 1/30 qui, un rapporto 10:1), la codifica a lunghezza variabile conviene sostanzialmente.
Programmi Auto-Compilanti
Hamming termina il Capitolo 11 con un'idea straordinaria: un encoder Huffman può codificare se stesso. L'albero di decodifica (che dice al decoder come leggere il messaggio compresso) viene trasmesso insieme ai dati compressi. Il ricevente non ha bisogno di conoscenze precedenti del codice.
L'encoder: campiona i dati, stima le probabilità, costruisce il codice Huffman, codifica l'albero di decodifica come intestazione, poi codifica i dati.
Il decoder: legge l'intestazione per ricostruire l'albero, poi decodifica i dati usando.
Il punto di Hamming: l'intera pipeline può funzionare come una funzione di libreria senza alcun coinvolgimento umano. Lo chiami, comprime e decomprime automaticamente. I moderni formati di archiviazione (ZIP, gzip, bzip2) implementano esattamente questo pattern.
Il principio più profondo: l'intelligenza è nell'algoritmo, non in una tabella di codice fissa. L'algoritmo si adatta a qualsiasi dato riceva. Questo è il pattern che Hamming vede in tutti i grandi sistemi di ingegneria: l'adattabilità incorporata, non aggiunta in seguito.