Název:
Slovníkové metody jako druhá fáze BWT
Překlad názvu:
Dictionary methods as second phase of BWT
Autoři:
Kovalčin, Stanislav ; Žemlička, Michal (oponent) ; Lánský, Jan (vedoucí práce) Typ dokumentu: Diplomové práce
Rok:
2007
Jazyk:
slo
Abstrakt: [eng][cze] 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.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.