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:
- 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ů).
- 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.
- 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 bloků.
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.