Algoritmul de codare Huffman

1.1.1. Parte teoretica

Se da un set de simbouri de intrare a caror probabilitati sunt cunoscute. Trebuie sa gasim un cod binar a carui lungime sa fie minima.

Alfabetul,

este alfabetul simbolurilor, avand  lungimea  n.

Setul:

este setul probabilitatilor simbolurilor ca de exemplu:

,

La iesire se va regasi codul:

 

ce este un set (binar) de cuvinte , unde ‚’ci’ este un cuvant de cod pentru ’ai’,

Telul:  dorim ca :

sa fie

pentru orice cod

1

Exemplu

Tabel 1: Exemplu de codare Huffman.

Intrare (A,W) Simbol (ai) a b c d e Suma

Probabilitati (wi) 0,10 0,15 0,30 0,16 0,29 =1

Iesirea C Cuvinte de cod (ci)

000 001 10 01 11

Lungimea cuvintelor de cod (li)

3 3 2 2 2

liwi 0,30 0,45 0,60 0,32 0,58 L(C)=2,25

Optimalitate Probabilitati de

aparitie ( )

1/8 1/8 1/4 1/4 1/4 =1,00

Continutul de informatie(−log2 wi)

3,32 2,74 1,74 2,64 1,79

Entropia(−wi log2 wi)

0,332 0,411 0,521 0,423 0,518 H(A)=2,205

 

Pentru orice cod unic decodabil, suma tuturor posibilitatilor simbolurilor este intotdeauna mai mica sau egala cu 1. In acest exemplu, suma este strict egala cu 1, deci ca rezultat avem un cod numit si cod complet. Daca nu este cazul de asa ceva, se poate intotdeauna deriva un echivalent al codului, prin adaugarea de simboluri cu probabilitate nula, pentru a face codul complet.

Asa cum a definit Shanon in 1948, continutul de informatie h (in biti) al fiecarui simbol ai cu probabilitate nenula este:

Continutul de informatie al simbolurilor cu probabilitate nula nu este definit, dar in practica poate fi definit ca o valoare finita, deoarece informatia va fi absenta din mesajul codat (doar daca lungimea mesajului A este infinita, dar in acest caz probabilitatile simbolurilor au o probabilitate pozitiva infinit zecimala).

2

Entropia H (in biti) este suma ponderata a simbolurilor ai cu probabilitate nenula wi a continutului de informatie a fiecarui simbol:

Toate simbolurile de probabilitate 0 au teoretic o entropie pozitiv infinita, dar deoarece sunt absente din mesajul original ce va fi codat, acestea nu contribuie la entropia mesajului codat, deci ele ar putea fi facute sa aiba entropie 0 in suma de mai sus, scotand astfel restrictia de indici.

Ca o consecinta a teoremei lui Shannon, entropia este o masura a cuvantului cu cea mai mica lungime de cod. In acest exemplu, media este 2,25 biti per simbol, doar un pic mai mare ca entropia calculata de 2,205 biti per simbol. Deci acest cod nu este doar optimal in sensul ca nici un alt cod nu are performante mai bune, dar este foarte aproape de limita teoretica stabilita de Shannon.

Tehnica de constructie a arborelui

Presupunem ca avem o sursa ce genereaza 4 simboluri diferite {a1,a2,a3,a4} cu probabilitati de aparitie {0.4;0.35;0.2;0.05}.

Se genereaza un arbore binar de la stanga la dreapta. Luam cele mai improbabile doua simboluri, si le unim intr-un simbol echivalent de

probabilitate egala cu suma probabilitatilor celor doua.

Se repeta pasii 1 si 2, pana cand ramane un singur simbol.

Se citeste arborele invers, de la dreapta la stanga, asignand diferiti biti diferitelor ramuri.

 

Codul Huffman rezultat astfel este:

Simbol Cod

a1 0

a2 10

3

a3 111

a4 110

 

Proprietati

Codarea Huffman este optimala atunci cand probabilitatea fiecarui simbol de intrare este o putere negativa a lui 2. Codurile fara prefix, au tendinta de a fi usor ineficiente, pe alfabete reduse, unde probabilitatile cad deseori intre punctele optimale.

Cel mai defavorabil caz pentru codarea Huffman se poate intampla atunci cand probabilitatea unui simbol depaseste 2-1 = 0.5, atingand astfel limita superioara a granitei de ineficienta. In aceste situatii de obicei se foloseste codarea RLE. Codarea aritmetica produce rezultate usor mai bune, dar in practica rareori au fost cu atat mai bune cat sa merite sacrificarea unei puteri mai mare computationare si de plata a patentelor detinute din iulie 2006 de catre IBM.

Variatii

Exista multe variatii ale codului Huffman. Iata cateva dintre acestea:

Codarea Huffman n-ara o Algoritmul foloseste alfabetul {0, 1, ..., n − 1} pentru codarea mesajului si

constructia arborelui n-ar.

Codare adaptiva Huffman

o variatie ce calculeaza frecventa de aparitie a simbolurilor dinamice bazata pe frecventa actuala de emisie a sursei. Acest algoritm este oarecum inrudit cu familia de algoritmi LZ.

Codare Huffman template

o Poate rezolva probleme  de minimizare ca de exemplu:

Codare Huffman limitata ca lungime

Codare Huffman cu costuri de transmisie inegale

Arbori optimali binari alfabetici

1.1.2. Programul Principal(Matlab)

4

In programul principal al proiectului „programhuffman.m” se citeste mesajul ce se doreste a fi codificat si se vor apela functiile principale prezentate ulterior. De asemenea, acesta contine si liniile de cod necesare afisarii elementelor de interes.

clc;clear clc;clear all;

Se deschide fisierul ’text.txt’ cu mesajul,dupa care se citeste continutul si se formeaza vectorul „secventa” cu elementele mesajului.

fid=fopen('text.txt','r'); secventa=fread(fid,'*char'); fclose(fid);

secventa=reshape(secventa,1,length(secventa));

Se apeleaza functia „modelulprobabilistic.m” care realizeaza modelul

probabilistic necesar.[caracter p]=modelulprobabilistic(secventa); l=length(secventa);

Se verifica daca vectorul cu caracterele ce apar in mesaj este nul. Daca valoarea de adevar este „1” se va parcurge instructiunea ’if’.

if ~isempty(caracter)

Se apeleaza functia ’codaresursa.m’ in care se determina un cod unic pentru fiecare caracter in parte dar si propietatile codului obtinut.

[huff entropia lmed eficienta redundanta coduri]=codaresursa(caracter,p); disp(strcat('Secventa de codat : ',secventa));

Se verifica daca variabila ’huff’ este nula. Daca nu este nula se va parcurge instructiunea ’if’. Liniile de cod urmatoare au rolul de a afisa pentru fiecare caracter unic atat probabilitatea de aparitie a acestuia cat si codul.

if ~isempty(huff) lp=length(p); for i=1:lp string=huff(i).simbol; string=strcat(string,' -> '); string=strcat(string,num2str(huff(i).probabilitate)); string=strcat(string,' -> '); string=strcat(string,huff(i).codul); disp(string); end

Urmatoarele linii de cod realizeaza afisarea secventei codata: secvcod='Secventa codata : ';

5

for j=1:l for i=1:lp if secventa(j)==caracter(i) secvcod=strcat(secvcod,coduri(i)); end endenddisp(char(secvcod));

Se afiseaza si propietatile codului obtinut in urma codarii de sursa:

disp(strcat('Entropia = ',num2str(entropia))); disp(strcat('Lungimea Medie = ',num2str(lmed))); disp(strcat('Eficienta = ',num2str(eficienta))); disp(strcat('Redundanta = ',num2str(redundanta)));end

Daca prima instructiune ’if’ nu se parcurge intru-cat nu se indeplineste conditia de adevar se va afisa mesaj de eroare:else display('Secventa Goala');

1.2. Modelul Probabilistic

Functia care realizeaza modelul probabilistic este denumita „modelulprobabilistic.m”. Aceasta are ca variabila de intrare vectorul cu mesajul de codificat si returneaza alte doua variabile, „caracter”-vectorul ce contine caracterele unice in ordinea aparitiei lor din care este constituit mesajul si „p”-vectorul cu probabilitatile corespunzatoare fiecarui element din vectorul cu caractere:

function [caracter p]=modelulprobabilistic(secventa) if ~isempty(secventa)

Primul element din caracter va fi retinut din vectorul „secventa”. Prin urmare numarul de aparitii al acestuia va fi minim 1.

caracter(1)=secventa(1); p(1)=1; l=length(secventa); % l = lungimea mesajului k=2;

Se parcurge „for”-ul de la al 2-lea element din secventa pana la ultimul. In momentul in care un element din „secventa” este regasit in ”caracter” ,instructiunea „find” returneaza indicele(pozitia) acestuia,sau,in caz contrar returneaza null.

for i=2:l indice=find(secventa(i)==caracter);

In continuare,daca „indice” este null, se va parcurge instructiunea „if” si noile caractere gasite vor fi scrise in vectorul „caractere”. Altfel, se sare peste si numarul de aparitii al caracterului in cauza va creste cu 1. if isempty(indice) caracter(k)=secventa(i); p(k)=1;

6

k=k+1; else p(indice)=p(indice)+1; end end p=p./l;

Probabilitatile obtinute vor fi rotunjite la 5 zecimale prin urmatoare comanda:

p=roundn(p,-5); else caracter=[]; p=[]; end suma=sum(p);end

1.3. Codarea de sursa

Am definit functia ce urmeaza sa parcurga etapa de codare a sursei „codaresursa.m” , functie ce are ca variabile de intrare cei doi vectori construiti in etapa modelului probabilistic, si care returneaza alte sase variabile necesare.

function [huff entropia lmed eficienta redundanta coduri]= =codaresursa(caracter,p)

Se pune conditia intr-un „if” ca codul sa fie complet,adica suma totala a probabilitatilor sa fie egala cu 1.

suma=sum(p);lc=length(caracter); % lungime caracterlp=length(p); % lungime probaparitieif lc==lp && suma~=1

Se calculeaza entropia codului: entropia=p.*log2(p); % ".*" -> inmultire element cu element entropia=-sum(entropia(:));

Algoritmul de codare al sursei potrivit modelului Huffman: am inceput prin sortarea vectorului cu probabilitati „p” folosind instructiunea de mai jos si obtinand si indicii corespunzatori pozitiilor probabilitatilor din vectorul „p”, asezate acum descrescator in vectorul nou format : „pdesc”. Sub aceeasi forma este obtinut si vectorul „pdesc1”. vector=1:lp; % un vector egal cu lungimea vectorului p [pdesc ipdesc]=sort(p,'descend'); % sortare vector p => 'pdesc' cu probabilitatile in ordine descrescatoare si % indicii(ipdesc) corespunzatori lor pdesc1=sort(p,'descend');

7

Am pornit de la ideea ca pentru a realiza tabelul Huffman sunt necesare un numar de 'k' etape de insumare a ultimelor doua probabilitati din fiecare vector nou format. Pentru a forma un tabel asemanator am creat o matrice de zero-uri de dimensiune „lp”(lungimea vectorului p) x „k”(etape) in care voi contura tabelul. Astfel in prima coloana se vor scrie probabilitatile asezate descrescator in vectorul „pdesc”:

k=(length(p)-1); m=zeros(lp,k); m(1:length(pdesc1),1)=pdesc(1,:)'; for i=1:k-1 % in fiecare etapa (i:k-1) vom insuma ultimele 2 probabilitati pana vom obtine doar 2 elemente in coloana 'k' a lui 'm' paux=pdesc1; % fie 'paux' un vector auxiliar laux=length(paux); paux=paux(1:laux-2); % 'paux' va contine doar elemente pana la laux-2 paux(laux-1)=pdesc1(laux-1)+pdesc1(laux); % se adauga inca un element 'laux-1' constituit de fiecare data din suma ultimelor doua probabilitati ai vectorilor coloana formati dupa fiecare etapa

Intru-cat vom avea nevoie de probabilitatile nou obtinute prin insumare le vom salva in vectorul „s”, iar indicii(pozitiile) acestora vor fi scrisi in vectorul „is”,folosind instructiunea „find”. s(i)=paux(laux-1); paux=sort(paux,'descend'); % se sorteaza 'paux' descrescator pdesc1=paux; % pdesc1 ia valorile lui 'paux' auxiliar=pdesc1'; % fie vectorul 'auxiliar' m(1:length(auxiliar),i+1)=auxiliar(:,1); % se copiaza in matrice,pe coloana, elementele corespunzatoare fiecarei etapa de reducere. is(i)=find(pdesc1==s(i), 1, 'last'); % fie 'is' vectorul cu indicii sumelor corespunzatoare fiecarei etapa end

coduri(1:lp,1:k)={''}; % matrice de coduri de dimensiunea matricei 'm' : {''} {''} ... {''} {''}

. . . . {''} ... ... {''}

Se compara cele doua probabilitati obtinute in ultima etapa de reducere si se atribuie valoarea „1” celei mai mari. Se scriu valorile in ultima coloana din matricea de coduri.

if(m(1,k)> m(2,k)) coduri(1,k)=strcat('1',coduri(1,k)); coduri(2,k)=strcat('0',coduri(2,k)); else coduri(1,k)=strcat('0',coduri(1,k)); coduri(2,k)=strcat('1',coduri(2,k)); end

lis=length(is); % fie 'lis' lungimea vectorului cu pozitiile probabilitatilor obtinute prin insumare

8

c=3; % constanta reprezentand initial numarul de elemente al primei etape de parcurgere a matricei 'm' INVERS

De aceasta data matricea „m” trebuie parcursa invers si fiecare coloana,de la ultima (k) spre prima(k=1) va avea un numar crescator de elemente(c=c+1 pentru fiecare etapa parcursa invers). Vom lucra in matricea de coduri in functie de „j” pe linii si de „k” pe coloane. while c<=lp for j=1:c if (j<=c-2)&&(is(lis)==1) coduri(j,k-1)=coduri(is(lis)+j,k); elseif (j<=c-2)&&(j<is(lis)) coduri(j,k-1)=coduri(j,k); elseif (j<=c-2)&&(j==is(lis)); coduri(j,k-1)=coduri(j+1,k); elseif (j<=c-2)&&(j>is(lis)) coduri(j,k-1)=coduri(j+1,k); elseif j<=c-1 coduri(j,k-1)=coduri(is(lis),k); coduri(j,k-1)=strcat(coduri(j,k-1),'1'); else coduri(j,k-1)=coduri(is(lis),k); coduri(j,k-1)=strcat(coduri(j,k-1),'0'); end end c=c+1; lis=lis-1; % se decrementeaza 'lis' ( lungimea vectorului cu indicii probabilitatilor obtinute prin insumare ) k=k-1; end

Scurta descriere a obtinerii matricii de coduri : tinem cont ca ultimele doua probabilitati din fiecare coloana(etapa) au algoritm de determinare a codurilor separat. Pentru primele C-2 linii procedam astfel: luam fiecare probabilitate din coloana „K” si verificam daca pe aceeasi pozitie in coloana anterioara „K-1” se afla probabilitatea obtinuta prin insumare. Daca pe linia care lucram,in coloana din etapa anterioara, nu se intalneste probabilitatea obtinuta prin insumare, atunci codurile se rescriu din coloana „K-1”. In momentul cand ajungem pe linia unde se afla si probabilitatea obtinuta prin insumare(linia „is(lis)”) atunci codurile se scriu tot din coloana „K-1”,insa decalate cu 1 unitate, pentru a sari peste probabilitatea insuma. Procedeul continua pana ajungem la ultimele doua elemente de pe coloana/etapa curenta:”C-1 si ”C”, caz in care se scrie codul probabilitatii insumate din etapa anterioara si se concateneaza la cod cifra „1” pentru penultimul element si „0” pentru ultimul.

9

coduri=cellstr(coduri(:,1)); [index1 index2]=sort(ipdesc,'ascend'); coduri=coduri(index2);

Am creat o structura huff(i) 1x47 : .simbol .probabilitate

.codul

for i=1:lp huff(i).simbol=caracter(i); huff(i).probabilitate=p(i); huff(i).codul=coduri(i); end

Calcularea Lungimii Medii: lmed=0; for i=1:lp lmed=lmed+huff(i).probabilitate*length(cell2mat(huff(i).codul)); end

Calcularea Eficientei: eficienta=entropia/lmed;

10

Calcularea Redundantei: redundanta=((lmed-entropia)/lmed);else display('Eroare'); huff=[]; end

11