 |  |
|
Universitatea "POLITEHNICA" Bucuresti
Proiect Analiza Algoritmilor
Comprimare/decomprimare Huffman--
Cuprins
Prezentare algoritmului de comprimare/decomprimare Huffman
2 Explicarea programelor
3 Teste
4 Concluzii
1 Descriere algoritm de comprimare Huffman
1.1 Necesitatea comprimarii datelor
Comprimarea datelor este o tehnica mult folosita in lumea de azi a calculatoarelor. Ea are aplicatii in grafica, transmisie de date prin sateliti, fibre optice sau cabluri electrice, baze de date de mari dimensiuni si multe alte domenii, si, bineinteles, in economisirea spatiului pe HDD.
1.2 Ideea. Algoritmul
Ideea de baza a algoritmului de comprimare Hufman este aceea ca intr-un fisier de tip text apar diverse caractere cu frecvente de aparitie diferite- s-a observat ca litere precum 'a', 'i', 'e' apar mai des decat 'z', 'w', 'x'. In cele mai multe din calculatoarele actuale toate caracterele se codifica pe opt biti, dupa codul ASCII. In acest fel toate caracterele ocupa fix un octet in fisier, adica opt biti, indiferent de frecventa lor de aparitie.
De aici provine si ideea compresiei: atribuirea de coduri mai scurte caracterelor care apar mai des in text si coduri mai lungi celor care apar mai rar.
1.3 Construirea arborelui Huffman
Pentru inceput se calculeaza numarul de aparitii in text pentru fiecare din caractere. Apoi se ordoneaza caracterele dupa acest numar, in ordine crescatoare. Sa presupunem ca in urma calculului obtinem literele din text cu frecventele lor:
g[1] i[2] t[3] r[4] e[6] a[6]
Se considera ca fiecare dintre litere ca fiind un arbore binar format dintr-un singur nod. In continuare se vor lua primii doi arbori din secventa si se vor concatena intr-un singur arbore a carui radacina va avea ca frecventa suma frecventelor arborilor concatenati. Apoi lista arborilor se reordoneaza.
Iata cum arata lista dupa aplicarea acestor operatii:
3 t[3] r[4] e[6] a[6]
/
g[1] i[2]
Se aplica operatia inca odata:
r[4] 6 e[6] a[6]
/
3 t[3]
/
g[1] i[2]
Si inca odata:
e[6] a[6] 10
/
r[4] 6
/
3 t[3]
/
g[1] i[2]
Din nou:
10 12
/ /
r[4] 6 e[6] a[6]
/
3 t[3]
g[1] i[2]
Si pentru ultima oara:
22
/
/
/
10 12
/ /
r[4] 6 e[6] a[6]
/
3 t[3]
/
g[ i[2]
Se observa ca algoritmul se aplica pina ce se obtine un singur arbore. Pentru a obtine un 'arbore de codificare Huffman' mai trebuie etichetate arcele ce pornesc spre stinga cu 0 si cele ce pornesc spre dreapta cu 1:
22
/
0/ 1
/
10 12
0/ 1
r[4] 6 e[6] a[6]
0/ 1
3 t[3]
0/ 1
g[1] i[2]
Pe baza acestui arbore putem obtine noile coduri astfel: codul unui caracter este format in succesiunea de cifre binare ce se afla pe calea dinspre radacina spre acel caracter. In exemplul nostru codurile sint:
g -> 0100 i -> 0101 t -> 011 r -> 00 e -> 10 a
-> 11
Se observa ca nici unul din coduri nu este prefix pentru vreun altul, acest lucru fiind asigurat de arborele Huffman. Sa vedem cum se realizeaza efectiv compresia si decompresia datelor folosind acest arbore.
1.4 Comprimarea
Pentru compactare se procedeaza astfel: se parcurge fisierul sursa si se stabileste numarul de aparitii pentru fiecare din cele 256 de caractere din codul ASCII. Pe baza acestor numere se construieste arborele Huffman ce se memoreaza in 'lista', unde se pastreaza caracterul, frecventa, si legaturile specifice unui arbore : fii si tata .
Apoi incepe procesul de comprimare propriu-zis. Pentru inceput se salveaza in fisierul comprimat arborele construit pentru a putea fi reconstituit atunci cind se va trece la decomprimare. In continuare se parcurge fisierul sursa si pentru fiecare caracter se emite in fisierul arhiva codificarea conform arborelui Huffman. Aceasta emisie este ceva mai delicata deoarece codurile au un numar variabil de biti in vreme ce functiile de scriere in fisier emit numai un numar intreg de octeti, adica un numar de biti divizibil cu opt.
1.5. Decomprimarea
Decomprimare este ceva mai simpla. La inceput se restaureaza din fisierul comprimat arborele salvat la c ompresie (de fapt numai vectorul ce memoreaza fiii). In continuare vom considera un cursor asezat initial pe nodul radacina al arborelui restaurat si vom citi siruri de biti din fisierul arhiva. Pentru fiecare bit 0 se executa un avans al cursorului pe fiul sting, respectiv pentru fiecare bit 1 un avans al cursorului pe fiul drept al nodului curent. Atunci cind cursorul ajunge pe un nod ce nu mai are fii se emite in fisierul destinatie caracterul asociat acelui nod si se repozitioneaza cursorul pe nodul radacina al arborelui. Se procedeaza astfel pina la decomprimarea completa.
2 Explicarea programelor
2.1 Programul de comprimare 'huffcompc.c'
Deoarece pot exista si caractere ce pot sa nu apara in text am facut functia
int getzero() ce returneaza numarul de caractere a caror frecventa e mai mare de 0. Acestea nu sunt memorate in arborele de comprimare Huffman.
unsigned char oddchar() transforma codul binar in cod zecimal retinut pe un octet. Lungimea noilor coduri ale caracterelor nu e constanta. De aceea se completeaza codul cu zero pana se obtine un octet si apoi este transformat in zecimal.
void add2buff(int r) genereaza codul caracterului - insirurirea de 0 si 1 ce reprezinta calea de la radacina arborelui pana la frunza in care este retinut caracterul.
void refreshbuffer(FILE *p) scrie in fisierul comprimat noul cod al caracterului din fisierul de comprimat.
2.2 Programul de decomprimare 'huffdec.c'
Programul decomprimare e in general asemanator cu de comprimare. Aici apare o functie noua int retrievelf(char *filename) care are rolul de a extrage din fisierul comprimat frecventele de aparitie ale caracterelor, facand precizarea ca acestea au fost in prealabil memorate in fisierul comprimat.
Functia void add2buff(int c) are rolul de a face acum transformare codului din zecimal in binar ,care va arata modul de parcurgere al arborelui astfel incat pornind de la radacina sa se ajunga la frunza in care e memorat caracterul initial.
Functia void refreshbuffer(FILE *p) este in fapt functia ce se ocupa de decodarea fisierului, respectiv parcurce arborele de comprimare in functie de codul caracterului: 0 stanga, 1 dreapta.
In ambele programe citirea/scrierea datelor se face din si in fisier.
3 Teste:
Un fisier de 115KB format numai din cifra 1 a fost comprimat intr-un fisier de 1,1KB. In schimb un fisier format din 200 caractere 0 apoi 200 caractere 1 si asa mai departe pana la 9, de marime 1,82 KB a fost tranformat intr-un fisier de 1,77KB. Asadar se observa faptul ca marimea fisierului comprimat depinde de continutul fisierului de comprimat.
4 Observatii:
Principalul avantaj algoritmului este acela ca fisierele rezultate in urma comprimarii sunt, cu mici exceptii, mai mici decat fisierele initiale.
Un dezavantaj, al algoritmului este acela ca fisierul de comprimat trebuie parcurs de doua ori: o data pentru a afla frecventa de aparitie a caracterelor si apoi pentru comprimare propiu zisa.
Un alt dezavantaj este si faptul ca trebuie retinut arborele de comprimare huffman, lucru putin eficient in cazul fisierelor mici.
Acest referat nu se poate descarca
| E posibil sa te intereseze alte referate despre:
|
| Copyright © 2024 - Toate drepturile rezervate QReferat.com | Folositi referatele, proiectele sau lucrarile afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul referat pe baza referatelor de pe site. { Home } { Contact } { Termeni si conditii } |
Referate similare:
|
Cursuri |
Cauta referat |