Clasa VII/VIII lecția 29 - 27 mai 2014

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]

Lecţie - compresia folosind arbori Huffman

Voi prezenta în continuare o introducere în compresia datelor cu exemplificare prin metoda Huffman. Subiectul compresiei, pe lîngă faptul că este un subiect foarte interesant şi foarte important în lumea calculatoarelor, ne dă şi o temă cu implementare destul de grea, peste nivelul problemelor de olimpiadă. Este nevoie de minţi ascuţite pentru a implementa si depana codul compresiei :)

Introducere

Conform Wikipedia, în știința calculatoarelor și teoria informației compresia datelor implică o codificare a informației folosind mai puțini biți decît reprezentarea originală. Compresia poate să fie cu sau fără pierderi. Compresia este utilă deoarece reduce utilizarea resurselor cum ar fi spațiul de stocare a datelor sau capacitatea ocupată la transmisie.

Tipuri de compresie

  • Cu sau fără pierderi. Compresia este fără pierderi dacă putem obține originalul din datele comprimate (nu se pierde informație), cum ar fi compresia cu zip. Compresia este cu pierderi atunci cînd nu obținem originalul, ci ceva apropiat (pierdem informație la comprimare), cum ar fi în compresia imaginilor gen jpeg sau a sunetelor, gen mp3 sau ogg. În aceste cazuri se dorește ca "aruncînd" informație nesesizabilă (sperăm) să obținem o compresie mai bună.
  • Statică sau dinamică. O metodă statică își fixează parametrii înainte ca transmisia să înceapă, astfel încît un mesaj dat este codificat prin același cod de fiecare dată cînd apare. O schemă statică clasică este codificarea Huffman despre care vom vorbi mai jos. O metodă dinamică, prin contrast, se adaptează la variațiile locale, schimbînd codurile mesajelor în timpul compresiei.
  • Universală sau dedicată. Metodele universale se aplică tuturor șirurilor de simboluri, indiferent de semnificația lor

semantică. Ele țin cont numai de redundanța probabilistă ce apare uzual în datele manipulate de om. Ca exemplu avem arhivatoarele generale cum ar fi zip. Metodele dedicate se aplică unor categorii restrînse de date și se bazează pe o anumită redundanță, ordine și reguli specifice categoriei căreia i se aplică. Schemele de codificare dedicate obțin de obicei o rată de compresie mult mai bună, deoarece dispun de mai multă informație. Ca exemplu avem compresia de imagini, video sau sunet.

Arbori de codificare

Să considerăm un fișier care conține un text scris în limba română, de exemplu această pagină. în general, în limba noastră apar mai des caractere ca 'a', 'e' sau 'i' și mai rar caractere ca 'z', 'w', 'x', etc. Cu toate acestea, calculatorul codifică toate aceste caractere folosind opt biți de informație, adică un octet, indiferent de frecvența lor de apariție. Un șir de 10 caractere va ocupa întotdeauna exact 10 octeți într-un fișier, adică 80 de biți.

Astfel apare următoarea idee: ce s-ar întîmpla dacă am codifica literele frecvente cu coduri mai scurte iar cele mai puțin frecvente cu coduri mai lungi? De exemplu să codificăm pe 'a' cu 001, pe 'e' cu 010, iar pe 'z', care este relativ rar, cu 0000000001. Această idee este veche, fiind aplicată şi în alfabetul Morse, care codifică literele prin șiruri de linii (semnale lungi) și puncte (semnale scurte). In mod similar, codul ASCII le codifică prin 0 și 1.

O metodă de compresie pe baza acestei idei a fost descrisă de către David A. Huffman în anul 1952. Ea folosește pentru memorarea noilor coduri ale caracterelor arbori de codificare. Ce sînt acești arbori? Să luăm un exemplu. Fie arborele de mai jos:

                                  *
                                0/ \1
                                /   \
                               /     \
                              *       *
                            0/ \1   0/ \1
                            A   *   E   I
                              0/ \1
                              M   N

El este format din noduri interioare (marcate cu *) și noduri terminale, marcate cu litere. Obsevăm două lucruri:

  1. Toate nodurile interioare au exact doi descendenți.
  2. Toate ramurile din stînga sînt etichetate cu '0', iar toate cele din dreapta cu '1'.

Pe baza acestui arbore de codificare putem obține codurile literelor conținute în el, astfel: codul unui caracter se obține luînd șirul de biți ce se găsește pe calea dinspre rădăcină spre caracterul respectiv. De exemplu, în acest arbore, caracterele au următoarele coduri:

       A - 00, E - 10, I - 11, M - 010, N - 011

Arborii de codificare asigură faptul că nici un cod al unui caracter nu este prefix pentru alt cod. închipuiți-vă ce s-ar întîmpla dacă am codifica astfel:

      A - 0001, E - 1001, K - 10010001

în cazul acesta, dacă întîlnim secvența 10010001, nu știm dacă este este vorba despre codificarea lui 'EA' sau a lui 'K'. Acesta este rostul arborilor de codificare, de a nu permite asemenea situații.

Construcția arborilor de codificare Huffman

Arborele Huffman este un arbore de codificare special, care dă coduri mai scurte caracterelor care apar mai des în datele de comprimat. El se construieşte astfel:

Pentru început se calculează numărul de apariții în text pentru fiecare din caractere. Apoi se ordonează caracterele după acest număr, în ordine crescătoare. De exemplu, pentru textul

      eteraitareagaireataere

obținem următoarele litere cu frecvențele lor:


      g[1] i[2] t[3] r[4] e[6] a[6]

Considerăm fiecare dintre litere ca fiind un arbore binar format dintr-un singur nod. în continuare vom lua primii doi arbori din secvență și îi vom concatena într-un singur arbore a cărui rădăcină va avea ca frecvență suma frecvențelor arborilor concatenați. Apoi lista arborilor se reordonează. Să urmărim cum arată lista după aplicarea acestor operații :

                    3     t[3] r[4] e[6] a[6]
                   / \
                g[1] i[2]

Aplicăm operația încă odată:

                   r[4]      6     e[6] a[6]
                            / \
                           3  t[3]
                          / \
                       g[1] i[2]

și încă odată:

                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]

și pentru ultima oară :

                                   22
                                  /  \
                                 /    \
                                /      \
                              10        12
                             /  \      /  \
                           r[4]  6  e[6]  a[6]
                                / \
                               3  t[3]
                              / \
                           g[1] i[2]

Se observă că algoritmul se aplică pînă ce obținem un singur arbore. Pentru a obține un arbore de codificare Huffman mai trebuie etichetate arcele ce pornesc spre stînga cu 0 și cele ce pornesc spre dreapta cu 1 :

                                   22
                                  /  \
                                0/    \1
                                /      \
                              10        12
                            0/  \1    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 obține noile coduri astfel: codul unui caracter este format in succesiunea de cifre binare ce se află pe calea dinspre rădăcină spre acel caracter. în exemplul nostru codurile sînt:

       g -> 0100   i -> 0101   t -> 011   r -> 00   e -> 10  a -> 11

Se observă că nici unul din coduri nu este prefix pentru vreun altul, acest lucru fiind asigurat de arborele Huffman. Să vedem cum se realizează efectiv compresia și decompresia datelor folosind acest arbore.

Compresia

Pentru compresie se procedează astfel : se parcurge fişierul sursă și se stabilește numărul de apariții pentru fiecare din cele 256 de caractere posibile. Pe baza acestor numere se construieste arborele Huffman (detalii de implementare mai jos).

Apoi începe procesul de compresie propriu-zis. Pentru început se salvează în fișierul arhivă arborele construit (vom discuta despre diverse moduri de stocare) pentru a-l putea reconstitui atunci cînd vom trece la decompresie. în continuare se parcurge fișierul sursă și pentru fiecare caracter se emite în fișierul arhivă codificarea conform arborelui Huffman.

Decompresia

Pentru decompresie se restaurează din fișierul arhivă arborele salvat la compresie. în continuare vom considera un cursor așezat inițial pe nodul rădăcină al arborelui restaurat și vom citi șiruri de biți din fișierul arhivă. Pentru fiecare bit 0 se execută un avans al cursorului pe fiul stîng, respectiv pentru fiecare bit 1 un avans al cursorului pe fiul drept al nodului curent. Atunci cînd cursorul ajunge pe un nod ce nu mai are fii se emite în fișierul destinație caracterul asociat acelui nod și se repoziționează cursorul pe nodul rădăcină al arborelui. Se procedează astfel pînă la decompresia completă.

Considerente de implementare

Să menţionăm cîteva detalii de implementare.

Fişiere binare

În limbajul C fişierele pot fi deschise în mod text (implicit) sau în mod binar. În mod text sfîrşitul de linie poate fi transformat. Nu intru aici în detalii, dar desigur că aceasta nu este de dorit, drept pentru care vom folosi modul de deschidere binar, adăugînd litera b la modul de deschidere:

fin = fopen( "lectie.odt", "rb" );
fout = fopen( "lectie.huf", "wb" );

Revenirea cursorului la început de fişier

Fişierul de citire va fi parcurs de două ori. Pentru a doua parcurgere putem să îl închidem şi apoi să îl redeschidem, dar este mai uşor, mai elegant şi mai eficient să îl "derulăm" la început cu comanda:

fseek( fin, 0, SEEK_SET ); // revino la începutul fişierului

Operaţiuni pe biţi în fişier

Pentru implementare vom avea nevoie să citim şi să scriem bit cu bit în fişier. Cum facem acest lucru cînd funcţiile fgetc()/fputc() operează cu octeţi? Vom folosi un caracter tampon (buffer), pe care îl putem declara global, pentru uşurinţa programării. Funcţia noastră de scriere a unui bit va adăuga de fapt la acest tampon. În momentul cînd se strîng opt biţi scriem tamponul în fişier:

int hufbyte, hufnbits;
...
// scrie un bit in fisier folosind un buffer de un caracter
inline void fputb( int bit ) {
  hufbyte = (hufbyte << 1) + bit;
  if ( ++hufnbits == BITS_PER_CHAR ) {
    fputc( hufbyte, fout );
    hufnbits = 0;
    hufbyte = 0;
  }
}

Trebuie să avem grijă ca la finalul compresiei să scriem tamponul în fişier în caz că hufnbits nu este zero, deoarece în acest caz vom avea biţi rămaşi nescrişi.

Structura de date arbore de codificare

Cum stocăm arborele Huffman? Să observăm că el va avea 256 de frunze (toate caracterele posibile) şi 255 de noduri interne. O posibilă reprezentare în memorie ar fi să memorăm 511 noduri. Pentru fiecare nod trebuie să ştim părintele lui, fiul stîng, fiul drept şi "greutatea" lui, respectiv numărul total de apariţii al tuturor caracterelor din subarborele său, care este suma apariţiilor tuturor frunzelor din acel subarbore. O reprezentare facilă este:

#define BITS_PER_CHAR 8
#define NO_CHAR (1<<BITS_PER_CHAR)
#define NODES (NO_CHAR * 2 - 1)
...
int parent[NODES];
long long freq[NODES];
int left[NODES], right[NODES];

Remarcaţi că frecvenţele sînt de tip long long, deoarece ele pot depăşi un întreg pentru fişiere foarte mari.

În acest arbore primele noduri, cele cu indici între 0 şi 255, vor fi frunzele, respectiv chiar caracterele de codificat.

Stocarea arborelui Huffman pe disc

La stocarea pe disc a arborelui dorim ca el să ocupe cît mai puţin, deoarece el se adaugă la fişierul comprimat. Avem următoarele posibilităţi:

Stocarea frecvenţelor

Dacă stocăm frecvenţele caracterelor pe disc putem să refacem apoi arborele. Memorie necesară: 256 de long long = 2048 octeţi.

Stocarea vectorilor fii

Dacă stocăm vectorii fii, left şi right putem să refacem apoi arborele. Memoria necesară ar fi, la prima vedere, 511 * 2 * int, adică 4088 octeţi. În realitate observăm că:

  • frunzele nu au fii, ci doar nodurile interne
  • valorile indicilor fiilor sînt între 0 şi 510

Ceea ce înseamnă că putem stoca doar 255 * 2 * 9 biţi = 4590 biţi = 574 octeţi.

Stocarea parcurgerii arborelui

O metodă mai eficientă porneşte de la următoarea optimizare a ideii anterioare: în loc să memorăm indicii fiilor pentru fiecare nod intern am putea să memorăm un singur bit 1 pentru nod intern sau 0 pentru frunză şi să avem grijă la ordinea de stocare a nodurilor. Mai exact, pentru un nod intern vom stoca un bit 1 şi apoi codificarea subarborelui stîng, urmată de codificarea subarborelui drept. Pentru un nod frunză vom stoca un bit 0 şi apoi codul ASCII al caracterului frunză.

De exemplu, pentru arborele Huffman anterior:

                                   22
                                  /  \
                                0/    \1
                                /      \
                              10        12
                            0/  \1    0/  \1
                           r[4]  6  e[6]  a[6]
                               0/ \1
                               3  t[3]
                             0/ \1
                           g[1] i[2]

Vom stoca:

110r110g0i0t10e0a

unde r înseamnă de fapt cei opt biţi din reprezentarea ASCII a lui r.

Această codificare necesită stocarea tuturor caracterelor plus cîte un bit pentru fiecare nod al arborelui, intern sau frunză. Cum numărul de noduri este 511 rezultă că memoria ocupată va fi: 256 * 8 + 511 biţi = 2559 biţi = 320 octeţi.

Precum vedeţi această stocare are o definiţie recurentă şi se implementează natural cu o funcţie recursivă.

Arbori Huffman canonici

Există o stocare mai bună ce necesită cel mult 256 octeţi, bazată pe canonizarea arborelui Huffman obţinut. Vom proceda astfel:

În primă fază vom calcula pentru fiecare simbol lungimea codului Huffman obţinut. Apoi vom "arunca" arborele Huffman. În exemplul nostru avem următoarele lungimi de coduri:

a(2) e(2) g(4) i(4) r(2) t(3) 

Observaţi că am scris caracterele în ordine alfabetică (în ordinea codurilor ASCII pentru cazul general).

Ce facem mai departe? Vom atribui coduri de aceleaşi lungimi, în ordinea lungimii codurilor, de la mic la mare, şi în cadrul aceleiaşi lungimi în ordinea numărului codului Huffman, atribuindu-le caracterelor de aceeași lungime în ordine alfabetică a caracterelor. În cazul nostru vom avea:

a -> 00
e -> 01
r -> 10
t -> 110
g -> 1110
i -> 1111

Aşezînd aceste coduri într-un arbore Huffman vom obţine:

                                   *
                                  / \
                                0/   \1
                                /     \
                               *       *
                             0/ \1   0/ \1
                             a   e   r   *
                                       0/ \1
                                       t   *
                                         0/ \1
                                         g   i

Acesta este arborele Huffman canonic. El este unic, precum spune şi denumirea. Aceasta înseamnă că, date lungimile de cod ale fiecărui caracter, există un unic arbore Huffman canonic care corespunde acelor lungimi.

Această proprietate îl face perfect pentru stocarea pe disc: vom memora doar lungimile de cod ale fiecărui caracter. Cum lungimea unui cod nu poate fi mai mare de 255 de biţi (demonstraţi!) rezultă că avem nevoie de un octet pentru memorarea unei lungimi, în total 256 de octeţi pentru toate lungimile.

Unicitatea compresiei

Arborele obţinut depinde de următoarele de modul de sortare a numărului de apariţii şi de modul de inserţie al subarborilor obţinuţi pe parcurs în lista ordonată de subarbori. Unicitatea arborelui nu este importantă. Cu toate acestea, pentru a putea crea o problemă pe vianuarena avem nevoie de unicitate, drept pentru care vom adăuga următoarele reguli:

  • la sortarea iniţială a caracterelor după numărul de apariţii caracterele care au acelaşi număr de apariţii vor apărea în ordine alfabetică
  • atunci cînd creăm un nou subarbore îl vom migra spre finalul vectorului de arbori pînă la prima poziţie unde se potriveşte

Oprirea din decompresie

De unde ştim cînd ne oprim din decompresie? Ştim că la final de fişier este posibil să avem nişte biţi "de umplutură", deoarece lungimea codificării în biţi nu este neapărat multiplu de 8. Dacă vom folosi acei biţi extra în procedura de decompresie s-ar putea să obţinem caractere în plus care nu există în fişierul sursă. Ce putem face? O soluţie simplă este să stocăm în fişierul comprimat lungimea fişierului original. Vom stoca această lungime chiar la începutul fişierului comprimat. La decompresie vom citi lungimea, apoi arborele Huffman şi apoi ne vom opri din decompresie cînd am decodificat numărul de caractere necesar.

Dezavantajele compresiei Huffman

Metoda de compresie cu arbori de codificare Huffman statici, are unele dezavantaje:

  • Fișierul de comprimat trebuie parcurs de două ori, o dată pentru a calcula numărul de apariții al fiecărui caracter și a doua oară pentru compresia propriu-zisă. Acest lucru înseamnă că metoda nu poate fi folosită, de exemplu, în cazul transmisiilor de date prin cablu sau prin satelit, deoarece în acest caz datele nu sînt neapărat memorate ceea ce face imposibilă reluarea. Totodată datele avînd un flux continuu nu se poate pune un "capăt" transmisiei pentru a construi arborele Huffman și a face efectiv compresia.
  • Arborele generat trebuie memorat în fișierul arhivă, ceea ce generează o încărcare suplimentară a codului comprimat. Modul standard de stocare a unui arbore Huffman canonic necesită 256 octeți, ceea ce înseamnă destul de mult pentru fișiere mici.
  • Ca orice metodă statică de compresie metoda Huffman nu se adaptează variațiilor locale ale frecvenței caracterelor. De exemplu, dacă presupunem un text ce conține 1000 de caractere cu cod 0, apoi 1000 de caractere cu cod 1, apoi 1000 cu cod 2 și așa mai departe pînă la 1000 de caractere cu cod 255, acest text nu va fi comprimat, ci dimpotrivă, va fi "umflat" din cauza memorării arborelui.

Temă

Scrieţi un program care să comprime sau să decomprime un fişier folosind metoda Huffman.

Opţional, pentru cine se simte aventuros, aveţi următoarea temă destul de grea, care vă va cere compresia/decompresia cu arbori Huffman canonici:

Tema 29 clasele 7/8

Rezolvări aici [2]