Algoritmul lui Huffman

Algoritmul lui Huffman

Se aplica atunci cand probabilitatile sunt de puteri intregi ale lui ½. E o expresie a algoritmului Schannon - Fano. Prevede tot divizarea submultimii astfel incat sumele probabilitatilor sa fie cat mai apropiate. Algoritmul introduce in plus o regula suplimentara si anume dupa fiecare divizare a multimii mesajele se reordoneaza in ordine descrescatoare a probabilitatilor. Asta permite gruparea ultimelor mesaje cu probabilitatile minime la fiecare pas.

Prin aceasta metoda se obtin coduri instantanee si compacte. Deoarece divizarea se poate face in mai multe moduri rezulta ca se pot obtine mai multe moduri se pot obtine mai multe coduri instantanee compacte pentru o sursa data.

Se poate arata ca acest cod e instantaneu construind graful. Lungimea medie a cuvantului de cod e cea mai mica posibila(practic).

Alg. Lui Huffman poate fi generalizat pt. situatia cand alfabetul canalului contine mai mult de 2 simboluri (nr de simboluri = M) M >2. Metoda fiind similara cu precizarea ca de data asta mesajele se grupeaza cate M. Daca sursa S contine N mesaje atunci exista legatura: N=M+n (M-1) unde n - nr. gruparii (a cata grupare de mesaje s-a realizat). Cu ajutorul acestei relatii se va determina intotdeauna cate simboluri pot grupa pt. ca expresia sa fie satisfacuta. Daca e cazul se vor adauga arbitrar mesaje suplimentare dar cu probabilitatea 0.

Ex: Sa consideram sursa S cu probabilitatea din exemplul anterior. Sa consideram M=3(un canal ce accepta 3 simboluri, acestea fiind 0,1,2). N=6 iar pe baza relatiei pe care a descris-o anterior rezulta N=3+2*n. Daca luam n=1 rezulta N=3 care nu acopera nr. de mesaje ale sursei.

Pt. n=2 rezulta N=7 care acopera nr. de mesaje al sursei dar introducerea unui mesaj suplimentar(al 7-lea), cu probabilitatea 0(nu apare niciodata ).

sp(s) = 0

s 0,25 0,25 0,5 0 C=020

0,25 1 C=021

s 0,25 0,25 0,25 2 C=00

s 0,2 0,2 C=1

s 0,15 0,15 C=01

0,20 C=2

s 0,1 0,15 C=022

s 0,05 Acest ultim cuvant de cod nu se

transmite niciodata pt. ca are probabilitatea 0.

s 0