Hlavní navigace

Unixová komprese v praxi: Bzip2

Petr Krčmář 28. 4. 2003

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ů.

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.

Našli jste v článku chybu?

15. 6. 2011 14:27

Majkl (neregistrovaný)

Řekl bych že s tím poměrem náročnosti kódování a dekódování u BW transformace nemáte pravdu.
Při kódování musíte třídit jednotlivé rotované kopie originálního bloku a je jich stejně jako znaků v původním bloku.
Složitost komprese by mohla být O(n x log_2(n) x n/2).
Naproti tomu v dekódování se použijí dva nevnořené cykly z nichž jeden obsahuje prohledání části permutovaného bloku. Tedy O(n * log_2(n/2) + n).
Implementoval jsem a vskutku je dekódování řádově rychlejší a je také paměťově méně náro…



7. 5. 2003 14:11

Honza (neregistrovaný)

Co to je "obecny salat"? Nahodna data pochopitelne nezkomprimuje nic, a u jinych by chtelo lepe upresnit, jaky "salat" mate na mysli.

Uz jsem taky potkal data, ktera bzip2 komprimuje hure, ale je to spise vyjimka nez pravidlo.



Vitalia.cz: Jak koupit Mikuláše a nenaletět

Jak koupit Mikuláše a nenaletět

Podnikatel.cz: Platební brány a EET? Stále s otazníkem

Platební brány a EET? Stále s otazníkem

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Podnikatel.cz: Přivýdělek u Airbnb nebo Uberu? Čekejte kontrolu

Přivýdělek u Airbnb nebo Uberu? Čekejte kontrolu

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel

DigiZone.cz: Flix TV má set-top box s HEVC

Flix TV má set-top box s HEVC

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony

Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí

Měšec.cz: Finančním poradcům hrozí vracení provizí

Finančním poradcům hrozí vracení provizí

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu