> huffman | codifica | ottimale <
// Codifica Huffman - algoritmo di compressione ottimale senza prefisso
Codici ottimali
Genera la lunghezza media del codice più breve possibile per le frequenze date.
Senza prefisso
Nessun codice è il prefisso di un altro, garantendo una decodifica non ambigua.
Basato sulle frequenze
I caratteri più frequenti ricevono automaticamente codici più corti.
>> informazioni tecniche
Come funziona la codifica Huffman:
La codifica Huffman costruisce un albero binario dal basso verso l'alto. A partire dalle frequenze dei caratteri, combina ripetutamente i due nodi con frequenza più bassa in un nodo padre finché rimane solo la radice. I rami a sinistra rappresentano '0' e quelli a destra '1'. I caratteri più frequenti ottengono codici più corti, ottenendo così una compressione ottimale per la distribuzione di frequenze data.
Esempio di codifica Huffman:
Text: "AABBBCCCC"
Frequencies:
A: 2
B: 3
C: 4
Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)
Tree:
Root(9)
/ \
C(4) AB(5)
/ \
A(2) B(3)
Codes:
C: 0
A: 10
B: 11
Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000
Perché usare la codifica Huffman:
- ▸Rapporto di compressione quasi ottimale
- ▸Implementazione semplice
- ▸Base della compressione ZIP/JPEG
- ▸Nessuna perdita di dati
- ▸Efficienza dimostrata nella pratica
>> domande frequenti
Che cos'è la codifica Huffman?
La codifica Huffman è un algoritmo di compressione ottimale e privo di prefisso, proposto da David A. Huffman nel 1952. Assegna ai caratteri codici di lunghezza variabile in base alla loro frequenza: i caratteri più frequenti ricevono codici più corti, ottenendo la minima lunghezza media possibile.
Perché si dice che è priva di prefisso?
Un codice è privo di prefisso quando nessun codice è il prefisso di un altro. Ad esempio, se "A" ha il codice "01", nessun altro carattere può avere un codice che inizi con "01". Questa proprietà garantisce una decodifica non ambigua: è sempre chiaro dove termina un codice e dove inizia il successivo, senza separatori aggiuntivi.
Quanto è efficiente la codifica Huffman?
La codifica Huffman raggiunge la compressione ottimale per una data distribuzione di frequenze, in genere entro 1 bit dal limite teorico di entropia. Per testo in inglese si ottengono spesso compressioni del 60–70% ed è particolarmente efficace quando le frequenze dei caratteri differiscono molto.
Dove viene usata la codifica Huffman?
La codifica Huffman è utilizzata nella compressione di immagini JPEG, nella compressione di file ZIP (insieme a LZ77 in DEFLATE), nell'audio MP3 e in molti altri formati. Spesso viene combinata con altri algoritmi: ad esempio JPEG usa Huffman dopo DCT e quantizzazione, mentre ZIP lo applica dopo LZ77.
// Esempio svolto
| Symbol | Freq | Bits | Code |
|---|---|---|---|
| A | 4 | 1 | 0 |
| B | 2 | 2 | 10 |
| C | 1 | 2 | 11 |
// Esempi di codice
Input AAAABBC (7 symbols, 56 bits as 8-bit ASCII) Counts A=4 B=2 C=1 Merge C(1)+B(2) -> node(3); node(3)+A(4) -> root(7) Codes A=0 B=10 C=11 (0/1 on left/right branches; ties may swap) Encoded 0 0 0 0 10 10 11 = 4*1 + 2*2 + 1*2 = 10 bits
>> Altre domande
D: Il codice di Huffman è unico?
R: Non necessariamente. A parità di frequenze, la scelta dei nodi e l’assegnazione di 0 e 1 possono variare. Ma le lunghezze dei codici e la dimensione totale sono ottime e identiche in ogni albero di Huffman corretto.
D: Cosa significa senza prefissi?
R: Nessun codice è l’inizio di un altro. Il flusso di bit si decodifica quindi senza separatori: si seguono i bit dalla radice fino a una foglia.
D: Quando Huffman non è ottimale?
R: Assegna un numero intero di bit per simbolo. Con probabilità molto sbilanciate (es. 0,99) perde efficienza; la codifica aritmetica si avvicina di più all’entropia. Il decodificatore ha inoltre bisogno della tabella dei codici.