Slovníkové metody jako druhá fáze BWT

Abstract

Burrows-Wheelerova transformace je jeden z nejoblíbenějších algoritmů používaných při bezztrátové kompresi dat. Druhá fáze obvykle pozůstává z kombinace algoritmů Move-to-front, Run-length encoding a bývá zapsaná Huffmanovým nebo aritmetickým kódováním. Jiná skupina algoritmů pro bezztrátovou kompresi dat používá slovníkové metody prostřednictvím algoritmů rodiny LZ. Tato diplomová práce experimentálně testuje vhodnost zapojení vybraných slovníkových metod (LZC, LZSS) do druhé fáze Burrows-Wheelerove transformace, nejen nad abecedou znaků a slov, ale i slabik. Tato vhodnost je testovaná i na velkých XML souborech. Je proto vhodné navrhnout modifikaci algoritmů druhé fáze Burrows-Wheelerove transformace pro velké abecedy. Je uvedené porovnání kompresního poměru s programy, které využívají Burrows-Wheelerove transformace nejen nad velkými XML soubory ale i nad Calgary korpusem.

Burrows-Wheeler transform is one of the most favorite lossless data compression algorithm. Second phase of Burrows-Wheeler transform consists of combination of Move-tofront, Run-length encoding algorithm and used to be written by Huffman or arithmetic encoding. Dictionary methods are used by means of LZ family algorithm in another lossless data compression algorithm group. This master thesis is experimentally testing suitability of integration selected dictionary methods (LZC, LZSS) in second phase of Burrows-Wheeler transform, not only over alphabet of symbols and words, but also over alphabet of syllables. This suitability is tested likewise on large XML files. It is appropriate to propose modification of Burrows-Wheeler second phase's algorithms for large alphabets. Comparation of compression ratios not only over large XML files, but also over Calgary corpus with others programs using Burrows-Wheeler transform is presented.