TECHNICKÁ UNIVERZITA V LIBERCI

´ UNIVERZITA V LIBERCI TECHNICKA Fakulta mechatroniky a mezioborov´ ych inˇzen´ yrsk´ ych studi´ı

Komprese mˇeˇreny´ch dat v 0.1

Liberec 2007

Viktor Bubla

Obsah 1 Proˇ c komprimace? 2 Filosofie z´ akladn´ıch komprimaˇ cn´ıch 2.1 Slovn´ıkov´e . . . . . . . . . . . . . . 2.2 Statistick´e . . . . . . . . . . . . . . 2.3 Ostatn´ı . . . . . . . . . . . . . . .

2 algoritm˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 2 2 3

3 Hlediska hodnocen´ı 3.1 Rychlost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Kompresn´ı pomˇer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Pamˇet’ov´ a n´ aroˇcnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 3 4

4 Poˇ zadavky pro c´ılovou aplikaci

4

5 Z´ avˇ er

4

1

1

Proˇ c komprimace?

Nejz´ asadnˇejˇs´ım d˚ uvodem, proˇc v˚ ubec zaˇcali vznikat jak´ekoli komprimaˇcn´ı algoritmy, je u ´spora mnoˇzstv´ı prostor potˇrebn´ ych pro uchov´ an´ı dat a z toho plynouc´ı dalˇs´ı d˚ usledky, jako zv´ yˇsen´ı rychlosti toku uˇziteˇcn´e informace skrze pˇrenosovou cestu s limitovanou pˇrenosovou rychlost´ı (vˇzdy), nebo tˇreba zv´ yˇsen´ı vyuˇzitelnosti u ´loˇzn´ ych zaˇr´ızen´ı (vˇetˇs´ı kapacita). Pokaˇzd´e dojde ke sn´ıˇzen´ı n´aklad˚ u, coˇz je vlastnˇe nepˇr´ım´ ym hlavn´ım d˚ uvodem. Pochopitelnˇe kaˇzd´e plus m´a i sv´e minusy. M˚ uˇzeme hovoˇrit o vyˇsˇs´ı sloˇzitosti softwaru a s t´ım u ´zce souvisej´ıc´ımi hardwarov´ ymi n´aroky ˇci o tom, ˇze data nem˚ uˇzeme pˇr´ımo ˇc´ıst, ale mus´ıme pˇredt´ım prov´est inverzn´ı operaci atd.

2 2.1

Filosofie z´ akladn´ıch komprimaˇ cn´ıch algoritm˚ u Slovn´ıkov´ e

Slovn´ıkov´e nebo tak´e substituˇcn´ı kod´ery pracuj´ı na principu hled´an´ı shodn´ ych ˇretˇezc˚ u mezi komprimovan´ ymi daty a datovou strukturou naz´ yvanou slovn´ık, kterou enkod´er postupnˇe upravuje. Ve chv´ıli, kdy je nalezena shodn´ a ˇc´ ast ˇretˇezce, je tento nahrazen referenc´ı na sv˚ uj pˇredchoz´ı v´ yskyt. Pro vysok´ y stupeˇ n komprese je tˇreba vyuˇz´ıvat velk´ y slovn´ık, d´ıky kter´emu je komprese pamˇet’ovˇe a v´ ypoˇcetnˇe dosti n´ aroˇcn´ a. Slovn´ıkov´e algoritmy jsou univerz´ alnˇe pouˇziteln´e a maj´ı obzvl´aˇstˇe dobr´e v´ ysledky pˇri kompresi dat, ve kter´ ych se urˇcit´e bloky ˇcasto opakuj´ı (text). Lempel-Ziv ˇ ezcov´a reference je zde typicky LZ77 je jedn´ım z pˇredstavitel˚ u slovn´ıkov´ ych kompresn´ıch algoritm˚ u. Retˇ reprezentov´ ana unik´ atn´ım markerem, offsetem a d´elkou substituovan´eho ˇretˇezce, pˇriˇcemˇz d´elka reference je promˇenn´ a. Nev´ yhodou je zdlouhav´e porovn´ av´ an´ı, kdy pro kaˇzd´ y jednotliv´ y byte vstupn´ıch dat m˚ uˇze kaˇzd´ y pˇredeˇsl´ y byte b´ yt potenci´ aln´ım poˇc´ atkem pro porovn´av´an´ı ˇretˇezce, coˇz znamen´a, ˇze komprese je velice pomal´ a. Jako slovn´ık je vyuˇz´ıv´ ano tzv. plovouc´ı okno, kde jsou uchov´ana posledn´ı naˇcten´a data tak, aby v nich bylo moˇzn´e hledat shody ˇretˇezc˚ u. Lempel-Ziv-Oberhumer LZO je z´ asadnˇe vylepˇsen´ a varianta LZ. Zamˇeˇruje se na rychlost komprese a extr´emn´ı rychlost dekomprese.

2.2

Statistick´ e

Kompresn´ı algoritmy v t´eto kategorii vytv´ aˇrej´ı (pˇresnˇeji ˇreˇceno pouˇz´ıvaj´ı) tabulky znak˚ u seˇrazen´e podle poˇctu v´ yskytu ve vstupn´ım souboru dat. Znaky jsou pomoc´ı tabulky pˇrev´adˇeny do bin´arn´ı formy, pˇriˇcemˇz ty s nejvˇetˇs´ım poˇctem v´ yskyt˚ u (nejpravdˇepodobnˇejˇs´ı) jsou substituov´any nejmenˇs´ım poˇctem bit˚ u a ty nejm´enˇe ˇcetn´e nejvˇetˇs´ım poˇctem bit˚ u. Tabulka se ukl´ad´a na zaˇc´atek komprimovan´eho souboru. Podle konkr´etn´ı implementace jsou varianty, kde se tabulka (tzv. hufmann˚ uv strom) vytv´aˇr´ı pˇri prvn´ım pr˚ uchodu komprimovan´ ymi daty, kde je tabulka pevnˇe dan´a a nemus´ı se tedy ukl´adat spolu se souborem, nebo kde je implicitn´ı poˇc´ ateˇcn´ı tabulka a bˇehem komprimace se dynamicky modifikuje. Huffman V prvn´ım kroku jsou veˇsker´e znaky seˇrazeny dle frekvence v´ yskytu od nejˇcastˇejˇs´ıho po nejneobvyklejˇs´ı. D´ ale jsou vybr´ any dva znaky s nejmenˇs´ı frekvenc´ı v´ yskytu, logicky seskupeny a jejich frekvence seˇcteny. T´ım se zapoˇc´ın´ a stavba tzv. bin´ arn´ıho stromu“. Opˇet jsou vybr´any dva prvky s nejniˇzˇs´ı frekvenc´ı, ” pˇriˇcemˇz v posledn´ım kroku seˇcten´ a kombinace znak˚ u je nyn´ı povaˇzov´ana takt´eˇz za jeden element, jejich v´ yskyty jsou seˇcteny atd. V posledn´ı iteraci dostaneme jeden jedin´ y koˇren huffmanova stromu. Nyn´ı se postupuje od koˇrene a kaˇzd´emu rozvˇetven´ı je pˇridˇelena 1 a 0. Je dokonce jedno, jak´a z dvojice vˇetv´ı dostane pˇridˇelenu kterou hodnotu, avˇsak pouˇz´ıv´a se jeden konzistentn´ı styl. Pokraˇcujeme do koruny ” stromu“ ve vˇsech vetv´ıch. Nyn´ı jiˇz kaˇzd´emu znaku odpov´ıd´a bin´arn´ı hodnota dan´a posloupnost´ı 1 nebo 0 od koˇrene stromu aˇz k m´ıstu, kde konˇc´ı vˇetev s dan´ ym znakem. Je jasn´e, ˇze znak s nejvˇetˇs´ı frekvenc´ı v´ yskytu m´ a od koˇrene ke sv´e vˇetvi“ nejkratˇs´ı cestu, tedy nejm´enˇe bitov´e vyj´adˇren´ı. ” Pˇri kompresi se proch´ az´ı zdrojov´ a data a kaˇzd´ y znak je konvertov´an do sv´eho bin´arn´ıho obrazu dan´eho huffmanov´ ym stromem. 2

Shannon-Fano Shannon-Fano algoritmus je ve sv´e podstatˇe totoˇzn´ y s huffmanov´ ym. Rozd´ıl je pouze ve zp˚ usobu v´ ystavby bin´ arn´ıho stromu. Zat´ımco Huffman ho stav´ı odspodu nahoru, Shannon-Fano odshora dolu. Dle sv´ ych frekvenc´ı v´ yskytu seˇrazen´e znaky jsou vˇzdy rozdˇeleny na dvˇe poloviny tak, aby souˇcty v´ yskyt˚ u obou skupin byly co nejbliˇzˇs´ı. Stejnˇe se pokraˇcuje pˇri dalˇs´ım dˇelen´ı. Pˇriˇrazen´ı bin´arn´ıch hodnot jednotliv´ ym znak˚ um jiˇz prob´ıh´ a naprosto totoˇznˇe. Vytvoˇren´ y strom je dokonce tak´e shodn´ y jako strom vytvoˇren´ y huffmanov´ ym algoritmem. Komprese Shannon-Fano vznikla dˇr´ıve a huffman˚ uv zp˚ usob v´ ystavby stromu byl pouze jej´ım vylepˇsen´ım a zefektivnˇen´ım.

2.3

Ostatn´ı

RLE - Run Length encoding Funkce jednoho z nejjednoduˇsˇs´ıch algoritm˚ u spoˇc´ıv´a v nahraˇzen´ı za sebou se opakuj´ıc´ıho symbolu escape sekvenc´ı, poˇctem opakov´ an´ı vyj´ adˇren´ ym bin´arn´ım ˇc´ıslem a opakuj´ıc´ım se symbolem. Veta s opakujiciiiiiiiiiiiiiiiim se i. Veta s opakujic<ESC><16>im se i. Pˇri kompresi textov´ ych soubor˚ u nem´ a RLE t´emˇeˇr v´ yznam pouˇz´ıvat, avˇsak ˇcasto se vyuˇz´ıv´a jako prvn´ı stupeˇ n sloˇzit´ ych algoritm˚ u sloˇzen´ ych z nˇekolika r˚ uzn´ ych zp˚ usob˚ u komprese, jako je napˇr´ıklad JPEG. Kupˇr´ıkladu u monochromatick´eho obrazov´eho souboru je moˇzn´e dos´ahnout proveden´ım RLE i o nˇekolik ˇr´ ad˚ u menˇs´ı velikosti. Jako nev´ yhodu m˚ uˇzeme oznaˇcit nemoˇznost v´ıce neˇz 256 n´asobn´eho opakov´an´ı a probl´em souvisej´ıc´ı s moˇznost´ı v´ yskytu escape sekvence (znaku) v komprimovan´em souboru. Prvn´ı nev´ yhoda se ˇreˇs´ı pouˇzit´ım ˇctyˇrbytov´eho popisu opakov´ an´ı, ˇc´ımˇz je zvˇetˇsen rozsah na 32768 opakuj´ıc´ıch se znak˚ u, a v druh´em pˇr´ıpadˇe se na v´ ystup zap´ıˇse dvakr´ at po sobˇe znak escape sekvence. T´ım se bohuˇzel zbyteˇcnˇe navyˇsuje v´ ystupn´ı velikost a proto je znak volen tak, aby se vyskytoval s nejmenˇs´ı frekvenc´ı v´ yskytu, nebo v˚ ubec.

3 3.1

Hlediska hodnocen´ı Rychlost

Rychlost komprese vypov´ıd´ a o sloˇzitosti algoritmu. D´a se ˇr´ıci, ˇze rychlost je nepˇr´ımo u ´mˇern´a kvalitˇe“ ” komprese, tedy kompresn´ımu pomˇeru (viz 3.2), a pˇr´ımo u ´mˇern´a pamˇetov´e n´aroˇcnosti (viz 3.3). Jasnˇe se zde nab´ız´ı ot´ azka, ˇcemu d´ at pˇrednost. V´ ybˇer je samozˇrejmˇe ot´azkou kompromisu mezi rychlost´ı, kompresn´ım pomˇerem a pamˇet’ovou n´ aroˇcnost´ı. V ide´aln´ım pˇr´ıpadˇe bychom vˇzdy mohli pouˇz´ıt dokonal´ y“ ” kompresn´ı algoritmus, kter´ y by ve vˇsech ohledech zv´ıtˇezil. V praxi to nen´ı moˇzn´e uˇz jen z toho d˚ uvodu, ˇze pokaˇzd´e komprimujeme data jin´eho charakteru a n´aˇs dokonal´ y algoritmus by tedy musel b´ yt velice sloˇzit´ y kv˚ uli dosaˇzen´ı velk´eho kompresn´ıho pomˇeru a tedy by nemohl konkurovat v rychlosti jednoduˇsˇs´ım variant´ am. Rychlost komprese je u ´daj porovnavateln´ y pouze s hodnotami z´ıskan´ ymi za stejn´ ych podm´ınek na stejn´em stroji. Z´ asadnˇe jin´e v´ ysledky z´ısk´ ame pˇri komprimov´an´ı na r˚ uzn´em hardwaru. Na rozd´ıl od kompresn´ıho pomˇeru je zde v´ ysledek vlastnˇe pokaˇzd´e jin´ y. Ovlivˇ nuj´ı ho napˇr´ıklad dalˇs´ı spuˇstˇen´e procesy, nebo tˇreba i jen pohyb ukazatelem myˇsi. Mˇeˇren´ım ˇcasu, s vyuˇzit´ım ˇcasovaˇc˚ u bˇeˇz´ıc´ıch pro kaˇzd´ y proces zvl´ aˇst, lze vliv minimalizovat. Rychlost komprese budu uv´ adˇet v kB/s. Jako pˇr´ıklad m˚ uˇzeme zkomprimovat 50 kB dat za 10 ms: Speed =

InSize 50 kB = = 5000 kBs−1 T ime 10 ms

(1)

Jak z v´ ypoˇctu vypl´ yv´ a, poˇc´ıt´ a se se vstupn´ı velikost´ı dat.

3.2

Kompresn´ı pomˇ er

Teoreticky by dokonal´ y kompresn´ı algoritmus mohl b´ yt schopen ze sign´alu ˇci informace odstranit veˇskerou redundanci a na jeho v´ ystupu by mˇel b´ yt bal´ık dat o velikosti dan´e mnoˇzstv´ım informace vstupn´ıho sign´alu dle shannonova teor´emu. V praxi se tomuto ide´alu snaˇz´ıme co nejv´ıce pˇribl´ıˇzit a jedn´ım z krit´eri´ı v´ ybˇeru

3

je pr´ avˇe hodnota vypov´ıdaj´ıc´ı o schopnosti zkomprimovat data, j´ıˇz je pomˇer mezi vstupn´ı a v´ ystupn´ı velikost´ı. Rozhodl jsem se pouˇz´ıvat hodnotu v procentech. Na pˇr´ıkladu ilustruji zp˚ usob v´ ypoˇctu, pokud jsme naˇsich 50 kB dat zkomprimovali na 30 kB: Ratio =

3.3

OutSize 30 kB · 100 = · 100 = 60 % InSize 50 kB

(2)

Pamˇ et’ov´ a n´ aroˇ cnost

´ ˇ E ˇ PORE ˇ SIT... ˇ TOHLE JE PROBLEM. MUS´ I SE JEST

4

Poˇ zadavky pro c´ılovou aplikaci

Komprese mˇeˇren´ ych dat m´ a b´ yt prov´ adˇena v embeded mˇeˇric´ım zaˇr´ızen´ı, na kter´em bˇeˇz´ı OS Linux. ´ Uloha komprimov´ an´ı bude vyuˇz´ıv´ ana periodicky vˇzdy po zachycen´ı urˇcit´eho mnoˇzstv´ı dat pˇred t´ım, neˇz budou v´ ysledky mˇeˇren´ı odesl´ any do spoleˇcn´eho u ´loˇzn´eho a monitorovac´ıho zaˇr´ızen´ı, v nˇemˇz budou trvale uchov´ av´ ana. Vzhledem k hardwarov´ ym parametr˚ um zaˇr´ızen´ı je nejz´asadnˇejˇs´ım krit´eriem pro v´ ybˇer kompresn´ıho algoritmu jeho pamˇet’ov´ a n´ aroˇcnost. Z uˇz tak mal´eho mnoˇzstv´ı dostupn´e pamˇeti vyuˇz´ıvaj´ı bˇeˇz´ıc´ı procesy tolik, ˇze pro veˇskerou kompresn´ı ˇcinnost zb´ yvaj´ı jednotky kB. Dalˇs´ı vlastnost´ı, jiˇz je tˇreba zv´ aˇzit, je v´ ypoˇcetn´ı n´aroˇcnost — tedy rychlost komprese. Aˇc se jedn´a o komprimaci nˇekolika kB namˇeˇren´ ych dat, velmi pomal´a komprese by mohla ˇcinit pot´ıˇze, protoˇze musej´ı b´ yt pravidelnˇe obsluhov´ any dalˇs´ı procesy a v´ ykon CPU v embeded zaˇr´ızen´ı nen´ı nˇeˇc´ım, ˇc´ım by se dalo pl´ ytvat. Na posledn´ım m´ıstˇe, i kdyˇz v neposledn´ı ˇradˇe, je dosahovan´ y kompresn´ı pomˇer. Podle nˇej bychom se rozhodovali v pˇr´ıpadˇe, ˇze bychom mˇeli na v´ ybˇer z v´ıce kompresn´ıch algoritm˚ u s vlastnostmi popsan´ ymi v´ yˇse na stejn´e u ´rovni.

5

Z´ avˇ er

´ CO PSAT. ´ PRED ˇ ´ EREM ˇ ´ UVEDL POPIS TESTOV TUTO CHV´ ILI SEM NEMAM ZAV BYCH RAD ´ ˚ ´ ´ ´ ´ VACIHO PROGRAMU A ZPUSOB GENEROVANI DAT PRO KOMPRESI, DALE TABULKY VY˚ ˚ ´ ˚ ˇ ´ ˇ ´ SLEDKU PRO RUZNE ZPUSOBY ULOZENI DAT, NEJAKE TY GRAFY A NAKONEC TABULKU ˇ U“ ˚ SERAZENOU ˇ ˇ ´ ´ ´ ERU ˇ ˇ ˇ ROZEBRAT V´ ITEZ PODLE VSECH KRITERI I. DO ZAV SAMOZREJM E ” ˇ ˇ PROC TA A TA KOMPRESE DOPADLA TAK A TAK A PROC JE TEDY MINI-LZO NEJLEPSˇ´ I :-).

Reference [1] Introduction to Losseless Data Compression: http://web.archive.org/web/20060410170411/http://www.vectorsite.net/ttdcmp1.html [2] LZ77: http://en.wikipedia.org/wiki/LZ77 and LZ78 [3] Basic Compression Library Manual http://bcl.comli.eu/home-en.html [4] LZO: http://www.oberhumer.com/opensource/lzo/

4