Algoritmul V

Algoritmul V

Algoritmul adaptiv Huffman al lui Vitter (algoritmul V) incorporeaza doua imbunatatiri fata de algoritmul FGK. In primul rand, numarul de interschimbari prin care un nod este mutat in sus in arbore in timpul recalcularii este limitat la unu. Acest numar este legat in algoritmul FGK doar de l/2, unde l este lungimea cuvantului cheie pentru a(t+1) cand incepe recalcularea. In al doilea rand, metoda lui Vitter minimizeaza valoarea SUM si MAX sensibil la cerinta de minimizare a SUM. Explicatia intuitiva a avantajului algoritmului V asupra algoritmului FGK este: ca si in algoritmul FGK, arborele construit de algoritmul V, este arborele cod Huffman pentru prefixul ansamblului. Metodele adaptive nu presupun ca frecventele relative ale unui prefix reprezinta corect probabilitatile simbolului asupra intregului mesaj. Pentru aceasta, faptul ca algoritmul V garanteaza un arbore de inaltime minima (inaltime = MAX si lungimea caii minime externe (SUM) inseamna ca este mai potrivit pentru a coda urmatorul mesaj al ansamblului, stiind ca oricare dintre frunzele arborelui poate reprezenta urmatorul mesaj.

Aceste imbunatatiri sunt indeplinite prin utilizarea unui nou sistem de numarare a nodurilor. Numerotarea, numita numerotare implicita, corespunde unei ordonari pe nivele a nodurilor (de jos in sus, si de la stanga la dreapta). Numaratoarea in algoritmul FGK nu este intotdeauna o ordonare a nivelelor. ????In algoritmul lui Vitter de mentine urmatoarea invarianta: pentru fiecare pondere w, toate frunzele de pondere w preced (in numerotarea implicita) toate nodurile interne de pondere w. Vitter arata ca aceasta invarianta intareste legatura dorita intre noduri. Invarianta implementeaza deasemenea imbinarea in partea de jos, pentru a minimiza SUM si MAX. Diferenta dintre metoda lui Vitter si algoritmul FGK consta in felul in care este updatat arborele intre transmisii. Pentru a putea intelege operatia de updatare, este necesara urmatoarea definitie a unui bloc de noduri: blocurile sunt clase de echivalenta de noduri definite de: u este echivalent cu v daca pondere(u)= pondere(v) si u si v sunt ambele ori frunze, ori noduri interne.

Leaderul unui bloc este nodul din bloc cu cel mai mare indice de numerotare (in numerotarea implicita). Blocurile sunt ordonate crescator dupa ponderi, cu conventia ca un bloc frunza intotdeauna precede un bloc intern de aceeasi pondere. Cand este ceruta o schimbare de noduri pentru a mentine proprietatea sibling, algoritmul V cere ca nodul care trebuie promovat sa fie schimbat in pozitia ocupata in acel moment de nodul leader din bloc.

In figura urmatoare, este afisat arborele Vitter corespunzator cu Figura 1c. Acesta este primul punct din EXAMPLE in care algoritmul FGK si algoritmul V difera semnificativ. La acest punct, arborele Vitter are inaltimea 3 si lungimea caii externe 12, in timp ce arborele FGK are inaltimea 4 si lungimea caii externe 14. Algoritmul V transmite cuvantul cheie 001 pentru al doilea c; FGK transmite 1101. Aceasta demonstreaza ca algoritmul V este mai bine pregatit pentru a coda mesajul urmator. In procesarea ansamblului EXAMPLE, algoritmul V transmite 124 de biti, in comparatie cu cei 129 de biti ai algoritmului FGK, si cei 117 biti ai algoritmului Huffman static. Este de notat ca aceste figuri nu includ overhead, si ca rezultat dezavantajeaza metodele adaptive.

Algoritm V care proceseaza ansamblul "aa bbb c".

Metoda adptiva a lui Vitter poate transmite cu un bit mai mult per cuvant cheie decat metoda Huffman statica. Imbunatatirile aduse de Vitter nu schimba complexitatea algoritmului; algoritmul V codeaza si decodeaza in O(l) timp asa cum face si algoritmul FGK.