Metode de codare Shannon Fano sau Huffman Static [625875]

Mijloace tehnice de protectie a
informatiei

Darea de seama

Tema: Metode de codare Shannon Fano sau Huffman Static

Grupa Ti -181
Student: [anonimizat]: Shannon Fano sau
Huffman static.

B. Aspecte teoretice

Ambii algoritmi considerați intră în categoria celor statistici . Implementarea cerut ă aici este cea
consacrată adică cea cu mode l semistatic (notația Huffman static este incorectă dar consacrată, de
aceea o vom folosi totuși în continuare).

Codorul parcurge următoarele etape :
1. Determinare a statisticii
2. Construire model (coduri)
3. Codare pe baza modelului

Decodorul parcurge următoar ele etape:
1. Preluare model
2. Decodare pe baza modelului

Pentru a simplifica transmiterea modelului spre decodor propun o soluție în care de fapt se
transmite spre decodor explicit statistica, etapele parcurse de decodor fiind în acest caz
următoarele:
1. Preluare statistică (din antet)
2. Construire model (coduri)
3. Decodare pe baza modelului

B1. Codificare Shannon -Fano – exemplu

Să considerăm fluxul: ABCDECDECD

1. Determinare a statisticii

Obținem frecvența de apariție a fiecărui simbol:

A B C D E
1 1 3 3 2
2. Construire model

Primul pas: sortarea (de obicei crescătoare) după frecvența de apariție.

A B E C D
1 1 2 3 3

Se împarte apoi mulț imea de simboluri în două submulțimi având suma frecvențelor cât mai
apropiat ă și atribuirea codului 0 respectiv 1 celor două ”jumătăți” (se încearcă astfel atribuirea
biților 0 și 1 cu o probabilitate cât mai apropiată de 0.5, cât este optimul teoretic).

A B E C D Simbol
1 1 2 3 3 Frecvență
-8 -6 -2 4 Diferența în cazul împărțirii în fiecare din poziții

Diferența minimă (în valoare absolută) este dată la împărțirea între E și C. Se împarte astfel și se
atribuie codul 0 primei “jumătăți” și codul 1 celei de a doua “jumătăți”. Se continuă apoi (de obicei
recursiv) asemănător pe fiecare din “jumătățile” o bținute până se ajunge la simboluri individuale.

În figura următoare prezentăm întregul proces.

A B E C D Simbol
1 1 2 3 3 Frecvență

0 1

0 1 0 1

0 1

Rezultă următoarele coduri:
A= 000
B= 001
C= 10
D= 11
E= 01

Observăm că avem de a face c u o abordare top -down de construcție a codurilor.

3. Codare pe baza modelului

Se parcurge fluxul (din nou) și se înlocuiește fiecare simbol cu codul aferent. Obținem astfel:

ABCDECDECD
șir inițial

0000011011011011011011
flux de date comprimate

Din păcate delimitarea între simboluri se pierde (codurile având lungime variabilă), ceea ce va
complica puțin decodarea.

B2. Codificare Huffman Static – exemplu

Să considerăm fluxul: ABCDECDECD

1. Determinare a statisticii

Obținem (la fel):
A B C D E
1 1 3 3 2
2. Construire model

În acest caz se grupează la fiecare pas cele două simboluri cu frecvența cea mai mica și se
înlocuiesc cu un simbol având frecvența egală cu suma acestora. Celor două sim boluri care s -au
grupat li se atribuie biții 0 respectiv 1. Se repetă acest procedeu până se grupează toate simbolurile
existente.

A B E C D
1 1 2 3 3
0\ /1

A+B E C D
2 2 3 3
0\ /1

A+B+E C D
4 3 3
0\ /1

A+B+E C+D
4 6
0\ /1
A+B+E+C+D
10

În final codul este dat de secvența de biți de pe calea spre simbolul inițial (de la final spre simbol).

Rezultă următoarele cod uri:
A= 000
B= 001
C= 10
D= 11
E= 01

Observăm că avem de a face cu o abordare down -top de construcție a codurilor.

Pentru exemple mici (ca cel de față) codurile dau la fel cu cazul Shannon -Fano. Pentru exemple mai
mari ele însă vor diferi (teoretic, Huf fman este codul optim).

3. Codare pe baza modelului

Se face la fel ca în exemplul de la Shannon -Fano.

C. Implementare

Sunt doar indicații, nu sunt strict obligatorii, dar cred că simplifică semnificativ implementarea.

C1. Structura fișierului comprim at

După cum am amintit anterior propun salvarea în fișierul comprimat a informațiilor legate de
statistica apariției simbolurilor în fluxul de intrare. Schema generală:

Antet Flux de date comprimate (șirul de biți rezultat) (model)

devine în acest caz:

Antet Flux de date comprimate (șirul de biți rezultat) (frecvențele de apariție)

C2. Decodarea

1. Preluare statistică – se realizează foarte simplu, prin citirea frecvențelor de apariție din antet
2. Construire model (coduri) – simplu, se folosește aceeași funcție ca la codor (pe baza acelorași
frecvențe se va genera același model).
3. Decodare pe baza modelului. Aici sunt două abordări posibile:

Prima : se citește câte un bit din fluxul de date comprimate până se obține un cod vali d. Această
soluție este destul de ineficientă (mai ales când sunt multe simboluri și codurile sunt lungi).

A doua : se citește câte un bit și se parcurge arborele (modelul). Se pleacă din rădăcină și se
parcurge stânga sau dreapta conform cu bitul următor di n flux până se atinge o frunză, obținând
astfel simbolul decodificat. Se reia apoi din rădăcină pentru următorul simbol, etc.

D. Concluzie

Putem spune ca ambele metode : Shannon Fano si Huffman Static, sunt niste metode benefice care
simplifica capacita tea de memorare a unor date dar fiecare are calea sa de parcurgere pentru codare.
Aceasta se observa dupa exemplele de mai sus B1 si B2, dar urmatindu -le se vede ca metoda
Shannon Fano este mai complicate decit cea Huffman Static. Din aceasta cauza putem s pune ca
metoda de codificarea a lui Huffman este mai eficienta si optima decit codarea Shannon Fano.