Perché la Strategia Greedy è Ottimale
L'algoritmo di Huffman è un algoritmo greedy: ad ogni passo, effettua la scelta localmente ottimale (unisce i due nodi più economici) senza guardare avanti. Gli algoritmi greedy non sono sempre globalmente ottimali; ma qui lo sono.
L'Argomento dell'Ottimalità
Supponiamo che un codice C abbia lunghezza media minima L. Considera i due simboli con la probabilità più bassa, diciamo p_a e p_b. In qualsiasi codice ottimale, questi due simboli devono apparire come foglie fratello al livello più profondo dell'albero. Perché?
Se non condividessero un genitore, potresti scambiare il simbolo più profondo con un codice più breve: questo riduce L. Quindi le foglie più profonde devono essere i simboli meno probabili.
Ora, se combini a e b in un meta-simbolo ab (con p_ab = p_a + p_b), qualsiasi codice ottimale per l'alfabeto ridotto meno un simbolo è precisamente il codice di Huffman sul problema ridotto. L'induzione completa l'argomento.
Vista Geometrica
L'algoritmo di Huffman costruisce l'albero binario dal basso verso l'alto, posizionando i simboli meno probabili alla massima profondità. Questo minimizza Σ p_i · depth(i) = L.
Una vista equivalente: stai assegnando etichette alle foglie dell'albero per minimizzare la lunghezza del percorso ponderato, dove il peso di ogni foglia è la sua probabilità.
Esecuzione dei Passi Greedy
Probabilità: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Somma = 1.0 ✓
Passo 1: I due più bassi: C(0.2), D(0.1). Unisci → CD(0.3). Lista: A(0.4), B(0.3), CD(0.3).
Passo 2: I due più bassi: B(0.3), CD(0.3) (parità; entrambi validi). Unisci → BCD(0.6). Lista: A(0.4), BCD(0.6).
Passo 3: Unisci A(0.4), BCD(0.6) → radice(1.0). Assegna A=0, BCD=1.
Indietro: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 bit.
Varianza della Lunghezza del Codice
Due codici di Huffman possono raggiungere la stessa L ma avere distribuzioni diverse delle lunghezze dei codici. La varianza delle lunghezze dei codici misura questo spread:
Var(l) = E[l²] − (E[l])²
dove E[l] = L (lunghezza media del codice) e E[l²] = Σ p_i · l_i².
Perché la varianza importa:
1. Requisiti di buffer. Nella decodifica in tempo reale, ogni simbolo richiede un numero variabile di bit. Alta varianza significa che alcuni simboli richiedono molti bit; hai bisogno di un buffer di input più grande per garantire di poter sempre leggere un simbolo completo.
2. Latenza di decodifica. I codici ad alta varianza hanno percorsi di decodifica lunghi nel caso peggiore. I codici a bassa varianza (ramificati) limitano il caso peggiore più strettamente.
3. Robustezza. Un bit perso in un codice ad alta varianza causa più danni alla sincronizzazione poiché le codeword lunghe devono essere completamente rilegge.
Raccomandazione di Hamming: quando esistono più codici di Huffman validi (scelte di rottura dei legami), preferisci quello con varianza inferiore; l'albero ramificato.
Calcolo della Varianza per Due Alberi
Usando p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 e il codice A=0, B=10, C=110, D=111:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
Codice di Huffman a 3 Simboli da Capo a Fondo
Un esempio completo da capo a fondo: costruisci il codice di Huffman, calcola L, calcola H, verifica L ≥ H, calcola Var.
Fonte: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Costruzione di Huffman:
Passo 1: Ordinato: X(0.6), Y(0.3), Z(0.1). I due più bassi: Y(0.3), Z(0.1).
Unisci → YZ(0.4). Lista: X(0.6), YZ(0.4).
Passo 2: Unisci X(0.6), YZ(0.4) → radice(1.0). Assegna X=0, YZ=1.
YZ → Y=10, Z=11.
Codice: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 bit.
Entropia: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 bit.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8.1% sopra l'entropia.
Varianza: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
Il Tuo Turno: Una Pipeline Completa
Valori log₂ per riferimento: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.