CODIFICA ARITMETICA
La codifica aritmetica una tecnica pi sofisticata di quella utilizzata da Huffman. Si
tratta di una codifica che permette la compressione dei dati senza la perdita di
informazioni. Permette di codificare sequenze di simboli e risulta quindi pi efficiente.
La codifica aritmetica assegna dei codici di lunghezza variabile, un intervallo di numeri
reali, ad ogni sequenza di simboli al fine di minimizzare il numero totale di bit da
trasmettere, cio assegna una singola codifica allintero messaggio o a blocchi di
messaggi. Essa in grado di codificare un simbolo anche con valori frazionari di bit.
Esempio
Abbiamo a disposizione quattro simboli: A, B, C e D.
BAABCADBADAACBAAAABDAABACBADCBAA"
Per i seguenti simboli conosciamo le probabilit di verificarsi di ognuno, cio:
A = = 0.5
B = = 0.25
C = 0.125
D = 0.125
A partire dalle probabilit dei simboli, possiamo riportarle tutte in un intervallo unitario.
Lintervallo unitario utilizzato sar e otteniamo la seguente suddivisione:
Per capire meglio:
A B C D
0.5 0.25 0.125 0.125
Simboli Valori Intervalli
A 0.5 [0;0.5) 0 + 0.5 = 0.5
B 0.25 [0.5;0.75) 0.5 + 0.25 = 0.75
C 0.125 [0.75;0.875) 0.75 + 0.125 = 0.875
D 0.125 [0.875;1) 0.875 + 0.125 = 1
Lobiettivo quello di codificare i primi quattro simboli del messaggio seguente:
BAABCADBADAACBAAAABDAABACBADCBAA"
1
Per prima cosa bisogna individuare allinterno dellintervallo il segmento relativo alla
probabilit che la sequenza BAAB ha di verificarsi.
Si parte dal primo simbolo B e poi si prosegue con il resto dei simboli della parte di
messaggio da codificare. Lampiezza degli intervalli diminuisce ad ogni passo.
La codifica aritmetica ci porta allora a concludere che lintervallo relativo alla sequenza
BAAB il seguente:
Quindi, esistono 64 () possibili combinazioni e ad ogni numero scelto corrisponde una
possibile combinazione di 4 lettere (o simboli).
Al termine della codifica dei quattro simboli troveremo 6 caratteri finali, invece degli 8
iniziali (caratteri iniziali dei simboli BAAB 00 01 10 11), quindi possiamo dire che c
stata compressione dei dati.
Fonti
PDF Compressione Huffman e codifica aritmetica
2
[Link]
[Link]
[Link]
[Link]
