Kompresija podataka

1. POJAM KOMPRESIJE PODATAKA I NJENI POSTUPCI
Kompresija (engl. data compression) je proces smanjivanja potrebnog fizičkog prostora za čuvanje podataka uz pomoć određenih metoda za zabeležavanje podataka. Najprostiji način da se u jednoj rečenici opiše šta je kompresija je: Kompresija podataka je postupak smanjenja jedne ili više datoteka u jednu, koja bi po pravilu trebala da bude manja od početne ili početnih datoteka.
Postoje dva postupka kompresije, zaboravni i nezaboravni.
Zaboravni postupak kompresije, tj kompresija sa gubicima (eng. lossy compression) je vrsta kompresije gde su prihvaćeni određeni gubici. Kod ove kompresije nije zagarantovano da će podaci koji se kompresuju nakon dekomprezacije biti isti kao oni sa početka. Ovim putem bi se dobio podatak koji je skoro identican, naravno uz male nedostatke koji „nisu bitni“. Ovaj vid kompresije se najčešće koristi prilikom rada sa slikama i video fajlovima.
Nezaboravni postupak kompresije, tj kompresija bez gubitaka (eng. lossless compression) je vrsta kompresije kod koje ne dolazi do bilo kakve razlike izmedju podatka pre kompresije i nakon dekompresije. Ovaj vid kompresije se koristi u slučajevima kada SVAKI bit mora da ostane nepromenjen.
Primer ove kompresije je u bankama i njihovim računima. U ovim slučajevima je bitno da sve ostane nepromenjeno da se ne bi zagubila ili dodala neka nula na računu.
Postoje tri norme za nezaboravno kompresovanje.
– RLE (eng. Run Length Encoding)
– Huffmanov postupak
– Lempel – Ziv postupak

2.1. RLE
RLE (eng. run lenght encoding)je vrlo jednostavna metoda koja koristi činjenicu da se u mnogim datotekama često nalazi niz istih znakova koji se pojavljivaju tako da je njen zadatak da ih zameni specijalnim znakovima ili kodom.
Primer: Ukoliko nam se u datotekama pojavljuje niz XXXXXXXXXX, koji je sačunjen od 10 karaktera, možemo ga zapisati kao 10X i time uštedeti 7 karaktera.
Na slici je prikazan još jedan primer RLE koda. U njemu se primećuje da se mnogo pojavljuju nule tako da ih možemo zapisati na specijalan način kako bi uštedeli memoriju.

Značajne karakteristike RLE-a su: lako se implementira, softverski ili hardverski, vrlo je brzo, lako se proverava, ali ima ograničene mogućnosti kompresije,jer postoji vrlo malo uzastopnih ponavljanja istog znaka u podacima, zbog čega i nije baš delotvoran.

2.2. HUFFMANOV POSTUPAK
Ovaj algoritam je razvio D.A.Huffman i temelji se na činjenici da se neki znakovi pojavljuju češće nego neki drugi. To je najstariji postupak kompresije.
Njemu se pripisuju kodovi različite dužine različitim znakovima. Time znak koji se pojavljuje često kodiramo jednim ili s dva bita, a onaj koji se retko pojavljuje s više od dva bita. Nedostatak je to što kodiramo znakove, a ne skupove znakova.
Algoritam se temelji na osnovi izgradnje binarnog stabla, gdje se svakom elementu tog stabla pridružuje nova kodna reč određena pozicijom znaka u stablu. Najčešće ponavljani znak postaje koren stabla i njemu se pridružuje najkraća kodna reč, dok kodna reč najređe ponavljanog znaka može biti i dvostruko duža od samog znaka.
Na slici ispod je prikazana kompresija podataka pomoću Huffmanovog postupk