Codari adaptive Codarea adaptiva Huffman
Codarea adaptiva Huffman a fost
initial conceputa independent de Faller si Gallager [Faller
1973; Gallager 1978]. Knuth a contribuit cu imbunatatiri la
algoritmul initial [Knuth 1985] si algoritmul rezultat este cunoscut sub numele de FGK. O versiune mai recenta
a algoritmului Huffman adaptiv, este descrisa de
Vitter [Vitter 1987]. Toate aceste metode sunt scheme de
cuvinte definite care determina impachetarea de la mesaje sursa la
cuvinte cheie bazate pe o estimatie a probabilitatilor mesajelor
sursa. Codul este adaptiv, schimbandu-se
astfel incat sa ramana optim pentru estimatia curenta.
In acest fel, codurile adaptive Huffman raspund la
localitate. In esenta, codorul invata
caracteristicile sursei. Decodorul trebuie sa
invete in acelasi timp cu codorul, sa updateze in mod continuu
arborele Huffman astfel incat sa ramana in sincronizare cu
codorul.
Alt avantaj al acestor sisteme este ca necesita doar un singur pas asupra datelor.
Metodele cu un singur pas nu sunt foarte interesante
daca numarul de biti transmisi este considerabil mai mare
decat cel al schemelor de doi pasi. Performanta acestor metode, in
ceea ce priveste numarul de biti
transmisi, poate fi mai buna decat performanta codarii
statice Huffman. Acest lucru nu contrazice optimalitatea metodei statice luand
in considerare ca metoda statica este
optima doar fata de metodele care presupun o impachetare de timp
invariant. Performanta metodelor adaptive poate fi
si mai scazuta decat aceea a metodelor statice.
.com