In questo articolo vengono descritti i principi di funzionamento dell’algoritmo di Huffman, ovvero l’algoritmo che sta alla base della maggiorparte dei formati compressi esistenti.
La compressione di Huffman appartiene alla famiglia di algoritmi con lunghezza variabile dei dati compressi. Ossia i singoli simboli (per esempio i caratteri in un file di testo) sono rimpiazzati da sequenze di bit che hanno una lunghezza distinta; quindi ai simboli che appaiono spesso in un file viene assegnata una sequenza molto più bassa dei simboli che appaiono meno spesso.
Esistono diverse implementazioni a livello di codice e di formato, ma il principio su cui il tutto si basa è sempre lo stesso:
Si costruisce una tabella in cui ad ogni simbolo del messaggio originale si associa la sua frequenza, cioè il numero di volte in cui questo simbolo appare nel messaggio da spedire. La tabella si usa più facilmente se è ordinata secondo la frequenza. Esempio: voglio spedire la frase “SOPRA LA PANCA LA CAPRA CAMPA, SOTTO LA PANCA LA CAPRA CREPA”. Ottengo questa tabella di frequenze: (sp è lo spazio, vr e la virgola)
A 16
sp 11
P 7
C 6
L 4
R 4
O 3
N 2
S 2
T 2
E 1
vr 1
M 1
Si considerano i due simboli meno frequenti (vr e M) e si raggruppano in un unico simbolo del quale si introduce in tabella la SOMMA delle due frequenze. Si associa un bit zero al primo simbolo considerato, un bit 1 al secondo e si riordina la tabella delle frequenze. Abbiamo quindi:
codici tabella
Huff frequenze
A A 16
sp sp 11
P P 7
C C 6
L L 4
R R 4
O O 3
N N 2
S S 2
T T 2
E (vr-M 2)
vr (0) E 1
M (1)
Nota: fra parentesi i bit aggiunti a questo passaggio e il nuovo simbolo
Si considerano ancora i due simboli meno frequenti, in questo caso vrM di freq 2 ed E di freq 1. Si raggruppano in un unico gruppo di freq 3, aggiungendo il bit 0 a tutti i simboli del primo gruppo (vr e M), e un bit 1 a tutti i simboli del secondo gruppo (la E). Si ottiene:
codici tabella
Huff frequenze
A A 16
sp sp 11
P P 7
C C 6
L L 4
R R 4
O O 3
N (vrM-E 3)
S N 2
T S 2
E (1) T 2
vr (0)0
M (0)1
Ora i gruppi da considerare sono S e T:
A A 16
sp sp 11
P P 7
C C 6
L L 4
R R 4
O (S-T 4)
N O 3
S (0) vrME 3
T (1) N 2
E 1
vr 00
M 01
e così via fino ad ottenere un gruppo solo:
A A 16
sp sp 11
P P 7
C C 6
L (vrME-N 5)
R L 4
O R 4
N (1) ST 4
S 0 O 3
T 1
E (0)1
vr (0)00
M (0)01
A A 16
sp sp 11
P P 7
C (ST-O 7)
L C 6
R vrMEN 5
O (1) L 4
N 1 R 4
S (0)0
T (0)1
E 01
vr 000
M 001
A A 16
sp sp 11
P (L-R 8)
C P 7
L (0) STO 7
R (1) C 6
O 1 vrMEN 5
N 1
S 00
T 01
E 01
vr 000
M 001
A A 16
sp sp 11
P (C-vrMEN 11)
C (0) LR 8
L 0 P 7
R 1 STO 7
O 1
N (1)1
S 00
T 01
E (1)01
vr (1)000
M (1)001
A A 16
sp (P-STO 14)
P (0) sp 11
C 0 CvrMEN 11
L 0 LR 8
R 1
O (1)1
N 11
S (1)00
T (1)01
E 101
vr 1000
M 1001
A (CvrMEN-LR 19)
sp A 16
P 0 PSTO 14
C (0)0 sp 11
L (1)0
R (1)1
O 11
N (0)11
S 100
T 101
E (0)101
vr (0)1000
M (0)1001
A (PSTO-sp 25)
sp (1) CvrMEN-LR 19
P (0)0 A 16
C 00
L 10
R 11
O (0)11
N 011
S (0)100
T (0)101
E 0101
vr 01000
M 01001
A (1) (CvrMENLR-A 35)
sp 1 PSTOsp 25
P 00
C (0)00
L (0)10
R (0)11
O 011
N (0)011
S 0100
T 0101
E (0)0101
vr (0)01000
M (0)01001
A (0)1 (CvrMENLRA-PSTOsp 60)
sp (1)1
P (1)00
C (0)000
L (0)010
R (0)011
O (1)011
N (0)0011
S (1)0100
T (1)0101
E (0)00101
vr (0)001000
M (0)001001
Fine del procedimento, il codice di Huffman è:
A 01
sp 11
P 100
C 0000
L 0010
R 0011
O 1011
N 00011
S 10100
T 10101
E 000101
vr 0001000
M 0001001
Si notano alcune cose importanti:
- i simboli più frequenti si codificano con sequenze di bit più corte, con evidente risparmio di spazio.
- la frequenza totale dell’ultimo gruppo trovato è 60, uguale alla somma delle frequenze iniziali (ovvio, ma serve per verifica)
- il codice generato non è l’unico che si poteva generare, infatto ad ogni passaggio la scelta di associare ai due gruppi 0 e 1 oppure 1 e 0 non fa cambiare la lunghezza finale dei simboli
- la lunghezza media del codice generato si calcola moltiplicando le frequenze per le lunghezze generate, sommando il tutto e dividendo per la frequenza totale
sorg Huffman lunghezza frequenza calcolo
A 01 2 16 16x2 = 32
sp 11 2 11 11x2 = 22
P 100 3 7 7x3 = 21
C 0000 4 6 6x4 = 24
L 0010 4 4 4x4 = 16
R 0011 4 4 4x4 = 16
O 1011 4 3 4x3 = 12
N 00011 5 2 5x2 = 10
S 10100 5 2 5x2 = 10
T 10101 5 2 5x2 = 10
E 000101 6 1 6x1 = 6
vr 0001000 7 1 7x1 = 7
M 0001001 7 1 7x1 = 7
-------
tot 193 / 60 =
bit per simbolo 3.216
La frase di partenza deve essere codificata sostituendo ad ogni simbolo la sequenza di bit di Huffman, poi impacchettata a byte e memorizzata. Si ottengono 193 bit, cioè 17 byte invece dei 60 di partenza. Huffman è molto più efficace su distribuzioni di frequenza molto disomogenee, cioè con pochi simboli a frequenza alta e tanti simboli a frequenza bassa. Se la distribuzione è troppo omogenea può diventare addirittura più lungo dell’originale. Importante memorizzare insieme al messaggio codificato anche la tabella di conversione!
Per tramutare tutta questa teoria in codice, ho allegato una utility che comprime i files utilizzando il metodo di Huffman. L’algoritmo originale è stato scritto da HatemMostafa ed è una dimostrazione molto chiara del metodo sopra descritto. Il codice è molto ben commentato per facilitarne al massimo la comprensione; non è compatibile con altri compressori/archiviatori.