Algoritmul FGK

Algoritmul FGK

Baza algoritmului FGK o reprezinta proprietatea sibling, definita de Gallager: un arbore cod binar are proprietatea sibling, daca fiecare nod, exceptand nodul radacina, are o sibling si daca nodurile pot fi afisate in ordine descrescatoare a ponderii cu fiecare nod adiacent cu siblingul lui. Gallager arata ca un cod prefix binar este un cod Huffman daca si numai daca arborele are proprietatea sibling. In algoritmul FGK, ambii senderul si receiverul mentin schimbarile dinamice ale arborilor codului Huffman. Frunzele arborelui cod reprezinta mesajele sursa si ponderile frunzelor reprezinta numararile frecventei pentru mesaje.

Figura 1--algoritmul FGK aplicat pe EXAMPLE (a) arbore dupa prelucrarea "aa bb" ; 11 se va transmite pentru urmatorul b ; (b) dupa codarea celui de-al treilea b; 101 se va transmite pentru urmatorul element space; arborele nu se va schimba ; 100 se va transmite pentru primul c; (c) arborele dupa update urmand primul c.

Initial, arborele cod consta intr-un singur nod frunza, numit nodul-0. Nodul-0 este un nod special utilizat pentru a reprezenta cele n-k mesaje nefolosite. Pentru fiecare mesaj transmis, ambele parti trebuie sa incrementeze ponderea corespunzatoare si sa recalculeze arborele cod astfel incat sa se mentina proprietatea sibling. La momentul din timp in care t mesaje au fost transmise, k dintre ele distincte si  k < n, arborele este un arbore de cod Huffman legal, cu k + 1 frunze , una pentru fiecare dintre cele k mesaje si una pentru nodul-0. Daca mesajul cu numarul t 1) este unul dintre cele k deja vazute, algoritmul transmite codul curent al a(t+1), incrementeaza si recalculeaza arborele. Daca apare un mesaj nefolosit, nodul-0 este descompus pentru a crea o pereche de frunze, una pentru a(t+1) si o sibling care devine noul nod-0. Din nou arborele de recalculeaza. In acest caz, codul pentru nodul-0 este trimis; in plus, receiverului trebuie sa i se spuna care dintre cele n-k mesaje nefolosite a aparut. La fiecare nod este stocat un calcul al aparitiei mesajului corespunzator. Nodurile sunt numarate indicand pozitia lor in ordinea proprietatii sibling. Updatarea arborelui poate fi facuta intr-o singura traversare de la nodul a(t+1) catre radacina. Aceasta traversare trebuie sa incrementeze numararea pentru nodul a(t+1) si pentru fiecare din parintii sai. Nodurile pot fi schimbate pentru a mentine proprietatea sibling, dar toate aceste schimbari implica un nod pe calea de la a(t+1) catre radacina. Figura urmatoare arata arborele cod final format prin acest procedeu, pe ansamblul EXAMPLE

Arborele  format prin algoritmul FGK pe ansamblul EXAMPLE

Neconsiderand overheadul, numarul de biti transmisi prin algoritmul FGK este 129. Algoritmul static Huffman transmite 117 biti in procesarea acelorasi date. Overheadul asociat metodei adaptive este de fapt mai mic decat cel al algoritmului static. In cazul adaptiv, overheadul este de n log n biti necesari pentru a reprezenta fiecare dintre cele n mesaje sursa diferite atunci cand apar pentru prima oara. (Acest lucru este de fapt conservativ; decat sa transmita un cod unic pentru fiecare din cele n mesaje sursa, mai degraba senderul ar putea transmite pozitia mesajului din lista mesajelor ramase si sa salveze cativa biti in cazul obisnuit.)

In cazul static, mesajele sursa trebuie sa fie trimise dupa forma arborelui cod. Dupa cum am mai spus, o reprezentare eficienta a formei arborelui necesita  2n biti. Algoritmul FGK se compara bine cu codarea staticp Huffman cand se tine seama de overhead.

Figura de mai jos ilustreaza un exemplu pe care algoritmul FGK actioneaza mai bine decat algoritmul static Huffman, chiar fara a lua in consideratie overheadul. Algoritmul FGK  transmite 47 de biti pentru acest ansamblu in timp ce algoritmul static Huffman necesita 53 de biti.

Arbore format prin algoritmul FGK pentru ansamblul 'e eae de eabe eae dcf