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