Codarea statica Huffman

Codarea statica Huffman

Algoritmul Huffman porneste de la o lista de ponderi(greutati) pozitive si construieste un arbore binar in care fiecare nod are 0 sau 2 fii.

Frunzele acestui arbore sunt ponderile. Cand algoritmul este folosit la construirea unui cod, ponderile reprezinta probabilitatile asociate cu literele sursa. Initial exista un set de arbori singleton, unul pentru fiecare pondere din lista. La fiecare pas al algoritmului, arborii corespunzatori celor mai mici doua ponderi, w(i) si w(j), sunt imbinati intr-un nou arbore a carui pondere este w(i)+w(j) si a carui radacina are doi fii, care sunt subarborii reprezentati de w(i) si w(j). Ponderile w(i) si w(j) sunt scoase din lista si este inserata w(i)+w(j). Acest proces continua pana cand lista de ponderi contine o singura valoare. Daca, la orice moment, exista posibilitatea de a alege intre mai mult de o pereche de ponderi, oricare asemenea pereche poate fi aleasa. In algoritmul dat de Huffman procesul incepe cu o lista descrescatoare de ponderi. Acest detaliu nu este important in legatura cu corectitudinea algoritmului, dar obtine o implementare mai eficienta a algoritmului.

Procesul Huffman: (a) lista;

(b) arborele;

Algoritmul Huffman determina lungimile cuvintelor cod prin inlocuirea literelor sursa a(i).

Exista multe alternative pentru specificarea cifrelor actuale; este necesar ca secventa de cod sa aiba proprietatea de prefix. Sarcina uzuala presupune etichetarea marginilor de la fiecare parinte, la fiul sau stang cu cifra 0 si la fiul drept cu 1. Cuvantul cod pentru fiecare litera sursa este secventa de etichete existenta pe calea care porneste de la radacina la nodul frunza reprezentat de litera respectiva. Cuvintele de cod pentru sursa din figura, in ordinea descrescatoare a probabilitatilor, sunt . In mod clar, acest proces produce un cod prefix minim. Mai departe, algoritmul este garantat sa produca un cod optim (din punct de vedere al redundantei minime).

Gallager a incercat sa imbunatateasca rezultatele in ceea ce priveste redundanta codului Huffman, printr-o limita superioara  :

p n) + log [(2 lg e e care este aproximativ p n , unde p n) este probabilitatea celui mai putin probabil mesaj sursa.

Figura de mai jos prezinta motivele pentru care codarea Huffman este optima, in timp ce codarea Shannon-Fano nu este.

In legatura cu faptul ca exista multe posibilitati de a forma cuvinte de cod de lungimi corespunzatoare, exista cazuri in care algoritmul Huffman nu determina in mod unic aceste lungimi conform alegerii arbitrare a ponderilor minime egale.

De exemplu, codurile cu lungimile cuvintelor de cod si , ambele produc aceeasi lungime medie a cuvantului cheie, pentru o sursa cu probabilitatile . Schwartz  defineste o variatie a algoritmului Huffman care produce "bottom merging" - imbinarea in partea inferioara; adica ordoneaza un nou nod parinte deasupra nodurilor deja existente de aceeasi pondere, si intotdeauna imbina ultimele doua ponderi in lista.

Codul astfel construit reprezinta codul Huffman cu valori minime ale lungimii maxime a cuvantului cheie (max) si lungimea totala a cuvantului cheie (sum). Schwartz si Kallick descriu o implementare a algoritmului Huffman cu bottom merging.

Algoritmul Schwartz-Kallick foloseste procedura lui Huffman pentru determinarea lungimilor cuvintelor cheie, si cifrele actuale sunt date astfel incat codul sa detina proprietatea de secventa numerica, ceea ce inseamna ca cuvintele cheie de lungimi egale formeaza o secventa consecutiva de numere binare. Codarea Shannon-Fano are deasemenea proprietatea de secventa numerica. Aceasta proprietate poate fi exploatata pentru a obtine o reprezentare compacta a codului si codare si decodare rapida.

Schwartz-Kallick si Huffman

a 0.35 00 1
a 0.17 01 011
a 0.17 10 010
a 0.16 110 001
a 0.15 111 000

lungimea medie 2.31 2.30
a cuvintului cheie