Codifica di Shannon-Fano
La codifica di Shannon-Fano è un algoritmo che permette di ottenere un codice basato sulla frequenza di simbolo di sorgente. L'idea di principio, come per altri codici, è creare parole di codice più corte per i simboli che ricorrono con maggior frequenza. Sviluppato da Claude Shannon e Robert M. Fano, diede le basi da cui partirà David A. Huffman per sviluppare poi il suo algoritmo di compressione (Codifica di Huffman). Un codice di Shannon-Fano correttamente ottenuto ha la caratteristica di univoca decifrabilità che è indispensabile affinché il decodificatore riconosca correttamente le stringhe di simboli codificati.
Algoritmo
- Si ordinano in modo decrescente di probabilità di emissione i simboli di sorgente;
- Per ogni passaggio della codifica si formano due insiemi per i quali la somma delle probabilità di emissione sia la più simile possibile;
- A ciascuna delle due parti si assegna un "1" o uno "0" arbitrariamente;
- Per ogni sottoinsieme che ottengo da ogni passaggio, si effettuano i passi 2 e 3 fino a ottenere sottoinsiemi di un solo elemento;
- Il codice per ogni simbolo si otterrà mettendo in sequenza gli "0" e "1" partendo dal primo passaggio fino ad arrivare all'ultimo.
Esempio
Si ha un vocabolario di sorgente L ={A, B, C, D, E}. Le probabilità di emissione per ogni simbolo sono P(A)=1/10, P(B)=1/10, P(C)=2/10, P(D)=2/10, P(E)=4/10.
Li Pi 1 2 3 E 4/10 0 0 — D 2/10 1 — C 2/10 1 0 — B 1/10 1 0 A 1/10 1
Il primo passaggio forma due insiemi, quello con probabilità 6/10 che contiene i simboli E e D e quello con probabilità 4/10 con i simboli C, B e A. L'unica altra scelta sarebbe stata quella di formare un insieme con probabilità 4/10 (solo il simbolo E) e 6/10 (i simboli D, C, B, A): il codice finale in tal caso sarebbe diverso ma le prestazioni sarebbero identiche.
Al secondo passaggio per l'insieme di sopra non si hanno alternative, per quello di sotto possono essere creati due insiemi con identica probabilità totale pari a 2/10.
Infine al terzo passaggio non resta che dividere gli ultimi due simboli.
Le parole di codice corrispondenti a ogni simbolo si leggono dal passo 1 al passo 3:
Simbolo Codice A 111 B 110 C 10 D 01 E 00
È facile notare che ai simboli più frequenti è associato un codice più corto.
Bibliografia
- Bruce Carlson, Communication Systems, MCGRAW-HILL COLLEGE
