Această metodă este numită după D.A. Huffman, care a dezvoltat procedura în anii 1950. Fig. 27-2 prezintă o histogramă a valorilor octeților dintr-un fișier ASCII mare. Mai mult de 96% din acest fișier conține doar 31 de caractere: literele minuscule, spațiul, virgula, perioada și carriage return. Această observație poate fi utilizată pentru a face o schemă de compresie adecvată pentru acest fișier. Pentru a începe, vom asocia fiecăruia dintre aceste 31 de caractere comune un cod binar de cinci biți: 00000 = "a", 00001 = "b", 00010 = "c" etc. Aceasta permite ca 96% din mărimea fișierului să fie redusă cu 5/8. Ultimul cod de 5 biți, 11111, va fi un steag care indică faptul că caracterul transmis nu este unul dintre cele 31 de caractere comune. Următorii opt biți din fișier indică ce caracter este, în conformitate cu atribuirea standard ASCII. Aceasta are ca rezultat 4% din caracterele din fișierul de intrare care necesită 5 + 8 = 13 biți. Ideea este de a atribui caracterelor frecvent utilizate mai puțini biți, și caracterelor rareori folosite mai mulți biți. În acest exemplu, numărul mediu de biți necesar pentru fiecare caracter original este: 0,96 × 5 + 0,04 × 13 = 5,32. Cu alte cuvinte, un raport general de compresie de: 8 biți/5,32 biți sau aproximativ 1,5: 1.

Codificarea Huffman duce această idee la extrem. Caracterele care apar cel mai adesea, cum ar fi space și period, pot fi atribuite la unu sau doi biți. Caracterele folosite frecvent, cum ar fi:!, @, #, $ și %, pot necesita o duzină sau mai mulți biți. În termeni matematici, situația optimă este atinsă atunci când numărul de biți utilizați pentru fiecare caracter este proporțional cu logaritmul probabilității de apariție a caracterului.

O caracteristică inteligentă a codificării Huffman este modul în care codurile de lungime variabilă pot fi împachetate împreună. Imaginați-vă că primiți un flux de date seriale de unu și zerouri. Dacă fiecare caracter este reprezentat de opt biți, puteți separa direct un caracter de altul prin ruperea bucăților de 8 biți. Acum, luați în considerare un flux de date codificat Huffman, unde fiecare caracter poate avea un număr variabil de biți. Cum separați un caracter de următorul? Răspunsul constă în selectarea corectă a codurilor Huffman care permit separarea corectă. Un exemplu va ilustra modul în care lucrează.

Figura 27-3 prezintă o schemă de codificare Huffman simplificată. Caracterele A până la G apar în fluxul de date original cu probabilitățile arătate. Deoarece caracterul A este cel mai frecvent, îl vom reprezenta cu un singur bit, codul: 1. Următorul caracter cel mai comun, B , primește doi biți, codul: 01. Acest lucru continuă până la cel mai puțin frecvent caracter, G, fiind alocați șase biți, 000011. După cum se arată în această ilustrare, codurile de lungime variabilă sunt utilizate în grupuri de opt biți, standard pentru utilizarea computerului.

Atunci când apare o decompresie, toate grupurile de opt biți sunt plasate cap-la-cap pentru a forma un șir de serial lung de unu și zerouri. Priviți cu atenție tabelul de codare din Fig. 27-3 și observați cum fiecare cod constă din două părți: un număr de zerouri înainte de unu și un cod binar opțional după unu. Acest lucru permite ca fluxul de date binare să fie separat în coduri fără a fi nevoie de delimitatori sau de alt marker între coduri. Programul de decompresie se uită la fluxul de unu și zerouri până când se formează un cod valid și apoi începe să caute următorul caracter. Modul în care sunt formate codurile asigură că nu există nici o ambiguitate în separare.

O versiune mai sofisticată a abordării Huffman se numește codificare aritmetică. În această schemă, secvențele de caractere sunt reprezentate de coduri individuale, în funcție de probabilitatea lor de apariție. Acest lucru are avantajul unei compresii mai bune a datelor, să spunem 5-10%. Codarea lungimii de rulare (RLE) urmată de codarea Huffman sau aritmetică este, de asemenea, o strategie comună. Așa cum v-ați putea aștepta, aceste tipuri de algoritmi sunt foarte complicate și, de obicei, sunt lăsate la specialiști în compresia datelor.

Pentru a implementa codificarea Huffman sau aritmetică, algoritmii de compresie și decompresie trebuie să convină asupra codurilor binare utilizate pentru a reprezenta fiecare caracter (sau grupuri de caractere). Acest lucru poate fi tratat într-unul din două moduri. Cel mai simplu este să utilizați un tabel de codare predefinită care este întotdeauna același, indiferent de informațiile comprimate. Schemele mai complexe utilizează codificarea optimizată pentru datele particulare utilizate. Aceasta necesită includerea tabelului de codare în fișierul comprimat pentru a fi utilizat de programul de decompresie. Ambele metode sunt comune.

Secțiunea următoare: Codificarea Delta