art02.pdf

TESTAREA EXPERIMENTL A UNOR ALGORITMI DE COMPRESIE A DATELOR

drd. ing. Cristian-Valentin Eremia prof. dr. ing. Mihai [email protected] [email protected]

Universitatea Politehnica Bucureti

Rezumat: Lucrarea prezint rezultatele testrii experimentale a 5 algoritmi de compresie a datelor (Shannon-Fano, LZW, Huffman Standard, Huffman Dinamic, Compresie Aritmetic). Testarea a avut scop evidenierea performanelor acestor algoritmi de compresie n funcie de caracterul datelor (text, imagine, sunet, executabil, librrii dinamice, C++, Pascal).

Cuvinte cheie: Shannon-Fano, LZW, Huffman Standard, Huffman Dinamic, Compresie Aritmetica

Abstract: The paper presents results of experimental testing of 5 data compression algorithms (Shannon-Fano, LZW, Standard Huffman, Dynamic Huffman, Arithmetic Compression). Testing was intended to highlight the performance of compression algorithms depending on the nature of the data (text, image, sound, executable, dynamic libraries, C++, Pascal).

Keywords: Shannon-Fano, LZW, Standard Huffman, Dynamic Huffman, Arithmetic Compression

1. Introducere

Scopul compresiei de date este acela de a mbunti performanele operaiilor ulterioare efectuate asupra acestor date: stocare, transmisie etc. Toate sistemele de compresie necesit doi algoritmi: unul pentru comprimarea datelor la surs i altul pentru decomprimarea datelor la destinatar. Prin compresie de date se urmrete ca, folosind anumite procedee, s se realizeze o trecere (transformare) a unui fiier F, de lungime L bii, ntr-un fiier Fc, de lungime Lc

Un limbaj este alctuit din mulimea de cuvinte i regulile de folosire a acestora.

Compresia datelor este folosit i n cadrul sistemelor de stocare ori de transmisie la distan, a datelor de tip text sau a datelor de tip sunet ori de tip imagine reprezentate n format digital. Explozia dimensional a fiierelor de date are loc n primul rnd n cazul sistemelor multimedia care comport transmisia i prelucrarea unui volum mare de informaii n reelele de calculatoare.

Toate sistemele de compresie conin un codor i un decodor. Codorul realizeaz conversia datelor provenite de la surs, n date comprimate, iar decodorul ncearc, la recepie, s reconstituiasc datele iniiale pe baza datelor comprimate. Datele reconstituite prin decodare fie coincid cu datele emise de surs, fie difer ntr-o msur nesemnificativ pentru scopul propus. Aceast diferen ntre lungimea n bii a fiierului compresat i a celui necompresat trebuie evaluat i sistemul de compresie se ajusteaz funcie de scopul propus. Pentru a evalua calitile unui sistem de compresie se definete o mrime numit raport de compresie:

Dimensiunea datelor emise de surs n biiDimensiunea datelor comprimate n bii r = (1.1)

Un raport de compresie "2 la 1", semnific faptul c datele comprimate au jumtate din dimensiunea datelor emise de surs. Un raport de compresie mare va desemna un sistem de compresie mai bun.

Procedurile de compresie de date se utilizeaz de mai mult vreme, fiind la nceput legate de stocarea pe un suport magnetic a textelor redactate n format electronic. Chiar i n acest domeniu evoluia a fost foarte spectaculoas, performanele algoritmului de compresie mbuntindu-se n ritm accelerat. Dar aceste tehnici care permit prin operaia invers de decompresie, refacerea exact (fr pierderi) a ansamblului original ofer un grad redus de compresie, deoarece se bazeaz doar pe eliminarea redundanei naturale a sursei de informaie, care chiar dac exist, are o valoare limitat. Rapoartele mult mai mari de compresie se pot obine dac se renun la refacerea exact a semnalului informaional, dar atunci trebuie acceptat un compromis ntre factorul de compresie i precizia cu care se realizeaz refacerea.

Scopul acestei lucrri este s se realizeze:

- Studiul teoriei frecveniale Shannon de compresie a fiierelor de tip TXT;

- Implementarea unui sistem ilustrativ bazat pe algoritmul ShannonFano, Huffman etc. de compresie;

- Testarea experimental a principalelor metode de compresie a fiierelor de date i evaluarea comportamentului acestora n cazul diverselor tipuri de fiiere: TXT, EXE, C++, Pascal, sunet, video. Evaluarea metodelor se face pe baza ratei de compresie.

1.1. Teorema lui Shannon privind fiierul compresat

Conceptele de entropie, cantitate de informaii i redundan au fost definite la nceputul anilor '40, adic odat cu primele noiuni de Teoria Informaiei. Ideea de baz care a declanat numeroase cercetri n domeniul Compresiei Datelor a fost urmtoarea: dac s-ar cunoate probabilitatea ce apare ntr-un set de date, atunci aceste simboluri ar putea fi recodificate n aa fel nct lungimea total a noilor coduri s fie inferioar lungimii originale a setului de date. n termeni de compresie, acest efect se numete minimizarea redundanei setului de date.

Redundana empiric se evalueaz prin diferena ntre numrul de bii iniial No i numrul de bii din fiierul compresat Nc.

ENTROPIA unui simbol exprim cantitatea de nedeterminare pe care o elimin prezena simbolului respectiv n fiier. Spre exemplu, dac din alfabet este ters unul din simbolurile de frecven maxim, practic nu se mai nelege ce vrea s exprime coninutul informaional al fiierului. Deci, cantitatea de informaie coninut n simbol, respectiv aportul informaional al simbolului la cantitatea de informaie a ntregului fiier, este mare, dac

Revista Romn de Informatic i Automatic, vol. 20, nr. 1, 2010 22


simbolul are frecvena mare i deci entropia aceluiai simbol este mic.

Relaia de definiie, propus de SHANNON pentru ENTROPIA H(sk) a unui simbol sk din alfabet este[2]:

H(sk)=-f(sk)log2f(sk), (1.2) n care log2 este logaritmul n baza 2.

De remarcat c, ntruct frecvenele sunt aceleai att pentru simbolurile din fiierul compresat ct i necompresat, entropiile simbolurilor sunt aceleai dar lungimile codurilor compresate sunt diferite n fiierul compresat i necompresat.

1.2. Teorema Shannon privind lungimea i entropia fiierului compresat:

Observaie:

Nici o metod de compresie nu poate furniza o lungime Lc, a fiierului compresat, mai mic dect H entropia fiierului.

Compresia de date este operaia prin care se reprezint compact datele furnizate de o anumit surs. n funcie de sursa care le genereaz, forma i tipul de date variaz:

- text,

- imagine,

- semnal vocal,

- semnal video.

Cnd ne referim la multimedia ne referim la combinarea dintre dou sau mai multe media continue, adic media care trebuie s se desfoare ntr-un interval bine definit, de obicei folosind interaciunea cu utilizatorul. n practic cele dou media sunt audio i video. O und audio este o und cu specific acustic.

1.3. Standardul JPEG pentru compresia imaginilor n tonuri continue

Figura 1. Structura i coninutul procedurii, n 6 pai de codificare a imaginii RGB cu JPEG

Standardul JPEG (Joint Photographic Experts Group) pentru comprimarea imaginilor n tonuri continue, a fost dezvoltat de experii n fotografii. Este important pentru multimedia deoarece la o prim aproximare, standardul multimedia pentru filme, MPEG este codificarea JPEG a fiecrui cadru separat, plus cteva caracteristici pentru comprimarea ntre cadre i detectarea micrii. JPEG este definit n Standardul Internaional 10918. JPEG are patru moduri i multe opiuni, fiind folosit n mod normal pentru codificarea imaginilor video de 24 bii RGB. Ne vom ocupa mai mult de modul secvenial cu pierderi. n figura 1.1 este prezentat structura i coninutul procedurii, n 6 pai de codificare, cu JPEG, a unei imagini RGB.

Pregtirea

Transformarea cosinusoidal

discret

Cuantificarea Cuantificarea diferenial

Codificarea funciei de lungime

Codificarea statistic

1.4. Standard MPEG (Motion Picture Experts Group)

Algoritmii principali din familia MPEG sunt destinai pentru compresia video i sunt standarde internaionale din 1993. Deoarece filmele conin att imagini ct i sunete, MPEG le poate comprima pe amndou. Primul standard finalizat a fost MPEG-1. Scopul lui a fost de a produce ieiri video de calitatea video-recorder-elor (352x240) folosind o rat de bii de l,2 Mbps. Video necomprimat poate ajunge la 472 Mbps, reducerea lui la 1,2 Mbps este nsemnat, chiar i la aceast rezoluie sczut. MPEG-1 poate fi transmis pe linii torsadate la distante modeste.Urmtorul standard din familia MPEG a fost MPEG-2 care a fost proiectat iniial pentru comprimarea video-ului de calitate de difuzare ntre 4 i 6 Mbps. Mai trziu MPEG a fost extins pentru a suporta rezoluii nalte. MPEG-4 este pentru video-conferine de rezoluie medie cu cadre de vitez sczut, (10 cadre/sec) i la lrgimi sczute de banda (64 Kbps). Principiile de baz ale lui MPEG-1 i MPEG-2 sunt similare dar detaliile sunt diferite.

Codificator

audio

Codificator video

Multiplexorul de sistem

Semnal audio

Semnal video

MPEG-1 CEAS

Figura 2. Structura standardului MPEG-1

Compresia audio MPEG este fcut prin eantionarea formei de und la 33 kHz, 44,1 kHz sau 48 kHz. Ea poate s gestioneze mono, stereo disjunct (fiecare canal separat) sau stereo reunit (este exploatat redundana ntre canale). Este organizat pe trei nivele, fiecare dintre ele aplicnd optimizri suplimentare pentru a obine o compresie mai mare. Nivelul 1 este schema de baz. Acest nivel este folosit, de exemplu, n sistemul de band DCC. Nivelul 2 adaug schemei de baz alocarea avansat de bii. Este folosit pentru CD-ROM-uri audio i de pistele sonore ale filmelor. Nivelul 3 adaug filtre hibride, cuantificare neuniform, codificare Huffman i alte tehnici avansate.

Audio MPEG poate comprima un CD de muzic pn la 96Kbps fr o pierdere perceptibil a calitii. Numrul difer de la o muzic la alta pentru c rata de semnal-zgomot difer. Comprimarea audio este realizat prin transformata Fourier rapid a semnalului audio pentru a-l converti din domeniul timpului n cel al frecvenei. Spectrul realizat este divizat n 32 benzi de frecven fiecare procesat separat. Atunci cnd exist dou canale stereo, redundana inerent n a avea dou surse audio suprapuse este de asemenea exploatat. Fluxul audio MPEG-1 rezultat este ajustabil de la 32Kbps la 448Kbps.

Obiectivul principal al cercetrii n faza definitivrii tezei de doctorat este testarea unor algoritmi de compresie pe diverse tipuri de fiiere de date cu scopul de a verifica experimental pentru care tipuri de fiiere se preteaz, cel mai bine, diverii algoritmi pentru compresii de date. Rezultatele experimentale ale acestei testri sunt coninute de acest capitol.

2. Testarea experimental

n ceea ce privete programele de implementare a diverilor algoritmi testai, le-am folosit pe cele care se gsesc prezentate n lucrarea recent, intitulat Compresia datelor, publicat n anul 2003, de ctre domnul profesor universitar Dr. ing. Dan STEFNOIU.


Exist o diversitate foarte mare de algoritmi de compresie i variaii ale acestora. Vom face o analiz comparat pe mai multe tipuri de fiiere, de dimensiuni diferite i cu diferii algoritmi.

n analiz vom folosi urmtoarele 8 tipuri de fiiere: dll: biblioteci dinamice; pas: fiiere Pascal; txt: fiiere text; exe: fiiere executabile; wav: fiiere sunet; bmp: fiiere BitMap; cpp: fiiere C++; img: fiiere imagine.

Analiza o vom face folosind urmtorii algoritmi:

- A: compresia Huffman standard; - B: compresia Shannon-Fano; - C: compresie Huffman dinamic; - D: compresie aritmetic de ordin n; - E: compresie LZW

2.1. Calculul gradului de compresie

Relaia de definiie a gradului de compresie g, utilizat pentru prelucrarea datelor experimentale este urmtoarea:

'1 * 1 0 0

Lg

L= (1.3)

Unde: - L' - lungimea fiierului compresat printr-un algoritm de compresie din

mulimea celor selectate pentru testare; - L - lungimea fiierului iniial necompresat.

2.2. Rezultatele testrii celor 5 algoritmi pe 10 diverse tipuri de fiiere de lungimi diferite

Tabelul 1 - Rezultate pentru fiiere de tip dll (librrii dinamice):

Fiier iniial Huffman Huffman Compresie Shannon Fano LZW (dim n bytes) Standard Dinamic Aritmetic

37440 33% 31% 34% 26% 49% 119056 26% 18% 19% 31% 52% 161552 33% 18% 19% 31% 48% 59904 32% 22% 23% 17% 54% 109424 30% 16% 17% 14% 47% 11776 31% 29% 34% 26% 39% 217088 43% 17% 18% 20% 50% 470528 27% 21% 16% 34% 51% 469504 33% 22% 16% 24% 52% 5632 33% 28% 38% 19% 49% Media 33% 23% 24% 25% 50%



Tabelul 2 - Rezultate pentru fiiere de tip PAS (surse Pascal)

Fiier iniial (dim n bytes)

HuffmanStandard Shannon Fano

HuffmanDinamic

Compresie Aritmetic LZW

25840 38% 37% 38% 38% 55% 49249 43% 43% 44% 44% 59% 18845 41% 41% 42% 42% 61% 27712 35% 35% 36% 36% 57% 33336 36% 36% 37% 37% 55% 30238 37% 37% 38% 38% 58% 10901 35% 34% 36% 36% 53% 7494 33% 33% 35% 35% 50% 16738 36% 36% 38% 37% 55% 9432 33% 32% 34% 34% 51% Media 37% 36% 38% 38% 56%

Tabelul 3 - Rezultate pentru fiiere de tip TXT(fiiere text)



HuffmanDinamic


19411 37% 36% 38% 38% 53% 36232 38% 37% 38% 39% 50% 42862 41% 41% 42% 42% 53% 4549 35% 35% 38% 39% 55% 36459 41% 41% 42% 42% 57% 20309 38% 38% 39% 42% 53% 23294 37% 37% 38% 38% 54% 10884 40% 40% 42% 42% 54% 60646 35% 37% 38% 38% 56% 90108 7% 34% 35% 35% 35% Media 35% 37% 40% 41% 54%

Tabelul 4 - Rezultate pentru fiiere de tip EXE (executabile)



HuffmanDinamic


74192 37% 25% 29% 26% 22% 39280 30% 30% 31% 31% 29% 19456 29% 27% 32% 31% 29% 2708 9% 3% 19% 17% 13% 10774 9% 9% 14% 14% 11% 44032 25% 25% 26% 26% 22% 15656 17% 15% 20% 20% 16% 77312 49% 33% 36% 34% 33% 111376 36% 23% 25% 24% 19% 19729 17% 15% 19% 19% 16% Media 26% 20% 25% 25% 22%


Tabelul 5 - Rezultate pentru fiiere de tip WAV (sunet)



HuffmanDinamic


12479 37% 15% 26% 26% 18% 55490 17% 6% 50% 45% 51% 1226 11% 18% 47% 30% 49% 7754 16% 16% 46% 50% 50% 4296 14% 12% 42% 42% 74% 12106 20% 13% 53% 22% 39% 25704 20% 20% 51% 51% 9% 22570 12% 12% 49% 14% 54% 33848 24% 2% 54% 51% 48% 28282 25% 12% 60% 47% 65% Media 19% 14% 48% 38% 48%

Tabelul 6 - Rezultate pentru fiiere de tip bmp (BitMap)



HuffmanDinamic


2118 75% 75% 77% 79% 74% 582 56% 55% 61% 58% 57% 470 46% 46% 58% 52% 35% 2102 31% 30% 39% 35% 37% 578 60% 60% 67% 62% 67% 38462 20% 20% 22% 22% 22% 590 50% 50% 59% 55% 55% 339178 66% 54% 59% 54% 64% 578 53% 53% 59% 56% 33% 198 29% 29% 47% 34% 27% Media 49% 47% 55% 51% 52%

Tabelul 7 - Rezultate pentru fiierele de tip CPP (surse C++)



HuffmanDinamic


15375 37% 37% 38% 38% 55% 40382 34% 34% 34% 35% 51% 23162 32% 32% 33% 33% 51% 478 14% 14% 34% 26% 25% 12501 32% 32% 33% 34% 47% 1354 25% 25% 36% 34% 35% 990 24% 24% 37% 34% 34% 35746 44% 43% 44% 45% 62% 405 16% 15% 40% 32% 21% 12234 35% 34% 36% 36% 59% Media 30% 29% 37% 35% 44%

Tabelul 8 - Rezultate pentru fiiere de tip IMG (imagine)

Fiier iniial Huffman Huffman Compresie Shannon Fano LZW (dim n bytes) Standard Dinamic Aritmetic 40410 26% 26% 27% 27% 27% 54696 29% 29% 31% 30% 65% 33822 34% 34% 35% 35% 38% 40028 17% 17% 19% 29% 51% 16900 26% 26% 29% 49% 48% 35640 18% 17% 19% 39% 36% 33622 17% 16% 18% 38% 41% 33230 19% 18% 20% 40% 44% 20894 19% 19% 21% 32% 70% 31652 18% 18% 20% 40% 39% Media 23% 22% 25% 33% 46%

2.3. Rezultate ale analizei comparative a testului

n cadrul etapei de analiz comparativ a rezultatelor experimentale ale testului s-au realizat reprezentari grafice ,prin bargrafuri, pentru toate rezultatele comparaiei ratelor medii calculate de compresie. Aceste reprezentari grafice ale rezultatelor analizei comparative si concluziile desprinse din acestea sunt prezentate in continuare.

Figura 3. Valorile medii ale ratelor de compresie a 5 algoritmi i 8 tipuri de fiiere

Figura 4. Cei 5 algoritmi testai pe 10 fiiere de acelai tip PASCAL dar de lungimi diferite

prezentate n tabelele de mai sus.



n figura 3, cele 8 fiiere sunt ordonate cresctor ca lungime iniial. Concluzia care se desprinde este c, cea mai bun comportare o are algoritmul LZW care practic prezint cea mai mare rat de compresie pentru toate fiierele, indiferent de lungimeaacestora.n figurile 4 i 5 sunt prezentate rezultatele testrii celor 5 algoritmi pe 10 fiiere de lungimi diferite dar de acelai tip, PASCAL respectiv WAV. Din figura 5 rezult c la toi algoritmii, rata de compresie crete cu lungimea fiierelor i mai rezult c algoritmii LZW i HD furnizeaz cele mai bune rezultate la compresia fiierelor de sunet.

Figura 5. Cei 5 algoritmi testai pe 10 fiiere de acelai tip WAV dar de lungimi diferite

3. Concluzii

- Compresia datelor este folosit att n cadrul sistemelor de stocare ori de transmisie la distan, a datelor de tip text sau a datelor de tip sunet ori de tip imagine reprezentate n format digital. Aplicaiile dezvoltate n domeniul conducerii centralizate a unor roboi cu vedere artificial, precum i n cazul avioanelor de spionaj fr pilot este necesar transmisia datelor video ntr-o form compresat pentru scurtarea duratei achiziiei i transmisiei datelor la sol. Aceasta explic importana acordat compresiei datelor de ctre cercettori.

- Tehnicile pentru compresia imaginilor sunt dominate de prelucrrile de semnale n domeniul tehnologiei informaiei. Creterea vertiginoas a aplicaiilor care folosesc reprezentri 2D i 3D i n special transferul de fiiere grafice pe Internet au impus dezvoltarea de tehnici speciale i mai ales de standarde specializate. Procedurile de compresie de imagini sunt complexe, asociind mai muli algoritmi. De aceea, rata distorsiunii este decisiv n alegerea nivelului de compresie, pentru c n funcie de aplicaie se poate merge pn la rate foarte nalte de compresie, dac detaliile imaginii nu sunt importante sau se lucreaz cu imagini binarizate. Un alt aspect important este acela a timpilor de rulare a algoritmilor de compresie/decompresie, anumite proceduri nefiind indicate pentru transmitere la distan, ci doar pentru stocare, datorit timpului prea lung n care se face compresia. n fine, un aspect care nu poate fi neglijat este acela c exist aplicaii n care compresia de imagini trebuie asociat cu cea a semnalului audio i eventual a unor dale de proces sau fiiere text, ceea ce ridic probleme de mpachetare a cadrelor i mai ales de armonizare a debitelor informaionale.

- Fiierele de sunet avnd dimensiuni relativ mici, comprimarea lor se realizeaz n bune condiii i n timp scurt folosind algoritmul Huffman Standard chiar dac rata de compresie pentru aceste fiiere este destul de sczuta 35%.

BIBLIOGRAFIE

1. DIATCU, E., A. TERTICO, F. IACOB, M. TACHE, Z. RACOVI: Elemente fundamentale ale teoriei sistemelor i calculatoarelor, editura HYPERION XXI, 1997;

2. STEFNOIU, D.: Compresia datelor, editura Printech, 2003;


art02.pdf

Documents