bzip2 (Čeština)

Bzip2 používá několik vrstev kompresních technik naskládaných na sebe, které se během komprese vyskytují v následujícím pořadí a během dekomprese v opačném pořadí:

1. Run-length encoding (RLE) of initial data.
2. Burrows – Wheeler transformation (BWT), or block sorting.
3. Move-to-front (MTF) transformation.
4. Run-length encoding (RLE) of MTF result.
5. Huffman coding.
6. Výběr mezi více Huffmanovými tabulkami.
7. Unární kódování base-1 výběru Huffmanovy tabulky.
8. Delta kódování (Δ) bitových délek Huffmanova kódu.
9. Řídké bitové pole ukazující, které symboly jsou použity.

Initial run-length encodingEdit

Jakákoli sekvence 4 až 255 po sobě jdoucích duplicitních symbolů je nahrazena prvními 4 symboly a délkou opakování mezi 0 a 251. Tedy sekvence AAAAAAABBBBCCCD je nahrazen AAAA\3BBBB\0CCCD, kde \3 a \0 představují hodnoty bajtů 3 a 0. Běhy symbolů jsou vždy transformovány po 4 po sobě jdoucích symbolech, i když je délka běhu nastavena na nulu, aby byla transformace reverzibilní.

V nejhorším případě to může způsobit expanzi 1,25 a v v nejlepším případě snížení na < 0,02. Zatímco specifikace teoreticky umožňuje kódování běhů o délce 256–259, referenční kodér takový výstup neprodukuje.

Autor bzip2 uvedl, že krok RLE byl historickou chybou a byl určen pouze k ochraně původní implementace BWT před patologickými případy.

Burrows – Wheeler transformEdit

Toto je reverzibilní blokování, které je jádrem bzip2. Blok je zcela samostatný a vstupní a výstupní vyrovnávací paměti zůstávají stejné velikosti – v bzip2 je provozní limit pro tuto fázi 900 kB. Pro třídění bloků se vytvoří (fiktivní) matice, ve které řádek i obsahuje celou vyrovnávací paměť, otočenou tak, aby vycházela z i-tého symbolu. Po otočení jsou řádky matice seřazeny v abecedním (číselném) pořadí. Je uložen 24bitový ukazatel označující počáteční pozici, když je blok netransformovaný. V praxi není nutné konstruovat úplnou matici; spíše se třídění provádí pomocí ukazatelů pro každou pozici ve vyrovnávací paměti. Výstupní vyrovnávací paměť je poslední sloupec matice; obsahuje celou vyrovnávací paměť, ale přeuspořádána, takže je pravděpodobné, že bude obsahovat velké série identických symbolů.

Move-to-front transformEdit

Tato transformace opět nemění velikost zpracovaného bloku. Každý ze symbolů používaných v dokumentu je umístěn v poli. Když je symbol zpracován, je nahrazen jeho umístěním (indexem) v poli a tento symbol je zamíchán do přední části pole. Výsledkem je, že okamžitě se opakující symboly jsou nahrazeny nulovými symboly (dlouhé cykly libovolných symbolů se tak stávají cykly nulových symbolů), zatímco ostatní symboly jsou přemapovány podle jejich místní frekvence.

Mnoho „přirozených“ dat obsahuje identické symboly, které se opakují v omezeném rozsahu (text je dobrým příkladem). Vzhledem k tomu, že transformace MTF přiřazuje nízké hodnoty symbolům, které se často objevují, vede to k datovému proudu obsahujícímu mnoho symbolů v rozsahu nízkých celých čísel, přičemž mnoho z nich je identických (různé opakující se vstupní symboly lze ve skutečnosti mapovat na stejný výstupní symbol). Taková data lze velmi efektivně kódovat jakoukoli starší metodou komprese.

Run-length encoding of MTF resultEdit

Long strings of neroos in the output of the move-to-front transform ( které pocházejí z opakovaných symbolů na výstupu BWT) jsou nahrazeny posloupností dvou speciálních kódů, RUNA a RUNB, které představují délku běhu jako binární číslo. Skutečné nuly nejsou nikdy zakódovány do výstupu; osamělá nula se stane RUNOU. (Tento krok se ve skutečnosti provádí současně s MTF; kdykoli by MTF vyprodukoval nulu, místo toho zvýší počitadlo a poté kóduje pomocí RUNA a RUNB.)

Sekvence 0, 0, 0, 0, 0, 1 by byl reprezentován jako RUNA, RUNB, 1; RUNA, RUNB představuje hodnotu 5, jak je popsáno níže. Kód délky běhu je ukončen dosažením jiného normálního symbolu. Tento proces RLE je flexibilnější než počáteční krok RLE, protože je schopen kódovat libovolně dlouhá celá čísla (v praxi je to obvykle omezeno velikostí bloku, takže tento krok nekóduje běh více než 900 000 bajtů). Délka běhu je kódována tímto způsobem: přiřazení hodnot místa 1 k prvnímu bitu, 2 k druhému, 4 k třetímu atd. V pořadí, vynásobte každou hodnotu místa v místě RUNB číslem 2 a přidejte všechny výsledné hodnoty míst (pro hodnoty RUNA i RUNB) společně. Je to podobné jako bijektivní číslování základny-2.Výsledkem posloupnosti RUNA, RUNB je tedy hodnota (1 + 2 × 2) = 5. Složitější příklad:

RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49

Huffman codingEdit

Tento proces nahrazuje symboly pevné délky v rozsahu 0–258 kódy s proměnnou délkou na základě četnosti použití. Častěji používané kódy končí kratší (2–3 bity), zatímco vzácné kódy lze přidělit až 20 bitů. Kódy jsou vybírány opatrně, aby nebylo možné zaměnit žádnou sekvenci bitů za jiný kód.

Kód konce toku je obzvláště zajímavý. Pokud se v nekomprimovaných datech používá n různých bajtů (symbolů), bude se Huffmanovův kód skládat ze dvou RLE kódů (RUNA a RUNB), n – 1 symbolových kódů a jednoho kódu na konci toku. Z důvodu kombinovaného výsledku kódování MTF a RLE v předchozích dvou krocích nikdy není potřeba explicitně odkazovat na první symbol v tabulce MTF (v běžném MTF by byl nulový), čímž se uloží jeden symbol pro koncový of-stream marker (a vysvětlení, proč je ve stromu Huffmana kódováno pouze n – 1 symbolů). V extrémním případě, kdy je v nekomprimovaných datech použit pouze jeden symbol, nebudou ve stromu Huffmana vůbec žádné kódy symbolů a celý blok bude sestávat z RUNA a RUNB (implicitně opakující jeden bajt) a konce -stream značka s hodnotou 2.

0: RUNA, 1: RUNB, 2–257: hodnoty bajtů 0–255, 258: konec streamu, dokončení zpracování (může být až 2).

Více tabulek Huffmana Upravit

S blokem lze použít několik stejně velkých tabulek Huffmana, pokud zisk z jejich použití je větší než náklady na zahrnutí další tabulky. Mohou být přítomny alespoň 2 až 6 tabulek, přičemž nejvhodnější tabulka se znovu vybere před zpracováním každých 50 symbolů. To má tu výhodu, že máme velmi citlivou Huffmanovu dynamiku, aniž bychom museli průběžně dodávat nové tabulky, jak by bylo požadováno v DEFLATE. Kódování běhu v předchozím kroku je navrženo tak, aby se postaralo o kódy, které mají inverzní pravděpodobnost použití vyšší než nejkratší kód Huffman, který se používá.

Unární kódování výběru tabulky HuffmanEdit

Pokud se používá více Huffmanových tabulek, výběr každé tabulky (číslované od 0 do 5) se provádí ze seznamu bitem s nulovým zakončením o délce 1 až 6 bitů. Výběr je do seznamu MTF tabulek. Použití této funkce vede k maximálnímu rozšíření kolem 1,015, ale obecně méně. Je pravděpodobné, že tato expanze bude výrazně zastíněna výhodou výběru vhodnějších Huffmanových tabulek a běžný případ pokračování v používání stejné Huffmanovy tabulky je představován jako jediný bit. Spíše než unární kódování se ve skutečnosti jedná o extrémní formu Huffmanova stromu, kde každý kód má poloviční pravděpodobnost oproti předchozímu kódu.

Delta encodingEdit

Huffmanovy kódové délky bitů jsou k rekonstrukci každého z použitých kanonických Huffmanových stolů. Každá bitová délka je uložena jako zakódovaný rozdíl oproti bitové délce předchozího kódu. Nulový bit (0) znamená, že předchozí bitová délka by měla být duplikována pro aktuální kód, zatímco jeden bit (1) znamená, že by měl být přečten další bit a bitová délka by měla být zvýšena nebo snížena na základě této hodnoty.

V běžném případě se použije jeden bit na symbol na tabulku a nejhorší případ – od délky 1 do délky 20 – bude vyžadovat přibližně 37 bitů. V důsledku dřívějšího kódování MTF začaly délky kódu začínat 2–3 bity dlouhými (velmi často používané kódy) a postupně se zvyšovaly, což znamená, že formát delta je poměrně efektivní a vyžadoval přibližně 300 bitů (38 bajtů) na celou Huffmanovu tabulku .

Sparse bit arrayEdit

Bitmapa se používá k označení, které symboly se používají uvnitř bloku a měly by být zahrnuty do stromů Huffmana. Binární data pravděpodobně využijí všech 256 symbolů, které lze reprezentovat bajtem, zatímco textová data mohou používat pouze malou podmnožinu dostupných hodnot, které možná pokrývají rozsah ASCII mezi 32 a 126. Uložení 256 nulových bitů by bylo neúčinné, pokud by byly většinou nepoužité. Používá se řídká metoda: 256 symbolů je rozděleno do 16 rozsahů a pouze v případě, že jsou v tomto bloku použity symboly, je zahrnuto 16bitové pole. Přítomnost každého z těchto 16 rozsahů je indikována přídavným 16bitovým bitovým polem vpředu.

Celková bitmapa využívá mezi 32 a 272 bity úložiště (4–34 bajtů). Naproti tomu algoritmus DEFLATE by ukázal absenci symbolů kódováním symbolů tak, že mají nulovou délku bitů s kódováním délky běhu a dalším Huffmanovým kódováním.