Codarea Shannon-Fano

Tehnica Shannon-Fano detine avantajul ca este simpla. Codul este construit in felul urmator: mesajele sursa a(i) si probabilitatile lor p(a(i)) sunt introduse intr-o lista in ordine descrescatoare dupa probabilitati. Aceasta lista este apoi impartita in asa fel incat sa formeze doua grupuri care sa aiba pe cat posibil egale probabilitatile totale. Fiecare mesaj din primul grup primeste 0 ca prima cifra a cuvantului cod; mesajele din al doilea grup primesc 1 la inceputul codului. Fiecare dintre aceste grupuri este apoi impartit dupa acelasi criteriu folosit anterior si cifrele de cod rezultate se adauga fiecarui cuvant cod in parte. Procesul se continua pana cand fiecare subset contine doar un singur mesaj. In mod clar algoritmul Shannon-Fano produce un cod prefix minim.

Exemplu de un cod Shannon-Fano:

a 1/2 0
b 1/4 10
c 1/8 110
d 1/16 1110
e 1/32 11110
f 1/32 11111

Tabelul de mai sus arata aplicatia metodei la o distributie simpla de probabilitati. Lungimea fiecarui cuvant cod x este egala cu - log p(x). Aceasta relatie este adevarata atat timp cat este posibila impartirea listei in subgrupuri de probabilitati exact egale. Cand acest lucru nu este posibil, anumite cuvinte cod pot avea lungimile -log p(x)+1. Algoritmul Shannon-Fano produce un cuvant cod de lungime medie S care satisface relatia H<=S<=H+1.

In urmatoarea figura este dat codul Shannon-Fano pentru exemplul EXAMPLE dat. Deseori se intampla ca lungimea medie a cuvantului cod sa fie la fel ca cea determinata de codarea Huffman.

g 8/40 00
f 7/40 010
e 6/40 011
d 5/40 100
space 5/40 101
c 4/40 110
b 3/40 1110
a 2/40 1111
Codul Shannon-Fano pentru EXAMPLE (lungimea codului=117)