Aritmetické kódování nad abecedou slabik

Abstract

Slabiková komprese je nová metoda komprese textu, nabízející zajímavý kompromis mezi kompresí po znacích a po celých slovech, která by měla být výhodná především pro soubory střední velikosti. Slabiky jsou pro kódování vhodné, neboť přirozeně tvoří logické často se opakující jednotky, ze kterých se skládají celá slova. Nevýhodou slabik je, že datové struktury s nimi pracující se musí vyrovnat s teoreticky nekonečnou množinou slabik, která se může v textu vyskytnout. Tato diplomová práce se zaměřuje na využití aritmetického kódování pro slabikovou kompresi a použití rychlých a efektivních datových struktur pro statistický model a slabikový kontext. V práci je popsán nový aritmetický slabikový kompresní algoritmus AritSyll, který vychází z algoritmu HuffSyll. Značného vylepšení, oproti HuffSyll, doznal slabikový kontextový model, který je v AritSyllu dlouhý až tři slabiky a lépe reprezentuje skladbu věty v přirozeném jazyce, a statistický model, který je inicializován statistickými informacemi lišící se podle zvoleného jazyka, pro lepší kompresi souborů malé velikosti. Kromě "klasických" textových souborů s osmibitovou velikostí znaku, je pomocí AritSyllu možné efektivně kódovat i textové soubory v kódování UTF8. Implementovaný slabikový kompresní algoritmus je srovnáván s jinými znakovými i slovními...

A syllablebased compression is a new method of a text compression, offering interesting tradeoff between a characterbased compression and a wordbased compression. Syllablebased compression should be best suited for middle sized files. Syllables are favorable, because they are forming logical units, which words are composed of. Syllables have disadvantage that data structures working with them must deal with infinite set of syllables. This thesis is focused to usage of arithmetic coding for syllablebased compression and usage of fast and effective data structures for a statistical model and a syllable context. In this thesis is described new arithmetic syllablebased compression algorithm AritSyll, which is based on the HuffSyll algorithm. A considerable improvement is new syllable context, which is up to three syllables long and which better represents sentences in a language. The next improvement is statistical model, which is initialized with statistical information based on selected language, for better compression of small sized files. With the AritSyll is possible to effectively encode text files in UTF8 coding. Implemented syllablebased compression algorithm is compared with other characterbased, wordbased compression algorithms.