Compresia Datelor

Compresia datelor

Cuprins:

1.Marimea si evolutia datelor

2.Compresia datelor

2.1 O scurta istorie a algoritmilor de compresie

2.2 Clasificarea algoritmilor

2.2.1 Compresia lossless

2.2.2 Compresia lossy

2.3 Privire de ansamblu asupra tehnicilor de compresie

2.3.1 Compresia audio

2.3.2 Compresia vocii

2.3.3 Compresia imaginilor

2.3.4 Compresia video

2.3.5 Compresia informatiilor genetice

2.3.6 Compresia executabilelor si a codului sursa

2.4 Evaluarea algoritmilor de compresie

2.4.1 Viteza

2.4.2 Rata compresiei

3.SmartCompresser

3.1 Inceputuri

3.2 Fundamentul structural

3.3 Implementarea algoritmilor de compresie

3.3.1 Algoritmul Lempel-Ziv-Welch

3.3.1.1 Fundamentul teoretic

3.3.1.2 Implementare LZW in SmartCompresser

3.3.2 Algoritmul Run Length Encoding

3.3.2.1 Fundamentul teoretic

Astfel reuseste sa inlocuiasca secvente lungi care sunt alcatuite din repetarea aceluiasi byte, in unele mult mai scurte.

3.3.2.2 Implementare BitFileManager in SmartCompresser

3.3.2.3 Implementare Run-Length Encoding in SmartCompresser

3.3.3 Compresia Mu-Law

3.3.3.1 Fundamentul teoretic

3.3.3.2 Implementarea in SmartCompresser

3.3.4 Compresia Huffman

3.3.4.1 Fundamentul teoretic

Constructia arborelui Huffman

3.3.4.2 Implementarea algoritmului in SmartCompresser

3.4 Analiza asupra comportamentului SmartCompresser

3.4.1 Stabilirea testbedurilor

3.4.2 Analiza comportamentului

3.4.2.1 Fisiere din baze de date plate, fisiere text si documente HTML

3.4.2.2 Imagini

3.4.2.3 Audio raw

3.4.3.4 Fisiere variate

3.4.3.5 Timpul de executie

4. Idei finale

4.1 Privire de ansamblu

4.2 Concluzii

4.3 Oportunitati de continuare a dezvoltarii

1.Marimea si evolutia datelor

Suntem bombardati cu informatii: incepand cu telefoanele mobile, cartile de credit, posturile de televiziune, calculatoarele, de la cladirile echipate cu senzori, trenuri, autobuze, avioane, uzine si fabrici. Datele sunt din ce in ce mai multe iar cantitatea lor continua sa creasca foarte repede. In ultimii cativa ani, informatiile acumulate au fost mai multe decat in toata istoria omenirii.

Specialistii afirma ca este o adevarata evolutie a datelor. Aceasta nu se datoreaza doar cantitatii lor, ci faptului ca acum putem sa facem ceva cu acestea, adica sa le prelucram si sa obtinem informatii relevante.

Sunt multe motive pentru a explica aceasta explozie a cantatii de informatie disponibila. Desigur, cea mai importanta explicatie este evolutia tehnologiei. Pe masura ce aparatele digitale devin din ce in ce mai ieftine, senzorii din ele ne ofera o multime de informatii ce inainte nu ne erau cunoscute.

La toate acestea se adauga si faptul ca din ce in ce mai multi oameni au acces la unelte tot mai puternice din punct de vedere tehnologic. De exemplu, in acest moment sunt peste 6.8 miliarde telefoane mobile. Tinand cont de faptul ca multi oameni au mai mult de unul iar populatia lumii a trecut pragul de 7 miliarde, ne asteptam ca numarul de telefoane sa creasca repede pe masura ce economia tarilor subdezvoltate creste. Un alt exemplu este numarul de utilizatori care au acces la internet: putin peste 3 miliarde, numar aflat, de asemenea, in crestere.

Legea lui Moore, pentru care industria computerelor este cel mai bun exemplu, afirma ca puterea ce procesare si capacitatea de stocare se dubleaza la fiecare 18 luni, sau preturile se injumatatesc. Asadar putem afirma faptul ca informatiile, ca si cantitate, se inzecesc la fiecare 5 ani. Acesta tendinta s-a mentinut mai mult de jumatate de second. In anii 2005, specialistii preziceau ca se legea se va pastra pana in anii 2010, dupa care, perioada de crestere se va ridica la aproximativ 3 ani. Cu toate acestea, observam ca si in zilele curente legea se pastreaza.

Imaginile de mai jos ne reprezinta grafic evolutia celor doua elemente esentiale: capacitatea de stocare si capacitatea de procesare data de numarul de tranzistori dintr-un microprocesor.

O cantitate uriasa de informatie este transferata in fiecare secunda, drept dovata sta faptul ca in anul 2015, totalul traficului facut pe internet a depasit pragul de 700 exabytes, conform raportului Cisco, o voce importanta din acest domeniu. Pe masura ce cantitatea informatiilor continua sa creasca din ce in ce mai repede, capacitatea de transfer a retelelor este depasita.

Pentru o imagine mai clara asupra situatiei, putem sumariza totul in urmatorul calcul: in fiecare minut din zi si din noapte, se trimit peste 144.000.000 emailuri, sunt efectuate aproximativ 3.000.000 de cautari pe Google, pe Twitter apar mai mult de 560.000 tweeturi, pe Youtube se vizioneaza mai mult de 6.000.000 videouri, toate acestea ducand la un trafic de 1600 terra-bytes.

Dupa cum putem observa, informatiile sunt din ce in ce mai multe din mai multe motive: pe de o parte a crescut foarte mult numarul dispozitivelor electronice care le genereaza. Pe de alta parte, datorita dezvoltarii tehnologice, tot mai multi oameni au acces la internet astfel crescand cantitatea de biti transferati. In acelasi timp, componentele hardware tin pasul cu aceasta evolutie insa totusi se pune o mare problema: cum putem pastra toate aceste informatii, avand in vedere ca dimensiune ocupata de ele este uriasa ?

Incepand cu microfoane, aparate de fotografiat, senzori, carti de credit, televiziuni, trenuri, autobuze si avioane, sunt bombardati de informatii pe care dorim sa le inregistram. Ne punem intrebarea cum de este totusi posibil salvarea lor, avand in vedere ca sunt intr-o cantitate asa de mare.
Sa luam, de exemplu, aparatul de fotografiat digital: apesi un buton si iti imortalizeaza imaginea cuprinsa de obiectivul acestuia. Ce se intampla, de fapt, atunci cand se creeaza acea poza ?

Trecand printr-o serie de lentile, imaginea ajunge intr-un final la senzorul de imagine. Fiind alcatuit din mai multe celule fotosensibile, cantitatea de lumina ce cade pe ele este direct proportionala cu sarcina electrica acumulata pe senzor. Pentru a genera o imagine in culori, o serie de filtre transforma lumina in cele trei culori de baza: rosu, verde si albastru. Astfel se realizeaza transformarea imaginii initiale intr-un semnal eletric.

Semnalul electric obtinut este mai apoi digitalizat, adica inpartit in multe elemente mici, numite pixeli. Atributele unui pixel sunt facute pe un numar de 1, 2, 4, 8, 16 sau mai multi biti pentru fiecare plan de culoare sau transparenta. De exemplu, folosind doar pixeli de 1 bit, se va forma o imagine alb-negru. Daca folosit 8 biti, vom obtine o imagine cu 256 nuante de gri. Cele mai intalnite imagini sunt cele care au pixelii caracterizati prin 24 de biti, cate 8 biti pentru ficare culoare de baza.

Sa recapitulam: imaginea trece prin lentile, este procesata de celulele fotosensibile si convertita intr-o matrice de pixeli. Pentru un aparat obisnuit, cu rezolutia de 12 mp, vom obtine 12 milioane de pixeli asociati imaginii initiale. Daca luam in calcul numarul de biti pentru fiecare pixel, vom obtine 288 Mb pentru o singura imagine.

Daca o imagine ocupa 288 Mb, cum este posibil ca un smartphone, care are o capacitate de 16 Gb sa stocheze pana la 1500 poze ?

2.Compresia datelor

Compresia este actiunea de a reprezenta informatia intr-o forma concisa, mai compacta decat varianta originala care este numita si forma necompresata. In alte cuvine, compresia datelor se rezuma la reducerea dimensiunii unui fisier sau a unui flux de date. Aceasta este foarte folositoare cand se proceseaza, stocheaza sau transfera cantitati mari de informatii. Daca algoritmii de compresia au un randament bun, ar trebui sa fie o diferenta destul de mare intre fisierul original si varianta compresata. Atunci cand compresia este folosita in aplicatiile ce transfera date, scopul principal este de a mari viteza transferului. Aceasta depinde de numarul de biti trimisi si de timpul necesar decompresorului sa desfaca pachetul primit adica sa il aduca in forma originala. Pe de alta parte, atunci cand este folosita in aplicatiile ce se ocupa de stocarea datelor, principalul obiectiv este gradul de compresie. Marimea bazelor de date moderne, a aplicatiilor sau a fisierelor multimedia poate fi extrem de mare. Reducerea marimii lor salveaza resurse sau reduce timpul de transmisie. Uneori, nu am putea fi capabili sa stocam secvente de date fara a fi compresate inainte. Asadar, studiul posiblitatilor de compresie este foarte important.

La baza compactarii informatiei sta faptul ca aceasta contine foarte multe redundante. Redundanta exista in forme variate: poate fi sub forma de corelatie, de exemplu, pixelii apropiati dintr-o imagine au, in general, aproape aceeasi culoare sau unele parti din ea sunt repetate. Redundanta poate exista si in functie de context: numarul de posibilitati pentru o anumita litera intr-un text din limba romana este drastic redus daca litera anterioara a fost q. De asemenea, aceasta poate fi si probabilistica: este mult mai probabil ca o litera dintr-un text sa fie litera “a” decat litera “q”. Un alt punct poate fi si modul in care a fost generata informatia: de exemplu, vocea umana are o structura periodica. Amintim, de asemenea, si reduntanta informatiei pentru utilizator: de exemplu, atunci cand ne uitam la o imagine, nu putem percepe peste o anumita frecventa, de aceea informatia ce are o frecventa mai mare este nefolositoare, deoarece ne este imposibil sa o sesizam datorita aparatului vizual uman. Filmele sunt, in mod normal, compuse din mai multe frameuri. Putem considera ca fiecare frame este o imagine, astfel, pentru a compresa un film, o varianta ar fi sa compresam fiecare imagine separat. O alternativa mai eficienta ar fi sa analizam framurile consecutive: ce se poate intamplat intr-un video in intervalul de o fractiune de secunda ? In mod normal, nu prea multe, asadar, putem presupune ca frameurile succesive sunt aproape similare.

Redundanta este definita ca fiind “o parte a mesajului care poate fi eliminata fara a pierde informatii esentiale”. Asadar, aspectul principal al compresiei este eliminarea redundantei. Dupa terminarea procesului de eliminare a acesteia, informatia trebuie codata intr-o reprezentare binara. In aceasta faza, tinem cont de faptul ca daca ea este reprezentata folosind un anume alfabet, atunci este mai probabil sa apara anumite litere decat altele. In partea de codare scopul este sa folosim un cod cat mai scurt pentru literele care apar cel mai des, astfel vom folosi mai putini biti necesari pentru a reprezenta intrega informatie.

Compresia, in toate formele ei, exploateaza structura sau redundanta pentru a putea obtine o reprezentare compacta a datelor initiale. Construirea unui algoritm de compresie implica intelegerea tipurilor de redundanta prezente in informatiile pe care dorim sa le compresam. Oamenii au venit cu multe idei ingenioase de a caracteriza, utilizand diferite tipuri de redundanta prezente in diferite tehnologii: incepand cu telegraful, continuand cu telefoanele mobile si filmele digitale.

2.1 O scurta istorie a algoritmilor de compresie

Acestia sunt folositi de mai bine de 2000 ani, atunci cand au aparut primele metode de reprezentare codata si mai concisa a informatiilor

sec. I IEN: stenografia

sec. XIX: alfabetele Morse si Braille

anii ‘50: se dezvolta algoritmi de compresia pe baza redundantei statistice, modele de biti cu lungime variabila sunt folosite pentru a reprezenta un anume simbol, in functie de frecventa relativa a acestuia

anii ‘70: incep sa fie folosite dinctioare, astfel, fiecare secventa de simboluri este asociata in dictionar cu un indice cat mai mic

anii ‘70: o data cu digitalizarea retelelor de telefonie, companiile sunt interesate d proceduri prin care sa fie folosite mai multe canale pe un singur fir de transmisie

anii ‘80: prima aplicatie ce foloseste imagini digitale apare pe piata, “revolutia digitala” este data de compresia audio

anii ‘90: transmiterea video etc.

2.2 Clasificarea algoritmilor

O metoda pentru a separa aceste scheme este in functie de modelul utilizat pentru a caracteriza redundanta prezenta in inforamtii. Pe scurt, sunt doua mari categorii de algoritmi: lossless si lossy. Primii pastreaza toata informatia in datele compresate iar reconstructia este identica cu forma originala. In cea de-a doua categorie, unele informatii sunt pierdute in mod irecuperabil. Acest efect secundar este pretul care trebuie platit pentru a putea atinge niveluri mult mai inalte de compresie.

2.2.1 Compresia lossless

Atunci cand avem nevoie de siguranta ca ceea ce obtinem in urma unei decomprimari este exact continutul initial, singura optiune este folosirea unui astfel de algoritm. Aplicabilitatea lor este necesara in special asupra fisierelor binare sau a textelor deoarece ar fi de neimaginat un algoritm care schimba litere din text. Acest algoritmi mai sunt folositi si in cazul unor imagini in care este prezent un text scanat iar culorile prezente sunt aproape aceleasi.

Pe scurt, folosim aceasta metoda atunci cand cdorim sa reconstituit cu exactitate continutul initial.

2.2.2 Compresia lossy

Este foarte important sa stim cine va folosi informatii pe care le comprimam atunci cand ne dorim sa alegem un algoritm optim deoarece astfel vom putea determina mai bine redundantele sau datele pe care le putem pierde fara efecte majore. De exemplu, atunci cand codam informatii audio, unele tonuri nu pot fi percepute de oameni deoarece simturile noastre sunt imperfecte. Daca cel care va folosi un fisier audio compresat este un om, putem elimina fara griji aceste date nenecesare. De retinut faptul ca dupa decompresie nu vom obtine fisierul audio original ci unul care “suna” identic. Uneori putem accepta mici distorsiuni daca acestea sunt rezultatul unei ratii de compresie foarte buna. Acest lucru se intamplat atunci cand avem urmatoare dilema: putem avem putine sunete distorsionate sau nu putem avea niciun sunet din cauza restrictiilor de stocare care nu ne permit sa memoram informatiile. Atunci cand vrem sa codam o imagine sau un film, avem aceleasi optiuni: sa sacrificam asemanarea perfecta cu fisierul original pentru a castiga o ratie de compresie mai buna.

De remarcat faptul ca algoritmii lossy pot obtine o ratie de compresie mult mai buna fata de cei lossless, acesta fiind cel mai important argument pentru a-i folosi. Diferenta intre rezultatul compresiei lossless si cea lossy pentru fisiere audio si video este atat de mare incat cei fara pierderi nu sunt aplicati aproape niciodata. Compresia lossy are prioritate, in general, si asupra imaginilor cu cateva exceptii: in primul rand unele imagini nu pot fi compresate in acest mod datorita legii iar in cel de-al doilea, imaginile medicale trebuie transmise fara pierderi de informatii.

Pe scurt, metoda lossy poate fi utilizata pe informatii care au fost digitalizate inainte de compresie. In procesul digitalizarii se produc mici distorsiuni iar pe parcursul compresiei aceste doar se pot mari ca si proportie.

2.3 Privire de ansamblu asupra tehnicilor de compresie

2.3.1 Compresia audio

Compresia audio are capacitatea de a reduce banda utilizata la transmisie si cerintele legate de stocare. Algoritmii cu pierdere de date au ca rezultat o mai buna rata a compresiei cu costul reducerii fidelitatii fata de varianta originala. Aproape toti algoritmii se bazeaza pe psihoacustica pentru a elmina sunetele ce nu pot fi percepute, reducand astfel dimensiunea informatiilor. Atat in compresia lossless cat si in cea lossy, redundanta datelor este redusa utilizand metode cum ar fi codarea, recunoasterea modelelor si predictia liniara pentru a micsora cantitatea de informatie utilizata pentru a reprezenta informatiile necompresate.

Compresia audio lossless produce o reprezentare a datelor originala care, decompresate, sunt exact fluxul audio intial. Rata de compresie este un jur de 50% din marimea originala, valoare similara cu rata compresiilor fara pierderi asupra informatiilor generice. Acesti algoritmi nu pot compresa foarte mult datorita complexitatii undelor si schimbarile lor rapide in unde sonore. Unele codecuri folosesc predictia liniara pentru a estima lungimea undelor. Cei mai multi algoritmi folosesc convolutia cu filtru [-1 1] pentru a aplatiza spectrul ajutand astfel algoritmii de compresie lossless sa lucreze mult mai eficient.

Compresia audio cu pierderi de informatii este folosita intr-o mare plaja de aplicatii si, pe langa acestea, mai este utilizata in televiziunea digitala, transmiterea audio-video pe internet, sateliti si cabluri radio. Aceasta categorie (lossy) ajunge la performate mult mai bune fata dfe cea anterioara, un fisier ajung la o marime de 5-20% din valoarea initiala. Inovatia acestei metode a fost folosirea psihoacusticii pentru a oberva ca nu toata informatiile dintr-un flux audio pot fi percepute de sistemul auditiv uman. Cei mai multi algoritmi micsoreaza reduntanta in primul rand prin eliminarea sunetelor irelevante, adica a acelora care sunt foarte greu de auzit. Un exemplu tipic include frecventele inalte sau sunete care apar in acelasi timp in care se aud si sunete mult mai puternice. Acetea sunt codate cu o acuratete scazuta sau chiar eliminate.

2.3.2 Compresia vocii

Reprezinta o particularitate a compresiei audio pentru cazurile in care fluxul contine un discurs. Aceasta foloseste un parametru de estimare, specific doar pentru astfel de fisiere audio, dedus utilizand tehnici de procesare a semnalelor audio pentru a modela discursul. Pe langa aceasta tehnica, se folosesc si algoritmi de compresie generici aplicati pe fluxul modelat, obtinand astfel o compactare foarte eficienta a informatiilor. Cel mai des, aceasta este folosita de retelele de telefonie mobila dar si in VoIP (Voice over IP).

Compresia vocii difera de compresiile audio deoarece semnalul este mult mai simplu si exista mai multe informatii statistice disponibile despre convorbire. Cel mai important criteriu este pastrearea intengibilitatii si a fluentei discursului, avand in calcul numarul de biti transmisi. Astfel, doar informatia cu frecventa intre 400Hz si 3500Hz este procesata, in rest fiind eliminata.

Cea mai comuna schema de compresie este Code Excited Linear Prediction (CELP), care este utilizata si de standanrdul GSM. In aceasta, modelarea este impartita in doua etape: prima este o predictie liniara care modeleaza spectrul audio iar cea de-a doua este utilizarea unui dictionar pentru defectele modelului realizat cu predictie liniara.

2.3.3 Compresia imaginilor

Algoritmii din aceasta categorie pot fi atat cu pierdere cat si fara pierdere de date. Cei lossless sunt utilizati atunci cand scopul compresiei este de a arhiva anumite imagini dar si pentru cele care reprezinta informatiil medicale sau desene tehnice. Metodele din cealalta categorie se potrivesc cel mai bine imaginilor naturale cum ar fi fotografiile in aplicatii in care micile diferente, uneori insesizabile, sunt acceptate pentru a obtine o rata a compresiei mare. Diferentele imperceptibile generate de algoritmii din urma sunt numite si vizual identice.

Cele mai eficiente metode de compresie lossless sunt:

Run-length encoding (utilizata de formatul .bmp) memoreaza, pentru mai multe valori consecutive identice, doar prima si numarul de repetari

Area image compression

Predictive coding: valorile urmatoare sunt deduse pe baza celor anterioare

Entropy encoding: fiecare simbol este inlocuit de un cod unic in toate aparitiile lui. Astfel, simbolul de lungime fixa este transformat in codul ce are o lungime variabila, proportionala cu negativul logaritmului probabilitatii aparitiei. Practic, cele mai comune simboluri au codurile foarte scurte, reducandu-se astfel dimensiunea totala

Algoritmi adaptabili bazati pe dictionare (cum ar fi LZW) (utilizata in formatele .gif si .tiff)

Deflation reprezinta o combinatie a algoritmilor LZ77 si codarea Huffman: initial se reduce numarul de simboluri care apar iar apoi sunt inlocuite cu coduri unice de dimensiune variabila

Chain codes este specific imaginilor monocrome, separa imaginea in componente conexe. Pentru fiecare componenta conexa, se transmite cate un punct initial si toate miscarile facute pentru a o parcurge

Metodele lossy au la baza:

reducerea spatiului de culori la cele mai intalnite culori din imagine. Fiecare din cele selectate este idexata iar toti pixelii doar referentiala indexul acesteia

Chrome subsampling utilizeaza faptul ca ochiul uman percepe schimbarile de luminozitate mai puternic decat cele de culoare. Astfel culorile sunt agregate iar unele eliminate, obtinand mai putine valori

Transform coding este cea mai utilizata metoda, are la baza transformarea Fourier cu functia Cosinus discret: un element este scris ca o suma de functii cosinus de diferite valori.

2.3.4 Compresia video

Pentru a micsora redundanta informatiilor, compresia video foloseste tehnici moderne de codare. Acestea combina atat compresia de imagini cat si compensarea miscarii temporare adica prezicerea unui cadru in functie de cele apropiate, utilizand miscarea camerei si a obiectelor din imagine.

Avand in vedere ca videourile necompresate au nevoie de o rata foarte mare de date, majoritatea algoritmilor din aceasta categorie se bazeaza pe compresia cu pierdere de informatii. Aceasta deoarece algoritmii din cealalta categorie au capacitatea de a compresa cu un factor de valoare 3, in timp ce algoritmii lossy pot ajunge la un factor intre 20 si 200. Ca in toate compresiile cu pierdere de informatii, se pune in balanta, pe de o parte calitatea filmarii iar pe cealalalta parte costul procesarii, comprimarii si decomprimarii .

Cele mai puternice scheme de compresie au la baza impartirea pixelilor invecinati in grupuri ce au forma patrata, numit si macro-blocuri. Acestea sunt comparate de la un frame la altul. Daca macro-blocul este neschimbat, atunci se semnaleaza faptul ca trebuie copiat din framul anterior, bit cu bit, in cel curent. In cazul in are s-a efectuat o miscare simpla, compresorul semnaleaza acest fapt notificand decompresorul sa schimbe, roteasca, cresca sau scada intensitatea culorilor pentru noul bloc. Deoarece aceasta metoda foloseste cadrul anterior pentru a-l determina pe cel curent, daca o parte din acesta s-a pierdut la transmisie, cel nou nu poate fi reconstituit corect.

In cazul secventelor mai foarte dinamice, informatiile legate de schimbarea macro-blocurilor este foarte mare. Acest lucru se intampla cel mai des atunci cand se filmeaza o explozie, flacari sau grupuri de animale, solutia fiind scaderea calitatii sau cresterea bitrateului.

2.3.5 Compresia informatiilor genetice

Algoritmii de compresie a informatiei genetice fac parte din cea mai noua generatie de algoritmi ce compreseaza informatiile fara pierdere de date care sunt particularizati si adaptati pentru secvente de nucleoide.

2.3.6 Compresia executabilelor si a codului sursa

Fisierele executabile se aseamana oarecum cu limba romana, iar codul sursa este chiar mult mai apropiat, asadar compresia acestor tipuri de fisiere se comporta foarte asemanator cu cea pentru fisiere text. Acelasi lucru nu il putem afirma si in sens invers, aceasta deoarece unii algoritmi specifici acestor fisiere nu au un comportament adecvat asupra altor tipuri. De exemplu:

executabilele auto-extractoare

eliminarea codului care nu poate fi executat deoarece nu exista cazuri care sa duca la rularea lui

eliminarea codului redundant

biblioteci comune

Un fapt surprinzator este acela ca atunci cand compresam codul sursa al unui limbaj de nivel inalt obtinem un rezultat de aceeasi marime cu rezultatul compresiei fisierului executabil asociat sursei.

Multe metode de compresie si chiar si cele care sunt specifice fisierelor executabile au rolul de a da rezultate invizibile pentru un utilizator uman. Unele din aceste idei de compersie (utilizarea shared libraries, refactorizarea, utilizarea limbajelor de nivel inalt etc.) reduce cantitatea de informatii pe care un programator trebuie sa o citeasca pentru a intelege un program, rezultand astfel o experiente semnificativ mai buna. Astfel, compresiile asupra codului sursa sunt mult mai bune decat varianta originala, lucru ce vine in contradictoriu cu celelalte metode de compresie care, de obicei, ofera o calitate mai scazuta a continutului compresat.

2.4 Evaluarea algoritmilor de compresie

Atunci cand se doreste implementarea unui algoritm de compresie, trebuie sa se tina cont de mai multi factori care reprezinta caracteristici principale ale unui astfel de algoritm:

Viteza: cat de repede va rula

Rata de compresie: care este raportul intre dimensiunea datelor inainte si dupa codare

Memorie folosita: care este raportul intre dimenisunea datelor de intrare si memoria folosita de program

Complexitate: daca trebuie schimbat, cat timp este suficient pentru a se realiza acest lucru si cat timp este necesar testarii ca modificarile facute nu au stricat corectitudinea algoritmului

2.4.1 Viteza

Viteza unui algoritm de compresie este data de raportul intre marimea datelor initiale si numarul de secunde necesar prelucrarii lor. In cazul streamingului audio si video, viteza este calculata prin numarul de biti din strem care pot fi prelucrati intr-o secunda.

Unele aplicatii folosesc tehnici de compresie chiar si atunci cand nu sunt constranse din punct de vedere al memoriei folosite deci nu ar avea niciun interes pentru a micsora datele. Cu toate acestea, unele operatii se realizeaza mai rapid pe fisiere compresate, un bun exemplu ar fi cautarea in fisiere text care este mult mai rapida atunci cand acestea sunt compresate.

Alti algoritmi facuti special pentru a compresa fisiere bitmap: byte-aligned bitmap code (BBC), word-aligned hybrid code (WAH) si compressed adaptive index(COMPAX) ofera posibilitatea ca operatiile pe biti sa fie realizate direct pe fisierul compresat. Astfel, acestea pot fi mult mai rapide decat a decompresa, a face operatiile si a compresa inapoi fisierul.

2.4.2 Rata compresiei

Este definita ca fiind raportul dintre marimea datelor necompresate si marimea lor dupa codare. In cazul streamurilor audio video, se defineste ca fiind relatia intre rata datelor inainte si dupa compresie.

Toti algoritmii oferta diverse rate de compresie in functie de fiserele de intrare si se comporta mai bine pe unele tipuri de fisiere. Este usor sa construim fisiere in asa fel incat sa fie compresate foarte bine de un anume algoritm insa ne ascund capacitatile metodai pentru cazuri reale, atunci cand fiserele nu sunt in tiparul nostru. O metoda buna care garanteaza ca algoritmul nu este personalizat prea mult pe un tip de date iar pe celalalte se comporta oribil este sa avem un oracol cu fisiere de diferite marimi si formate, astfel incat sa putem preveni aceste probleme.

Spre deosebire de algoritmii generici, cei care se ocupa de compresie unul format specific de date pot fi imbunatatiti ajungand astfel la o rata a compresiei mai mare. Se incearca eliminarea redundantelor din datele initiale tinand cont de particularitatile formatului respectiv. De exemplu, fisierele text contin intr-o mai mare proportie unele litere fata de altele. De asemenea, multi pixeli invecinati ai unei fotografii pot avea valori identice, mai ales in cazul celor cu un numar mic de culori. Un alt exemplu ar fi informatiile audio care sunt alcatuite din tonuri repetitive.

Cu toate ca se comporta mai bine pe tipurile de date pentru care au fost construiti, in general, acestia tind sa aiba performante mai scazute in comparatie cu algoritmii generici.

3.SmartCompresser

3.1 Inceputuri

In calitate de programatori, ne dorim unelte cat mai flexibile, usor de utilizat si de integrat in produsele noastre dar care sa se comporte foarte bine si sa ne ofere functionalitati foarte rapide.

Ce facem atunci cand lucram la o aplicatie de sincronizare a fisierelor special conceputa pentru retele cu viteza mica ? Cum le putem actualiza daca acestea au dimensiuni mari ? Cum putem rezolvat problema traficului intr-o aplicatie de tipul Voice Over IP ?

Observam ca toate probleme de mai sus au aceeasi cauza: datele cu care lucram au o dimensiune prea mare raportata la capacitatile hardware de care dispunem.

Solutia este comprimarea datelor inainte de a fi transferate, asigurand astfel o diminuare a efectelor produse de viteza scazuta de transfer.

SmartCompresser este o librarie practica si usor de folosit care rezolva problema compresiei si decompresiei. Avand mai multe tipuri de utilizare, poate fi folosita atat cu algoritmi specifici (LZW, LRE, Huffman sau MuLaw) dar si cu optiunea Smart, care incearca sa gaseasca algoritmul care se pliaza cel mai bine pe datele care vor fi comprimate.

3.2 Fundamentul structural

Din punct de vedere al implementarii, SmartCompresser este alcatuit din mai multi algoritmi de comprimare fiecare putand fi utilizat in mod explicit de catre integrator.

enum Mode

{

RunLengthEncoding,

LempelZivWelch,

Mulaw,

HuffmanCoding,

Smart

};

int compressFile(const std::string& input, const std::string& output, Mode mode)

{

switch (mode)

{

case RunLengthEncoding:

return rle.compressFile(input, output);

case LempelZivWelch:

return lzw.compressFile(input, output);

case Mulaw:

return audioComp.compressFile(input, output);

case HuffmanCoding:

return huffman.compressFile(input, output);

case Smart:

return smartCompress(input, output);

}

}

In functie de modul ales, SmartCompresser va utiliza algoritmul corespunzator.

Atunci cand este ales modul “Smart”, libraria incearca sa determine algoritmul care se pliaza cel mai bine pe fisierul care se doreste a fi compresat. Astfel, din fisierul tinta se extrage o portiune de 80 KB, se arhiveaza cu fiecare algoritm si se foloseste cel care a dat cele mai bune rezultate.

Avem urmatoarea problema: integratorul face o compresie Smart insa nu stie ce algoritm s-a folosit. Cum poate decompresa fisierul obtinut ? Un prim raspuns ar fi sa incerce toate posibilitatile si sa o ia pe cea care s-a realizat fara erori. Ce se intampla daca reusesc mai multe, cum isi poate da seama care este algoritmul corect ?

Solutia este ca fiecare algoritm sa adauge un header(semnatura) fisierul de iesire intr-un mod propriu. Astfel, atunci cand se va dori decompresia lui, in functie de semnatura gasita se va sti ce algoritm trebuie utilizat. Asadar, fiecare algoritm trebuie sa primeasca o cheie unica. Pentru o intelegere mai rapida, utilizam o cheie pe 8 biti, ceea ce ne ofera posibilitatea de a implementa 511 algoritmi distincti.

const char HuffmanKey = static_cast<char>(1);

const char RleKey = static_cast<char>(2);

const char LzwKey = static_cast<char>(3);

const char MuLawKey = static_cast<char>(4);

Iar instantierea se va face in modul urmator:

RLECompresser rle(RleKey);

AudioCompresser audioComp(MuLawKey);

HuffmanCompresser huffman(HuffmanKey);

LZWCompresser lzw(LzwKey);

Avand acestea, decompresia unui fisier nu trebuie sa primeasca drept parametru algoritmul folosit deoarece acesta va fi identificat in mod automat.

int decompressFile(const std::string& input, const std::string& output)

{

Mode mode;

std::ifstream is(input, std::ios_base::binary);

std::ofstream os(tempFileName, std::ios_base::binary);

if (!is.is_open() || !os.is_open())

return EXIT_FAILURE;

char data;

is.get(data);

is.close();

if (data == RleKey)

mode = RunLengthEncoding;

if (data == MuLawKey)

mode = Mulaw;

if (data == HuffmanKey)

mode = HuffmanCoding;

if (data == LzwKey)

mode = LempelZivWelch;

switch (mode)

{

case RunLengthEncoding:

return rle.decompressFile(input, output);

case LempelZivWelch:

return lzw.decompressFile(input, output);

case Mulaw:

return audioComp.decompressFile(input, output);

case HuffmanCoding:

return huffman.decompressFile(input, output);

}

}

Vrem ca fiecare algoritm sa primeasca o cheie unica, de asemenea, trebuie sa aiba cele doua metode pentru compersie si decompresie. Pe langa acestea, ne trebuie un mecanism comun tuturor prin care sa scriem si sa citim headerul din fisier.

Ajungem la concluzia ca trebuie sa implementam o clasa de baza care sa ne ofere functiile de mai sus.

class BaseCompression

{

protected:

typedef char PrivateKeyType;

void addHeader(std::ostream& os)

{

os << privateKey;

}

bool checkHeader(std::istream& is)

{

char data;

is.get(data);

return data == privateKey;

}

public:

virtual int compressFile(const std::string& inPath, const std::string& outPath) = 0;

virtual int decompressFile(const std::string& inPath, const std::string& outPath) = 0;

BaseCompression(PrivateKeyType key) :privateKey(key)

{};

private:

const PrivateKeyType privateKey;

};

Fiecare algoritm va mosteni BaseCompression, va implementa cele doua functii virtuale pure si va folosi addHeader si checkHeader pentru a-si semna fisierele compresate folosindu-si cheia privata.

Din punct de vedere structural, orice algoritm trebuie sa respecte urmatoarea configuratie:

class CompressionAlgorithm: public BaseCompression

{

public:

int compressFile(const std::string& inPath, const std::string& outPath)

{

//implement me

};

int decompressFile(const std::string& inputPath, const std::string& outputPath)

{

//implement me

};

CompressionAlgorithm(BaseCompression::PrivateKeyType key) : BaseCompression(key)

{};

};

3.3 Implementarea algoritmilor de compresie

Avand modelul anterior, vom parcurge rand pe rand, intelegerea si implementarea algoritmilor Lempem-Ziv-Welch, MuLaw-Encoding, Run-Length Encoding si Huffman.

3.3.1 Algoritmul Lempel-Ziv-Welch

3.3.1.1 Fundamentul teoretic

Lempel-Ziv-Werlch este un algoritm de compresie fara pierdere de date, universal, rezultat in urma optimizarii algoritmului LZ78. Printre avantajele acestuia se numara: usurinta de implementare, este foarte flexibil, deci se poate particularile pentru orice sistem.

LZW este un algoritm ce are la baza un dictionar. Dictionarul, initial, contine coduri asociate tuturor secventelor de 1 byte. Pe masura ce fisierul care va fi compresat este parcurs, se actualizeaza si informatiile din dictionar. Practic, se adauga noi coduri asociate diferitelor secvente iar in cazul in care numarul de elemente ii atinge limita superioara, acesta este golit si procesul este reluat de la secventele de 1 byte.

Pseudocod algoritm de compresie:

//dictionary: un dictionar ce asigura asocierile intre diferite secvente(cuvinte) si coduri //pentru identificarea lor

//currentString: cuvantul curent

//data: byteul care se proceseaza

//is: fisierul care se doreste a fi comprimat

//os: fisierul rezultat

dictionary = toate cuvintele de 1 byte

while ( citeste data din is)

{

if( dictionary nu contine newString)

{

dictionary.Add(currentString + data); //in dictionar se adauga noul cuvant

//in functie de implementarea dictionarului, codul asociat acestui cuvant

//poate varia insa este preferat codul cel mai mic disponibil

os.write(dictionary[currentString]); //scriem codul asociat vechiului cuvant care se gasea in dictionar (fusese adaugat la un pas anterior)

currentString = data; //noul cuvant va incepe cu byteul citit

}

else

currentString += data;//adaugam la finalul cuvantului curent noul byte

}

if(currentString nu e gol)

os.write(dictionary[currentString]);

Asadar, fisierul de iesire va contine mai multe chei care, daca sunt inlocuite cu datele echivalente, se va obtine fisierul initial.

Pentru o intelegere mai clara, parcurgem urmatorele exemple.

Pseudocod decompresie:

//dictionary: un dictionar ce asigura asocierile intre diferite secvente(cuvinte) si coduri //pentru identificarea lor

//currentString: cuvantul curent

//key: cheia

//is: fisierul care se doreste a fi decomprimat

//os: fisierul rezultat

dictionary = toate cuvintele de 1 byte

while ( citeste key din is)

{

if( key == dictionart.size()) //caz special de tipul sWsWs

dictionary.Add(currentString + currentString[0]);

//remarcam ca in acest caz, ultima litera a cuvantului care nu este gasit in dictionar

//este egala cu prima sa litera

else if(currentString nu este gol)

dictionary.Add(currentString + dictionary[key][0]);

os.write(dictionary[key]);

currentString = dictionary[key];

}

De remarcat faptul ca fisierul compresat nu contine si informatiile din dictionar. Acestea pot fi reconstituite in timp ce se parcurge fisierul compresat.

Un factor important in eficienta algoritmului este lungimea cheii, aceasta poate fi de 8, 16, 32 sau chiar mai multi biti. In cazul unei chei de 8 biti, remarcam ca pot fi stocate 256 valori distincte, deci dictionarul se va umple foarte repede.

In cazul unei chei de 16 biti, cele 65536 valori ne ofera suficienta libertate pentru a putea comprima fisiere nu foarte mari.

Cheile cu valori de peste 32 biti se folosesc doar in cazuri particulare, pentru fisiere foarte mari, deoarece, in mod normal, facand o astfel de compresie este posibil ca fisierul rezultat sa aiba dimensiunea mai mare decat cel initial.

Sa mai luam un exemplu, de data aceasta unul de tipul sWsWs: ababababab

Atunci cand vrem sa decompresam:

Observam ca la pasul 4 trebuie sa traducem cheia 4 insa nu aveam niciun cuvant in dictionar cu aceasta valoare. Acesta este rezolvata de faptul ca, in acest tip de caz, cuvantul se termina si incepe cu aceeasi litera.

3.3.1.2 Implementare LZW in SmartCompresser

void compress(std::istream &is, std::ostream &os)

{

Dictionary dict;

KeyType index = dictMaxSize;

char data;

while (is.get(data))

{

const KeyType temp = index;

if ((index = dict.searchInsert(temp, data)) == dictMaxSize)//string doesn't exist in the dictionary

{

os.write(static_cast<const char *> (&temp), sizeof (KeyType));

index = dict.searchInitials(data);

}

}

if (index != dictMaxSize)

os.write(static_cast<const char *> (&index), sizeof (KeyType));

}

Dictionarul “dict” are la baza un arbore binar ne-echilibrat deoarece, fiind un arbore de dimensiuni relativ mic (maxim 2^16 noduri) si data fiind entropia datelor de intrare, echilibrarea acestuia nu are un impact vizibil asupra performantei.

void decompress(std::istream &is, std::ostream &os)

{

std::vector<std::pair<KeyType, char>> dictionary;

resetDictionary();

KeyType i = dictMaxSize; // Index

KeyType k; // Key

while (is.read(static_cast<char *> (&k), sizeof (KeyType)))

{

// dictionary's maximum size was reached

if (dictionary.size() == dictMaxSize)

reset_dictionary();

if (k > dictionary.size())

throw std::runtime_error("invalid compressed code");

const std::vector<char> *s; // String

//special case sWsWs:

if (k == dictionary.size())

{

dictionary.push_back({ i, rebuild_string(i)->front() });

s = rebuild_string(k);

}

else

{

s = rebuild_string(k);

if (i != dictMaxSize)

dictionary.push_back({ i, s->front() });

}

os.write(&s->front(), s->size());

i = k;

}

if (!is.eof() || is.gcount() != 0)

throw std::runtime_error("corrupted compressed file");

}

3.3.2 Algoritmul Run Length Encoding

3.3.2.1 Fundamentul teoretic

LRE este unul dintre cei mai practici algoritmi utilizati la scara larga. Spre deosebire de altii, nu incearca sa reduca marimea medie a unui simbol, cum este in cazul Huffman dar nici nu inlocuieste cuvinte pe baza unui dictionar, cum face Lemple-Ziv-Welch. Practic, RLE inlocuieste un cuvant obtinut prin copierea aceluiasi byte de mai multe ori, cu un nou cuvant format din lungimea initiala si byteul care se repeta.

Astfel reuseste sa inlocuiasca secvente lungi care sunt alcatuite din repetarea aceluiasi byte, in unele mult mai scurte.

Exemplu:

a a a a a a a a a b b b b b b b c c c a a a a a a b

–algortim de compresie LRE–

9a7b3c6a1b

Desi lungimea inputului comprimat este mai mica de aproximativ 3 ori, aceasta nu este cea mai optima implementare a algoritmului. De exemplu, putem renunta la comprimarea secventelor care contin un singur byte.

Acest algoritm nu se aplica doar la stringuri, el avand o mare varietate de aplicatii.

Sa luam un alt exemplu:

a b c d a b c d

–algortim de compresie LRE–

1a1b1c1d1a1b1c1d

Observam ca lungimea outputului este de 2 mai mare decat cea de intrare. Ce avem de facut in acest caz ? Dupa cum observasem mai sus, putem ignora secventele de 1 byte insa se pune urmatoare problema : atunci cand decomprimam, cum stim daca urmeaza o secventa de un byte sau una compresata ?
O solutie ar fi sa punem un marcator care sa ne semnaleze acest fapt. Problema este ca si acel marcator are nevoie de un numar de biti asa ca suntem nevoiti sa punem unul cat mai mic.
Cea mai eficienta varianta este sa punem un bit(1) daca urmeaza o secventa compresata sau un bit(0) daca urmeaza una necompresata. Pentru a face acest lucru, avem nevoie de un mecanism care sa ne ajute sa scriem fisierul la nivel de bit, lucru posibil doar realizand un sistem care sa se ocupe si de gestiunea bufferului de date.

Ne dorim sa implementam un manager care sa ne ajute sa scriem si sa citim biti. Practic, avem nevoie de o metoda read si una write care sa ne ofere ori un byte, ori un bit, integrarea acesteia fiind usor de facut. Streamul se va deschide in constructorul managerului, si se va inchide, eventual va goli bufferul, pe destructor.

3.3.2.2 Implementare BitFileManager in SmartCompresser

BitFileManager(Mode mode_, const std::string& filePath)

{

mode = mode_;

if (mode == Mode::Read)

is = std::ifstream(filePath, std::ifstream::eofbit | std::ios::binary);

if (mode == Mode::Write)

os = std::ofstream(filePath, std::ios::binary);

}

~BitFileManager()

{

flush(true);

if (mode == Mode::Read)

is.close();

if (mode == Mode::Write)

os.close();

}

Metodele de read si write au cate doua supra-incarcari: o data pentru un byte (unsigned char) dar si pentru bit, reprezentat, prin conventie, de tipul bool.

void write(unsigned char value) //writes 1 byte

{

std::bitset<8> bits(value);

for (i = 7; i >= 0; i–)

{

buffer[bufferSize++] = bits[i];

flush();

}

}

void write(bool value) //writes 1 bit

{

std::bitset<1> bits(value);

buffer[bufferSize++] = value ? true : false;

flush();

}

int read(unsigned char& value) //gets 1 byte from buffer

{

value = 0;

for (j = 0; j < 8; j++)

{

if (bufferSize == 0)

{

int err = flush(true);

if (err != EXIT_SUCCESS)

return err;

}

value |= (buffer[–bufferSize] << ((7 – j) & 7));

}

return EXIT_SUCCESS;

}

int read(bool& value) // gets 1 bit from buffer and converts to bool

{

if (bufferSize == 0)

{

int err = flush(true);

if (err != EXIT_SUCCESS)

return err;

}

value = buffer[–bufferSize];

return EXIT_SUCCESS;

}

De asemenea, trebuie manageriat si continutul bufferului. Ne asiguram ca bufferul nu ramane gol dar nici nu este plin.

inline int flush(bool force = false)

{

if (bufferSize == MAX_BUFFER_SIZE || force)

{

if (mode == Read) //reads MAX_BUFFER_SIZE and converts it to bitset

{

const int bfrSize = ((MAX_BUFFER_SIZE + 7) >> 3);

char bfr[bfrSize];

is.read(bfr, bfrSize);

std::streamsize bytes = is.gcount();

std::bitset<MAX_BUFFER_SIZE> revBuffer;

bufferSize = bytes << 3;

for (int j = 0; j < bufferSize; j++)

revBuffer[j] = ((bfr[(j >> 3)] >> ((7 – j) & 7)) & 1);

buffer.reset();

for (int j = 0; j < bufferSize; j++)

buffer[j] = revBuffer[(bytes << 3) – j – 1];

if (bytes == 0)

return EXIT_FAILURE;

}

if (mode == Write) //writes bitset by converting into byte array

{

const int dim = (bufferSize + 7) >> 3;

std::vector<unsigned char> result(dim);

for (int j = 0; j < bufferSize; j++)

result[j >> 3] |= (buffer[j] << ((7 – j) & 7));

for (int i = 0; i < dim; i++)

os << result[i];

buffer.reset();

bufferSize = 0;

}

return EXIT_SUCCESS;

}

}

3.3.2.3 Implementare Run-Length Encoding in SmartCompresser

Avand BitFileManager, ne este usor sa scriem si sa citim date la nivel de bit, iar implementarea algoritmului Run Length Enconding se realizeaza foarte repede. Pe scurt: se citeste un byte, daca este identic cu cel anterior, se incrementeaza contorul de frecventa, daca nu, se scrie bitul care marcheaza daca urmeaza sau nu o secventa compresata, numarul de aparitii (daca e cazul) si byteul anterior.

Decompresia se realizeaza la fel de usor: se citeste marcatorul. Daca urmeaza o secventa compresata, se citeste frecventa iar apoi byteul si se reconstituie secventa. Daca nu, se citeste byteul si se scrie direct in fisierul de iesire.

int compressFile(const std::string& inputPath, const std::string& outputPath)

{

BitFileManager fileManager(BitFileManager::Mode::Write, outputPath);

file.get(lastChar);

auto writeData = [&]()

{

fileManager.write(bool(frequency > 1));

if (frequency > 1)

fileManager.write(frequency);

fileManager.write(static_cast<unsigned char>(lastChar));

};

while (file.get(currentChar))

{

if (lastChar != currentChar || frequency >= 255)

{

writeData();

lastChar = currentChar;

frequency = 1;

}

else

frequency++;

}

writeData();

file.close();

return EXIT_SUCCESS;

}

int decompressFile(const std::string& inputPath, const std::string& outputPath)

{

std::ofstream os;

char currentChar;

unsigned char frequency;

BitFileManager fileManager(BitFileManager::Mode::Read, inputPath);

os.open(outputPath, std::ios_base::binary);

bool moreData = true;

while (moreData)

{

bool hasFrecv = false;

if (fileManager.read(hasFrecv) != EXIT_SUCCESS)

{

moreData = false;

continue;

}

if (hasFrecv == true)

fileManager.read(frequency);

else frequency = 1;

if (fileManager.read(static_cast<unsigned char&>(currentChar)) == EXIT_SUCCESS)

{

for (unsigned char j = 0; j < frequency; ++j)

os.write((char*)&currentChar, sizeof(char));

}

}

os.close();

return EXIT_SUCCESS;

}

3.3.3 Compresia Mu-Law

3.3.3.1 Fundamentul teoretic

Atunci cand vorbim despre compresia fisierelor audio, ne gandim automat la faptul ca nu toate sunetele sunt perceptibile de aparatul nostru auditiv. In plus, micile imperfectiuni ale sunetelor trec adesea neobservate. Astfel ne ducem cu gandul la compresii de tip lossy.

O particularitate a fisierelor audio este reprezentata de cele care contin discursuri vocale. La argumentele de mai sus, adaugam si faptul ca vocea nu poate acoperi toate frecventele perceptibile.
Compresia Mu-Law este o metoda care reduce varietatea semnalului audio pentru a putea fi transmis mai repede. La baza ei sta faptul ca multe semnale sunt mai probabil sa fie percepute decat altele. Asadar, sunetul este reprezentat ca o unda insa noi percepem cel mai mult “mijlocul” undei, cu alte cuvinte, daca am elimina sunetele foarte inalte si cele foarte joase, nu am simti nicio diferenta.

In practica, avand in semnat audio sub forma unui numar pe 16 biti, Mu-Law, printr-o serie de transformari, il reduce la numai opt biti. Atunci cand se realizeaza decompresia, nu este reconstituit cu exactitate semnalul initial insa diferentele sunt insesizabile, facand acest algoritm in unul des folosit.

In varianta discreta, tabelul de mai jos descrie transformarile suferite de semnal.

“Pasii algoritmului de compresie (dintr-un numar pe 16 biti se da unul pe 8):

Salveaza bitul de semn

Daca este necesar, inverseaza magnitudinea (pentru a ne proteja de buffer overflow)

Adauga interferenta de 132 magintudinii (pentru a ne asigura ca in rezultat va aparea cel putin un bit 1)

Regiunea reprezentanta este formata din primii 8 biti dupa bitul de semn si noteaza cu P pozitia celui mai din dreapta bit de 1

Mantisa este egala cu urmatorii 4 biti dupa P (spre stanga)

Rezultatul este format din bitul de semn, primii trei biti din regiunea reprezentanta si mantisa

Sa luam un exemplu: 0010 1110 1001 1011

Semnul de bit este 0

Nu este necesara inversarea magnitudinii

Adaugam interferanta 0010 1110 1001 1011 + 1000 0100 = 0010 1111 0001 1111

Regiunea reprezentanta 010 1111 0 iar P este 6 (numararea se face de la 0)

Mantisa este 0111

Rezultatul este 0110 0111

Asadar, compresia lui 0010 1110 1001 1011 este 0110 0111.

Pasii algoritmului de decompresie:

Salveaza bitul de semn

Salveaza regiunea reprezentanta (urmatorii 3 biti dupa cel de semn) in e

Salveaza mantisa (bitii care au mai ramas) in m

a = 3 + e

b = 1000 0100 shiftat la stanga cu e biti – 1000 0100

rezultat = m shiftat la stanga cu a biti + b

Adauga bitul de semn ca fiind cel mai din stanga bit

Sa facem decompresia lui 0110 0111

Bitul de semn este 0

Regiune reprezentanta este 110 = 6

Mantisa este 0111

a = 3 + 6 = 9
b = (1000 0100 shiftat la stanga cu 6 biti) – 1000 0100 = 10 0000 0111 1100
rezultat = 0 1110 0000 0000 + 10 0000 0111 1100 = 10 1110 0111 1100

Adaugam bitul de semn si obtinem 0010 1110 0111 1100

Am obtinut 0010 1110 0111 1100 (119000) desi rezultatul initial era 11931, ceea ce ne demonstreaza ca acest algoritm pierde foarte putine informatii. Cu cat magnitudinea este mai mica, cu atat se micsoreaza si eroarea. Astfel, pentru valori apropiate de 0, rata de succes este 100%, in timp ce, pentru valorile medii avem o eroare de cateva procente.”

3.3.3.2 Implementarea in SmartCompresser

int8_t encode(int16_t data)

{

uint16_t bitMask = 0x1000;

uint8_t sign = 0;

uint8_t pos = 12;

uint8_t mantissa = 0;

if (data < 0) //Step 1: save sign bit

{

data = -data; //Step 2: reverse magnitude

sign = 0x80;

}

data += BIAS; //Step 3: add the bias

if (data > MMAX)

data = MMAX;

while((data & bitMask) != bitMask && pos >= 5) //Step 4: exponent region

{

bitMask >>= 1;

pos–;

}

mantissa = (data >> (pos – 4)) & 0x0f; // Step 5: mantissa

return (~(sign | ((pos – 5) << 4) | mantissa )); // Step 6: build result

}

int16_t decode(int8_t data)

{

uint8_t sign = 0, pos = 0;

int16_t result = 0;

data = ~data;

if (data & 0x80)

{

sign = -1; // Step 1: save sign bit

data &= ~(1 << 7);

}

pos = ((data & 0xF0) >> 4) + 5; // Step 3: mantissa

result = ((1 << pos) | ((data & 0x0F) << (pos – 4))

| (1 << (pos – 5))) – BIAS; // Step 4

return (sign == 0) ? (result) : (-(result)); // Step 5: add sign bit

}

Apelul celor doua metode se face pentru fiecare element din fiserul de intrare: la compresie, pentru int16_t iar la decompresie, int8_t.

La compresie:

int16_t data;

while (input_file.read(reinterpret_cast<char *>(&data), sizeof(data)))

{

int8_t result = encode(data);

output_file.write(reinterpret_cast<const char *> (&result), sizeof(int8_t));

}

La decompresie:

int8_t data;

while (input_file.read(reinterpret_cast<const char *>(&data), sizeof(int8_t)))

{

int16_t result = decode(data);

output_file.write(reinterpret_cast<char*>(&result), sizeof(int16_t));

}

Observam ca, de fiecare data, fisierul comprimat este de exact 2 ori mai mic fata de cel original. Asta se intampla deoarece numarul de elemente este identic, diferenta fiind doar dimensiunea lor.

3.3.4 Compresia Huffman

3.3.4.1 Fundamentul teoretic

Compresia Huffman face parte din categoria algoritmilor fara pierderi de date. Aceasta este o metoda de a asocial unor simboluri coduri binare care sa reduca, per total, numarul de biti folositi pentru a reprezenta informatiile initiale.

Are la baza codarea statistica, asta inseamna ca pentru a genera un secventa de biti asociata unui simbol, se tine cont de probabilitatea ca acesta sa apara in inputul dat. De exemplu, daca ne gandim ca vrem sa compresam un text, alcatuit din mai multe litere si cunoastem detalii despre cat de frecvent apare o litera, am putea sa o codam pe fiecare cu un numar fix de biti. Pentru a creste eficienta variem lungimea cheilor si putem stabili pentru cele care apar mai frecvent, putem stabili siruri reprezentate pe mai putini biti, iar cele mai dese sa aiba asociate simboluri mai mari.

Remarcam ca folosirea unor reprezentari binare de lungime fixa ne va duce exact la caracterele ASCII, deci nu putem afirma ca algoritmul este eficient. Astfel, solutia este folosirea unor chei de lungime variabila. Sa presupunem ca litera “a” este cea mai intalnita urmata de ‘e’ , iar litera “q” apare de cele mai putine ori. ‘a’ va avea asociat codul binar “001”, e “011” iar ‘q’ “001011”.

Sa ne gandim putin la decompresie: vedem ca la un moment dat urmeaza secventa “001011”. Ce e de facut in acest moment ? Urmeaza litera ‘q’ sau e de fapt grupul ‘ae’ ? Pentru a evita astfel de confuzii, constructia arborelui Huffman asigura faptul ca reprezentarea unui simbol nu reprezinta prefix pentru reprezentarea unui altul. Altfel spus, fiecare secventa de biti are exact o metoda pentru decompresie.

Constructia arborelui Huffman

Arborele Huffman este un arbore binar care are propritatea ca reprezentarea fiecarui simbol nu este prefix pentru o alta reprezentare, adica simbolurile sunt frunze in acest arbore. Nodurile care nu sunt frunze se numesc noduri interne. Fiecare nod intern are exact doi fii, unul reprezentat de mucia ‘0’ iar celalalt de muchia ‘1’ dar si o frecventa asociata.

Dupa ce am calculat frecventa de aparitie a fiecarui simbol, procesul incepe avand o multime de frunze, cata una pentru fiecare simbol. Rand pe rand, se iau cate doua noduri care a caror frecventa este cea mai mica si se creeaza unul nou, tata pentru ambii, caruia i se asociaza sumarea frecventelor fiilor sai. Procesul continua ignorand cele doua noduri tocmai alese pana cand mai ramane unul singur, radacina arborelui.

Algoritm pseudocod pentru compresie foloseste o coada cu prioritati:

Calculeaza pentru fiecare simbol, frecventa de aparitie in fisierul de intrare.

Adauga in coada cu prioritati toate simbolurile si frecventele asociate

Cat timp mai sunt noduri in coada:

Scoate doua noduri care au cea mai mica frecventa

Construieste un parinte pentru cele scoase anterior si asociaza-I frecventa ca fiind suma fiilor

Adauga in coada si in arbore nodul nou construit

Nodul ramas reprezinta radacina arborelui Huffman

Parcurgem urmatorul exemplu pentru a intelege mai bine algoritmul:

Decompresia

“In mod general, procesul decompresiei este doar traducerea fiecarei secvente de biti in simbolul initial, realizata in mod normal prin traversarea arborelui Huffman nod cu nod, pe masura ce se citeste cate un nou bit din fisierul de intrare si se cunoaste simbolul initial atunci cand se ajunge intr-o frunza. Inainte de a face asta, arborele Huffman trebuie reconstruit. In cazul cel mai simplu, caracterele au o frecventa predictibila iar arborele va fi intotdeauna acelasi. In celelalta cazuri exista mai multe variante. Una ar fi ca inainte de fiserul codat, sa avem simbolurile initiale si frecventele asociate. O alta ar fi serializarea intregului arbore printr-o traversare de tipul pre-ordine.

Cateva observatii ale compresiei text:

In cazul in care compresie se realizeaza pe date al caror simboluri au aceleasi frecvente, atat compresia cat si decompresia se pot realiza utilizand tabele standard de frecventa. In general, acest lucru nu prea se intampla deoarece frecventele literelor variaza de la o limba la alta: de exemplu, cea mai utilizata consoana in limba romana este R in timp ce in limba engleza este t. De asemenea, putem lua in calcul si fisiere sursa scrise in diverse limbaje de programare, observam ca in C/C++ cel mai utilizat simbol este ‘;’.

Daca simbolurile au frecvente diferite, pentru o compresie optima trebuie sa generam cate un arbore Huffman pentru fiecare tip de fisier pe care vrem sa il compresam si sa il transmitem pentru a putea fi folosit la reconstituirea fisierului initial. Cu toate acestea, costul transmisiei arborelui folosit pentru codare poate depasi eventualele castiguri datorate folosirii lui.

Asadar, se recomanda construirea unor arbori specifici doar atunci cand dorim sa compresam fisiere mari ce nu au o frecventa a simbolurilor similara cu cea a tabelei standard.”

3.3.4.2 Implementarea algoritmului in SmartCompresser

Partea de compresie s-a impartit in 3 pasi: construirea arborelui Huffman, generarea cheilor pentru fiecare simbol si codarea propriu-zisa. BuildHuffmanTree intoarce un pointer catre nodul radacina al arborelui generat, avand la intrare frecventa simbolurilor. Arborele este alcatuit din 2 tipuri de noduri: LeafNode si InternalNode. Primul corespunde frunzelor adica simbolurilor pe care vrem sa le codam iar cel de-al doilea este un nod intern, ce ne ajuta la construirea arborelui. Pentru o claritate mai mare a codului, implementarea a fost facuta folosita o coada cu prioritati

INode* BuildHuffmanTree(const int(&frequencies)[UniqueSymbols])

{

std::priority_queue<INode*, std::vector<INode*>, NodeComparator> tree;

for (int i = 0; i < UniqueSymbols; ++i)

if (frequencies[i] > 0)

tree.push(new LeafNode(frequencies[i], (char)i));

while (tree.size() > 1)

{

INode* childR = tree.top();

tree.pop();

INode* childL = tree.top();

tree.pop();

INode* parent = new InternalNode(childR, childL);

tree.push(parent);

}

return tree.top();

}

Urmatorul pas este construirea vectorilor de biti in care se transforma fiecare simbol. Functia GenerateHuffmanCodes primeste ca parametri nodul pentru care se doreste generarea codului, un vector de bool prefix ceea ce reprezinta codul format pana in acel moment si o referinta la tabela ce retine corespondenta intre simboluri si codurile asociate.

void GenerateHuffmanCodes(const INode* node, const HuffmanCode& prefix, HuffCodeMapping& outCodes)

{

if (const LeafNode* lf = dynamic_cast<const LeafNode*>(node))

{

outCodes[lf->c] = prefix;

}

else if (const InternalNode* in = dynamic_cast<const InternalNode*>(node))

{

HuffmanCode leftPrefix = prefix;

leftPrefix.push_back(false);

GenerateHuffmanCodes(in->left, leftPrefix, outCodes);

HuffmanCode rightPrefix = prefix;

rightPrefix.push_back(true);

GenerateHuffmanCodes(in->right, rightPrefix, outCodes);

}

}

Avand acestea, compresia se realizeaza foarte usor: intai se calculeaza frecventa fiecarui simbol, apoi se construieste arborele huffman si se genereaza codurile corespunzatoare fiecarui simbol.

Pentru fiecare simbol citit, scriem in fisierul de iesire codul asociat. Avand in vedere ca dorim sa scriem in fisierul de iesire mai multi vectori de biti, apelam din nou la BitFileManager care are capacitatea de a face operatii in cadrul fisierelor folosind biti.

int compressFile(const std::string& inputPath, const std::string& outputPath)

{

// Build frequency table

int frequencies[UniqueSymbols] = { 0 };

std::ifstream is(inputPath, std::ios_base::binary);

if (!is.is_open())

return EXIT_FAILURE;

unsigned char data;

while (is.get(reinterpret_cast<char&>(data)))

++frequencies[data];

INode* treeRoot = BuildHuffmanTree(frequencies);

HuffCodeMapping codes;

GenerateHuffmanCodes(treeRoot, HuffmanCode(), codes);

delete treeRoot;

is.clear();

is.seekg(0, std::ios::beg);

BitFileManager os(BitFileManager::Mode::Write, outputPath);

for (HuffCodeMapping::const_iterator it = codes.begin(); it != codes.end(); ++it)

{

unsigned char data = static_cast<unsigned char>(it->first);

os.write(data);

std::vector<bool> coded = codes[data];

for (const auto& it : coded)

it == true ? os.write('1') : os.write('0');

}

while (is.get(reinterpret_cast<char&>(data)))

{

std::vector<bool> coded = codes[data];

for (const auto& it : coded)

os.write(it);

}

is.close();

return EXIT_SUCCESS;

}

Avand in vedere ca la compresie am scris in fisierul de iesire corespondenta dintre simboluri si codurile binare, pentru a realiza decompresia nu suntem nevoiti sa reconstruim arborele, ci este suficienta doar codarea simbolurilor. Stiind ca arborele Huffman are proprietatea ca orice cod asociat nu este prefix pentru un alt simbol, atunci cand citim o secventa ce se poate traduce intr-un simbol, scriem traducerea si resetam secventa.

int decompressFile(const std::string& inputPath, const std::string& outputPath)

{

// Build frequency table

std::ofstream os(outputPath, std::ios_base::binary);

if (!os.is_open())

return EXIT_FAILURE;

HuffDecodeMapping decodes;

BitFileManager is(BitFileManager::Mode::Read, inputPath);

unsigned char data;

for (is.read(data); data != 0;)

{

unsigned char code;

std::vector<bool> enc;

for (is.read(code); code == '0' || code == '1'; is.read(code))

enc.push_back(code == '0' ? false : true);

decodes[enc] = data;

data = code;

}

bool bit;

std::vector<bool> enc;

while (is.read(bit) == EXIT_SUCCESS)

{

enc.push_back(bit);

auto it = decodes.find(enc);

if (it != decodes.end())

{

enc.clear();

os.write(reinterpret_cast<const char *> (&it->second), sizeof (char));

}

}

os.close();

return EXIT_SUCCESS;

}

3.4 Analiza asupra comportamentului SmartCompresser

In ultima etapa vom analiza comportamentul algoritmilor implementati dar si a compresiei de tipul “Smart”.

In prima faza vom face cateva observatii asupra mecanismului din spatele fiecarei metoda de compresie:

Lempel-Ziv-Welch, fiind bazat pe un dictionar, se comporta bine pe o mare plaja de tipuri de fisiere.

Huffman genereaza siruri de biti pentru fiecare simbol, deci ar fi avantajat pentru fisierele in care sunt prezente mai putine simboluri, cum ar fi baze de date plate. In extrema cealalta se situeaza fisierele binare sau cele deja compresate.

MuLaw reduce cu exact 50% dimensiunea fisierelor audio in format raw pe 16 biti iar pe celalalte tipuri de fisiere nu poate fi folosit deoarece este un algoritm cu pierderi de informatii.

Run Length-Ecoding inlocuieste secvente de bytes egali cu valoarea si numarul de repetitii deci un rezultat mai bun s-ar obtine pe fisiere care au aceasta proprietate, de exemplu imagini in format cu un numar mic de culori.

3.4.1 Stabilirea testbedurilor

In functie de tipul de date pe care doreste sa le comprimeze integratorul, se poate alcatui cate un testbed. Pentru cele mai intalnite apliicatii, am stabilit urmatoarele 5 seturi de date pe care le vom folosite in testarea capacitatilor algoritmilor implementati.

fisiere din baze de date plate, fisiere text, documente HTML

imagini

fisere audio raw

fisiere aleator alese: binare, imagini, audio, temporare, arhive, documente

3.4.2 Analiza comportamentului

Pentru fiecare din cazurile de mai sus putem folosi toti algoritmii cu exceptia Mu-Law. Acesta, fiind cu pierderi de date, poate fi folosit doar asupra fisierelor audio in format raw.

3.4.2.1 Fisiere din baze de date plate, fisiere text si documente HTML

Observam ca LZW s-a comportat cel mai bine pe acest tip de fisiere iar compresia Smart s-a adaptat foarte bine, utilizand acelasi algoritm in toate cazurile. RLE a avut o crestere liniara ceea ce ne face sa credeam ca fisierele au avut, in mare parte, pe pozitii consecutive caractere diferite.

3.4.2.2 Imagini

Avand cateva ce erau dominate de o singura culoare, RLE a dat rezultate foarte bune pe ele, realizand o compresie extrem de eficienta, fiind folosit si de compresia Smart. Acelasi comportament l-a avut si LZW, algoritm utilizat pe celalalte imagini de catre Smart.

3.4.2.3 Audio raw

Observam avantajul urias al compresiei cu pierdere de date folosita de algoritmul Mu-Law. Acesta se diferentiaza detasat fata de restul metodelor. Avand in vedere ca modul Smart utilizeaza doar algoritmiti lossless, acesta a preferat in general doar utilizarea Huffman deoarece s-a comportat cel mai bine pe exemplele din test.

3.4.3.4 Fisiere variate

In acest caz general, foarte intalnit, observam ca modul Smart utilizeaza de fiecare data algoritmul care se pliaza cel mai bine pe modul de reprezentare al datelor din fisierul de intrare. Per general, LZW este cel mai optim insa pentru unele fisiere Huffman a dat rezultate mai bune.

3.4.3.5 Timpul de executie

Un alt criteriu de performata il reprezinta si timpul de rulara. Vom utiliza ultimul set de exemple pentru a analiza comportamentul.

In ciuda faptului ca trebuie sa gestioneze intrarile din dictionar, LZW are un timp de rulare foarte mic, aceasta deoarece opereaza direct cu streamul de date. Principalul consumator de timp in cazul RLE dar si Huffman il reprezinta BitFileManager care face multe conversii in timp ce opereaza operatii de citire/scriere. Asa cum ne asteptam, “Smart” depaseste cu putin timpul in care ar rula in mod normal algoritmul ales deoarece face cateva compresii pentru a o determina pe cea mai buna.

4. Idei finale

4.1 Privire de ansamblu

Dupa cum am observat, cantitatea de date va continua sa cresca cu aceeasi viteza ca si pana acum, ajungand in punctul in care capacitatea de transfer a retelelor sa nu faca fata acestui volum urias de informatii. In calitate de programatori, atunci cand avem de a face cu probleme in ceea ce priveste cantitatea de date pe care trebuie sa o transferam sau prelucram, o buna solutie este utilizarea unor metode de compresie eficiente si rapide.

Dezvoltarea algoritmilor de compresie implica atat intelegerea modului in care sunt structurate datele cat si capacitatile celui care are nevoie de ele. Astfel, metodele de tip lossy ofera un randament foarte bun in schimbul unor diferente nesesizabile asupra informatiilor.

4.2 Concluzii

SmartCompresser este o biblioteca flexibila, usor de utilizat si integrat in produsele proprii. Aceasta ofera suport pentru utilizarea mai multor metode de compresie dar si pentru tipul “Smart”, prin care deduce in mod automat algoritmul care se potriveste cel mai bine fluxului de date pe care dorim sa il codam.

Prin utilizarea caracteristicii sale principale, modul “Smart”, scapam de grija analizei datelor in vederea alegerii unei metode de compresie deoarece acest lucru se realizeaza in mod automat si ne ofera siguranta ca datele sunt compresate intr-o maniera rapida si robusta.

Asadar, SmartCompresser poate fi utilizata cu usurinta, scapandu-ne de eventualele dificultati in ceea ce priveste comprimarea informatiilor cu care trebuie sa operam.

4.3 Oportunitati de continuare a dezvoltarii

In ceea ce priveste continuarea dezvoltarii, oportunitatile se impart in doua categorii.

In primul rand partea inovare. Pot fi adaugati noi algoritmi atat lossless cat si lossy care sa se plieze mai bine pe anumite tipuri de informatii.

In al doilea rand este optimizarea. Metodele existente de compresie pot fi optimizate pentru a rula mai bine atat din punct de vedere al timpului dar si din punct de vedere al rezultatului compresiei. Asa cum am observat, unele structuri au nevoie de o atentie sporita si optimizari ce pot fi realizate dupa o foarte buna intelegere atat a informatiilor care vor fi comprimate cat si a modului in care se comporta structurile de date din C++.

De asemenea, algoritmul de compresie “Smart” poate fi imbunatatit astfel incat sa tina cont de marimea fisierului sau alte criterii.

Bibliografie

[1] Internet Live Stats. (2015) “Internet Users in the World”. [Online] Available from http://www.internetlivestats.com . [Accesed: 02.04.2015]

[2] Wikipedia. (2015) Moore’s Law. [Online] Available from: http://en.wikipedia.org/wiki/Moore%27s_law [Accesed 04.04.2015]

[3] Cisco Visual Networking Index. (2014) “Forecast and Methodology 2014-2019”. [Online] Available from http://www.cisco.com/c/en/us/solutions/collateral/service-provider/ip-ngn-ip-next-generation-network/white_paper_c11-481360.html . [Accesed 04.04.2015]

[4] Mahdi O. A, Mohamed M. A, Mohamed A. J “Implementing a Novel Approach an Convert Audio Compression to Text via Hybrud Technique”, International Journal of Computer Science Issues

[5] M. Arjona Ramiez, M. Minami “Technology and standars for low-bit-rate vocoding methods” in The Handbook of Computer Networks, Ed. New York: Wiley 2011, vol 2

[6] Burt P., Andelson E. “The Laplacian Pyramid as a Compact Image Code” Transactions on Communications 31 (1983).

[7] “Video Coding” Center for Signal and Information Processing Research. Georgia Institute of Technology (March 2013).

[8] Pavlichin DS, Weissman T “The human genome contracts again”, Bioinformatics 29, (September 2013)

[9] Charles Lefurgy, Eva Piccininni, Trevor Mudge “Reducing Code Size with Run-time decompression”

[10] WikiBooks. (2012) Data Compression/Evaluating Compression Effeciveness. [Online] Available from: http://en.wikibooks.org/wiki/Data_Compression/Evaluating_Compression_Effectiveness [Accessed: 02.06.2015].

[11] Udi Manber. (1993) “A Text Compression Scheme That Allows Fast Searching Directly In The Compressed File”.

[12] Duke Univerity. (2015) LZW Data compression. [Online] Available from: http://www.cs.duke.edu/csed/curious/compression/lzw.html. [Accesed 18.04.2015].

[13] Wikipedia. (2014)μ-law algorithm. [Online] Available from: http://en.wikipedia.org/wiki/%CE%9C-law_algorithm. [Accesed: 18.04.2015]

[14] Wake Forest University. (2015) Mu-Law Encoding in C++. [Online] Available from: http://csweb.cs.wfu.edu/~burg/CCLI/Tutorials/C/Chapter5/Mu_Law_Encoding_in_C++.pdf. [Accesed 18.04.2015]

[15] Wikipedia. (2015) Huffman Coding. [Online] Available from: http://en.wikipedia.org/wiki/Huffman_coding. [Accesed 03.06.2015]

[16] Wikipedia. (2015) Huffman Coding. [Online] Available from: http://en.wikipedia.org/wiki/Huffman_coding. [Accesed 03.06.2015]

Bibliografie

[1] Internet Live Stats. (2015) “Internet Users in the World”. [Online] Available from http://www.internetlivestats.com . [Accesed: 02.04.2015]

[2] Wikipedia. (2015) Moore’s Law. [Online] Available from: http://en.wikipedia.org/wiki/Moore%27s_law [Accesed 04.04.2015]

[3] Cisco Visual Networking Index. (2014) “Forecast and Methodology 2014-2019”. [Online] Available from http://www.cisco.com/c/en/us/solutions/collateral/service-provider/ip-ngn-ip-next-generation-network/white_paper_c11-481360.html . [Accesed 04.04.2015]

[4] Mahdi O. A, Mohamed M. A, Mohamed A. J “Implementing a Novel Approach an Convert Audio Compression to Text via Hybrud Technique”, International Journal of Computer Science Issues

[5] M. Arjona Ramiez, M. Minami “Technology and standars for low-bit-rate vocoding methods” in The Handbook of Computer Networks, Ed. New York: Wiley 2011, vol 2

[6] Burt P., Andelson E. “The Laplacian Pyramid as a Compact Image Code” Transactions on Communications 31 (1983).

[7] “Video Coding” Center for Signal and Information Processing Research. Georgia Institute of Technology (March 2013).

[8] Pavlichin DS, Weissman T “The human genome contracts again”, Bioinformatics 29, (September 2013)

[9] Charles Lefurgy, Eva Piccininni, Trevor Mudge “Reducing Code Size with Run-time decompression”

[10] WikiBooks. (2012) Data Compression/Evaluating Compression Effeciveness. [Online] Available from: http://en.wikibooks.org/wiki/Data_Compression/Evaluating_Compression_Effectiveness [Accessed: 02.06.2015].

[11] Udi Manber. (1993) “A Text Compression Scheme That Allows Fast Searching Directly In The Compressed File”.

[12] Duke Univerity. (2015) LZW Data compression. [Online] Available from: http://www.cs.duke.edu/csed/curious/compression/lzw.html. [Accesed 18.04.2015].

[13] Wikipedia. (2014)μ-law algorithm. [Online] Available from: http://en.wikipedia.org/wiki/%CE%9C-law_algorithm. [Accesed: 18.04.2015]

[14] Wake Forest University. (2015) Mu-Law Encoding in C++. [Online] Available from: http://csweb.cs.wfu.edu/~burg/CCLI/Tutorials/C/Chapter5/Mu_Law_Encoding_in_C++.pdf. [Accesed 18.04.2015]

[15] Wikipedia. (2015) Huffman Coding. [Online] Available from: http://en.wikipedia.org/wiki/Huffman_coding. [Accesed 03.06.2015]

[16] Wikipedia. (2015) Huffman Coding. [Online] Available from: http://en.wikipedia.org/wiki/Huffman_coding. [Accesed 03.06.2015]