Hlavní navigace

Unixová komprese v praxi: Bzip2

28. 4. 2003
Doba čtení: 5 minut

Sdílet

Bzip2 je poměrně mladý, ovšem velmi nadějný kompresní prográmek Juliana Stewarda, který už delší dobu útočí na pozice oblíbeného gzipu. Dnes se mu podíváme na zoubek.

Bzip2 je přenositelný, bezztrátový datový kompresor založený na Burrows-Wheelerově transformaci. Existuje pro velké množství platforem a je psán tak, aby jej bylo možno bez problémů portovat na další. Je k dispozici ve dvou podobách. Jako klasický kompresní program, nebo jako knihovna, kterou můžou vývojáři jednoduše začlenit do svých dalších projektů. Opět, podobně jako gzip, není zatížen žádnými patenty ani nepříjemnými licencemi. Bzip2 se snaží stát novým nástupcem gzipu. Existuje sice teprve od roku 1996, stihl si už ale najít mnho příznivců.

Burrows-Wheelerova transformace je poměrně novou metodou, která sama o sobě data nezhušťuje. Dokáže je ale „předžvýkat“ před samotnou kompresí tak, že je jejich následná komprese mnohem účinnější. Tato metoda byla vynalezena už v roce 1984, publikována byla ale až roku 1994. Vidíte, že je skutečně velmi mladá. Transformace je úplně jednoduchá a přitom geniální (tak už to ve světě chodí – většina geniálních věcí je naprosto banální, ale … vymyslete to). Je tak jednoduchá, že si ji můžeme ukázat na příkladu:

Nejlépe se komprimují data, kde se opakuje jedna sekvence často za sebou, čili něco jako:

aaaaaabbbbcccccccc

Pak si kompresní algoritmus zaznamená jenom:

6 x a, 4 x b, 8 x c

a je to, ale přiznejme si to otevřeně: Kolik takových souborů asi existuje? Akorát tak … pár.

A právě Burrows-Wheelerova transformace umožní jakýkoliv soubor dat přeskládat do podobného tvaru pro lepší kompresi a (a to je hodně podstatné) umí jej pak vrátit do původní podoby. Vezměme si jako příklad slovo alabama. V praxi se pochopitelně bzip2 zabývá delšími sekvencemi, ale pro náš příklad je tahle dostatečná. Vidíte, že slovo alabama obsahuje čtyři písmena a. Pokud se nám podaří dostat je k sobě, budeme mít pěkně komprimovatelný blok dat.

Nejdřív náš blok dat necháme rotovat (posouvat písmena jedním směrem s tím, že to, které se nám dostane za konec, dáme zase na začátek) a zapíšeme si všechny jeho podoby pod sebe. Vznikne nám:

alabama
labamaa
abamaal
bamaala
amaalab
maalaba
aalabam

Pak setřídíme řádky jednoduše podle abecedy:

aalabam
abamaal
alabama
amaalab
bamaala
labamaa
maalaba

A je vlastně hotovo. Že nic nevidíte? Podívejte se na poslední sloupec. Je tam:

mlabaaa

Vidíte ta tři áčka? K tomu, aby byl proces vratný, si program ještě musí zaznamenat řádek, na kterém byl po setřídění původní blok dat, což je v našem případě řádek tři. Takže na úplném konci nám z bloku dat alabama vznikl blok mlabaaa3. Pak už provedeme klasickou kompresi. Zpětný chod si už můžete odvodit sami. Jenom vám poradím, že znáte první a poslední sloupec naší matice (ten druhý je setříděný podle abecedy) a hledáte jeden známý řádek. Když jsme si vysvětlili princip algoritmu, řekněme si, co nám z něj plyne:

  1. Je jasné, že čím víc budeme zvětšovat vstupní blok dat, tím víc nám poroste efektivita algoritmu. Ideální by bylo vzít najednou celý komprimovaný soubor. To je ale velmi paměťově náročné, proto volíme rozumný kompromis (řádově stovky kilobajtů).
  2. Nelze nijak volit dobu provádění jako u jiných algoritmů, a tím měnit kompresní poměr. Jediným nastavitelným faktorem je v tomto případě velikost vstupních dat, která ovlivňuje kompresní poměr.
  3. Komprese i dekomprese je paměťově velmi náročná. Je náročnější i na výkon procesoru, což může být u slabších strojů velmi znát.

V praxi je ovládání bzip2 úplně stejné jako ovládání gzip. Je to tak zařízeno schválně, aby měl uživatel přecházející od gzip k bzip2 co nejméně práce. Navíc, pokud používáte oba, nemusíte si pamatovat dvoje různé parametry. K ovládání jen tolik, že existuje podobná sada příkazů jako u gzip a jsou to: bzip2, bunzip2 a bzcat.

Při kompresi můžeme zvolit velikost vstupního bloku parametry –1 až –9. Číslo nám udává velikost krát sto kilobajtů. Při dekompresi nemá tato volba žádný vliv. Ovšem objevuje se nám tady malý paradox. Je jasné, že pokud zvolíme největší možný blok, získáme tak nejlepší kompresní poměr. Problém ovšem nastane ve chvíli, kdy se takto komprimovaný soubor dostane k někomu, kdo má hodně málo paměti (4 MB). Při dekompresi totiž musíme používat stejně velké bloky, které jsme použili při kompresi. Proto musíme na strojích s takto malým množstvím paměti použít při dekompresi parametr -s, ten přepne bzip2 do úspornějšího režimu, při kterém mu stačí polovina paměti než běžně, ale za cenu dvojnásobné doby dekomprese. V dnešní době stovek megabajtů paměti se sice může takové upozornění zdát směšné, ale nesmíme zapomenout na to, že ještě poměrně velká část uživatelů používá například starší notebooky, kde je rozšíření paměti přinejmenším problematické.

Velkou výhodou, která je také častým argumentem pro náhradu gzipu bzipem2, je možnost záchrany dat z poškozeného souboru. Algoritmus gzip má tu nepříjemnou vlastnost, že pokud se nám ztratí jenom jediný bitík, jsou všechna následující data zcela znehodnocena a jejich záchrana je téměř nemožná. Naproti tomu bzip2 nekomprimuje data najednou, ale po už zmíněných blocích, které jsou na sobě nezávislé. Pokud je tedy jeden blok poškozen, ostatní jsou v pořádku a můžeme z nich informaci zachránit. Každý blok je navíc opatřen svým vlastním kontrolním součtem a lze tak jednoduše zkontrolovat, které bloky jsou poškozené a které ne. K obnově takto poškozených dat slouží program bzip2recover, který rozdělí velký archiv na jednotlivé bloky a zapíše je do samostatných očíslovaných souborů. Ty lze pak jednoduše najednou dekomprimovat a zachránit tak data z nepoškozených blo­ků.

root_podpora

Je jasné, že tímto způsobem můžeme zachránit jen soubory, které se skládají z více než jednoho bloku. Pokud máme poškozený soubor, který měl původně 20KB, obsahuje archiv jenom jeden, poškozený blok a z něj už nic zpět nezískáme. Chceme-li snížit riziko větší ztráty, měli bychom při kompresi zvolit co nejmenší vstupní bloky.

Bzip2 je velmi nadějným pokračovatelem gzip, jehož většímu rozšíření brání snad jenom náročnost na procesorový čas a paměť, které jsou ale vyváženy lepším kompresním poměrem a menším rizikem ztráty dat.

Byl pro vás článek přínosný?

Autor článku

Petr Krčmář pracuje jako šéfredaktor serveru Root.cz. Studoval počítače a média, takže je rozpolcen mezi dva obory. Snaží se dělat obojí, jak nejlépe umí.