Cuprins:

1. Coduri binare

2. Coduri de lungime fixă

3. Coduri de lungime variabilă

4. Codificarea/Decodificarea codurilor de lungime fixă

5. Codificarea/Decodificarea?? codurilor de lungime variabilă

6. Proprietatea prefix

7. Arborele Binar Strict cu Ponderi (ABSP)

8. Decodificare cu Arbore Binar Strict cu Ponderi

9. Algoritmul lui Huffman

Problema de rezolvat:

Avem la dispoziție un fișier ce contine o secvență de 100.000 de caractere.

Cum putem să-l stocăm cât mai compact?

Coduri binare:

• Dat V, un alfabet finit, 

• definim o funcție injectivă c:V->{0,1}*. Această funcție poartă numele de cod binar. Ex: c("A")=1010

• Prin extensia canonică a funcției peste șiruri de caractere din V, putem defini c:V*->{0,1}*, astfel încât pentru orice mesaj alcătuit prin concatenarea caracterelor din V, obținem o codificare acătuită din concatenarea codurilor respective din {0,1}*, ale fiecărui caracter din mesaj: c("AB") = c("A")|c("B") .

• Codurile se pot clasifica în

  1. coduri de lungime variabilă (cuvintele-cod au lungimi diferite)

  2. coduri de lungime fixă (cuvintele-cod au aceeași lungime)

• Definim frecvența de apariție a unui caracter într-o secvență ca fiind numărul de apariții al caracterului în secvență (eventual exprimată ca și procent din numărul total de caractere al secvenței).

• Un cod se bucură de proprietatea prefix dacă niciun cuvânt cod nu reprezintă prefixul altui cuvânt cod.

• Un cod care satisface proprietatea prefix se numește cod prefix (mai corect, cod liber de prefixe).

• Codurile prefix ne rezolvă problema anterioară, întrucât secvența codificată nu mai este ambiguă.

Există și o reprezentare mai bună pentru codurile prefix în așa fel încât să fie ușor de identificat cuvintele cod. Această reprezentare este dată de ...

• Strict = fiecare nod are 0 sau doi fii

• Cu ponderi = frunzele arborelui dețin în plus câmpuri de informație denumite ponderi.

În cazul nostru,

• 1. informația din frunze = caracterele ce trebuiesc codificate

  2. Ponderile = frecvențele apariției acestor caractere

În această reprezentare, cuvintele cod sunt determinate de parcurgerea drumului dinspre rădăcină către frunze, unde 0 înseamnă continuarea drumului către fiul stâng, iar 1 către fiul drept.

Singura problemă rămasă:

Cum construim ABSP corespunzător codurilor de lungime variabilă?

Răspuns:

Algoritmul lui Huffman construiește un ABSP optim (din toți ABSP garantează cea mai scurtă codificare).

Algoritmul lui Huffman:

  0. Introducem frunzele (caracter, frecvență) într-o coadă cu priorități. 

1. se extrag primele 2 noduri (corespunzătoare celor mai putin frecvente simboluri)

2. se creeaza un nou nod avand ca si frecvență suma celor 2 noduri extrase iar nodurile extrase devin fiu stang, respectiv drept

3. nodul nou se insereaza in coadă astfel încat coada este din nou sortată după frecvență

4. Repetăm pașii 1-3 până când avem un singur nod în coadă.

Rădăcina arborelui Huffman se găsește acum în coadă. Arborele a fost creat într-o manieră bottom-up dinspre frunze spre rădacină, iar nu top-down ca până acum.

• Pentru aflarea codurilor binare, se parcurge arborele dinspre radacina si se retine drumul parcurs 

• (0 dacă mergem pe legătura stangă si 1 când mergem pe legătura dreaptă)

• Când ajungem în noduri frunză (caracter, frecvență), atunci obtinem codul corespunzător acelui caracter.