Structuri de Date

L A B O R A T O R 8a

Compresia Huffman

Metoda de codificare Huffman inlocuieste fiecare caracter printr-un cod cu numar variabil de biti, astfel incat caracterele folosite mai frecvent sa aiba coduri mai scurte. Metoda Huffman are 2 etape:- Construirea unui arbore binar in care fiecare caracter apare ca o frunza;- Parcurgerea arborelui pentru generarea codurilor Huffman ale caracterelor.

In arborele creat caracterele de codificat se afla in frunze, iar caleade la radacina la o frunza (cu 0 pentru ramificare la stanga si 1 pentruramificare la dreapta) reprezinta codul Huffman al caracterului respectiv. Caracterele si frecventele lor de aparitie se preiau din doi vectori. Exemplu de date :

char ch[]={'a','b','c','d','e','f'};short fr[]={36,14,12,10,20,8};

Coduri caractere:a=11, b=101, c=100, d=001, e=01, f=000

1. Sa se defineasca tipul structura "hnod" care contine un caracter,o frecventa ( de tip "short) si pointeri catre cei doi fii (stanga si dreapta). Sa se scrie o functie de creare a unui nod de arbore cu fii cunoscuti:

hnod* make ( char ch, short fr, hnod* left, hnod* right) {

Obs: Nodul creat nu are inca parinte, dar se modifica legaturile de la fiisai catre acest nod (daca exista acesti fii).

Sa se defineasca tipul "pq" pentru o coada cu prioritati realizata ca lista inlantuita ordonata de pointeri "void*", din care se extrage mereu elementul cu frecventa minima (in functia delPQ). Functii necesare:

void initPQ(pq & q); // initializare coada vida void addPQ(pq & q, void* p); // adauga la coada o adresa void* delPQ(pq & q);// scoate din coada adresa nod cu frecv minima int emptyPQ(pq q);// 1 daca coada este vida, 0 daca nevida

Sa se verifice operatiile cu coada folosind programul urmator:

int main () { char ch[]={'a','b','c','d','e','f'}; short fr[]={36,14,12,10,20,8}; pq q; initPQ(q); for (int i=0;ich,p->fr); } getchar();}

2. Sa se scrie si sa se verifice o functie "build" pentru crearea unui arbore Huffman pe baza a doi vectori (de caractere si de frecvente): hnod* build (char c[], short f[], int n);// n=dimensiune vectori

Arborele este construit treptat de jos in sus, folosindu-se o coada cuprioritati "pq" ordonata dupa numarul de aparitii, dupa algoritmul urmator:

ch='0' // caractere pentru noduri nou create initializare coada pq repeta de n ori { creare nod de arbore cu caracter si frecventa adauga la coada pq adresa nod creat } repeta cat timp coada pq nu e goala { scoate un element din coada pq in t1 daca coada e goala se iese din ciclu scoate un element din coada pq in t2 f = suma frecvente din t1 si t2; creare nod t3 cu perechea (++ch,f) si fii t1 si t2 adauga la coada pq adresa nod creat t3 } rezultat=t3// ultimul nod creat este radacina arborelui

Verificarea se va face prin afisarea prefixata cu indentare a arborelui. Se va afisa continutul cozii la fiecare pas din ciclul principal.

3. Sa se scrie si sa se verifice o functie pentru afisarea codului binaral unui caracter dat pe baza arborelui Huffman (ca sir de caractere '0' si '1'),

void encode (hnod* r, char ch, char* hc); // hc=cod Huffman ptr ch

Se va scrie si folosi o functie de cautare a unui caracter intr-un arbore Huffman astfel:

repeta cat timp nodul r are fii daca ch exista in subarborele stanga al nodului r atunci adauga 0 la sirul hc r= adresa fiu stanga daca ch exista in subarborele dreapta al nodului r atunci adauga 1 la sirul hc r=adresa fiu dreapta

Sa se scrie o functie "encodetext" care foloseste functia "encode" pentru codificarea unui text "text" intr-un unui sir de caractere '0' si '1' (htxt)

void encodetxt (hnod* r, char* text, char * htxt);

5. Sa se scrie si sa se verifice o functie pentru decodificarea unui codHuffman (sir de caractere '0' si '1' ) intr-un caracter ASCII :

char decode (hnod* r, char* & hc); // rezultat caracter ASCII

Sa se scrie o functie "decodetxt" care foloseste functia "decode" pentru decodificarea unui sir de caractere '0' si '1' (htxt) intr-un text ASCII:

void decodetxt (hnod* r, char * & htxt, char* text);

Sa se afiseze textul "text" refacut dupa decodificare si sa se compare cu textul initial, folosind functia "strcmp".

Exemplu de text: afaeadaceababacefadeaebaecfeadaeabadcababdcabacefe

6. Sa se modifice definitia tipului hnod prin adaugarea unui pointer catrenodul parinte. Se va modifica si functia "make" pentru adaugarea legaturii la parinte pentru nodurile fii "left" si "right". Functia "encode" se va rescrie dupa algoritmul urmator:

cauta adresa p a nodului ce contine pe "ch" repeta cat timp p != r { daca p este fiu stanga atunci adauga '0' la sirul "hc" daca p este fiu dreapta atunci adauga '1' la sirul "hc" p = parinte(p) } inversare sir "hc" cu functia "strrev"

Sa se verifice functiile modificate impreuna cu celelalte functii din program.