Algoritmy pro kompresi dat: slovníkové metody

LZ77

Metodu LZ77 publikovali v roce 1977 izraelští vědci Abraham Lempel a Jacob Ziv. Má mnoho modifikací a je použita např. jako základ algoritmu Deflate. Jádrem metody je pohyblivé okno (sliding window), do kterého tečou zprava doleva nekomprimovaná data.

Kodér vstupující data analyzuje a na výstup produkuje kódová slova neboli značky. Dekodér načítá vyprodukované značky a na jejich základě rekonstruuje původní datový tok, který pak z pohyblivého okna vytéká.

Pohyblivé okno je rozděleno na vyhledávací a předvídací část čili buffer. Vyhledávací buffer slouží jako slovník, proto se metoda řadí mezi slovníkové kompresní metody. Vyhledávací buffer je typicky dlouhý desítky kilobajtů, předvídací naproti tomu desítky bajtů. Kompresor se snaží nalézt obsah předvídacího bufferu v bufferu vyhledávacím. Na výstup pak produkuje značky s informací o místě a délce nalezené shody. Čím delší shodu se podaří nalézt, tím větší komprese je vytvořením značky dosaženo.

Značku konkrétně tvoří prvky (offset, délka, symbol). Prvek offset je pozice ve vyhledávacím bufferu, na které byl nalezen nekomprimovaný řetězec shodný s fragmentem na počátku předvídacího bufferu. Prvek délka je délka tohoto řetězce a symbol je následující symbol, který byl už neshodný.

V následujícím případě jsou nalezeny 2 shody „eas“ na pozicích 8 a 13. Pro jednoduchou implementaci se použije poslední shoda. Vytvoří se tedy značka  (13, 3, 'e').

Prvky značky se zakódují na odpovídajícím počtu bitů ⌈log₂S⌉, ⌈log₂(L−1)⌉, ⌈log₂A⌉, kde A je velikost abecedy. Při nenalezení shody se generuje značka ve tvaru (0, 0, symbol) .

Shoda může překročit hranici vyhledávacího bufferu. V následujícím případě bude vytvořena značka (1, 5, 't') .

Poslední symbol předvídacího bufferu musí být vždy zakódován jako prvek značky symbol, což je také důvod pro počet bitů ⌈log₂(L−1)⌉ prvku značky délka . LZ77 předpokládá, že fragmenty se vyskytují blízko u sebe, tj. že nebyla ještě vysunuta z vyhledávacího bufferu. Existuje množství vylepšení této metody, např. značky proměnné délky, důmyslné datové struktury nebo zrušení posledního pole značky.

LZ78

Metodu LZ78 publikovali A. Lempel a J. Ziv v roce 1978. Opět má několik modifikací, např. algoritmus LZW. Na rozdíl od LZ77 nemá pohyblivé okno, ale opravdový slovník, ve kterém jsou fragmenty nekomprimovaného souboru identifikovány pomocí indexu neboli ukazatele do slovníku. Metoda je v praxi náročná na paměť, což lze řešit různě, např. vhodnou datovou strukturou k udržování slovníku.

Tato vhodná struktura může být trie (forma datové struktury strom). V tomto případě je první položka slovníku prázdný řetězec (kořen stromu). Kodér vytváří značky ve tvaru (index, symbol). Při kompresi se vyhledá nejdelší shodný řetězec obsažený ve slovníku a vygeneruje se značka s jeho indexem a následujícím symbolem, který způsobil neshodu. Každá značka přitom udává nový řetězec, který je třeba umístit do slovníku. Dekodér načítá značky, rekonstruuje nekomprimovaný soubor a přitom si buduje slovník stejně jako kodér.

Následuje příklad zakódování řetězce ABRAKADAKABRA . Odpovídající slovník tvořený datovou strukturou trie je vyobrazen na obrázku výše. Výstupem komprese je sedm značek. SymbolEOF signalizuje dekodéru konec dat. Postupem času se do slovníku dostávají delší fragmenty vstupu a roste účinnost komprese:

1. Na počátku je prázdný slovník (pouze kořen).
2. Řetězce „A“, „B“, „R“ se zakódují jako značky (0, 'A'), (0, 'B'),  (0, 'R').
3. Dále „AK“ a „AD“ se přidají pod uzel ‚A‘ a zakódují se jako (1, 'K'),  (1, 'D').
4. Stejně se zakóduje „AKA“, „BR“ a poslední „A“ jako (4, 'A'), (2, 'R'),  (1, EOF).

LZW

LZW je varianta LZ78, kterou vyvinul v roce 1984 americký vědec Terry Welch. Je použita např. ve formátech GIF, TIFF nebo PDF. Stejně jako u LZ78 je zde použit slovník, který je na počátku inicializován na všechny symboly vstupní abecedy. Značka má však již pouze jedno pole (index). Kodér pracuje podle následujícího algoritmu.

1. Ve vstupu hledá nejdelší řetězec I obsažený ve slovníku.
2. Následující symbol x způsobí, že řetězec Ix ve slovníku již není.
3. Na výstup nyní vyšle index řetězce I, uloží řetězec Ix do slovníku, řetězec I dále bude jen symbol x.
4. Pokračuje se krokem 1.

Dekodér pracuje následovně.

1. Načte index a zapíše odpovídající řetězec I na výstup.
2. Je třeba přidat do slovníku řetězec Ix, ale symbol x ještě není znám.
3. Načte se další index, na výstup zapíše odpovídající řetězec J, jeho první znak je symbol x.
4. Nyní může dekodér uložit řetězec Ix do slovníku, řetězec J bude dále řetězec I.
5. Pokračuje se bodem 2.

Deflate

Metoda Deflate je použita ve formátech ZIP (původně), zlib, gzip, 7-Zip, PNG, MNG nebo PDF. Je to kombinace LZ77 a Huffmanova kódování. Na rozdíl od LZ77 mají značky jen dvě pole (offset, délka). Scházející položka (symbol) se zapisuje do výstupního toku separátně. Komprimovaný tok se tedy skládá ze tří entit: symbolů neboli literálů, offsetů neboli vzdáleností shody a délek shody.

Tyto entity se kódují pomocí Huffmanových kódu za pomoci dvou tabulek (literály/délky a vzdálenosti). Velikost vyhledávacího bufferu je až 32 kB. Data se komprimují nezávisle po blocích různé délky. Dekodér musí být schopen dekomprimovat bloky libovolné délky. Metoda definuje 3 režimy komprese:

• bez komprese (blok může mít maximálně 65 535 bajtů, užitečné pro nekomprimovatelná data a pro segmentaci souborů),
• komprese s fixními tabulkami kódů (urychlí zpracování, sníží kompresní poměr, tabulky netřeba zapsat do výstupního toku) a
• komprese s tabulkami zapsanými do komprimovaného toku (vyšší kompresní poměr, protože tabulky mohou být sestaveny na základě četnosti výskytu symbolů ve vstupním toku, tabulky jsou do výstupu zapsány speciální kompresí).

Přitom každý blok může být komprimován v jiném režimu komprese. Metoda je na implementaci více komplikovaná.

Na rozdíl od původní LZ77 může kompresor odložit výběr shody a zakódovat první znak předvídacího bufferu jako literál.

V tomto případě Deflate nevybere(11, 3) = „the“, ale „t“ zakóduje jako literál a vybere(20, 5) = „he#ne“. Tento odklad shody je při kompresi řízen parametrem – normální režim, režim vysoké komprese, rychlý mód. V rychlém módu je hledání odložené shody zcela vynecháno. V režimu vysoké komprese provede kompresor vždy úplné hledání, což je ale časově náročné. V normálním režimu může kompresor provést redukované hledání – jak moc je hledání redukováno je záležitostí konkrétního kompresoru.

Protože lineární hledání shody v bufferu velikosti až 32 kB je dosti časově náročné, je k hledání této shody ve specifikaci Deflate silně doporučeno použít hashovací funkci. Kompresor, který bude hledat shodu jiným způsobem, však může také produkovat platný formát dat Deflate. Toto hledání řetězců pomocí hashovací funkce je význačným rysem metody Deflate.

(Autorem obrázků je David Bařina.)