Comparatia codurilor Shannon-Fano si Huffman

Ambele codari Shannon-Fano si Huffman pot fi generate in O(n) timp, unde n este numarul de mesaje in ansamblul sursa (presupunand ca ponderile au fost presortate). Fiecare dintre acesti algoritmi inlocuieste un mesaj sursa a(i) care are probabilitatea p, cu un cuvant cheie de lungime l (-log p <= l <= -log p + 1). Timpii de codare si decodare depind de felul de reprezentare al inlocuirii. Daca codarea este memorata sub forma unui arbore binar, atunci decodarea cuvantului cheie pentru a(i), implica urmarirea unei cai de lungime l in arbore. Un tabel indexat de mesajele sursa, poate fi utilizat pentru codare; codul pentru a(i) ar fi memorat in pozitia i din tabel, si timpul de codare ar fi O(l).

Algoritmul lui Connell foloseste indexul codului Huffman, o reprezentare a distributiei lungimilor cuvintelor cheie, sa codeze si sa decodeze in timpul O(c) unde c este numarul a diferite lungimi de cuvinte cheie.

Cum s-a observat mai devreme, limita redundantei pentru codurile Shannon-Fano este 1 si limita pentru metoda Huffman este:

p(n + 0.086) unde p(n) este probabilitatea celui mai putin probabil mesaj sursa (deci p(n) <=.5 si in general mult mai putin). Este important de notat ca in definirea redundantei ca fiind lungimea medie a cuvantului cheie minus entropia, costul transmiterii codurilor calculate de acesti algoritmi, este ignorat. Costul de overhead pentru orice metoda in care nu a fost stabilita prioritatea de transmisie a alfabetului sursa, include n log n biti pentru a trimite n litere sursa. Pentru un cod Shannon-Fan, poate fi transmisa o lista de cuvinte cheie ordonate asa incat sa corespunda literelor sursa.

Timpul necesar suplimentar este S l(i), unde l(i) sunt lungimile cuvintelor cheie. Pentru codarea Huffman, poate fi transmisa o codare sub forma de arbore. Cum orice arbore binar plin poate fi un arbore Huffman, codarea sub forma de arbore poate solicita log 4ⁿ = 2n biti. In cele mai multe cazuri ansamblul de mesaje este foarte mare, astfel incat numarul de biti de overhead este minuscul in comparatie cu lungimea totala a transmisiei codate. Totusi este imprudent a se ignora acest cost.

Daca un cod mai putin decat optim este acceptabil, costul overheadului poate fi evitat printr-o intelegere a senderului si receiverului, in ceea ce priveste impachetarea codurilor. Mai degraba s-ar putea folosi codul bazat pe statistici pentru o clasa de transmisii, din care ansamblul curent apartine, decat codul Huffman bazat pe caracteristicile ansamblului de mesaje curente. Aceasta inseamna ca atat senderul cat si receiverul ar putea avea acces la o carte de cuvinte cheie care contine k codari. Senderul ar putea atunci sa anunte foarte usor receiverul, care dintre codurile obisnuite foloseste si pentru acest lucru necesita doar log k biti de overhead. Presupunand ca clasele de transmisie cu caracteristici relativ stabile ar putea fi identificate, aceasta apropiere hibrida ar reduce destul de mult redundanta datorata overheadului fara a creste in mod semnificativ lungimea cuvintelor cheie. In plus costul calcularii impachetarii ar fi amortizat asupra tuturor fisierelor unei clase date. Aceasta inseamna ca impachetarea ar fi calculata o singura data pe un exemplu statistic semnificativ si apoi utilizata pe un numar mare de fisiere pentru care acel exemplu este reprezentativ.

Exista un risc substantial clar asociat cu presupuneri in legatura cu caracteristicile fisierelor si este necesara o atentie deosebita in alegerea exemplului din care va fi derivata impachetarea.