Algoritmul Huffman și arhivarea informației

Capitolul 1

Codarea surselor

Codarea este operat»ia prin care simbolurilor unei surse (denumite surs¸a primar¸a) i

se ata»seaza cuvinte de cod form^andu-se astfel o nou¸a surs¸a, de numit¸a surs¸a secun-

dar¸a. Ideea de baz¸a a cod¸arii este c¸a entropia sursei secundare s¸a ¯e mai mare dec^at

cea a sursei primare sau, altfel spus, s¸a se reduca, chiar anuleaze, redundant»a sursei

primare.

Un cod bun va ^³ncerca s¸a atribuie unui simbol cu probabilitatea o lungime a

cuv^antului de cod mic¸a (se repet¸a des, deci aici se poate face economie), iar celor

cu probabilitate mare cuvinte mai lungi (sunt rare deci pierderile sunt mai mici).

Un exemplu foate des folosit este codul Lempel-Ziv-Welch care st¸a la baza pro-

gramelor de tip WinRar, WinZip; rezultatul unei asemenea cod¸arii duce la compresia

¯»sierelor si deci la economisirea spat»iului pe un disc de stocare a informat»iei.

Mai departe vom formaliza cele spuse ^³n alineatul precedent. Ne vom restr^ange

la a considera numai cazul surselor f¸ar¸a memorie.

Sursa primar¸a are alfabetul de lungime N :

[S] = [s1; s2; : : : sN]

cu setul de probabilit¸at»i:

[PS] = [p(s1); p(s2); : : : p(sN)]

Sursa secundar¸a este caracterizat¸a de alfabetul (de lungime D;D · N):

[X] = [x1; x2; : : : xD]

Cu aceste simboluri se formeaz¸a cuvinte de cod. Fiec¸arui simbol al sursei i se

ata»seaz¸a un cuv^ant de cod. Totalitatea cuvintelor formeaz¸a codul.

Ne intereseaz¸a numai codurile unic decodabile adic¸a acele coduri unde unei

secvent»e a cuvintelor de cod ^³i corespunde o unic¸a succesiune de simboluri ale sursei.

Exemple:

1. Fie o surs¸a cu 4 simboluri: s1; s2; s3; s4. Acestora le corespund cuvintelor de

cod provenite dintr-un alfabet binar : s1 ! 00; s2 ! 01; s3 ! 10; s4 ! 11

Acesta este un cod unic decodabil, pentru ca orice secvent¸a de cuvinte de cod

s-ar considera decodarea este simpl¸a: se grupeaz¸a doi c^ate bit»ii; ¯ecare grup

are o singura corespondent¸a ^³n simbolurile sursei.

1

2 CAPITOLUL 1. CODAREA SURSELOR

2. Fie o surs¸a cu 4 simboluri: s1; s2; s3; s4. Corespondent»a este: s1 ! 0; s2 ! 1; s3 ! 00; s4 ! 11. Acesta nu este un cod unic decodabil pentru c¸a unei

secvent»e de tipul : 0011 ^³i poate corespunde secvent»a s1s1s2s2 sau secvent»a

s3s4. Deci nu avem informat»ie cert¸a la ie»sirea decodorului.

Mai mult dec^at at^at, ^³n practic¸a se folosesc coduri instantanee sau ireductibile.

Acestea sunt acele coduri care respect¸a proprietatea de pre¯x (nici un cuv^ant de

cod nu este pre¯xul altui cuv^ant). Un exemplu de cod reductibil este:

s1 ! 0; s2 ! 01; s3 ! 011; s4 ! 0111

Acesta este un cod unic decodabil pentru ca orice cuv^ant de cod ^³ncepe cu 0. Nu

este un cod instantaneu pentru c¸a la o secventa de tipul 01 nu se poate decide ce

simbol a fost transmis »si trebuie s¸a se a»stepte bitul urm¸ator. Dac¸a e 0 atunci se

decide c¸a anterior a fost transmis s1, dar cu ^³nt^arziere. Dac¸a e 1, secvent»a devine

011 »si mai trebuie a»steptat. Se folosesc coduri instantanee din motive de vitez¸a.