Codifica di Huffman


Wikipedia: Huffman
La codifica di Huffman è il sistema ottimale per codificare stringhe basato sulla frequenza relativa di ciascun carattere.
Esso è stato sviluppato nel 1952 da David A. Huffman, uno studente dottorando presso il MIT.

Produce un codice senza prefissi che esprime il carattere più frequente nella maniera più breve possibile...

Se il numero di simboli è una potenza di 2 e se i simboli hanno distribuzione uniforme allora produce una semplice codifica a blocchi binari.

Algoritmo

Si usa un albero binario costruito in pochi e semplici passi
  1. ordina i simboli in base alla frequenza relativa nel messaggio
  2. ogni simbolo diventa una foglia di un albero binario
  3. combina i due nodi con la frequenza più bassa impostandone uno come ramo di sinistra e l'altro come ramo di destra e somma le due frequenze
  4. continua ... finché ottieni un solo nodo radice con frequenza 1
  5. associa il simbolo "0" ai rami a sinistra e il simbolo "1" ai rami a destra
  6. ogni simbolo sarà rappresentato dalla sequenza binaria dalla radice al simbolo.

Esempio

Sia
m="ABBAINO ABBA BARABBA" (20 caratteri, 7 simboli diversi)

Con una semplice codifica binaria sono sufficienti blocchi di 3 bit (piuttosto che 8 ASCII...)
ASCII3 BIT
B01000010000
A01000001001
00100000010
I01001001011
O01001111100
N01001110101
R01010001110

e il messaggio originale diventa
ABBAINO ABBA BARABBA
001000000001101011100010001000000010010000001110001000000001

quindi
m'=001000000001101011100010001000000010010000001110001000000001

Applico la codifica di Huffman Costruisco l'albero
Huffman 1
aggiungo le etichette ai rami
Huffman 2
Il codice corrispondente è
B0
A10
110
I11100
O11101
N11110
R11111


Il messaggio originale diventa
ABBAINO ABBA BARABBA
10001011100111101110111010001011001011111100010

quindi
m''=10001011100111101110111010001011001011111100010

Confronta le lunghezze dei messaggi
ASCIIBlocchi
binari
Codifica di
Huffman
Lunghezza1606047
Bit per carattere8347/20
2.35

Se la stessa sorgente trasmette il messaggio "ABBAIA" allora diventa
ABBAIA
1000101110010

quindi
m''=1000101110010

Confronta le lunghezze dei messaggi
ASCIIBlocchi
binari
Codifica di
Huffman
Lunghezza481813
Bit per carattere8313/6
2.16...


In effetti la lunghezza media dei messaggi codificati secondo il codice precedente sarà
pcodicelp*l
B7/2001(7/20)*1
A7/20102(7/20)*2
2/201103(2/20)*3
I1/20111005(1/20)*5
O1/20111015(1/20)*5
N1/20111105(1/20)*5
R1/20111115(1/20)*5
Lunghezza media47/20
2.35

There are no comments on this page.
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki