}w !"#$%&'()+,-./012345
M ASARYKOVA UNIVERZITA FAKULTA INFORMATIKY
Porovnání komprimaˇcních programu˚ na textových korpusech ˇ BAKALÁ RSKÁ PRÁCE
Jakub Foltas
Brno, 2014
Prohlášení Prohlašuji, že tato bakaláˇrská práce je mým puvodním ˚ autorským dílem, které jsem vypracoval samostatnˇe. Všechny zdroje, prameny a literaturu, které jsem pˇri vypracování používal nebo z nich cˇ erpal, v práci rˇ ádnˇe cituji s uvedením úplného odkazu na pˇríslušný zdroj.
Jakub Foltas
Vedoucí práce: RNDr. Miloš Jakubíˇcek ii
Podˇekování Chtˇel bych podˇekovat vedoucímu mé bakaláˇrské práce RNDr. Miloši Jakubíˇckovi za odborné vedení, cenné rady a trpˇelivost, kterou se mnou mˇel. Také bych rád podˇekoval své rodinˇe a pˇrátelum ˚ za podporu, kterou mi v dobˇe psaní bakaláˇrské práce poskytovali.
iii
Shrnutí Bakaláˇrská práce se zabývá porovnáním volnˇe dostupných bezeztrátových komprimaˇcních programu˚ na textových korpusech. Hlavním cílem výzkumu bylo najít vhodný komprimaˇcní program, který by nahradil souˇcasnˇe používaný program XZ v Laboratoˇri pro zpracování pˇrirozeného jazyka pˇri Masarykovˇe univerzitˇe. Testování na dvou odlišných textových korpusech se podrobilo celkem dvacet volnˇe dostupných komprimaˇcních programu. ˚ Primárním kritériem porovnání byla urˇcena velikost komprimace. Dále byla porovnávána doba bˇehu programu a programové vytížení pamˇeti. Dalším pˇredmˇetem zkoumání byly úˇcinky pˇredzpracování korpusu˚ pˇred samotnou komprimací testovanými programy. Tˇri programy dokázaly korektnˇe zkomprimovat oba zadané korpusy a významnˇe pˇredˇcily souˇcasnˇe používaný program XZ. Nejlepších výsledku˚ dosáhly programy 7-Zip a NanoZip, které pˇrekonaly program XZ ve velikosti komprimace i spotˇrebovaném cˇ ase. Experimenty s pˇredzpracováním korpusu˚ neprokázaly efektivitu.
iv
Klíˇcová slova komprimace, komprese, textový korpus, kompresní pomˇer, UNIX, Linux, komprimaˇcní program, komprimaˇcní algoritmus, slovníková komprimace, LZMA, PPM, BWT, CM, XZ, Zip, 7-Zip, Gzip, Bzip2, NanoZip, DURILCA, paq9a
v
Obsah 1
2
Komprimace dat . . . . . . . . . . . . . . . . . . . . . . 1.1 Ztrátová a bezeztrátová komprimace . . . . . . . . 1.2 Kódování . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Shannon–Fanovo kódování . . . . . . . . . 1.2.2 Huffmanovo kódování . . . . . . . . . . . . 1.2.3 Numerické kódy . . . . . . . . . . . . . . . Golombovy a Riceovy kódy . . . . . . . . Kódy s extra bity . . . . . . . . . . . . . . . 1.2.4 Aritmetické kódování . . . . . . . . . . . . 1.3 Modelování . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Model s pevným uspoˇrádáním . . . . . . . Model pˇrímého kontextu . . . . . . . . . . Model nepˇrímého kontextu . . . . . . . . . 1.3.2 Model s variabilním uspoˇrádáním . . . . . Pˇredpovˇed’ podle cˇ ásteˇcné shody (PPM) . Dynamické Markovovo kódování (DMC) Vážení kontextového stromu (CTW) . . . 1.3.3 Míchání kontextu˚ (CM) . . . . . . . . . . . 1.4 Transformace . . . . . . . . . . . . . . . . . . . . . 1.4.1 Kódování dlouhých bˇehu˚ (RLE) . . . . . . 1.4.2 Slovníkový pˇrístup . . . . . . . . . . . . . . LZ77 . . . . . . . . . . . . . . . . . . . . . . Deflate . . . . . . . . . . . . . . . . . . . . . LZSS . . . . . . . . . . . . . . . . . . . . . . ROLZ . . . . . . . . . . . . . . . . . . . . . LZP . . . . . . . . . . . . . . . . . . . . . . LZMA . . . . . . . . . . . . . . . . . . . . . LZ78 . . . . . . . . . . . . . . . . . . . . . . LZW . . . . . . . . . . . . . . . . . . . . . . 1.4.3 Posun dopˇredu (MTF) . . . . . . . . . . . . 1.4.4 Burrows–Wheelerova transformace (BWT) Metodika porovnávání . . . . . . . . . . . . . . . . . . . 2.1 Základní testování programu˚ . . . . . . . . . . . . 2.1.1 Formát získaných dat . . . . . . . . . . . . 2.2 Pokroˇcilé testování programu˚ . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 5 5 6 7 8 8 9 9 10 12 12 12 12 13 13 14 14 14 15 15 16 16 17 17 17 17 18 18 18 19 20 20 21 23 1
2.3
Komprimovaná data . . . . . . . . . . . . . . . . . 2.3.1 DESAM . . . . . . . . . . . . . . . . . . . . 2.3.2 Czes2 . . . . . . . . . . . . . . . . . . . . . . 2.4 Použitý Hardware . . . . . . . . . . . . . . . . . . . 3 Testované programy . . . . . . . . . . . . . . . . . . . . 3.1 BBB . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 BZip2 . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 comprolz . . . . . . . . . . . . . . . . . . . . . . . . 3.4 comprox . . . . . . . . . . . . . . . . . . . . . . . . 3.5 crook . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 ctw . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 DURILCA . . . . . . . . . . . . . . . . . . . . . . . 3.8 fpaq3d . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Gzip . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 lpaq . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 lrzip . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Lzip . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 LZPXj . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14 NanoZip . . . . . . . . . . . . . . . . . . . . . . . . 3.15 Ocamyd . . . . . . . . . . . . . . . . . . . . . . . . 3.16 paq9a . . . . . . . . . . . . . . . . . . . . . . . . . . 3.17 TinyCM . . . . . . . . . . . . . . . . . . . . . . . . . 3.18 XZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.19 Zip . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.20 7-Zip . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Výsledky . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Základní testování programu˚ na korpusu DESAM 4.2 Základní testování programu˚ na korpusu Czes2 . 4.3 Pokroˇcilé testování programu˚ . . . . . . . . . . . . 4.3.1 Komprimace po cˇ ástech . . . . . . . . . . . 4.3.2 Komprimace po cˇ ástech se slovníkem . . . Varianta I . . . . . . . . . . . . . . . . . . . Varianta II . . . . . . . . . . . . . . . . . . . Varianta III . . . . . . . . . . . . . . . . . . 5 Závˇer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A Obsah CD . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24 24 25 25 26 26 27 28 28 29 30 31 32 33 34 34 35 36 36 38 39 40 41 42 43 45 45 47 48 48 50 50 51 52 53 59
2
Úvod Komprimace (též komprese) dat se používá pro zmenšení poˇctu bitu, ˚ reprezentujících datový objekt. V podstatˇe se komprimaˇcní algoritmy snaží o vytvoˇrení kompaktnˇejší verze zakódovaných dat, což se využívá zejména pˇri archivaci nebo pˇrenosu dat. Na základˇe výsledných dat rozlišujeme dva základní typy komprimace, komprimaci ztrátovou a bezeztrátovou. Ztrátová komprimace bývá typicky velice úsporná, co se týˇce velikosti zkomprimovaných dat, ovšem pˇri komprimaci jsou nˇekterá data nenávratnˇe odstranˇena. Ztrátová komprimace se obvykle hodí pro data reprezentující hudbu nebo video. Oproti tomu komprimace bezeztrátová vytvoˇrí datový soubor, ze kterého mužeme ˚ opˇet zrekonstruovat puvodní ˚ data. Proto je bezeztrátová komprimace ménˇe úˇcinná, ale má velké použití všude, kde by ztráta informace mohla znamenat poškození celého souboru [1]. Bakaláˇrská práce se zabývá komprimací textových korpusu. ˚ Jazykové korpusy jsou rozsáhlé soubory textu, ˚ které bývají oznaˇckovány pomocí jazyka XML nebo staršího SGML. Metajazykové znaˇcky použité v textu popisují ruzné ˚ vlastnosti textu. Uvádˇejí napˇríklad autora, rok vydání, nakladatelství apod. U každého slova navíc urcˇ ují jeho slovní druh a další lingvistické a statisticky zajímavé informace. Jazykové korpusy jsou typicky uložené ve formˇe vertikálního textu. Bakaláˇrská práce je zamˇerˇ ena na korpusy formátované do sloupcu˚ oddˇelených tabulátorem, pˇriˇcemž v prvním sloupci najdeme samotný text a v dalších sloupcích jsou obsaženy metajazykové znaˇcky. Zadavatelem bakaláˇrské práce je Laboratoˇr pro zpracování pˇrirozeného jazyka pˇri Masarykovˇe univerzitˇe. V souˇcasnosti veškerá práce probíhá na strojích s operaˇcními systémy UNIX. Pro archivaci textových korpusu˚ se nyní používá volnˇe dostupný komprimaˇcní program XZ. Cílem této bakaláˇrské práce je porovnat dostupné komprimaˇcní programy na vzorku textového korpusu a najít takový, který pˇredˇcí souˇcasnˇe využívaný program XZ. Testované komprimaˇcní programy musí fungovat na strojích s operaˇcním systémem typu UNIX a být volnˇe šiˇritelné. Zejména pujde ˚ o programy bezeztrátové, nebot’ ztráta dat je v tomto pˇrípadˇe nežádoucí. Testované algoritmy jsou porovnávány podle tˇrí kritérií. Primárním cílem je zmenšení 3
objemu dat, proto prvním kritériem porovnávání je tzv. kompresní pomˇer. Kompresní pomˇer udává pomˇer velikosti výstupních dat ku velikosti vstupních dat [2]. Další použitá kritéria porovnání testovaných algoritmu˚ jsou cˇ as potˇrebný pro vykonání komprimace a nakonec vytížení pamˇeti stroje po dobu bˇehu komprimace. Pro dosažení objektivního porovnání testovaných algoritmu˚ byl použit shellový skript operaˇcního systému UNIX, který má za úkol spustit na testovacím korpusu daný algoritmus a po jeho dokonˇcení vypsat výsledná kritéria porovnávání. Ještˇe pˇred ukonˇcením skript své výsledky zapíše do výstupního souboru, ze kterého je cˇ erpáno pˇri sestavování tabulek efektivity testovaných programu. ˚ Pro zjištˇení, zda se komprimaˇcní programy chovají ruznˇ ˚ e na vˇetším poˇctu menších souboru˚ a menším poˇctu vˇetších souboru, ˚ byl vytvoˇren další skript, který slouží k rozdˇelení textového korpusu. Na rozdˇeleném korpusu byla provedena testování komprimaˇcních programu. ˚ Na závˇer došlo i k testování programu˚ na rozdˇelených korpusech pˇredzpracovaných pomocí slovníkového algoritmu. Ze všech dvaceti testovaných programu˚ dokázaly tˇri testované programy korektnˇe zkomprimovat dva testované korpusy a zárovenˇ významnˇe pˇredˇcit souˇcasnˇe používaný program XZ. Zatímco program paq9a dosáhl nejlepšího výsledku z hlediska výsledné velikosti, ale horšího cˇ asu. Programy 7-Zip a NanoZip se v testu jevily nˇekolikanásobnˇe rychlejší a zárovenˇ také docílily lepšího kompresního pomˇeru. Experimenty s dˇelením a následným pˇredzpracováním textového korpusu neprokázaly efektivitu ani z hlediska výsledné komprimace, ani délky bˇehu programu.
4
1 Komprimace dat Komprimace (též komprese) dat se používá pro zmenšení poˇctu bitu˚ reprezentujících datový objekt. To obvykle zahrnuje problém najít a odstranit redundantní data z puvodního ˚ souboru. V podstatˇe se komprimaˇcní programy snaží o vytvoˇrení kompaktnˇejší verze zakódovaných dat, což se používá zejména pˇri archivaci nebo pˇrenosu dat. Opakem komprimace dat je datová dekomprimace, pˇri které se zakódovaná data dekódují do výsledné podoby. Na základˇe výsledných dat rozlišujeme dva základní typy komprimace, komprimaci ztrátovou a bezeztrátovou. [2]
1.1
Ztrátová a bezeztrátová komprimace
Ztrátová komprimace bývá typicky velice úsporná, co se týˇce velikosti zkomprimovaných dat, ovšem pˇri komprimaci jsou cˇ ásti dat zámˇernˇe odstranˇeny. Ztrátová komprimace se typicky používá pro data reprezentující hudbu nebo video. Oproti tomu komprimace bezeztrátová vytvoˇrí datový soubor, ze kterého mužeme ˚ opˇet zrekonstruovat puvodní ˚ data. Z tohoto duvodu ˚ není bezeztrátová komprimace tak úˇcinná, ale má velké použití všude, kde by ztráta informace mohla zpusobit ˚ klíˇcovou chybu, napˇr. pro komprimaci textu. ˚ Pˇredstavme si vˇetu „K útoku dojde v 17:35.“, pak zˇrejmˇe ztrátou byt’ jediného bytu, muže ˚ dojít ke zmˇenˇe významu sdílené informace. Po ztrátˇe bytu muže ˚ vˇeta vypadat napˇríklad takto: „K útoku dojde v 7:35.“ [1].
1.2
Kódování
„Kódování se provádí pˇriˇrazením rˇ etˇezce bitu˚ symbolum ˚ tak, aby rˇ etˇezec bitu˚ byl jednoznaˇcnˇe dekódovatelný do puvodních ˚ dat.“ [3] Claude Shannon a Warren Weaver ve své knize dokazují, že symbolu s pravdˇepodobností výskytu p lze nejlépe pˇriˇradit kód délky log2 p1 bitu. ˚ [4] Nejmenší délka kódu je tedy závislá na pravdˇepodobnostech výskytu daných symbolu, ˚ a to se snižující se pravdˇepodobností se délka kódu zvyšuje. 5
1. K OMPRIMACE DAT Shannon definoval oˇcekávaný obsah informace neboli dvojsmyslnost (nyní cˇ astˇeji nazývanou entropie) náhodné promˇenné X jako její oˇcekávanou délku kódu. Za pˇredpokladu, že X nabývá hodnot X1 , X2 , . . . , Xn a pro každou hodnotu Xi existuje pravdˇepodobnost výskytu p(i), pak entropie X je H(X) =
Xn i=1
p(i) log2
1 p(i)
Entropie zastává svuj ˚ význam míry neurˇcitosti, zárovenˇ jde o dolní hranici míry komprese. Existují efektivní kódovací metody, mezi nˇež patˇrí napˇríklad aritmetické kódování a lze je použít pro praktické pˇríklady, kde je možné vypoˇcítat entropii dat. Na druhou stranu je duležité ˚ si uvˇedomit, že entropii mužeme ˚ vypoˇcítat pouze pro známá pravdˇepodobnostní rozdˇelení. Ovšem pro naprosto obecná data nemužeme ˚ snadno urˇcit matematický model dat. [3] 1.2.1 Shannon–Fanovo kódování Shannon–Fanovo kódování vyvinuli roku 1949 zároven, ˇ nezávisle na sobˇe, C. Shannon [5] a R. M. Fano [6]. Kódování symbolu˚ je provádˇeno na základˇe cˇ etnosti výskytu symbolu˚ ve zdrojových datech. Symboly s cˇ etnˇejším výskytem jsou kódovány pomocí kratších kódu˚ a obrácenˇe. Algoritmus vypadá následovnˇe: 1.
Vytvoˇr tabulku cˇ etností nebo pravdˇepodobností symbolu˚ pro seznam zdrojových symbolu. ˚
2.
Seˇrad’ tabulku podle cˇ etnosti sestupnˇe.
3.
Rozdˇel tabulku na dvˇe cˇ ásti, aby obˇe cˇ ásti obsahovaly co nejblíže stejný souˇcet cˇ etností symbolu. ˚
4.
Horní cˇ ásti tabulky pˇriˇrad’ binární cˇ íslici 0 a dolní binární cˇ íslici 1.
5.
Rekurzivnˇe aplikuj 3. a 4. krok na obˇe takto vzniklé cˇ ásti tabulky podrozdˇelováním tabulky a pˇridáváním bitu˚ kódum, ˚ dokud se každý symbol nestane odpovídajícím listem binárního stromu. 6
1. K OMPRIMACE DAT Shannon–Fanovo kódování obecnˇe nezaruˇcuje vytvoˇrení optimálního kódu. Efektivita kódu se zvyšuje, pokud se pravdˇepodobnosti výskytu symbolu˚ blíží mocninám 12 . [7] 1.2.2 Huffmanovo kódování Huffmanovo kódování popsal v roce 1952 David Huffman [8]. Jde o úspˇešnou metodu, puvodnˇ ˚ e urˇcenou pro komprimaci textu. V jakémkoli textu se nˇekterá písmena vyskytují daleko cˇ astˇeji než jiná. Základní myšlenkou Huffmanova kódování je použití kratších kódových slov pro symboly s cˇ astˇejším výskytem a delších kódových slov pro ménˇe používané symboly namísto obvyklého kódování s pevnou délkou kódových slov, jakým je napˇríklad 8bitové rozšíˇrené ASCII kódování. [2] Huffmanovo kódování se pˇríliš neliší od Shannon–Fanova kódování. Oba algoritmy nejdˇríve vytváˇrí tabulky pravdˇepodobností cˇ i cˇ etností výskytu symbolu˚ ve zdrojových datech. Rozdílem je právˇe následná tvorba binárního stromu, kdy Shannon–Fanovo kódování tvoˇrí strom shora dolu, ˚ zatímco Huffmanovo kódování zespoda nahoru. Huffmanovo kódování je dobˇre popsáno právˇe tvorbou binárního stromu: 1.
Mˇej seznam volných uzlu, ˚ kde každý uzel odpovídá symbolu z dané abecedy.
2.
Vyber ze seznamu dva uzly s nejmenší vahou.
3.
Tˇemto dvˇema uzlum ˚ vytvoˇr pˇredka s vahou rovnou souˇctu vah jeho synu. ˚
4.
Ze seznamu volných uzlu˚ odeber oba syny a pˇridej pˇredka.
5.
Opakuj tento proces od 2. kroku dokud není vytvoˇren jediný strom.
Po vytvoˇrení binárního stromu algoritmus pˇriˇradí symbolum ˚ kódy tak, že prochází strom od koˇrene po daný uzel, levým vˇetvím pˇriˇrazuje hodnoty 0 a pravým hodnoty 1. Tímto postupem vznikne prefixový kód. [7] 7
1. K OMPRIMACE DAT Huffmanovo kódování je v praxi neefektivní, protože délky kódu˚ v bitech musí být zaokrouhleny na celé cˇ íslo. Pokud pravdˇepodobnost výskytu symbolu není mocninou 12 , pak není pˇriˇrazení kódu˚ optimální. Tato neefektivita kódování je odstranitelná pˇriˇrazováním pravdˇepodobnosti výskytu delším skupinám symbolu, ˚ ale pouze za cenu exponencionálního zvýšení velikosti abecedy, a tedy i cˇ asu bˇehu algoritmu. [3] Pokud mluvíme-li o kódování s optimálním pˇrirˇ azením kódu, ˚ jde o optimální Huffmanovo kódování. Pracujeme-li s delšími skupinami symbolu, ˚ odkazujeme se obvykle na tzv. rozšírˇ ené Huffmanovo kódování. [1] 1.2.3 Numerické kódy Výraz Numerické kódy oznaˇcuje Huffmanovy kódy pro cˇ ísla s bˇežným pravdˇepodobnostním rozdˇelením. Jako takové se objevují napˇr. v kódování predikce chyb, grafiky, zvuku nebo pro RLE1 u vysoce redundantních dat. Numerické kódy mají obvykle jednodušší popisnou strukturu než celá Huffmanova tabulka kódu. ˚ [3] Golombovy a Riceovy kódy Golombuv ˚ a Riceuv ˚ kód se soustˇredí na kódování celých cˇ ísel a pracují s pˇredpokladem, že cˇ ím je cˇ íslo vˇetší, tím menší je jeho pravdˇepodobnost výskytu. Nejjednodušším pˇríkladem takového kódu je unární kód. Unární kód kladného celého cˇ ísla n je právˇe n jedniˇcek a jedna nula. Tedy napˇr. cˇ íslo 4 by bylo pomocí unárního kódu zakódováno jako 11110. Mluvíme-li o Golombovˇe kódu, jde ve skuteˇcnosti o celou rodinu kódu˚ parametrizovatelnou pomocí celého cˇ ísla m > 0. Golombuv ˚ kód s parametrem m pˇredstavuje celé cˇ íslo n > 0 pomocí cˇ ísel q a r, kde q je výsledek po dˇelení beze zbytku cˇ ísla n parametˇ rem m a r je zbytkem tohoto dˇelení. Císlo q je následnˇe zakódováno unárnˇe a cˇ íslo r binárnˇe. [2] Pokud jako parametr m zvolíme triviálnˇe cˇ íslo 1, dostaneme samotný unární kód. Unární kód tak odpovídá pravdˇepodobnostnímu 1 . Zvolíme-li parametr m jako mocninu rozdˇelení, kde P (n) = 2n+1 1. Run Length Encoding – jde o cˇ asto používanou transformaci kódu, více v podkapitole Tranformace
8
1. K OMPRIMACE DAT cˇ ísla 2, dostáváme tzv. Riceuv ˚ kód. U Riceových kódu˚ je zbytek r kódován pomocí log2 m bitu, ˚ v ostatních pˇrípadech jsou menší zbytky kódovány pomocí spodní celé cˇ ásti log2 m bitu˚ a vˇetší zbytky pomocí horní celé cˇ ásti log2 m bitu. ˚ Délka Golombova kódu s parametrem m se prodlužuje o 1 bit pro každých m kódovaných hodnot. Což se blíží ke geometrickému pravdˇepodobnostnímu rozdˇelení, kde n má pravdˇepodobnost výskytu pˇribližnˇe P (n) = 1mn . [3] 2
Kódy s extra bity Kódy s extra bity používají Huffmanovo kódování pro zakódování rozsahu cˇ ísel. Konkrétní hodnotu v daném rozsahu poté kódují binárnˇe (jde o tzv. extra bity). Toto kódování se využívá pro aproximaci jakéhokoli pravdˇepodobnostního rozdˇelení, které se pˇribližnˇe plynule mˇení. Kódování využívají napˇr. programy Zip a Gzip v algoritmu Deflate. [3] 1.2.4 Aritmetické kódování Aritmetické kódování se stalo nejúspˇešnˇejší alternativou Huffmanova kódování. Algoritmus vychází z práce Eliase, z velké cˇ ásti jej pozdˇeji rozvinuli Pasco, Risanene a Langdon. Aritmetické kódování je výkonnostnˇe lepší než Huffmanovo, a to pˇredevším pro texty s menšími abecedami. Oproti Huffmanovu kódování obchází myšlenku kódovat každý jednotlivý symbol kódovým slovem. Aritmetické kódování kóduje proud vstupních symbolu˚ pomocí jediného zlomku jako komprimovaného výstupu. [2] Aritmetické kódování pracuje na intervalu (0, 0; 1, 0). Tento interval je dále rozdˇelen na menší intervaly pro každý symbol vstupní abecedy, a to podle pravdˇepodobnosti jejich výskytu ve zdrojových datech. Po naˇctení prvního symbolu pˇri kódování je interval odpovídající danému symbolu opˇet rozdˇelen stejným zpusobem ˚ na stále menší intervaly. Takto algoritmus pokraˇcuje pro každý naˇctený symbol, dokud neprojde celý vstupní proud symbolu. ˚ Poslední interval vzniklý tímto zpusobem ˚ jedineˇcnˇe urˇcuje proud vstupních dat, která jsou následnˇe zakódována pomocí jakéhokoli zlomku z tohoto intervalu. Zlomek je ukládán ve tvaru desetinného cˇ ísla s plovoucí cˇ árkou. [7] 9
1. K OMPRIMACE DAT Mˇejme abecedu vstupních symbolu˚ A = {a1 , a2 , a3 } s pravdˇepodobnostmi výskytu P (a1 ) = 0, 7, P (a2 ) = 0, 1 a P (a3 ) = 0, 2. Pro vstupní proud symbolu˚ a1 a2 a3 dˇelíme interval jako na Obrázku 1.1. Jakékoliv cˇ íslo z intervalu (0, 5460; 0, 5558) je tedy kódem vstupních symbolu˚ a1 a2 a3 a1 , cˇ ísla z intervalu (0, 5558; 0, 5572) odpovídají vstupnímu proudu a1 a2 a3 a2 apod. [1] Obrázek 1.1: Dˇelení intervalu pro vstupní proud symbolu˚ a1 a2 a3 . [1]
Velká cˇ ást moderních komprimaˇcních programu˚ používá právˇe aritmetické kódování. Vˇetšina bˇežných programu˚ s aritmetickými kodéry kóduje data po jednom bytu (typické pro modelování pomocí PPM2 ) nebo po jednom bitu (typické pro modelování pomocí CM3 nebo DMC4 ). [3]
1.3
Modelování
Vytvoˇrení matematického modelu je esenciální cˇ ástí komprimaˇcního programu. Dobrý matematický model obvykle vede k dobrému vý2. 3. 4.
Prediction by Partial Match – více v cˇ ásti modelování Context Mixing – více v cˇ ásti modelování Dynamic Markov Coding – více v cˇ ásti modelování
10
1. K OMPRIMACE DAT sledku komprimaˇcního programu. Jde o popis komprimovaných dat pomocí matematických výrazu. ˚ V podstatˇe pˇredstavuje všechny informace, které komprimaˇcní program o datech nashromáždí. Koncovým výsledkem modelování by mˇel být proveditelný model, podle kterého komprimaˇcní algoritmus zakóduje zdrojová data do komprimované verze. Bˇežnˇe používané modely se dají rozdˇelit podle toho, jak pˇristupují k datum, ˚ do následujících kategorií: 1.
Fyzikální model – k popisu dat používá pˇrímou znalost zdrojových dat, jako je napˇríklad zpusob ˚ generování nˇekterých dat nebo empirická pozorování.
2.
Pravdˇepodobnostní model – k modelování dat používá pravdˇepodobnostní teorii.
3.
Markovuv ˚ model – používá pro popis dat teorii Markovových rˇ etˇezcu. ˚
4.
Složený model – pro modelování používá kombinaci ruzných ˚ pˇrístupu˚ a pˇrepínaˇc, pomocí kterého v daný cˇ asový okamžik aktivuje právˇe jeden z použitých pˇrístupu. ˚
Neexistuje obecný model vhodný pro všechna data. Pro ruzné ˚ problémy se hodí ruzné ˚ pˇrístupy matematického modelování, a to je pˇredmˇetem dalšího bádání v okruhu komprimace dat. [2] Matt Mahoney ve své knize [3] tvrdí, že jakmile získáme matematický model, kódování už je vyˇrešeným problémem. Ale jak dokázal ve své práci Three approaches to the quantitative definition of information A. Kolmogorov [9], neexistuje algoritmus pro nalezení nejlepšího modelu. Dále Mahoney modely dˇelí na statické a dynamické, pˇriˇcemž za nejlepší považuje kombinaci dynamických modelu˚ a aritmetického kódování. U statických modelu˚ kompresor programu analyzuje vstupní data, vytvoˇrí pravdˇepodobnostní rozložení pro zadané symboly a tato data posílá dekompresoru spoleˇcnˇe se zakódovanými symboly. Kompresor i dekompresor tedy používají pro pˇriˇrazení kódových slov stejný algoritmus. Statické modely se obvykle používají spoleˇcnˇe s Huffmanovým kódováním. U dynamických modelu˚ využívá 11
1. K OMPRIMACE DAT kompresor poslední cˇ tená data jako základ pro vytvoˇrení pravdˇepodobnostního rozdˇelení (pˇredpovˇed’) následujícího symbolu bez toho, aniž by daný symbol cˇ etl. Poté pˇredá kodéru pˇredpovˇed’ spoleˇcnˇe s cˇ teným symbolem a aktualizuje model. Podobnˇe probíhá i dekomprimace. [3] 1.3.1 Model s pevným uspoˇrádáním (Fixed order model) Model pˇrímého kontextu (Direct context model) Tento model patˇrí k nejjednodušším z dynamických modelu. ˚ Tzv. order n model používá posledních n cˇ tených bytu˚ nebo symbolu˚ (kontext), ty uloží do tabulky a vytvoˇrí pravdˇepodobnostní model pro následující symbol. Dalším krokem je fáze aktualizace modelu, kdy se odhalí následující symbol, a podle nˇej se upraví tabulka pravdˇepodobností pro další výskyt stejného kontextu. Podle užitého kontextu rozlišujeme takové modely na bytové (bytewise) a bitové (bitwise). Bytové modely obvykle používají jako kontext pˇredcházející symboly, zatímco bitové modely pˇredešlé bity právˇe kódovaného bitu. Zjevnˇe triviálním modelem je order 0 model, který nepoužívá žádný kontext. [3] Model nepˇrímého kontextu (Indirect context model) Model nepˇrímého kontextu nevyužívá pouze kontextu pro pˇriˇrazení pravdˇepodobnosti následujícímu symbolu, místo toho používá dvˇe tabulky. V první tabulce pˇriˇrazuje kontext bitové historii, stavu reprezentujícímu poslední cˇ tené bity. V druhé tabulce pˇriˇradí bitové historii pˇredpovˇed’, stejnˇe jako model pˇrímého kontextu. [3] 1.3.2 Model s variabilním uspoˇrádáním (Variable order model) Modely s ruzným ˚ uspoˇrádáním vˇetšinou vykazují lepší komprimaci s delšími kontexty, ale pouze do urˇcité meze. Za touto mezí dochází ke zhoršení kvality komprimace, nebot’ velké množství kontextu˚ je unikátních, a proto pro nˇe nemuže ˚ být vykonána pˇredpovˇed’. Modely s ruzným ˚ uspoˇrádáním proto zaznamenávají statistiku pro více ruzných ˚ uspoˇrádání a poté použijí nejdelší odpovídající záznam, ke 12
1. K OMPRIMACE DAT kterému znají pˇredpovˇed’. Mezi modely s ruzným ˚ uspoˇrádáním patˇrí napˇríklad PPM, který tvoˇrí uspoˇrádání na úrovni bytu, ˚ a DMC s uspoˇrádáním na úrovni bitu. ˚ [3]
Pˇredpovˇed’ podle cˇ ásteˇcné shody (PPM) Algoritmus PPM5 publikovali roku 1984 J. Cleary a I. Witten. V této dobˇe jej pˇredˇcily velice populární algoritmy založené na práci Abrahama Lempela a Jacoba Ziva tzv. Lempel–Ziv algoritmy. Pozdˇeji se vyvinuly efektivnˇejší verze tohoto algoritmu a ukázalo se, že jsou dostateˇcnˇe úˇcinné. Problémem algoritmu PPM bylo použití velkého kontextu, což vyžadovalo ukládání obrovského množství pravdˇepodobnostních záznamu. ˚ Namísto ukládání všech záznamu˚ dopˇredu se pˇristoupilo k dynamiˇctˇejšímu rˇ ešení ukládat pouze záznamy právˇe kódované sekvence symbolu, ˚ což vedlo k úspˇechu. [1] PPM používá ruzné ˚ metody pro stanovení tzv. escape probability, tedy pravdˇepodobnosti urˇcené symbolu, se kterým se program ještˇe v daném kontextu nesetkal. Jednou z tˇechto metod je metoda známá jako Secondary escape estimation (SEE). Tuto metodu ještˇe vylepšil v roce 2002 Dmitry Shkarin pod názvem PPMD. Tento zpu˚ sob komprimace používají napˇr. nˇekteré volnˇe dostupné programy jako 7-Zip a DURILCA nebo komerˇcní programy jako je WinZip a WinRAR. [3]
Dynamické Markovovo kódování (DMC) DMC6 popsal roku 1987 G. Cormack spoleˇcnˇe s N. Horspoolem [10]. Oproti schématu PPM, které se používá zejména ke komprimaci textových dat, DMC používá širší rámec využití možných vztahu˚ a korelací, a to ve smyslu rozšíˇrení kontextu dále než na úrovni jednoho symbolu [1]. DMC je implementováno napˇr. v komprimaˇcním programu Ocamyd [3].
5. 6.
v angliˇctinˇe prediction by partial match v angliˇctinˇe dynamic Markov coding
13
1. K OMPRIMACE DAT Vážení kontextového stromu (CTW) Metoda CTW7 podobnˇe jako DMC kóduje zdrojová data po jednotlivých bitech. Ke vstupním datum ˚ se chová jako k rˇ etˇezcum ˚ bitu. ˚ Pro výpoˇcet pravdˇepodobnosti právˇe kódovaného bitu používá metoda kontextový strom o hloubce stromu rovné velikosti použitého kontextu. Vypoˇcítaná pravdˇepodobnost spoleˇcnˇe s hodnotou bitu je následnˇe kódována pomocí aritmetického kódování, zatímco kontext je kódován bez další komprimace. [11] 1.3.3 Míchání kontextu˚ (CM) Metoda míchání kontextu˚ 8 je zastoupena mezi komprimaˇcními programy zejména rˇ adou programu˚ PAQ. Nutno podotknout, že tyto programy dosahují mnohdy na ruzných ˚ datech velice dobrého kompresního pomˇeru, ovšem jejich bˇeh trvá daleko delší dobu. Metoda míchání kontextu˚ udržuje nˇekolik ruzných ˚ kontextu˚ najednou a urcˇ uje pravdˇepodobnost symbolu zkombinováním pravdˇepodobností urˇcených pomocí všech kontextu. ˚ Takto kombinovaná pravdˇepodobnost je mnohdy daleko pˇresnˇejší a efektivnˇejší než všechny kontexty použité k její kombinaci samostatnˇe. Ke zkombinování více kontextu˚ se v souˇcasné dobˇe cˇ asto používají metody lineárního míchání (Linear mixing), logistického míchání (Logistic mixing), pˇrímého a nepˇrímého urˇcení druhého symbolu (Direct/Indirect Secondary symbol estimation) cˇ i modelu shody (Match model). [3]
1.4
Transformace
Transformace vstupních dat se provádí typicky pˇred modelováním a kódováním dat. Smyslem transformace je konvertovat vstupní data do sekvence symbolu, ˚ která jde dále jednodušeji cˇ i rychleji modelovat. Transformace je obvykle následována nˇejakou z forem modelování a kódování. V ideálním pˇrípadˇe by mˇela transformace být bi7. 8.
v angliˇctinˇe context-tree weighting v angliˇctinˇe context mixing
14
1. K OMPRIMACE DAT jekcí9 , mnohem cˇ astˇeji je však injektivní a surjektivní10 . [3] 1.4.1 Kódování dlouhých bˇehu˚ (RLE) Transformace RLE11 nahrazuje série opakujících se stejných symbolu˚ (tzv. bˇehu˚ (runs)) poˇctem opakování a daným symbolem. Tyto bˇehy jsou následnˇe transformovány do n-tic (run-flag, run-length, runsymbol), kde první hodnota udává, zda se jedná o bˇeh cˇ i nikoliv, dále délku bˇehu a opakovaný symbol. Napˇríklad rˇ etˇezec „FFFFFFF“ je bˇeh délky 7 symbolu F a po transformaci dostáváme trojici (r,7,F) nebo zkrácenˇe r7F. RLE se používá jak na bitové úrovni, tak na úrovni bytu. ˚ [2] 1.4.2 Slovníkový pˇrístup Slovníkový pˇrístup využívá faktu, že u vstupních dat se cˇ asto opakují shodné vzorky dat. Zejména u dat textových se nˇekterá slova (vzorky) opakují velice cˇ asto, a naopak nˇekterá slova se objevují velice vzácnˇe. Program si tedy udržuje seznam nebo slovník cˇ asto se objevujících vzorku˚ dat, a když opakovanˇe narazí na tyto vzorky, zakóduje je pomocí odkazu na udržovaný slovník. Pokud narazí na výraz, který ve slovníku není, výraz je zakódován pomocí jiné, ménˇe efektivní metody. Aby byla tato technika dostateˇcnˇe úˇcinná, je dule˚ žité, aby poˇcet cˇ asto používaných vzorku˚ (a tedy i velikost slovníku cˇ asto používaných vzorku) ˚ byl daleko menší než všechny vzorky vstupních dat. [2] První variantou je využití statického slovníku. Tato metoda pˇredpokládá nˇejakou pˇredem danou znalost vstupních dat, podle kterých se vytvoˇrí statický slovník, který se v dobˇe bˇehu algoritmu již neupravuje. Tento pˇrístup však funguje pouze pro specifická data, pro která je obvykle navržen. Jedním z bˇežných pˇrístupu˚ se statickým slovníkem je tzv. Diagram coding. Druhou a mnohem cˇ astˇeji používanou metodou je použití adaptivního slovníku. Velké množství algoritmu˚ s adaptivním slovníkem vychází z algoritmu˚ LZ77 a LZ78, 9. Každá sada vstupních dat se konvertuje na právˇe jednu sekvenci symbolu. ˚ 10. Každá sada vstupních dat muže ˚ mít po konverzi více výstupních sekvencí symbolu, ˚ které jsou však zpˇetnˇe jednoznaˇcnˇe konvertovatelné do puvodní ˚ podoby. 11. v angliˇctinˇe run length encoding
15
1. K OMPRIMACE DAT v prvním pˇrípadˇe mluvíme o rodinˇe LZ77 (také známé jako LZ1), podobnˇe v druhém pˇrípadˇe se literatura cˇ asto odkazuje na rodinu LZ78 (nebo LZ2). [1] LZ77 Název algoritmu LZ77 pochází z iniciálu A. Lempela a J. Ziva, kteˇrí jej v roce 1977 publikovali ve své práci [12]. Algoritmu LZ77 se také pˇrezdívá „Klouzající Okno“, nebot’ se dá takto metaforicky dobˇre popsat. Pˇredstavme si vstupní data jako dlouhý rˇ etˇezec znaku, ˚ algoritmus udržuje jakési okno, pˇres které se na tento rˇ etˇezec dívá. Okno je rozdˇeleno horizontálnˇe na dvˇe cˇ ásti, tzv. search buffer12 a lookahead buffer. V levé cˇ ásti okna algoritmus udržuje sekvenci znaku, ˚ které už zpracoval a zakódoval. Tato cˇ ást je právˇe používaným slovníkem zmínˇeného algoritmu. V cˇ ásti s názvem look-ahead buffer se nacházejí znaky, které teprve budou zpracovány. Co se týˇce implementace, search buffer mívá velikost nˇekolik tisícu˚ bytu, ˚ zatímco look-ahead buffer pouze pár desítek bytu. ˚ [11] Jak algoritmus postupuje, okno se posouvá po rˇ etˇezci znaku˚ smˇerem doprava a tím se aktualizuje slovník i znaky cˇ ekající na zakódování. Pro první znak v cˇ ásti look-ahead buffer se algoritmus snaží naleznout shodu ve slovníku, pˇriˇcemž postupuje zprava doleva. Pokud dojde ke shodˇe, algoritmus porovná následující znaky v obou cˇ ástech okna ve snaze najít co nejdelší shodný rˇ etˇezec znaku. ˚ V daném smyslu algoritmus postupnˇe prohledá celý search buffer a nejdelší shodu zakóduje do trojic
. Offset znaˇcí vzdálenost shodnˇe nalezených znaku, ˚ length délku shodného vzorku a codeword kód samotného znaku. Codeword se využívá v pˇrípadech, kdy není nalezena žádná shoda, pak jsou první dvˇe hodnoty nulové a znak je tedy nahrazen pouze svým kódem. Nejvˇetší slabinou algoritmu LZ77 je vysoká neefektivita pˇri použití výše zmínˇené trojice . Jedním z rˇ ešení je použití úˇcinnˇejšího kódování. [1] Deflate Široce rozšíˇreným algoritmem používajícím algoritmus LZ77 je Deflate, který pro kódování trojic používá Huffmanuv ˚ kód. Algoritmus 12. V ruzné ˚ literatuˇre se mužeme ˚ setkat také s oznaˇcením history buffer.
16
1. K OMPRIMACE DAT Deflate nalezneme napˇr. u programu˚ Zip, Gzip a dalších. [3] Oznacˇ ení Deflate oznaˇcuje komprimaˇcní algoritmus, dekomprimaˇcním algoritmem k takto vytvoˇreným výstupním datum ˚ je algoritmus Inflate [13]. LZSS Algoritmus Lempel–Ziv–Storer–Szymanski vychází také z LZ77. Pro ušetˇrení nadbyteˇcného využívání trojic používá tzv. flag bit, který urˇcuje, zda je následný symbol kódován klasicky nebo s použitím shody ve slovníku (v tom pˇrípadˇe je následný symbol offset). [3] ROLZ Zkratka ROLZ znaˇcí reduced offset Lempel–Ziv a jde o další rozšírˇ ení algoritmu LZ77. Metoda ROLZ nahrazuje použití offsetu v trojici kódovacích hodnot pomocí ukazatelu˚ do hashovacích tabulek. Díky tomu dochází ke zkrácení délky kódovaného offsetu, na druhou stranu tato technika obˇcas pˇrehlédne nejlepší možnou shodnu rˇ etˇezcu. ˚ [14] LZP LZP popsal roku 1995 Charles Bloom [15]. Jde o extrémní verzi metody ROLZ, kdy každá hashovací tabulka obsahuje pouze jednu položku [14]. LZMA Algoritmus LZMA (Lempel–Ziv–Markov chain algorithm) je výchozí metodou komprimace programu 7-Zip a k jeho autorství se hlásí Igor Pavlov [16]. LZMA je taktéž rozšíˇrením algoritmu LZ77, efektivita komprimace je zvýšená díky využití delšího search bufferu (do velikosti až 4 GB). Vyvinuta je také efektivnˇejší syntaktická analýza, která umožnuje ˇ použití kratšího shodného rˇ etˇezce pro právˇe kódovaný symbol, v pˇrípadˇe, že to zaruˇcí delší shodný rˇ etˇezec dalšímu kódovanému symbolu, a tedy celkovˇe delší sekvenci shodných rˇ etˇezcu. ˚ Dále LZMA používá kratší kódy pro 3 nedávno použité nej17
1. K OMPRIMACE DAT cˇ astˇeji shodné rˇ etˇezce. Další použitou technikou je tzv. Literal exclusion after matches. [3] LZ78 Algoritmus LZ77 implicitnˇe pˇredpokládá, že shodné vzorky se seskupují dohromady v lokálních cˇ ástech vstupních dat. Což však znamená, že pokud se vzorky opakují po delších intervalech, než jaké je schopna zachytit délka „Klouzajícího okna“, algoritmus není schopen tyto shody rozpoznat. Algoritmus LZ78 proto rˇ eší tento problém nahrazením search bufferu a look-ahead bufferu explicitním slovníkem. [1] Slovník na zaˇcátku algoritmu obsahuje pouze prázdný rˇ etˇezec na pozici 0 a postupnˇe jsou do nˇej ukládány slova na cˇ íslované pozice. Algoritmus naˇcítá vstupní data a porovnává vstupní rˇ etˇezce se slovníkem ve snaze najít co nejdelší shodu. K té pak pˇridá následující symbol, tento rˇ etˇezec uloží na další pozici do slovníku a data zakóduje ve formátu dvojice , kde ukazatel urˇcuje shodný rˇ etˇezec ve slovníku a symbol zustává ˚ stejný. Typicky ve slovníku pˇribývají nejdˇríve krátké rˇ etˇezce a posléze cˇ ím dál tím delší. Velikost slovníku je omezená dostupnou pamˇetí anebo programovˇe. ˇ Cím je slovník vˇetší, tím více rˇ etˇezcu˚ a tedy potenciálních shod obsahuje, na druhou stranu ukazatele jsou také vˇetší a prohledávání slovníku pomalejší. [11] LZW Nejpoužívanˇejší verzí algoritmu LZ78 je bezpochyby metoda LZW, kterou používá napˇr. program compress nebo známé grafické komprimaˇcní programy GIF a TIFF. [3] 1.4.3 Posun dopˇredu (MTF) Metoda MTF13 oznaˇcovaná také jako hodnocení symbolu˚ (symbol ranking) je transformací, která udržuje abecedu symbolu˚ [3]. Algoritmus zaˇcíná s nˇejakou pˇredem definovanou abecedou, s nejfrekventovanˇejšími symboly na vrcholu (krátké kódy). Poté naˇcítá po13. v angliˇctinˇe move–to–front
18
1. K OMPRIMACE DAT stupnˇe symboly ze vstupu, pro každý symbol použije kód z abecedy a posune právˇe použité písmeno na vrchol. Tímto postupem se delší sekvence stejných symbolu˚ kódují jako sekvence nul, což muže ˚ být velice efektivní. [1] 1.4.4 Burrows–Wheelerova transformace (BWT) Algoritmus BWT pˇredstavili v roce 1994 M. Burrows a D.J. Wheeler [17]. Pokud pˇred komprimací seˇradíme vstupní textová data abecednˇe, zvýšíme rapidnˇe efektivitu následných komprimaˇcních metod. Problém této úvahy se však skrývá v nenávratnosti takové transformace, jakou je abecední seˇrazení. BWT však používá sérii kroku, ˚ po kterých získá transformovaná vstupní data s lepšími vlastnostmi pro další komprimaci. BWT potˇrebuje mít vstupní data již pˇredzpracovaná, což se obvykle provádí pomocí algoritmu RLE. Implementace tohoto algoritmu je vcelku jednoduchá, pˇri použití polí navíc algoritmus pracuje rychle. Po zpracování dat algoritmem RLE a BWT se obvykle následnˇe používá pro kvalitní komprimaci Huffmanovo kódování. [2] BWT se v literatuˇre oznaˇcuje také jako algoritmus kontextového rˇ azení (context sorting algorithm) nebo algoritmus blokového rˇ azení (block sorting algorithm). Ve skuteˇcnosti totiž BWT netransformuje celá vstupní data pohromadˇe, ale rozdˇelí je na bloky fixní velikosti, podle dostupné pamˇeti. Typickým programem používající algoritmus BWT je napˇr. Bzip2, který roku 1996 vyvinul J. Seward, nebo program bbb, který napsal roku 2006 M. Mahoney. [3]
19
2 Metodika porovnávání Velice podobný výzkum této bakaláˇrské práci provádí Matt Mahoney, který mˇerˇ í efektivitu komprimaˇcních programu˚ na anglických textech. Konkrétnˇe na souborech enwik8 a enwik9. Tyto soubory odpovídají prvním 108 respektive 109 bytum ˚ z textu anglické Wikipedie ze dne 3. 3. 2003. Text je oznaˇckován jazykem XML. Ve svém výzkumu nehledá nejlepší algoritmus, ale snaží se podnítit výzkum umˇelé inteligence a zpracování pˇrirozeného jazyka [14]. Zabývá se jak programy pro platformu UNIX, tak programy urˇcené pro operaˇcní systém Windows nebo Mac. Má bakaláˇrská práce se zabývá pouze volnˇe dostupnými programy pro platformu UNIX. Nicménˇe výše zmínˇený výzkum Matta Mahoneyho sloužil jako výchozí bod mého výzkumu, jak z hlediska metodiky, která však byla trochu pozmˇenˇena, tak z hlediska použitých programu. ˚
2.1
Základní testování programu˚
Prakticky všechny dostupné programy urˇcené ke komprimaci dat na poˇcítaˇcích s operaˇcním systémem typu UNIX jsou spustitelné pomocí shellu 1 . Pro efektivní práci s programy v shellu byly vytvoˇreny shellové skripty, který mají za úkol spustit vždy daný komprimaˇcní program na zadaných datech. Pomocí pˇríkazu time skript zmˇerˇ í cˇ as bˇehu programu a za pomocí parametru -f %M zmˇerˇ í také programem nejvyšší spotˇrebovanou operaˇcní pamˇet’[19]. Argumentem tohoto pˇríkazu je volání komprimaˇcního programu s urˇceným nastavením pro daný bˇeh. Stejným zpusobem ˚ skript mˇerˇ í i cˇ as a pamˇet’ pˇri následné dekomprimaci dat. Dekomprimovaná data poté porovná se vstupními, aby zajistil, že nedošlo k poškození puvodních ˚ dat. Skript zjistí velikosti puvodních ˚ a zkomprimovaných dat a na jejich základˇe vypoˇcte pˇríslušný kompresní pomˇer. Využití jednoho skriptu pro všechny programy se stalo cˇ asem velice nepraktické, z duvodu ˚ chybovosti a cˇ astých pˇrerušovaných bˇehu˚ programu. ˚ Proto má každý program svuj ˚ vlastní samostatný skript. Volání jednotlivých programu˚ se totiž liší poˇctem, pˇrípadnˇe poˇra1.
interpret pro vytvoˇrení standardního pˇríkazového rˇ ádku [18]
20
2. M ETODIKA POROVNÁVÁNÍ dím argumentu. ˚ Vˇetšina programu˚ cˇ te jako první argument vstupní soubor a jako druhý argument soubor výstupní nebo naopak. Tyto programy používají dvˇe totožné kostry skriptu, pouze s úpravou poˇradí použitých promˇenných. Nˇekteré programy, jako napˇríklad XZ, oˇcekávají pouze jeden argument, a to vstupní soubor. Jako výstupní soubor pak oznaˇcí vstupní soubor se svou specifickou pˇríponou determinující typ souboru, napˇr. .xz. V tˇechto pˇrípadech bylo nutné skript upravit o chybˇející pˇrípony pˇri práci se zkomprimovaným souborem. Všechny skripty použité pˇri tvorbˇe této práce jsou umístˇeny v pˇríloze. 2.1.1 Formát získaných dat Pomocí skriptu se takto získaná data zapíší do výstupního souboru do sloupcu˚ oddˇelených tabulátorem spoleˇcnˇe s dalšími informacemi. Data v takovém formátu byla zvolena z duvodu ˚ dalšího zpracování. Data byla následnˇe zpracována pomocí programu awk cˇ i sed pro úpravu formátu. Výsledná data formátovaná do tabulky jsou ilustrovaná na další stránce v tabulkách 2.1 a 2.2. Tabulka obsahuje tato data (v závorce jsou uvedeny zkratky vyskytující se v záhlavích tabulek): •
název volání programu (program),
•
zadané parametry (pˇríznak),
•
velikost dat pˇred komprimací (puv. ˚ velikost),
•
velikost dat po komprimaci (komp. velikost),
•
vypoˇcítaný kompresní pomˇer (komp. pomˇer),
•
cˇ as potˇrený ke komprimaci dat (ˇcas k.),
•
pamˇet’ potˇrebnou pro komprimaci dat (pamˇet’ k.),
•
násobek kompresního pomˇeru s cˇ asem komprimace (k. pomˇer × cˇ as k.),
•
cˇ as potˇrebný k dekomprimaci dat (ˇcas d.),
•
pamˇet’ potˇrebnou pro dekomprimaci dat (pamˇet’ d.). 21
2. M ETODIKA POROVNÁVÁNÍ Pokud se výsledný dekomprimovaný soubor neshoduje s puvod˚ ním, do sloupcu˚ cˇ as dekomprimace a pamˇet’ dekomprimace jsou uloženy hodnoty „err“. ˇ Všechny velikosti dat jsou uvedeny v bytech. Cas, potˇrebný pro komprimaci a dekomprimaci, je uveden v sekundách a spotˇrebovaná pamˇet’ v megabytech, pokud není uvedeno jinak. Kompresní pomˇer je vypoˇcítán jako pomˇer komprimované velikosti dat ku velikosti pu˚ vodních dat. Všimnˇete si, prosím, že data uvedená v následujících tabulkách jsou již naformátovaná, všechny výsledné tabulky ve své puvodní ˚ podobˇe jsou pˇriloženy na CD.
Tabulka 2.1: Ilustraˇcní tabulka, cˇ ást 1. – aplikace programu XZ na korpus DESAM program pˇríznak xz xz xz xz xz xz xz xz
-zv0 -zv3 -zv6 -zv9 -zv0e -zv3e -zv6e -zv9e
puv. ˚ komp. velikost velikost 20433448 5409956 20433448 3747388 20433448 2933756 20433448 2864736 20433448 3979632 20433448 3055596 20433448 2931272 20433448 2860480
komp. cˇ as k. pomˇer [s] 0, 263788 1, 93 0, 182722 6, 62 0, 143049 23, 50 0, 139684 26, 12 0, 194046 16, 96 0, 148990 24, 52 0, 142928 26, 33 0, 139476 27, 59
22
2. M ETODIKA POROVNÁVÁNÍ Tabulka 2.2: Ilustraˇcní tabulka, cˇ ást 2. – aplikace programu XZ na korpus DESAM program pˇríznak xz xz xz xz xz xz xz xz
2.2
-zv0 -zv3 -zv6 -zv9 -zv0e -zv3e -zv6e -zv9e
pamˇet’ k. [MB] 3, 696 32, 752 96, 432 249, 28 5, 168 49, 324 96, 428 247, 968
k.pomˇer × cˇ as d. pamˇet’ d. × cˇ as k. [s] [MB] 0, 50911 0, 57 1, 268 1, 20962 0, 40 5, 112 3, 36165 0, 39 9, 208 3, 64855 0, 35 22, 392 3, 29102 0, 46 1, 264 3, 65323 0, 39 5, 108 3, 76329 0, 41 9, 208 3, 84814 0, 36 21, 876
Pokroˇcilé testování programu˚
V následující cˇ ásti bakaláˇrské práce byly korpusy nejprve zpracovány a až poté provedeny komprimace pomocí komprimaˇcních programu. ˚ Z korpusu bylo vyextrahováno xml znaˇckování do samostatného souboru a zbylý korpus byl po sloupcích rozdˇelen na samostatné soubory. Shellové skripty sloužící k rozdˇelení korpusu a skript pro testování takto rozdˇeleného souboru programem XZ se nachází na pˇriloženém CD. Takto rozdˇelený soubor byl po cˇ ástech zkomprimován, dekomprimován a znovu složen dohromady s cílem zjistit, zda takovéto rozdˇelení má vliv na výslednou komprimaci. Dále bylo otestováno, jakým zpusobem ˚ ovlivní pˇredzpracování takto rozdˇeleného korpusu pomocí slovníkové komprimace výsledné hodnoty. Každý soubor pˇredstavující jednotlivé sloupce puvod˚ ního korpusu byl pˇredzpracován pomocí algoritmu, který vytvoˇril danému souboru slovník všech vyskytujících se slov a výstupní soubor cˇ ísel odkazujících na rˇ ádky tˇechto slovníkových záznamu. ˚ Skript zabývající se touto problematikou je rovnˇež pˇriložen na CD, jeho zpracování i na menších korpusech je však velice zdlouhavé kvuli ˚ opakovaným pˇrístupum ˚ do slovníku voláním pˇríkazu grep. Navíc tento skript nerozpoznává ve slovníku záznamy znaku˚ „.“, „[“ a „]“ 23
2. M ETODIKA POROVNÁVÁNÍ a vytváˇrí tak duplicitní záznamy, které navyšují velikost slovníku i výstupního souboru. Pro výše zmínˇené duvody ˚ byl nadále použit korpusový manažer Manatee2 , který je vyvinutý speciálnˇe pro práci s textovými korpusy. [20] S jeho pomocí byly vytvoˇreny dílˇcí soubory korpusu˚ pˇredstavující jednotlivé sloupce puvodních ˚ korpusu˚ a pˇredzpracovány slovníkovým algoritmem, cˇ ímž vznikly pro každý sloupec puvod˚ ního korpusu dva soubory – slovník a výstup. Výstupní soubor má formu obsahu puvodního ˚ sloupce nahrazeného pomocí cˇ ísel odkazujících na slovníkové záznamy. Tato cˇ ísla jsou uložena jako klasické rˇ etˇezce a oddˇelena znakem nového rˇ ádku. Soubory byly ještˇe upraveny pomocí Manatee do dalších dvou verzí, poté byly zkomprimovány klasickými komprimaˇcními programy a výsledky byly porovnány se základním testováním programu. ˚ Komprimované verze mˇely formu: 1.
slovníku˚ i výstupu˚ v základním tvaru,
2.
slovníku˚ v základním tvaru a výstupu˚ zakódovaných pomocí kódování na pevnou délku,
3.
slovníku˚ v základním tvaru a výstupu˚ zakódovaný pomocí Eliasova delta kódování.
2.3
Komprimovaná data
Programy byly otestovány na relativnˇe malém cˇ eském korpusu DESAM a rˇ ádovˇe vˇetším cˇ eském korpusu Czes2. U souboru DESAM probˇehlo testování co nejvˇetšího množství ruzných ˚ nastavení programu, na korpusu Czes2 již pro vˇetšinu testovaných programu˚ pouze jejich potenciální nejúˇcinnˇejší nastavení z duvodu ˚ dlouhého trvání bˇehu. 2.3.1 DESAM „Jde o znaˇckovaný, desambiguovaný a proˇcištˇený korpus publicistických textu˚ vytvoˇrený na FI MU. Jde o jeden z nejlepších výsledku˚ 2.
Manatee je pˇrístupný na fakultním serveru aurora.fi.muni.cz
24
2. M ETODIKA POROVNÁVÁNÍ korpusové lingvistiky u nás. Texty byly automaticky oznaˇckovány programem lemma, který každému slovnímu tvaru v textu pˇriˇradí jeho slovní druh, základní tvar a gramatické kategorie. Všechny nejednoznaˇcnosti byly ruˇcnˇe desambiguovány (zjednoznaˇcnˇeny) a korpus byl dále ruˇcnˇe proˇcištˇen (odstranˇeny pˇreklepy a chyby na ruz˚ ných úrovních znaˇckování). Korpus obsahuje tˇri atributy: word – slovní tvar, lemma – základní tvar, tag – gramatickou znaˇcku obsahující slovní druh a pˇríslušné gramatické kategorie.“ [21] Korpus DESAM obsahuje více než 1 mil. tvaru˚ a má velikost 20,4 MB. 2.3.2 Czes2 Korpus Czes obsahuje cˇ lánky cˇ eských novin a cˇ asopisu˚ z let 1995 – 1998 a z roku 2002. Text byl nashromáždˇen ze serveru trafika.cz, ˇ domovských stránek novin (napˇr. Lidové noviny, Mladá fronta, Ceskomoravský profit, Právo a další), z menších webových stránek vytvoˇrených studenty a z archivu˚ CD cˇ asopisu˚ o poˇcítaˇcích. Korpus Czes byl vytvoˇrený na FI MU v Brnˇe. Ve verzi Czes2 došlo k odstranˇení duplicitních a témˇerˇ duplicitních záznámu. ˚ [22] Korpus Czes2 obsahuje okolo 470 mil. tvaru, ˚ soubor má velikost 10,5 GB.
2.4
Použitý Hardware
Všechny bˇehy programu˚ uvedené v této bakaláˇrské práci se uskuteˇcnily na osobním poˇcítaˇci s dvoujádrovým procesorem o taktovací frekvenci 2.27 GHz a 4GB operaˇcní pamˇeti. Vše probíhalo pod 64bitovým operaˇcním systémem Fedora 17.
25
3 Testované programy Mezi základní komprimaˇcní programy, které byly v rámci této práce testovány patˇrí programy XZ, Zip, Gzip, Bzip2 a 7-Zip. Tyto programy jsou souˇcástí základní výbavy operaˇcního systému Fedora 17, na kterém byly tyto programy testovány. Zbylé testované programy jsou zdarma dostupnými implementacemi ruzných ˚ komprimaˇcních algoritmu˚ cˇ i jejich kombinací. Všechny názvy programu˚ v tabulkách odpovídají jejich programovým ekvivalentum ˚ podle použitých dostupných verzí. Záznamy uvedené v tabulkách jsou seˇrazeny vzestupnˇe podle dosaženého kompresního pomˇeru.
3.1
BBB
Program BBB (Big Block BWT) napsal v roce 2006 Matt Mahoney. Oproti jiným kompresorum ˚ používajícím BWT dovoluje BBB použití bloku˚ velkých až 80 % dostupné pamˇeti. Díky tomu by mˇel program BBB dosahovat lepších výsledku˚ na velkých datech. Nicménˇe programu schází mechanismus pro tˇrídˇení dlouhých opakujících se rˇ etˇezcu, ˚ proto muže ˚ být pomalejší, zejména pˇri použití na datech s vysokou redundancí. [14] Pomocí pˇríznaku mN byla programu nastavena velikost N bloku pro algoritmus BWT. Nejlepších výkonu˚ program dosáhl s nastavením velikosti bloku˚ odpovídajících velikosti vstupních dat. Parametr f oznaˇcuje rychlejší bˇeh programu, pro tento bˇeh je nutná až pˇetinásobnˇe vˇetší alokace spotˇrebované pamˇeti. Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.1. 26
3. T ESTOVANÉ PROGRAMY Tabulka 3.1: Aplikace programu BBB na korpus DESAM program pˇríznak komp. cˇ as k. pamˇet’ pomˇer [s] [MB] bbb cfm20 0, 110 96, 0 140 bbb cm20 0, 110 114, 0 34 bbb cf 0, 135 91, 2 35 bbb c 0, 135 100, 8 12 bbb cfm1 0, 161 96, 1 14 bbb cm1 0, 161 97, 1 8
3.2
BZip2
Program BZip2 komprimuje data pomocí algotimu BWT a Huffmanova kódování. Výstupem je formát dat bzip2, obvykle specifikovaný pˇríponou .bz2. Testu se podrobila verze programu 1.0.6. Program byl testován s ruzným ˚ nastavením cˇ íselného parametru 1. . . 9, který urˇcuje velikost bloku˚ použitých pro funkci algoritmu BWT. Pro nastavení 1 jde o velikost bloku 0,1 MB, pˇri nastavení 9 má blok velikost 0,9 MB. Se zvyšováním velikosti bloku se zvyšují i nároky na pamˇet’ a spotˇrebovaný cˇ as, zlepšuje se však efektivita komprimace. [23] Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.2.
Tabulka 3.2: Aplikace programu BZip2 na korpus DESAM program bzip2 bzip2 bzip2 bzip2
pˇríznak -9 -6 -3 -1
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 176 3, 2 7 0, 185 3, 1 5 0, 202 2, 9 3 0, 232 2, 8 2
27
3. T ESTOVANÉ PROGRAMY
3.3
comprolz
Comprolz napsal roku 2012 Zhang Li. Jde o kompresor vycházející z algoritmu ROLZ. Parametr b urˇcuje velikost alokovaných bloku˚ pamˇeti v MB. Pˇríznak f udává použití flexibilní syntaktické analýzy. Z porovnání je zˇrejmé, že flexibilní syntaktická analýza nemá velký vliv na výsledný kompresní pomˇer, spotˇreba cˇ asu se však s jejím použitím výraznˇe zvyšuje. Velikost alokované pamˇeti má urˇcitý vliv na efektivitu komprimace, pˇri vyšších hodnotách však již není nijak výrazný. Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.3.
Tabulka 3.3: Aplikace programu comprolz na korpus DESAM
3.4
program
pˇríznak
comprolz comprolz comprolz comprolz comprolz comprolz comprolz
-b250 -f e -b1000 e -b2000 e -b250 e -b500 e -b16 -f e -b16 e
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 135 17, 9 136 0, 137 7, 2 138 0, 137 7, 3 138 0, 137 7, 4 137 0, 137 7, 4 137 0, 141 17, 3 133 0, 143 7, 1 134
comprox
Podobnˇe jako program comprolz i o program comprox se pˇriˇcinil Zhang Li a vychází z algoritmu LZ77, konkrétnˇe používá algoritmus LZ77-ARI. Testovaným pˇríznakem m program urˇcuje maximální délku search bufferu, parametrem b velikost pamˇet’ového bloku a parametrem f užití flexibilní syntaktické analýzy. Comprox nedosahuje tak dobrých výsledku˚ jako comprolz, použití flexibilní syntaktické analýzy se chová podobnˇe. Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.4 28
3. T ESTOVANÉ PROGRAMY Tabulka 3.4: Aplikace programu comprox na korpus DESAM
3.5
program
pˇríznak
comprox comprox comprox comprox comprox comprox comprox comprox comprox comprox comprox
-m100 -b250 -f e -m300 -b2000 e -m200 -b1000 e -m150 -b500 e -m40 -b250 -f e -m100 -b250 e -m40 -b250 e -m100 -b16 -f e -m40 -b16 -f e -m100 -b16 e -m40 -b16 e
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 150 40, 6 135 0, 150 12, 2 133 0, 150 9, 8 133 0, 151 8, 5 135 0, 151 20, 8 134 0, 151 6, 7 134 0, 153 4, 5 134 0, 156 39, 2 115 0, 157 19, 6 115 0, 157 6, 6 116 0, 159 4, 5 115
crook
Crook je datový kompresor, který navrhl Jüri Valdmann. Testována byla verze 0.1 z roku 2012. Crook používá modelování PPM na bitové úrovni. Crook tedy nepracuje s pravdˇepodobnostmi symbolu, ˚ ale jednotlivých bitu, ˚ proto nepoužívá již zmínˇený escape modeling. Chová se tedy spíše jako DMC, ale na rozdíl od DMC si neuchovává duplicitní stavy reprezentující stejný kontext, díky cˇ emuž šetˇrí pamˇet’. [14] Parametr m udává programu maximální velikost použité pamˇeti, pˇríznak O velikost použitého kontextu pˇri modelování dat. Z porovnání, které nalezneme v tabulce 3.5, je zˇrejmé, že velikost kontextu ovlivnuje ˇ rapidnˇe úˇcinek komprimace po urˇcitou hranici, od které již další zvyšování kontextu ztrácí na efektivitˇe. Pˇrebyteˇcné navyšování maximální pamˇeti, pokud je dostateˇcnˇe velká na efektivitu komprimace, nehraje roli, nicménˇe neprodlužuje výraznˇe trvání programu. 29
3. T ESTOVANÉ PROGRAMY Tabulka 3.5: Aplikace programu crook na korpus DESAM program crook crook crook crook crook crook crook crook crook crook crook crook
3.6
pˇríznak -m2000 -O14 -m2000 -O12 -m2000 -O10 -m500 -O10 -m500 -O12 -m500 -O14 -m2000 -O8 -m500 -O8 -m2000 -O6 -m500 -O6 -m2000 -O4 -m500 -O4
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 120 7, 6 1123 0, 120 7, 2 871 0, 120 6, 8 635 0, 121 6, 6 513 0, 121 7, 2 513 0, 122 7, 2 513 0, 124 6, 0 405 0, 124 6, 2 405 0, 135 5, 2 193 0, 135 5, 3 193 0, 168 3, 9 46 0, 168 3, 9 46
ctw
Program ctw napsal v roce 2002 Erik Franken spoleˇcnˇe s Marcelem Peetersem. Program ctw je založen na výše zminovaném ˇ algoritmu CTW. Program pomocí modelování CM kombinuje pˇredpovˇedi modelu s ruznˇ ˚ e velkými kontexty. Statistiky se ukládají do sufixového stromu. [14] Použitím parametru d nastavujeme hloubku kontextového stromu. V tabulce 3.6 si mužeme ˚ všimnout, že hloubka kontextového stromu ovlivnuje ˇ efektivitu kompresního pomˇeru, ovšem za cenu delšího bˇehu programu. Nejlepšího výsledku na korpusu DESAM dosáhl program s hloubkou stromu 7, poté se již kompresní pomˇer nesnížil, zatímco cˇ as stále narustal. ˚ Program v základním nastavení pracuje se stromem hloubky 6. 30
3. T ESTOVANÉ PROGRAMY Tabulka 3.6: Aplikace programu ctw na korpus DESAM program pˇríznak ctw ctw ctw ctw
3.7
-d7 -d6 -d8 -d5
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 142 181, 9 37 0, 143 147, 6 37 0, 144 204, 7 37 0, 151 83, 1 37
DURILCA
Zkratka DURILCA pˇredstavuje Dirty Useless Really ILlusory Compressor/Archiver a jde o celou rˇ adu verzí programu navrhovanou Dmitrim Shkarinem. Programy využívají modelování PPMD cˇ i PPMonstr, která vyvinul Dmitri Shkarin. Testování se podrobily verze DURILCA v.0.5 (Hutter) z roku 2006 a DURILCA v.0.5 (LTCB-3) z roku 2008 v testu oznaˇcená jako DURILCA4. Pˇríznak m urˇcuje velikost pamˇeti, v základním nastavení jde o 256 MB pro verzi DURILCA a 1024 MB pro verzi DURILCA4. Parametr o udává velikost použitého kontextu modelu a parametr t2 pˇridává k algoritmu textové pˇredzpracování vstupních dat. Oba programy dosáhly velice dobré komprimace, ovšem za cenu dlouhého bˇehu. Programy navíc pro znaˇcnou cˇ ást nastavení nebyly schopny korektnˇe zkomprimovat zadaná data. Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.7. 31
3. T ESTOVANÉ PROGRAMY Tabulka 3.7: Aplikace programu DURILCA na korpus DESAM
3.8
program
pˇríznak
DURILCA4 DURILCA4 DURILCA DURILCA DURILCA DURILCA4 DURILCA4 DURILCA DURILCA DURILCA DURILCA DURILCA
e -m1500 e e -m1500 e -m1500 -t2 e e -m1500 -o10 e -o10 e -t2 e -o10 e -m1500 -o10 e -m1500 -o10 -t2 e -o10 -t2
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 088 49, 2 1352 0, 088 63, 9 1134 0, 091 45, 2 1306 0, 091 53, 2 1460 0, 095 74, 2 300 0, 096 42, 9 171 0, 096 37, 8 171 0, 096 79, 2 302 0, 100 35, 0 126 0, 100 34, 9 124 0, 101 40, 3 129 0, 101 40, 1 129
fpaq3d
Program fpaq3d je jedna z mnoha verzí programu fpaq, který ve verzi fpaq0 napsal Matt Mahoney. Aritmetické kódování dále vylepšil D. Scott ve verzi fpaq0s. Fpaq3d je dílem N. F. Antonia a oproti pˇredchozímu programu s velikostí kontextu 0 pracuje s kontextem velikosti 2. [14] Program pˇri spuštˇení vyžaduje cˇ íselný parametr 1. . . 7, podle kterého je programu nastavena maximální dostupná pamˇet’ od 16 MB až po 2 GB. Opˇet jde pˇri zmˇenˇe parametru o kompenzaci kompresního pomˇeru na úkor spotˇrebovaného cˇ asu, jak si mužeme ˚ všimnout v tabulce 3.8. Pˇri použití parametru 7 program na použitém stroji nedokonˇcí komprimaci pro neoprávnˇený pˇrístup k pamˇeti. 32
3. T ESTOVANÉ PROGRAMY Tabulka 3.8: Aplikace programu fpaq3d na korpus DESAM program pˇríznak fpaq3d fpaq3d fpaq3d fpaq3d
3.9
6 5 3 1
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 163 25, 7 1023 0, 164 24, 0 525 0, 169 20, 1 133 0, 178 16, 7 35
Gzip
Program Gzip (GNU zip) napsal roku 1992 Jean-loup Gailly spoleˇcnˇe s Markem Adlerem, který se podílel na psaní kódu dekompresoru, jako náhradu za program compress. Program byl naposledy aktualizován roku 2013. Gzip používá ke komprimaci algoritmus Deflate. Komprimovaná data typicky ukládá ve formátu gzip, tedy s pˇríponou .gz. [13] Gzip je nastavitelný za pomoci cˇ íselného parametru 1. . . 9, který ovlivnuje ˇ rychlost komprimace na úkor délky bˇehu. Nastavení 1 urcˇ uje nejrychlejší bˇeh programu s malou komprimací, naopak s parametrem 9 program zaruˇcuje nejlepší komprimaci, leˇc trvá déle. Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.9.
Tabulka 3.9: Aplikace programu Gzip na korpus DESAM program gzip gzip gzip gzip
pˇríznak -9 -6 -3 -1
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 265 2, 0 1 0, 267 1, 3 1 0, 301 0, 6 1 0, 335 0, 5 1
33
3. T ESTOVANÉ PROGRAMY
3.10 lpaq Program lpaq pochází z dílny Matta Mahoneyho ve verzi lpaq1 z roku 2007. Lpaq1 používá metodu míchání kontextu, ˚ dohromady je jich 7. [14] Testován byl právˇe program lpaq1, který vyžaduje nastavení cˇ íselného parametru 0. . . 9 ovlivnujícího ˇ velikost použité pamˇeti vzestupnˇe od 6 MB po 1,5 GB. V tabulce 3.10 si mužeme ˚ povšimnout, že se zvyšující se dostupnou pamˇetí, pracuje program rychleji a kompresní pomˇer se zvyšuje. Program dosahuje na korpusu DESAM velice dobrého kompresního pomˇeru, cˇ asová nároˇcnost je však docela vysoká. Tabulka 3.10: Aplikace programu lpaq1 na korpus DESAM program lpaq lpaq lpaq lpaq
pˇríznak 9 6 3 0
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 106 107, 6 1333 0, 108 108, 3 186 0, 115 109, 2 27 0, 142 117, 2 6
3.11 lrzip Program lrzip je dílem Cona Colivase, pˇri jeho tvorbˇe vycházel z programu rzip. Program pˇredzpracovává slovníkovˇe vstupní data a zbavuje je redundantních dlouhých rˇ etˇezcu. ˚ Pomocí parametru˚ lze u tohoto programu nastavit další zpracování dat, na výbˇer je použití kompresoru BZip2 (-b), Gzip (-g), LZO (-l), Zpaq (-z) nebo žádného (-n), tedy ponechání dat v surovém stavu pro další zpracování. Následnˇe program nabízí urˇcení úrovnˇe komprese pomocí pˇríznaku Ln, kde n nabývá hodnot 1. . . 9. Ve výchozím nastavení pracuje program s úrovní 7, pˇriˇcemž nejvyšší výkon nabízí pod úrovní 9. [24] Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.11. Z té je zˇrejmé, že nejlepší komprimace dosáhl program s použitím kompresoru Zpaq, ovšem v porovnání s jinými kompresory nedosa34
3. T ESTOVANÉ PROGRAMY huje na korpusu DESAM tak dobrých výsledku. ˚ Tabulka 3.11: Aplikace programu lrzip na korpus DESAM program lrzip lrzip lrzip lrzip lrzip lrzip lrzip lrzip
pˇríznak -z -z -L9 -b -L9 -b -g -L9 -g -l -L9 -l
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 143 45, 8 412 0, 143 51, 1 409 0, 183 12, 4 107 0, 186 6, 7 106 0, 232 11, 8 102 0, 234 5, 8 107 0, 362 11, 5 106 0, 365 5, 5 106
3.12 Lzip ˇ Program Lzip je cˇ istou implementací algoritmu LZMA. Císelný pˇríznak 0. . . 9 urˇcuje míru komprimace, 0 znaˇcí nejrychlejší komprimaci a 9 nejsilnˇejší. Parametr s nastavuje velikost použitého slovníku, pˇríznak m maximální délku shodných rˇ etˇezcu. ˚ [25] Z tabulky 3.12 si mužeme ˚ všimnout, že míra komprese program pˇríliš neovlivnuje. ˇ Maximální délka hledaných shodných rˇ etˇezcu˚ se jeví jako kompenzace síly komprese na úkor spotˇrebovaného cˇ asu. Tabulka 3.12: Aplikace programu Lzip na korpus DESAM program lzip lzip lzip lzip lzip
pˇríznak -9 -m64 -s512MiB -9 -m64 -s8MiB -9 -m36 -s512MiB -6 -m36 -s8MiB -9 -m36 -s8MiB
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 140 24, 1 214 0, 143 23, 5 91 0, 146 20, 2 215 0, 149 19, 8 91 0, 149 19, 8 91
35
3. T ESTOVANÉ PROGRAMY
3.13 LZPXj Program LZPXj vyvinuli spoleˇcnˇe Ilia Muraviev a Jan Ondrus. Pro operaˇcní systém UNIX je funkˇcní pouze verze 1.2h, která kombinuje algoritmy LZP a PPM. [14] Program je nastavitelný pomocí jednoho cˇ íselného parametru. Ten nabývá hodnot 0. . . 9 a definuje míru komprese. Z tabulky 3.13 je zˇrejmé, že se jedná o kompenzaci efektivity komprese na úkor doby bˇehu programu a použití vˇetšího pamˇet’ového prostoru. Tabulka 3.13: Aplikace programu LZPXj na korpus DESAM program pˇríznak lzpxj lzpxj lzpxj lzpxj lzpxj
9 7 5 3 1
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 131 22, 0 808 0, 131 18, 8 219 0, 133 17, 5 71 0, 145 17, 2 22 0, 169 16, 6 7
3.14 NanoZip Program NanoZip napsal v roce 2008 Sami Runsas [26]. V této bakaláˇrské práci byla testována poslední dostupná verze 0.09a z roku 2011. Program NanoZip je volnˇe dostupný, jeho zdrojové kódy už ale ne. NanoZip používá ke komprimaci nˇekolik ruzných ˚ algoritmu, ˚ v základním nastavení jde o rychlé BWT (parametry co). Srovnání nalezneme v tabulce 3.14. Prvním použitým algoritmem bylo míchání kontextu˚ (pˇríznaky cc), dále BWT (co, cO), LZ77 (cd, cD) a LZP (cf, cF). Velká písmena v parametru znaˇcí použití o nˇeco kvalitnˇejší komprese na úkor cˇ asu a možného nárustu ˚ spotˇrebované pamˇeti. Z tabulky si ale mužeme ˚ všimnout, že pro algoritmus BWT (co, cO) dochází na korpusu DESAM u silnˇejší komprimace ke zlepšení kompresního pomˇeru i zkrácení doby bˇehu programu. Parametry p a P u algoritmu LZ77 nastavují použití paralelních výpoˇctu. ˚ Zvýšení 36
3. T ESTOVANÉ PROGRAMY dostupné pamˇeti programu za pomoci pˇríznaku m nemá pˇri komprimaci na korpusu DESAM význam, nebot’ program v základním nastavení pracuje s pamˇetí 512 MB. Nakonec parametr nm udává programu možnost neukládat metadata jako práva souboru, ˚ cˇ asové znaˇcky (timestamps) a kontrolní sumu. Zlepšení komprese pˇri použití parametru nm, již podle oˇcekávání není nijak výrazné. Program NanoZip vykazuje velmi dobrou úˇcinnost pro algoritmy CM a BWT, pˇri použití CM však spotˇrebovává daleko více cˇ asu a rozdíl v síle komprimace není tak velký. Nejlepšího výsledku na korpusu DESAM tak dosáhl za pomocí algoritmu BWT.
37
3. T ESTOVANÉ PROGRAMY Tabulka 3.14: Aplikace programu NanoZip na korpus DESAM program nz nz nz nz nz nz nz nz nz nz nz nz nz nz nz nz nz nz nz nz nz nz nz
pˇríznak a -cc -nm a -cc a -cO -nm a -cO a -nm a -co -m1500m a -co a a -cDP -nm a -cDP a -cDp -nm a -cDp a -cD -m1500m a -cD a -cdP -nm a -cdP a -cdp -nm a -cdp a -cdp a -cd -m1500m a -cd a -cf -m1500m a -cf
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0.098 48.1 448 0.098 48.1 448 0.111 3.3 130 0.111 3.3 130 0.120 4.1 124 0.120 4.2 122 0.120 4.2 122 0.120 4.2 122 0.218 2.7 62 0.218 2.7 62 0.221 2.4 60 0.221 2.4 60 0.223 1.5 54 0.223 1.5 48 0.235 1.4 56 0.235 1.4 56 0.238 1.2 54 0.238 1.2 54 0.238 1.2 54 0.252 0.6 48 0.252 0.6 48 0.403 0.2 44 0.403 0.2 44
3.15 Ocamyd Program Ocamyd je dílem Franka Schwellingera. Ocamyd kombinuje algoritmy DMC a PPM a s daty pracuje na úrovni bitu. ˚ Pˇríznak s1. . . 4 urˇcuje použití komprimaˇcních algoritmu˚ od nejpomalejších a nejefektivnˇejších (1) po nejrychlejší (4). Postupnˇe jsou to kombinace DMC, PPM a Match model pro nastavení s1, DMC a PPM pro nasta38
3. T ESTOVANÉ PROGRAMY vení s2, pouze DMC pro nastavení s3 a Hitcache s DMC pro nastavení s4. Parametr m0. . . 9 programu definuje velikost dostupné pamˇeti a to od 64 MB po 900 MB. [27] Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.15. Je zˇrejmé, že první dva zmínˇené algoritmy použité programem ocamyd spotˇrebovávají na korpusu DESAM pˇríliš mnoho cˇ asu. Nejlepšího výsledku na korpusu DESAM tak program dosáhl za pomocí algoritmu DMC s nastavením nejvyšší dostupné pamˇeti. Tabulka 3.15: Aplikace programu Ocamyd na korpus DESAM program pˇríznak ocamyd ocamyd ocamyd ocamyd ocamyd ocamyd ocamyd ocamyd ocamyd ocamyd ocamyd ocamyd
-s0 -m9 -s0 -m5 -s1 -m9 -s0 -m0 -s2 -m9 -s1 -m5 -s2 -m5 -s1 -m0 -s3 -m5 -s3 -m9 -s2 -m0 -s3 -m0
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 111 329, 3 923 0, 113 348, 1 514 0, 137 202, 8 708 0, 138 331, 7 67 0, 139 15, 1 708 0, 142 203, 0 398 0, 150 14, 6 479 0, 169 204, 6 61 0, 203 12, 8 193 0, 203 13, 1 242 0, 207 14, 2 33 0, 238 12, 2 33
3.16 paq9a Program paq9a je dalším zástupcem rˇ ady programu˚ paq, pochází z rukou Matta Mahoneyho. Paq9a používá algoritmus kontextového míchání (CM) spoleˇcnˇe s pˇredzpracováním pomocí algoritmu LZP, který zvyšuje rychlost programu pro vysoce redundantní data. [14] Paq9a lze nastavit pomocí cˇ íselného parametru 1. . . 9 pro definování maximální pamˇeti použité programem vzestupnˇe od 18 po 1585 MiB. Z tabulky 3.16 mužeme ˚ vyˇcíst, že na textovém korpusu DESAM pro39
3. T ESTOVANÉ PROGRAMY gram paq9a s vyšší dostupnou pamˇetí dosahuje lepšího kompresního pomˇeru a také kratší doby bˇehu.
Tabulka 3.16: Aplikace programu paq9a na korpus DESAM program pˇríznak paq9a paq9a paq9a paq9a
-9 -6 -3 -1
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 106 92, 0 1344 0, 106 88, 4 198 0, 114 109, 1 38 0, 131 137, 7 20
3.17 TinyCM Program TinyCM napsal roku 2012 David Werecat. TinyCM používá algoritmus míchání kontextu˚ (CM), a to s modely order 1, order 2, order 3 a order 6. Pˇri spuštˇení program vyžaduje cˇ íselný parametr 1. . . 9, pro nastavení síly komprese. [14] Parametrizované porovnání bˇehu˚ programu se nachází v tabulce 3.17. Nastavením síly komprese zˇrejmˇe dochází ke kompenzaci kompresního pomˇeru na úkor spotˇrebovaného cˇ asu.
Tabulka 3.17: Aplikace programu TinyCM na korpus DESAM program pˇríznak TinyCM TinyCM TinyCM TinyCM TinyCM
9 7 5 3 1
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 166 103, 6 2132 0, 171 41, 8 541 0, 179 38, 2 136 0, 196 37, 4 34 0, 230 35, 9 9
40
3. T ESTOVANÉ PROGRAMY
3.18 XZ
Program XZ Utils (dále jen XZ) byl v prubˇ ˚ ehu psaní této bakaláˇrské práce využívaný ke komprimaci dat v Centru zpracování pˇrirozeného jazyka. XZ je volnˇe dostupný program urˇcený pro komprimaci obecných dat. Jádrem kódu programu XZ se stal LZMA SDK 1 . Primárním komprimaˇcním algoritmem, na kterém souˇcasnˇe stojí program XZ, je algoritmus LZMA2 [29]. Komprimovaná data ukládá program XZ standardnˇe do svého formátu .xz. Formát dat lze pˇrenastavit na formát .lzma. XZ používá cˇ íselný parametr 0. . . 9. S nastavením 0–2 spotˇrebuje program XZ relativnˇe málo pamˇeti a komprimace trvá kratší dobu. Pro nastavení 3–5 dosahuje komprimace dobrých výsledku˚ se stˇredním vytížením pamˇeti ale delším trváním. Pro parametry 6–9 docílí program nejlepší kvality komprimace, za cenu vyšší spotˇreby pamˇeti i cˇ asu. Ve výchozím nastavení program používá parametr 6. Pomocí pˇríznaku e program bˇeží v tzv. extrémním módu, snahou je zvýšit efektivitu komprimace bez zvýšení spotˇrebované pamˇeti. To má za následek zvýšení délky trvání programu.[29] Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.18.
1. Zkratka SDK znaˇcí Software Development Kit, jde o balík obsahující dokumentaci, vzorky, hlaviˇcky, knihovny a nástroje potˇrebné k vývoji aplikací používajících komprimaˇcní algoritmus LZMA. [28]
41
3. T ESTOVANÉ PROGRAMY Tabulka 3.18: Aplikace programu XZ na korpus DESAM program xz xz xz xz xz xz xz xz xz xz xz xz xz xz xz xz
pˇríznak -F lzma -zv9e -zv9e -F lzma -zv9 -zv9 -F lzma -zv6e -zv6e -F lzma -zv6 -zv6 -F lzma -zv3e -zv3e -F lzma -zv3 -zv3 -F lzma -zv0e -zv0e -F lzma -zv0 -zv0
komp. cˇ as k. pomˇer [s] 0, 140 26, 2 0, 140 25, 8 0, 140 24, 5 0, 140 25, 7 0, 143 24, 3 0, 143 23, 9 0, 144 22, 9 0, 144 24, 4 0, 150 21, 9 0, 150 21, 5 0, 183 7, 1 0, 183 7, 3 0, 195 12, 7 0, 195 12, 6 0, 265 1, 9 0, 265 1, 9
pamˇet’ [MB] 247 247 247 247 96 96 96 96 49 49 33 33 5 5 4 4
3.19 Zip Program Zip slouží pouze ke komprimaci dat, pro následnou dekomprimaci je nutné použít program UnZip. Oba programy jsou dílem skupiny Info–ZIP založené roku 1990. Pro testování byla použita verze Zip 3.00 naposledy vydaná roku 2008 spoleˇcnˇe s verzí programu UnZip 6.00, která byla aktualizována naposledy roku 2009. Poslední verze podporuje pro komprimaci pouze použití algoritmu Deflate. Data jsou ukládána ve formátu .zip. [30] Stejnˇe jako u pˇredchozího programu má Zip cˇ íselný parametr 1. . . 9, který ovlivnuje ˇ dobu bˇehu programu na úkor efektivity komprimace. Nastavení 1 zaruˇcuje nejrychlejší bˇeh programu s nízkou efektivitou komprimace, pˇríznak 9 pak nejlepší komprimaci ale delší trvání. Parametrizované porovnání bˇehu˚ programu nalezneme v ta42
3. T ESTOVANÉ PROGRAMY bulce 3.19.
Tabulka 3.19: Aplikace programu Zip na korpus DESAM program zip zip zip zip
pˇríznak -9 -6 -3 -1
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 265 2, 0 1 0, 267 1, 2 1 0, 301 0, 6 1 0, 335 0, 5 1
3.20 7-Zip Autorem programu 7-Zip je Igor Pavlov. 7-zip byl vydán poprvé v roce 1997 , poslední dostupná verze 7-Zip 9.20 je aktualizována roku 2010. Výchozí metodou komprimace programu 7-Zip je algoritmus LZMA, mezi další podporované metody patˇrí LZMA2, PPMD, BZip2 a Deflate. 7-Zip používá svuj ˚ vlastní formát .7z, ale podporuje i další formáty komprimovaných dat jako napˇr zip, gzip, bzip2 a další. [16] Prvním testovaným pˇríznakem byl výbˇer metody použité komprimace. Nejlepší komprimace dosáhl program s metodou komprimace PPMD, zárovenˇ šlo o nejkratší bˇeh programu. Dobrých výsledku˚ také dosáhly metody LZMA a LZMA2. Pro metodu PPMD byla dále testována ruzná ˚ nastavení dostupné pamˇeti a hodnota n pro nastavení velikosti order-n modelu. Výsledky naznaˇcují, že velikost použitého kontextu s nedostatkem dostupné pamˇeti muže ˚ vést i ke zhoršení efektivity komprimace. Naopak, pokud má program k dispozici dostatek pamˇeti, zvyšování délky kontextu zvyšuje efektivitu komprimace ovšem na úkor doby trvání bˇehu programu. Parametrizované porovnání bˇehu˚ programu nalezneme v tabulce 3.20. 43
3. T ESTOVANÉ PROGRAMY Tabulka 3.20: Aplikace programu 7-Zip na korpus DESAM pˇríznak a -m0=ppmd:mem=2000m:o=32 a -m0=ppmd:mem=2000m:o=15 a -m0=ppmd:mem=2000m:o=10 a -m0=ppmd:mem=500m:o=10 a -m0=ppmd:mem=2000m:o=7 a -m0=ppmd:mem=500m:o=7 a -m0=ppmd:mem=25m:o=7 a -m0=ppmd:mem=25m:o=10 a -m0=ppmd a -mx=9 a -m0=ppmd:mem=25m:o=15 a -m0=lzma a a -m0=lzma2 a -m0=ppmd:mem=25m:o=32 a -m0=bzip2 a -m0=deflate
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 106 8, 8 745 0, 108 6, 0 221 0, 112 4, 5 94 0, 112 4, 3 94 0, 121 3, 3 42 0, 121 3, 7 42 0, 127 3, 6 32 0, 133 4, 6 32 0, 135 3, 0 23 0, 140 17, 7 254 0, 147 6, 1 32 0, 149 17, 8 193 0, 149 16, 8 193 0, 149 17, 8 195 0, 161 7, 3 32 0, 176 3, 4 39 0, 254 7, 4 6
44
4 Výsledky 4.1
Základní testování všech porovnávaných programu˚ s nejefektivnˇejším nastavením na korpusu DESAM
Finální porovnání je provedeno pro nastavení parametru, ˚ se kterým programy dosáhly na korpusu DESAM nejlepších výsledku. ˚ Pˇripomenme ˇ si, že jde o korpus velikosti 20, 4 MB. Preferovanou veliˇcinou pˇri volbˇe nastavení byl kompresní pomˇer, druhou rozhodující velicˇ inou cˇ as spotˇrebovaný programem ke komprimaci dat. Výsledky se nachází v tabulce 4.1. Pro pˇrehlednost byla do tabulky pˇridána hodnota alg. znaˇcící typ algoritmu, který program v daném nastavení použil pro modelování vstupních dat. Data jsou samozˇrejmˇe následnˇe kódována, typicky pomocí Aritmetického nebo Huffmanova kódování. Ze 20 testovaných programu˚ dosáhlo pˇri porovnání na korpusu DESAM 10 programu˚ lepšího kompresního pomˇeru než program XZ, souˇcasnˇe používaný program v Laboratoˇri pro zpracování pˇrirozeného jazyka pˇri Masarykovˇe univerzitˇe. Program XZ dosáhl na korpusu 86% komprimace za necelých 27 sekund. V tabulce nejlépe umístˇený program DURILCA4 dosáhl v testu nejvyšší komprimace, konkrétnˇe dokázal korpus DESAM zkomprimovat na 8, 8 % puvodní ˚ velikosti. Což je o 5, 2 % více než program XZ. Na druhou stranu ke komprimaci spotˇreboval témˇerˇ dvakrát více cˇ asu. Vˇetší spotˇreba cˇ asu se muže ˚ zdát pˇri testování na korpusu DESAM nepodstatná, ale pozdˇeji uvidíme, že pro vˇetší objemy dat, hraje velmi duležitou ˚ roli. Mezi tˇri nejlepší programy, které pˇrekonaly program XZ v míˇre komprimace i délce bˇehu programu, patˇrí programy 7-Zip, NanoZip a crook. Crook pˇredˇcil program XZ o 2 %, co se týˇce kompresního pomˇeru, a ušetˇril více než 60 % cˇ asu. NanoZip pˇrekonal program XZ o 2, 9 % z hlediska síly komprimace a uspoˇril témˇerˇ 87 % cˇ asu. Program 7-Zip zkomprimoval vstupní data o 3, 4 % úspornˇeji než program XZ s úsporou cˇ asu cca 70 %. Z porovnání také vyplývá, že výchozí programy operaˇcního systému Fedora sice nejsou pˇríliš efektivní, co se týˇce velikosti kompri45
4. V ÝSLEDKY mace, zato jsou velice cˇ asovˇe i pamˇet’ovˇe nenároˇcné. Programy, které využívají k modelování algoritmy z rodiny LZ dosahují výsledku˚ blízkých programu XZ v kompresním pomˇeru, spotˇrebovaném cˇ ase i nároˇcnosti na využití pamˇeti. Tabulka 4.1: Souhrn testovaných programu˚ na korpusu DESAM program
pˇríznak
DURILCA4 paq9a lpaq 7za bbb nz crook
e -m1500 -9 9 a1 cfm20 a -cO c -m2000 -O14 9 -b250 -f e -s2 -m9 -zv9e -9 -m64 s512MiB -d7 -z -m200 -b1000 e c6 9 -9 -9 -9
lzpxj comprolz ocamyd xz lzip ctw lrzip comprox fpaq3d TinyCM bzip2 gzip zip
1.
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 088 50, 6 1352 0, 106 92, 0 1344 0, 106 117, 1 1333 0, 106 8, 0 743 0, 110 95, 6 141 0, 111 3, 5 130 0, 120 10, 4 1123
alg. PPMD CM CM PPMD BWT BWT PPM PPM ROLZ DMC LZMA2 LZMA
0, 131 0, 135 0, 139 0, 140 0, 140
22, 0 19, 1 16, 1 26, 8 26, 4
808 131 709 247 216
0, 142 0, 143 0, 150
181, 9 47, 6 11, 7
37 CTW, CM 408 CM 127 LZ77
0, 163 0, 166 0, 176 0, 265 0, 265
23, 8 52, 4 3, 1 2, 1 2, 0
1029 2163 7 1 1
CM CM BWT Deflate Deflate
-m0=ppmd: mem=2000m:o=32
46
4. V ÝSLEDKY
4.2
Základní testování všech porovnávaných programu˚ na korpusu Czes2
Testování na korpusu Czes2 byly podrobeny všechny výše zminoˇ vané programy. Programy, které nejsou uvedeny ve výsledné tabulce 4.2, nedokázaly korpus Czes2 korektnˇe zkomprimovat za kratší dobu než 6 hodin. Program DURILCA komprimaci nedokonˇcil pro nedostatek dostupné pamˇeti, lpaq oznámil, že komprimovaný soubor je pˇríliš velký. Program crook komprimaci dokonˇcil, dekomprimovaný soubor se však neshodoval s puvodním. ˚ Ostatní programy nesplnovaly ˇ cˇ asový limit a byly násilnˇe ukonˇceny v prubˇ ˚ ehu komprimace. Jedinou výjimku tvoˇrí program paq9a, který byl pro ilustraci ponechán komprimaci dokonˇcit i pˇres dlouhé trvání komprimace. Korpus Czes2 tak v tomto testování dokázalo korektnˇe zkomprimovat již pouze 11 z puvodních ˚ 20 programu. ˚ Jak již bylo zmínˇeno výše, programy byly pˇri testování na korpusu Czes2 spuštˇeny s nejefektivnˇejším nastavením zjištˇeným pˇri bˇehu na korpusu DESAM. S ruznými ˚ parametry byly spuštˇeny programy XZ, 7-Zip, NanoZip a crook. Program XZ zkomprimoval korpus Czes2 pˇri nejefektivnˇejším nastavení na 10, 5 % puvodní ˚ velikosti korpusu za necelé 4 hodiny. Programem, který dosáhl nejvyšší míry komprimace se stal paq9a. Paq9a zkomprimoval korpus Czes2 na 7, 3 % puvodní ˚ velikosti, což je o 3, 2 % ménˇe než program XZ. Paq9a však k této komprimaci potˇreboval témˇerˇ dvakrát více cˇ asu. Pouze dva testované programy dosáhly na korpusu Czes2 lepšího kompresního pomˇeru i kratšího cˇ asu potˇrebného ke komprimaci. Jde o programy 7-Zip a NanoZip. 7-Zip dosáhl lepší komprimace o 2, 4 % za necelých 28 minut, cˇ ímž ušetˇril oproti programu XZ pˇres 87 % cˇ asu. NanoZip dokázal zkomprimovat korpus Czes2 o 1, 1 % lépe než program XZ a s cˇ asem 55 minut pˇredˇcil XZ o témˇerˇ 76 % cˇ asu. 47
4. V ÝSLEDKY Tabulka 4.2: Souhrn testovaných programu˚ na korpusu Czes2 program paq9a 7za 7za nz nz lrzip xz lzpxj comprolz comprox xz bzip2 xz xz gzip zip xz
4.3
pˇríznak -9 a2 a3 a -cO a -z -L9 -zv9 9 -b250 e -m100 -b250 e -zv6 -9 -zv3 -zv0e -9 -9 -zv0
komp. cˇ as k. pamˇet’ alg. pomˇer [min] [MB] 0, 073 439, 9 1586 CM 0, 081 27, 5 2564 PPMD 0, 083 59, 8 2052 PPMD 0, 094 55, 1 554 BWT 0, 103 47, 0 545 BWT 0, 104 267, 4 2454 CM 0, 105 223, 6 690 LZMA2 0, 106 114, 1 1308 PPM 0, 110 66, 9 621 ROLZ 0, 119 96, 2 1484 LZ77 0, 123 0, 158 0, 165 0, 173 0, 233 0, 233 0, 236
214, 4 33, 7 66, 5 108, 9 18, 5 18, 4 18, 2
96 8 33 5 1 1 4
LZMA2 BWT LZMA2 LZMA2 Deflate Deflate LZMA2
Pokroˇcilé testování programu˚
4.3.1 Komprimace po cˇ ástech V této cˇ ásti práce byl korpus DESAM nejdˇríve pomocí skriptu rozdˇelen na jednotlivé sloupce. Poté byl na všechny cˇ ásti aplikován program XZ. Výsledkem komprimace po cˇ ástech je více zkomprimovaných souboru. ˚ Vytvoˇrené soubory se opˇet dají dekomprimovat a pomocí druhého skriptu opˇet složit dohromady. Tato technika se snaží 2. 3.
-m0=ppmd:mem=2500m:o=10 -m0=ppmd:mem=2000m:o=32
48
4. V ÝSLEDKY využít struktury korpusu, nebot’ v jednotlivých sloupcích se vyskytují stejná slova, ale napˇr. slova z posledního sloupce obsahujícího tagy se v druhém sloupci nevyskytují. Metoda byla provedena ve dvou variantách, nejprve došlo k rozdˇelení korpusu na 5 samostatných souboru. ˚ První soubor obsahuje xml znaˇckování korpusu, které narušuje sloupcovou strukturu. Druhý soubor obsahuje cˇ íslování rˇ ádku˚ zbylých po odstranˇení xml znacˇ ek. A nakonec 3 samostatné soubory, pro každý sloupec jeden. Druhá verze je o jeden sloupec chudší, první dva sloupce korpusu, tedy slova a jejich základy, byly ponechány v jediném souboru spoleˇcnˇe právˇe pro redundanci spoleˇcných slovních základu. ˚ Porovnání nalezneme v tabulce 4.3, oznaˇcení programu xz(pp1) urˇcuje první z popsaných variant, xz(pp2) variantu druhou, s menším poˇctem souboru. ˚ Dˇelení korpusu se nezdá být efektivní z hlediska porovnávaných kritérií. Jedním z možných vysvˇetlení je jistˇe komprimace dat navíc, která vzniknou pˇri dˇelení souboru˚ (ˇcíslování rˇ ádku˚ pro zpˇetné sestavení puvodního ˚ souboru). Pˇri testech, kdy byl tento soubor zámˇernˇe vypuštˇen, však nebylo dosaženo lepších výsledku˚ než pˇri klasické komprimaci. Mužeme ˚ usuzovat, že komprimaˇcní programy pˇri bˇehu na korpusu DESAM pravdˇepodobnˇe kódují i delší sekvence symbolu, ˚ které pˇresahují sloupcové dˇelení, díky cˇ emuž dosahují lepší komprimace než pˇri bˇehu na rozdˇeleném souboru. Dalším vysvˇetlením by mohla být redundance mezi sloupci na bitové úrovni, která cˇ iní tuto metodu neefektivní.
Tabulka 4.3: Komprimace po cˇ ástech pomocí programu XZ na korpusu DESAM program xz xz(pp2) xz(pp1)
pˇríznak -zv9 -zv9 -zv9
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 140 25, 7 247 0, 195 31, 2 535 0, 247 31, 8 604
49
4. V ÝSLEDKY 4.3.2 Komprimace po cˇ ástech se slovníkovým pˇredzpracováním Komprimace po cˇ ástech se slovníkovým pˇredzpracováním byla provedena ve tˇrech ruzných ˚ variantách na korpusu DESAM s použitím programu˚ XZ a 7-Zip. Na korpusu Czes2 byl spuštˇen pouze program 7-Zip. Program XZ byl spouštˇen s nastavením zv9, program 7-Zip s nastavením a -m0=ppmd:mem=2000m:o=10. Každý prubˇ ˚ eh zaznamenával dva výsledky. První výsledek sledoval komprimaci pouze výstupních souboru, ˚ druhý výsledek komprimaci i se slovníky. Du˚ vodem je pˇrehnaná velikost slovníku, ˚ pro jejichž efektivnˇejší tvorbu již existují jiné nástroje založené na bázi minimálních koneˇcných automatu. ˚
Varianta I Varianta I pracuje se slovníky i výstupními soubory v základním tvaru. Výstupy jsou uloženy ve tvaru cˇ ísel v textové podobˇe oddˇelených znakem pro nový rˇ ádek.
Tabulka 4.4: Varianta I pro korpus DESAM program 7za xz 7za xz 7za xz
poznámka originálnˇe originálnˇe bez slovníku bez slovníku se slovníkem se slovníkem
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 112 4, 5 94 0, 140 25, 7 247 0, 170 5, 5 186 0, 183 15, 8 311 0, 197 6, 2 230 0, 214 17, 1 526
50
4. V ÝSLEDKY Tabulka 4.5: Varianta I pro korpus Czes2 program 7za 7za 7za
poznámka originálnˇe bez slovníku se slovníkem
komp. cˇ as k. pamˇet’ pomˇer [min] [MB] 0, 081 27, 5 2564 0, 134 57, 2 3432 0, 136 58, 1 3486
Varianta II Varianta II pracuje se slovníky v základním tvaru. Výstupní soubory jsou upraveny na kód pevné délky. Každému cˇ íslu ve výstupním souboru byl pˇridán prefix sestávající z 0, aby bylo dosaženo konstantní délky kódových slov, cˇ ísla jsou ukládána binárnˇe. Následnˇe byly odstranˇeny nyní již pˇrebyteˇcné oddˇelovaˇce nového rˇ ádku.
Tabulka 4.6: Varianta II pro korpus DESAM program 7za xz 7za xz 7za xz
poznámka originálnˇe originálnˇe bez slovníku bez slovníku se slovníkem se slovníkem
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 112 4, 5 94 0, 140 25, 7 247 0, 177 5, 9 157 0, 183 20, 5 339 0, 203 6, 8 198 0, 215 21, 9 555
51
4. V ÝSLEDKY Tabulka 4.7: Varianta II pro korpus Czes2 program 7za 7za 7za
poznámka originálnˇe bez slovníku se slovníkem
komp. cˇ as k. pamˇet’ pomˇer [min] [MB] 0, 081 27, 5 2564 0, 141 46, 1 2764 0, 143 47, 0 2818
Varianta III Varianta III pracuje se slovníky v základním tvaru. Výstupní soubory byly upraveny do Eliasova delta kódování. Jedná se o binární kódování variabilní délky. Tabulka 4.8: Varianta III pro korpus DESAM program 7za xz 7za xz 7za xz
poznámka originálnˇe originálnˇe bez slovníku bez slovníku se slovníkem se slovníkem
komp. cˇ as k. pamˇet’ pomˇer [s] [MB] 0, 112 4, 5 94 0, 140 25, 7 247 0, 209 4, 8 79 0, 226 2, 8 248 0, 236 5, 7 113 0, 258 4, 2 464
Tabulka 4.9: Varianta III pro korpus Czes2 program 7za 7za 7za
poznámka originálnˇe bez slovníku se slovníkem
komp. cˇ as k. pamˇet’ pomˇer [min] [MB] 0, 081 27, 5 2564 0, 157 58, 9 6154 0, 160 59, 8 7214
52
5 Závˇer Velice cˇ asto projevovaným jevem u komprimace textových dat se ukázala být kompenzace efektivity komprimace na úkor spotˇrebovaného cˇ asu, pˇrípadnˇe pamˇeti. Algoritmy Deflate a Huffmanovo kódování typicky spotˇrebovávají ménˇe cˇ asu a pamˇeti a dosahují horší komprimace. Oproti tomu programy modelující pomocí algoritmu˚ PPM cˇ i složitˇejších CM a používající aritmetické kódování dosahují lepší komprimace, ale spotˇrebovávají více cˇ asu a pamˇeti. Slovníková komprimace se neprojevila v testování na textových korpusech jako nejefektivnˇejší. Programy na bázi algoritmu˚ z rodiny LZ77 se v celkovém pˇrehledu umístily ve stˇrední cˇ ásti tabulky. Dosahovaly tak cˇ asto vyrovnaných výsledku˚ kompresního pomˇeru za spotˇrebovaný cˇ as. Oproti tomu programy využívající algoritmu CM dosahovaly podle použitých modelování ruzných ˚ výsledku. ˚ Zajímavé je, že pokud programy s algoritmem CM dosáhly dobrého kompresního pomˇeru, vždy to bylo kompenzováno daleko vˇetší spotˇrebou cˇ asu. Na textovém korpusu DESAM dosáhl nejlepšího kompresního pomˇeru program DURILCA. Z celkových dvaceti testovaných programu˚ dosáhlo deset programu˚ lepší komprimace než souˇcasnˇe používaný program XZ v Laboratoˇri pro zpracování pˇrirozeného jazyka pˇri Masarykovˇe univerzitˇe. Šest programu˚ dosáhlo pˇri testech na korpusu DESAM lepšího kompresního pomˇeru a zárovenˇ kratší doby bˇehu programu, z tˇechto si nejlépe vedly programy 7-Zip a NanoZip. U textového korpusu Czes2 se podaˇrilo všem úspˇešným programum ˚ dosáhnout lepší komprimace než na korpusu DESAM, což indikuje vˇetší redundanci dat u vˇetšího z korpusu. ˚ Testování na rˇ ádovˇe vˇetším korpusu Czes2 devˇet programu˚ z dvaceti nedokonˇcilo. Nejlepšího kompresního pomˇeru tak dosáhl program paq9a, spotˇreboval však oproti programu XZ daleko více cˇ asu. Pouze další dva programy dokázaly významnˇe pˇredˇcit program XZ v síle komprimace i délce bˇehu, a to programy 7-Zip a NanoZip. Rozdˇelení korpusu DESAM podle jednotlivých sloupcu˚ na samostatné soubory se neukázalo být efektivním. Naopak došlo ke zhoršení kvality komprimace i zvýšení cˇ asové nároˇcnosti použitého 53
ˇ 5. Z ÁV ER
komprimaˇcního programu. Komprimace po cˇ ástech se taktéž ukázala být neefektivní z hlediska dosaženého kompresního pomˇeru i délky komprimace. Podobnˇe dopadlo porovnání komprimace s použitím slovníkového pˇredzpracování. Žádná ze tˇrí testovaných variant nezvýšila efektivitu vykonávané komprimace.
54
Seznam tabulek 2.1 2.2
Ilustraˇcní tabulka, cˇ ást 1. 22 Ilustraˇcní tabulka, cˇ ást 2. 23
3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20
Aplikace programu BBB na korpus DESAM 27 Aplikace programu BZip2 na korpus DESAM 27 Aplikace programu comprolz na korpus DESAM 28 Aplikace programu comprox na korpus DESAM 29 Aplikace programu crook na korpus DESAM 30 Aplikace programu ctw na korpus DESAM 31 Aplikace programu DURILCA na korpus DESAM 32 Aplikace programu fpaq3d na korpus DESAM 33 Aplikace programu Gzip na korpus DESAM 33 Aplikace programu lpaq1 na korpus DESAM 34 Aplikace programu lrzip na korpus DESAM 35 Aplikace programu Lzip na korpus DESAM 35 Aplikace programu LZPXj na korpus DESAM 36 Aplikace programu NanoZip na korpus DESAM 38 Aplikace programu Ocamyd na korpus DESAM 39 Aplikace programu paq9a na korpus DESAM 40 Aplikace programu TinyCM na korpus DESAM 40 Aplikace programu XZ na korpus DESAM 42 Aplikace programu Zip na korpus DESAM 43 Aplikace programu 7-Zip na korpus DESAM 44
4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9
Souhrn programu˚ na korpusu DESAM 46 Souhrn programu˚ na korpusu Czes2 48 Komprimace po cˇ ástech 49 Varianta I pro korpus DESAM 50 Varianta I pro korpus Czes2 51 Varianta II pro korpus DESAM 51 Varianta II pro korpus Czes2 52 Varianta III pro korpus DESAM 52 Varianta III pro korpus Czes2 52
55
Literatura [1] K. Sayood, Introduction to data compression, 3rd ed. San Francisco: Morgan Kaufmann Publishers, 2006. [2] I. M. Pu, Fundamental data compression. Oxford: ButterworthHeinemann, 2006. [3] M. Mahoney, Data Compression Explained. Dell, Inc., 2013, [Accessed 2013-10-08]. [Online]. Available: http: //mattmahoney.net/dc/dce.html [4] C. E. Shannon and W. Weaver, The mathematical theory of communication. University of Illinois Press, c1998. [5] C. E. Shannon, “A mathematical theory of communication,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. vol. 5, no. issue 1, pp. 3– , 2001-01-01, [Accessed 2014-05-12]. [Online]. Available: http://portal.acm.org/citation.cfm?doid=584091.584093 [6] R. M. Fano, “Transmission of information,” American Journal of Physics, vol. vol. 29, no. issue 11, pp. 793–, 1961, [Accessed 2014-05-12]. [Online]. Available: http://scitation.aip. org/content/aapt/journal/ajp/29/11/10.1119/1.1937609 [7] S. Shanmugasundaram and R. Lourdusamy, “A comparative study of text compression algorithms,” International Journal of Wisdom Based Computing, vol. 1, no. 3, pp. 68–76, 2011. [8] D. Huffman, “A method for the construction of minimumredundancy codes,” Proceedings of the IRE, vol. vol. 40, no. 9, pp. 1098–1101, 1952, [Accessed 2013-12-04]. [Online]. Available: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper. htm?arnumber=4051119 [9] A. N. Kolmogorov, “Three approaches to the quantitative definition of information *,” International Journal of Computer Mathematics, vol. vol. 2, no. 1-4, pp. 157–168, 1968, [Accessed 56
ˇ 5. Z ÁV ER
2013-12-04]. [Online]. Available: http://alexander.shen.free.fr/ library/Kolmogorov65_Three-Approaches-to-Information.pdf [10] G. V. Cormack and R. N. Horspool, “Data compression using dynamic markov modelling,” The Computer Journal, vol. 30, pp. 541–550, 1986. [11] D. Salomon, Data Compression, 3rd ed. 2004.
New York: Springer,
[12] J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Transactions on Information Theory, vol. vol. 23, no. issue 3, pp. 337–343, 1977, [Accessed 201312-04]. [Online]. Available: http://ieeexplore.ieee.org/lpdocs/ epic03/wrapper.htm?arnumber=1055714 [13] J. loup Gailly and M. Adler, “The gzip home page,” 2003, [Accessed 2013-12-13]. [Online]. Available: http://www.gzip. org/ [14] M. Mahoney, “Large text compression benchmark,” [Accessed 2013-10-08]. [Online]. Available: http://mattmahoney.net/dc/ text.html [15] “Charles bloom’s page : Compression : Source code : Dictionary coder,” 1995, [Accessed 2013-12-05]. [Online]. Available: http://www.cbloom.com/src/index_lz.html [16] I. Pavlov, “7z format,” 2013, [Accessed 2013-12-02]. [Online]. Available: http://7-zip.org/7z.html [17] M. Burrows, D. J. Wheeler, M. Burrows, and D. J. Wheeler, “A block-sorting lossless data compression algorithm,” Tech. Rep., 1994. [18] “The open group,” 2013, [Accessed 2013-12-01]. [Online]. Available: http://pubs.opengroup.org/onlinepubs/9699919799/ [19] “Man-cgi home page,” 2000, [Accessed 2013-12-01]. [Online]. Available: http://unixhelp.ed.ac.uk/CGI/man-cgi?time 57
ˇ 5. Z ÁV ER
[20] P. Rychlý, “Manatee/bonito–a modular corpus manager,” 1st Workshop on Recent Advances in Slavonic Natural Language Processing, pp. 65–70, 2007. [21] “Zpravodaj Úvt mu,” 1997. [22] “Corpora/czes – sketch engine,” 1999, [Accessed 201312-03]. [Online]. Available: http://www.sketchengine.co.uk/ documentation/wiki/Corpora/czes [23] “Bzip2 : Home,” 1996, [Accessed 2013-12-13]. [Online]. Available: http://www.bzip.org/1.0.5/bzip2-manual-1.0.5.html [24] C. Kolivas, “The kernel patch homepage of con kolivas,” 2014, [Accessed 2013-12-05]. [Online]. Available: http://users. on.net/~ckolivas/kernel/ [25] A. D. Diaz, “Lzip - lzma lossless data compressor,” 2014, [Accessed 2014-05-12]. [Online]. Available: http://www.nongnu.org/lzip/lzip.html [26] S. Runsas, “Nanozip,” 2008, [Accessed 2014-05-12]. [Online]. Available: http://nanozip.net/ [27] F. Schwellinger, “Ocamyd,” 2008, [Accessed 2014-05-12]. [Online]. Available: http://www.geocities.ws/ocamyd/ [28] I. Pavlov, “Lzma sdk (software development kit),” 2013, [Accessed 2013-12-01]. [Online]. Available: http://7-zip.org/ sdk.html [29] L. Collin, “The tukaani project,” [Accessed 2013-12-01]. [Online]. Available: http://tukaani.org/xz/ [30] “Info-zip home page,” 1995, [Accessed 2013-12-13]. [Online]. Available: http://www.info-zip.org/
58
A Obsah CD K bakaláˇrské práci je pˇriloženo CD, na kterém se nachází: •
binární soubory všech testovaných programu, ˚
•
skripty použité k testování komprimaˇcních programu˚ na korpusech,
•
textové soubory s kompletními výsledky všech testovaných programu, ˚
•
skripty sloužící k rozdˇelení korpusu a samostatné komprimaci dílˇcích souboru˚ korpusu,
•
skripty použité k testování pˇredzpracovaných dílˇcích souboru˚ korpusu,
•
skripty pro úpravu textových dat získaných testováním programu˚ do formátu tabulek.
Pˇriložené skripty provádˇející testování nelze spustit bez úprav, jelikož nejsou pˇriloženy použité korpusy, které nejsou veˇrejnˇe pˇrístupné. Pro správný chod je tˇreba nahradit cesty ke zdrojovým datum. ˚
59
