Kontextové modely pro statistickou kompresi dat
| Název práce v češtině: | Kontextové modely pro statistickou kompresi dat |
|---|---|
| Název v anglickém jazyce: | Context modelling for statistical data compression |
| Akademický rok vypsání: | 2005/2006 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra softwaru a výuky informatiky (32-KSVI) |
| Vedoucí / školitel: | doc. RNDr. Tomáš Dvořák, CSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 11.11.2005 |
| Datum zadání: | 11.11.2005 |
| Datum a čas obhajoby: | 24.09.2008 00:00 |
| Datum odevzdání elektronické podoby: | 24.09.2008 |
| Datum odevzdání tištěné podoby: | 24.09.2008 |
| Datum proběhlé obhajoby: | 24.09.2008 |
| Oponenti: | RNDr. Michal Žemlička, Ph.D. |
| Zásady pro vypracování |
| Klasické statistické metody bezztrátové komprese dat se obvykle popisují jako algoritmy tvořené dvěma relativně nezávislými fázemi - modelováním a kódováním. Zatímco problém kódování je považován za poměrně uspokojivě vyřešený, otázka tvorby statistického modelu dat je stále předmětem výzkumu. Ačkoli praktické využití komplikovanějších modelů, které obvykle vedou k lepšímu kompresnímu poměru (např. modely typu PPM), v minulosti často naráželo na vysokou prostorovou i časovou náročnost [1,6], v nedávné práci [2] byla navržena řada heuristik a aproximací, které dle publikovaných experimentálních výsledků tento problém částečně eliminují.
Autor by měl nejprve prozkoumat známé přístupy ke tvorbě modelů dat a poté se je pokusit zobecnit se zaměřením na maximální dosahovaný kompresní poměr. Doporučuji pokusit se navázat na myšlenky autorů [2,3] s tím, že kromě obvyklých statistik na úrovni znaků budou uvažovány i modely na vyšší úrovni (slova [4], slabiky [5]) či jejich kombinace, využívající i jiné nežli lineární funkce. |
| Seznam odborné literatury |
| [1] A.Moffat, A.Turpin: Compression and Coding Algorithms. Kluwer Academic Publishers, 2002.
[2] D.Škarin: PPM: One Step to Practicality. Proceedings of the IEEE Data Compression Conference (DCC'2002), 202-211, 2002. [3] M.Mahoney: The PAQ Data Compression Programs. http://www.cs.fit.edu/~mmahoney/compression/ [4] J.Dvorský: Word-based compression methods for information retrieval systems. Diplomová práce MFF UK, Praha, 2003. [5] J.Lánský, M.Žemlička: Text compression: Syllables. In DATESO 2005, ed. by K.Richta, J.Snášel and J.Pokorný, Praha, 2005, pp. 32-45. [6] T.C.Bell, J.G.Cleary, I.H.Witten: Text compression. Prentice Hall, 1990. |
| Předběžná náplň práce |
| Cílem práce je porovnat známé přístupy k modelování dat pro statistickou kompresi a pokusit se o jejich zobecnění se zaměřením na maximální kompresní poměr. |