Sapevi che ogni volta che apri un file ZIP o guardi una foto JPEG stai usando un’intuizione matematica del 1952? 🤯
L’algoritmo di Huffman è il “motore invisibile” che ci permette di rimpicciolire i file e risparmiare giga preziosi.
Nel nostro nuovo articolo spieghiamo come funziona in modo semplice (niente paroloni!), con un esempio pratico passo-passo e il codice Python per testarlo. 👇
Esercizio – Codifica di Huffman (Medio/Difficile)
Testo
Devi comprimere un messaggio di testo assegnando a ogni carattere un codice binario (sequenza di [math]0[/math] e [math]1[/math]) in modo che la lunghezza totale del messaggio codificato sia minima. I codici devono essere prefissi (nessun codice è prefisso di un altro). Conoscendo le frequenze dei caratteri, costruisci l’albero di Huffman e genera i codici.
Esempio
Frequenze: [math]A:5[/math], [math]B:2[/math], [math]C:1[/math], [math]D:1[/math] Albero: unione di [math]C[/math] e [math]D[/math] ([math]2[/math]), poi unione con [math]B[/math] ([math]4[/math]), poi con [math]A[/math] ([math]9[/math]). Codici: [math]A:0[/math], [math]B:10[/math], [math]C:110[/math], [math]D:111[/math] (o simmetrici).
Algoritmo di Huffman: l’arte di risparmiare bit
Immagina di dover preparare la valigia per un lungo viaggio. Se dovessi pagare una tassa per ogni centimetro cubo di spazio occupato, probabilmente metteresti a portata di mano i vestiti che usi tutti i giorni, piegandoli il meglio possibile, mentre terresti in fondo quelli che indosserai solo una volta.
La compressione dei dati funziona esattamente così. Ogni volta che inviamo una foto, ascoltiamo musica in streaming o apriamo un file ZIP, un meccanismo silenzioso “impacchetta” le informazioni per non intasare la banda. L’algoritmo di Huffman è il motore di questa magia: un sistema elegante che rimpicciolisce i file senza perdere nemmeno un dettaglio.
L’idea: perché usare lunghezze diverse?
Normalmente, i computer assegnano a ogni carattere lo stesso numero di bit (lunghezza fissa). Ma in un testo, non tutte le lettere appaiono con la stessa frequenza. L’algoritmo di Huffman rompe questa monotonia: assegna codici brevissimi ai simboli frequenti e codici più lunghi a quelli rari.
Il “trucco” dei codici prefisso
Se usiamo lunghezze diverse, come fa il computer a capire quando finisce una lettera? Se [math]A=0[/math] e [math]B=01[/math], la sequenza [math]01[/math] è una “B” o una “A” seguita da qualcos’altro?
Huffman risolve il problema creando codici prefisso: nessun codice è l’inizio di un altro. Questo garantisce che la lettura dei bit sia fluida e priva di errori.
Esempio 1 (didattico): “ABAACDAB”
Prendiamo il messaggio “ABAACDAB” ([math]8[/math] caratteri). Contiamo le frequenze:
[math]A: 4[/math] volte
[math]B: 2[/math] volte
[math]C: 1[/math] volta
[math]D: 1[/math] volta
Costruiamo l’albero
L’algoritmo lavora come un sarto, unendo i pezzi più piccoli:
Unisci i minimi: Prendiamo [math]C (1)[/math] e [math]D (1)[/math] e creiamo un nodo “X” da [math]2[/math].
Passo successivo: Uniamo [math]B (2)[/math] con il nodo [math]X (2)[/math], ottenendo un nodo “Y” da [math]4[/math].
Chiusura: Uniamo [math]A (4)[/math] con il nodo [math]Y (4)[/math]. La radice finale vale [math]8[/math].
Seguendo i rami (Sinistra = [math]0[/math], Destra = [math]1[/math]), otteniamo i codici:
[math]A: 0[/math] ([math]1[/math] bit)
[math]B: 10[/math] ([math]2[/math] bit)
[math]C: 110[/math] ([math]3[/math] bit)
[math]D: 111[/math] ([math]3[/math] bit)
Il risparmio reale
In un sistema standard a [math]4[/math] simboli, useremmo [math]2[/math] bit fissi per ogni lettera ([math]8 \text{ caratteri} \times 2 = 16 \text{ bit}[/math]).
Abbiamo risparmiato il [math]12.5\%[/math] dello spazio. Su file di grandi dimensioni, questo risparmio diventa enorme.
Perché è un algoritmo greedy?
A ogni passo, l’algoritmo fa una scelta localmente ottima: unisce i due alberi con frequenza minore. Questa strategia porta alla soluzione globalmente ottima tra tutte le codifiche a prefisso (lunghezza media minima).
Huffman è ottimo perché soddisfa la proprietà di optimal substructure: l’albero ottimale contiene come sottoalberi ottimali gli alberi costruiti per i simboli meno frequenti.
Applicazioni reali
Compressione file: molti formati (come ZIP) lo usano.
Immagini JPEG: codifica i coefficienti finali.
Audio MP3: comprime le frequenze dei campioni.
Domanda: Cosa succederebbe se tutti i simboli avessero la stessa frequenza?
L’albero diventerebbe bilanciato e i vantaggi della compressione variabile sparirebbero.
Soluzione dell’esercizio principale
Implementazione:
Prima di guardare l’implementazione, è utile avere una “mappa mentale” di quello che sta succedendo dietro le quinte.
Heap (coda con priorità) È una struttura dati che ci permette di recuperare velocemente i due elementi con frequenza minima. In pratica, è come avere sempre sotto mano i due “pezzi più piccoli” da unire.
Nodo dell’albero Ogni nodo rappresenta un blocco di informazione:
una foglia contiene un carattere (es. A, B, C…)
un nodo interno rappresenta l’unione di due nodi più piccoli e contiene solo la somma delle loro frequenze
Ciclo while (il cuore dell’algoritmo) Ad ogni iterazione:
estraiamo i due nodi con frequenza più bassa
li uniamo in un nuovo nodo
reinseriamo il nuovo nodo nell’heap
Questo processo continua finché non resta un solo nodo: 👉 la radice dell’albero di Huffman
defhuffman(frequenze):# frequenze è un dict {carattere: frequenza}
heap =[Nodo(freq, sim)for sim, freq in frequenze.items()]
heapq.heapify(heap)whilelen(heap)>1:# estrai due minimi
a = heapq.heappop(heap)
b = heapq.heappop(heap)# crea nodo interno con somma frequenze
nuovo = Nodo(a.freq + b.freq, sinistro=a, destro=b)
heapq.heappush(heap, nuovo)
radice = heap[0]# genera codici con visita
codici ={}defgenera_codici(nodo, codice_corrente=""):if nodo.simbolo isnotNone:# foglia
codici[nodo.simbolo]= codice_corrente
else:
genera_codici(nodo.sinistro, codice_corrente +"0")
genera_codici(nodo.destro, codice_corrente +"1")
genera_codici(radice)return codici
# Test
freq ={'A':5,'B':2,'C':1,'D':1}
codici = huffman(freq)print(codici)
{‘B’: ’00’, ‘C’: ‘010’, ‘D’: ‘011’, ‘A’: ‘1’}
L’algoritmo di Huffman può generare codici diversi a seconda di:
come vengono ordinati i nodi quando hanno la stessa frequenza (nell’heap, l’ordine può variare in base all’implementazione),
come vengono assegnati i bit [math]0[/math] e [math]1[/math] ai rami sinistro e destro dell’albero.
Tutte le varianti sono ottimali, cioè producono la stessa lunghezza media ponderata.
Analisi dell’ output
Con le frequenze: [math]A=5[/math], [math]B=2[/math], [math]C=1[/math], [math]D=1[/math], la lunghezza totale del messaggio codificato è:
[math]A[/math] compare [math]5[/math] volte → [math]5 \times 1 = 5[/math] bit
[math]B[/math] compare [math]2[/math] volte → [math]2 \times 2 = 4[/math] bit
[math]C[/math] compare [math]1[/math] volta → [math]1 \times 3 = 3[/math] bit
[math]D[/math] compare [math]1[/math] volta → [math]1 \times 3 = 3[/math] bit
Totale = [math]5+4+3+3 = 15[/math] bit, che diviso per [math]9[/math] caratteri dà una lunghezza media di 1.667 bit/carattere.
Con l’altra codifica ipotizzata nel testo ([math]A:0[/math], [math]B:10[/math], [math]C:110[/math], [math]D:111[/math]) avremmo esattamente gli stessi numeri ([math]A=1[/math] bit, [math]B=2[/math], [math]C=3[/math], [math]D=3[/math]).
Quindi sono equivalenti.
Perché A ha un codice di un solo bit?
Perché [math]A[/math] è il carattere più frequente ([math]5[/math] occorrenze su [math]9[/math]). L’algoritmo di Huffman tende a dare codici più corti ai simboli con frequenza maggiore, e qui la frequenza di [math]A[/math] è così dominante che viene messo direttamente come figlio della radice.
Se vuoi verificare la struttura dell’albero che ha generato questi codici, ecco una possibile ricostruzione:
Unisci [math]C[/math] e [math]D[/math] (freq [math]1+1=2[/math]) → nodo [math]X[/math]
L’immagine mostra chiaramente come l’algoritmo di Huffman organizzi i dati in modo gerarchico basandosi sulla frequenza. Ecco i punti chiave per interpretare correttamente lo schema:
La Gerarchia dei Nodi:
Foglie (A, B, C, D): Sono i caratteri originali. Nota come più bassa è la frequenza (numeri tra parentesi), più il nodo è lontano dalla radice.
Nodi Interni (X, Y): Rappresentano le unioni intermedie. Il nodo [math]X[/math] unisce [math]C[/math] e [math]D[/math] ([math]1+1=2[/math]), mentre [math]Y[/math] unisce [math]B[/math] e [math]X[/math] ([math]2+2=4[/math]).
Radice (9): Rappresenta il messaggio completo, con la somma totale delle frequenze.
Assegnazione dei Bit:Il percorso dalla Radice alla foglia determina il codice binario:
Seguendo il ramo [math]1[/math] a destra, arriviamo subito ad [math]A[/math]. Codice: 1.
Per arrivare a [math]B[/math], andiamo a sinistra ([math]0[/math]) e poi ancora a sinistra ([math]0[/math]). Codice: 00.
Per [math]C[/math], il percorso è sinistra-destra-sinistra ([math]0 \to 1 \to 0[/math]). Codice: 010.
Efficienza Visiva:Si nota immediatamente lo sbilanciamento dell’albero verso destra. Questo non è un errore, ma il motivo del successo di Huffman: il carattere [math]A[/math], essendo il più frequente, occupa il livello più alto possibile (livello 1), garantendo che la maggior parte del messaggio pesi solo [math]1[/math] bit per carattere.
Questo albero conferma la proprietà dei codici prefisso: non puoi arrivare a nessuna foglia “passando attraverso” un’altra. Una volta raggiunta una lettera, il percorso termina, eliminando ogni ambiguità nella decodifica.
Domanda bonus
Quale sarebbe la lunghezza media se invece usassimo un codice a lunghezza fissa (es. [math]2[/math] bit per carattere)?
Con un codice a lunghezza fissa di [math]2[/math] bit, ogni carattere viene rappresentato con esattamente [math]2[/math] bit, indipendentemente dalla sua frequenza.
Quindi la lunghezza totale del messaggio sarebbe:
Numero totale di caratteri:
[math]5 + 2 + 1 + 1 = 9[/math]
Lunghezza media per carattere:
[math]18 / 9 = 2 \text{ bit}[/math]
Con il codice di Huffman ottenuto ([math]A = \text{‘1′}[/math], [math]B = \text{’00’}[/math], [math]C = \text{‘010’}[/math], [math]D = \text{‘011’}[/math]) la lunghezza totale è:
Risparmio:
[math]\displaystyle
\begin{aligned}
&{} 18 – 15 = 3 \text{ bit} \\
&{} \quad \text{(pari a circa il 16.7 % in meno rispetto} \\
&{} \quad \text{al codice a lunghezza fissa)}
\end{aligned}
[/math]
L’algoritmo di Huffman sfrutta le frequenze per assegnare codici più corti ai caratteri più comuni, riducendo la dimensione complessiva.
💡 Osservazione
La proprietà fondamentale è che i caratteri più frequenti ricevono codici più corti. L’algoritmo è un esempio di greedy in cui a ogni passo si uniscono i due alberi meno frequenti, minimizzando localmente il costo.
Domanda di riflessione
Cosa cambierebbe se tutte le frequenze fossero uguali? Quale sarebbe la lunghezza media dei codici?
Risposta:
Analizziamo cosa succede con Huffman quando le frequenze sono tutte uguali
Caso con [math]n[/math] caratteri di uguale frequenza
Supponiamo di avere [math]n[/math] caratteri, ciascuno con frequenza [math]f[/math] (ad esempio [math]1[/math]). L’algoritmo di Huffman unisce ripetutamente i due nodi con frequenza minore. Poiché all’inizio tutti hanno la stessa frequenza, l’ordine di unione dipende da come l’heap gestisce i pareggi, ma il risultato finale in termini di lunghezze è determinato.
1. Se [math]n[/math] è una potenza di 2 (es. [math]n = 2^k[/math])
L’albero di Huffman diventa perfettamente bilanciato: tutte le foglie si trovano alla stessa profondità [math]k[/math]. Quindi:
Ogni carattere ha un codice di lunghezza [math]k = \log_2 n[/math].
Lunghezza totale: [math]n \times f \times k[/math].
Lunghezza media: [math]k = \log_2 n[/math].
Esempio: [math]n = 4[/math] (A, B, C, D con freq [math]1[/math] ciascuno).
L’albero sarà bilanciato: unisci due coppie (es. [math]A+B[/math] e [math]C+D[/math]) ottenendo due nodi di freq [math]2[/math], poi li unisci. Codici possibili: [math]00, 01, 10, 11[/math] (lunghi [math]2[/math]). Lunghezza media: [math]2 = \log_2 4[/math].
2. Se [math]n[/math] non è una potenza di 2
L’albero sarà il più bilanciato possibile, ma alcune foglie avranno profondità [math]\lfloor \log_2 n \rfloor[/math] e altre [math]\lceil \log_2 n \rceil[/math]. La differenza tra le lunghezze sarà al massimo [math]1[/math].
Unisci due a due: [math](1+1)=2, (1+1)=2[/math], resta [math]1[/math].
Poi unisci i due da [math]2[/math]: [math](2+2)=4[/math], resta [math]1[/math].
Infine unisci [math]4+1=5[/math].
Calcolo Lunghezza Media:
I codici risultanti avranno lunghezze: tre caratteri lunghi [math]3[/math] e due caratteri lunghi [math]2[/math] (o viceversa).
[math]\displaystyle \text{Media} = (3 \times 3 + 2 \times 2) / 5 = (9 + 4) / 5 = 2.6 \text{ bit}[/math]
Confronto con codice a lunghezza fissa: servirebbero [math]3[/math] bit per rappresentare [math]5[/math] simboli (poiché [math]2^2 = 4[/math] non basta), lunghezza media fissa = [math]3[/math] bit. Huffman risparmia [math]0.4[/math] bit a carattere.
Formula generale
Per [math]n[/math] caratteri equiprobabili, la lunghezza media del codice di Huffman è compresa tra [math]\lfloor \log_2 n \rfloor[/math] e [math]\lceil \log_2 n \rceil[/math], e tende a [math]\log_2 n[/math] per [math]n[/math] grande.
È il miglior codice a prefisso possibile per simboli equiprobabili, e coincide con un codice a lunghezza fissa solo quando [math]n[/math] è potenza di [math]2[/math].
Nel caso di frequenze tutte uguali, l’algoritmo di Huffman produce essenzialmente un codice a lunghezza variabile che è il più vicino possibile a un codice a lunghezza fissa, ma con un leggero vantaggio quando [math]n[/math] non è potenza di [math]2[/math].
Dal metodo al limite teorico
Finora abbiamo ragionato in modo operativo: abbiamo costruito un algoritmo che funziona e che riduce il numero di bit necessari per rappresentare un messaggio. Ma a questo punto nasce una domanda più profonda:
Quanto possiamo comprimere al massimo?
Esiste un limite oltre il quale non possiamo andare?
La risposta arriva dalla teoria dell’informazione, sviluppata da Claude Shannon. Shannon dimostra che esiste un limite teorico assoluto alla compressione, chiamato entropia.
L’idea chiave dell’entropia
L’entropia misura il “contenuto medio di informazione” di una sorgente.
In termini intuitivi:
Simboli molto frequenti → poca informazione
Simboli rari → molta informazione
La formula è:
[math]\displaystyle H = -\sum p_i \log_2 p_i[/math]
Dove [math]p_i[/math] è la probabilità di ciascun simbolo.
Il punto cruciale
L’algoritmo di Huffman non è solo efficiente: è quasi perfetto.
Infatti:
Costruisce un codice ottimo tra quelli a prefisso.
La lunghezza media del codice è sempre molto vicina all’entropia.
Cosa ancora più importante: non può mai scendere sotto questo limite.
Questo significa che Huffman non è solo un buon algoritmo. È il modo più efficiente possibile di comprimere dati senza violare le leggi fondamentali dell’informazione.
Il “caso perfetto” del nostro esempio
Prendiamo il nostro messaggio di [math]8[/math] caratteri (ABAACDAB). Le probabilità sono:
E qual è la lunghezza media ([math]L[/math]) del nostro codice di Huffman?
[math]\displaystyle L = 14 \text{ bit totali} / 8 \text{ simboli} = \mathbf{1.75 \text{ bit/simbolo}}[/math]
In questo caso specifico, [math]L[/math] è esattamente uguale ad [math]H[/math]. Questo accade perché tutte le nostre frequenze sono potenze di 2. Quando ciò accade, Huffman raggiunge la perfezione assoluta: la compressione massima che le leggi della fisica permettono.
Quando la realtà non è fatta di potenze di 2
Nel nostro esempio precedente, tutto combaciava al millimetro: [math]1.75[/math] bit teorici richiesti, [math]1.75[/math] bit forniti da Huffman. Ma la vita reale è raramente così ordinata.
Cosa succede se un simbolo ha una probabilità di [math]0.3[/math]?
Secondo la formula di Shannon, quel simbolo richiederebbe circa [math]1.73[/math] bit. Tuttavia, i bit sono “indivisibili”: o ne usi [math]1[/math], o ne usi [math]2[/math]. Huffman è costretto ad arrotondare per eccesso alla cifra intera più vicina, creando un piccolo spreco.
È qui che nasce quel “[math]+1[/math]” nella formula [math]H \le L < H + 1[/math]. Quel bit extra è il “prezzo” che paghiamo perché dobbiamo usare codici binari discreti.
Il limite di Huffman: Se le frequenze sono molto sbilanciate ma non sono potenze di [math]2[/math], Huffman perde un po’ di efficienza.
La soluzione avanzata: Per superare questo limite, sono stati inventati algoritmi come la Codifica Aritmetica.
La Codifica Aritmetica non assegna un numero intero di bit a ogni singolo simbolo, ma codifica l’intero messaggio come un unico, lunghissimo numero frazionario. È un approccio molto più complesso, ma permette di scendere ancora più vicino a [math]H[/math].
L’esercizio di Huffman non è quindi solo un rompicapo per programmatori: è la dimostrazione di come possiamo usare la statistica per sfidare lo spazio. Se conosci il tuo nemico (la frequenza dei dati), puoi sconfiggere il volume dei file.
