Veškerý kód k metodě bwt je obsažen v souborech m_bwt.[hc] (navíc je využíván kód metody ahc ze souborů m_ahc.[hc]). Pro obecné seznámení s principy bwt doporučuji [1].
Veškerá komprese se provádí po blocích jejichž velikost je přímo úměrná kvalitě komprese. Burrows-Wheelerova transformace (viz [2]) je implementována fcí do_bwt(in_buf, out_buf, len, idx_buf), která provede transformaci vstupního bufferu in_buf (o délce len) na výstupní buffer out_buf. Oproti nejzákladnější implementaci transformace jsou tyto vylepšení : kruhový buffer není nový buffer, ale pole ukazatelů do vstupního bufferu (idx_buf), k urychlení třídění (které se provádí pomocí standardního qsort()) se na konec vstupního bufferu přimyslí tzv. eof znak, který má větší hodnotu než kterýkoliv jiný znak, tím pádem není třeba porovnávat kruhové řetězce, ale pouze suffixy vstupu. Jen je třeba zachovávat tento eof znak v průběhu celé komprese i dekomprese. Tímto bylo dosaženo přibližně dvojnásobného zrychlení. Toto vylepšení se zakládá na myšlence z článku Marka Nelsona (viz [3]). I přes toto vylepšení je komprese velice pomalá a to kvůli quicksortu. Ten dosahuje nejhorších výsledků na datech s vysokým podílem opakujících se úseků (je nutno porovnávat dlouhé bloky). Bohužel toto je přesně to, co způsobuje úspěšnost této transformace a vyskytuje se v běžných datech poměrně často. Proto byla vyzkoušena i odlišná metoda třídění a to suffixový strom. Bohužel se ukázalo, že časový zisk není tak vysoký, aby převýšil paměťovou náročnost (až 40-krát vyšší než u quicksortu). Zde je srovnání složitostí :
| qsort | stree | |
|---|---|---|
| časová | O(N*log(N)) | O(N) |
| paměťová | O(N) | O(N) |
To nevypadá tak zle, ale v absolutních číslech je vidět něco jiného : stree spotřebuje přibližně 20 bytů na uzel (v mé implementaci, normálně je to 16 bytů, ale s dodatečnými nároky při procházení stromu) při maximálním počtu 2*N uzlů. Implementace se suffixovým stromem je v adresáři bwt_as_stree, ale pozor, na některých datech třídí špatně a tedy i generuje špatné výstupy.
Dále navazuje Move-to-front kódování implementované fcí do_mtf(buffer, len), které se nijak neliší od běžných implementací.
Následně se výstup kóduje pomocí ahc (adaptivního huffmanova kódování), přičemž se nejdříve provede zakódování řetězců nul do dvojice (0, délka-1), to je víceméně postup navrhovaný v [1]. Řetězce nul jsou ve výstupu z mtf velice časté, takže se tím dosáhne výrazného zlepšení kompresního poměru, přibližně o čtvrtinu.
Komprimovaná data se nejprve proženou dekompresí pomocí ahc, v průběhu dekomprese se plynule dekódují zakódované řetézce nul.
Poté následuje zpětné mtf (fce rev_mtf(buffer, len)), na němž není nic zajímavého.
Zpětná Burrows-Wheelerova transformace je implementována funkcí rev_bwt(in_buf, op, out_buf, buf_len, tbuf), která transformuje in_buf do out_buf, op je pozice původních dat v setříděném bufferu a tedy i pozice jediného výskytu eof znaku v bufferu. Transformuje se pomocí konstrukce transformačního vektoru v tbuf.
Komprese je velice pomalá : oproti programu gzip (který používá slovníkovou kompresi) nebo programu bzip2 (který používá bwt) může být až 50-krát pomalejší - zde se projevuje pomalé třídění pomocí qsort(), bzip2 používá také qsort, ale modifikovaný (s vyšší paměťovou náročností). Kompresní poměr je vyšší než u programu gzip a je porovnatelný s programem bzip2 (horší v řádech desetin procenta). Dekomprese je velice rychlá, srovnatelná s ostatními programy.
This document was generated using AFT v5.095