> huffman | codifica | ottimale <
// Codifica Huffman - algoritmo di compressione ottimale senza prefisso
>> funzionalità
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.