Hierarchická komprese
| Název práce v češtině: | Hierarchická komprese |
|---|---|
| Název v anglickém jazyce: | Hierarchical compression |
| Klíčová slova: | textová komprese, trie, gramarická komprese, hierarchie |
| Klíčová slova anglicky: | text compression, trie, grammar based compression, hierarchy |
| Akademický rok vypsání: | 2007/2008 |
| Typ práce: | diplomová práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra softwarového inženýrství (32-KSI) |
| Vedoucí / školitel: | RNDr. Jan Lánský, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 12.11.2007 |
| Datum zadání: | 12.11.2007 |
| Datum a čas obhajoby: | 31.01.2011 11:00 |
| Datum odevzdání elektronické podoby: | 10.12.2010 |
| Datum odevzdání tištěné podoby: | 10.12.2010 |
| Datum proběhlé obhajoby: | 31.01.2011 |
| Oponenti: | doc. RNDr. Tomáš Dvořák, CSc. |
| Zásady pro vypracování |
| Při gramatické kompresi se vstupní soubor reprezentuje pomocí bezkontextové gramatiky, kterou následně komprimujeme místo původního souboru. Hierarchická komprese je speciálním případem gramatické komprese, splňující následující pravidla: Jednotlivé neterminály jsou rozděleny do skupin (úrovní) 1,...,n-1. Terminály tvoří jednu skupinu s číslem n. Úroveň 1 obsahuje pouze neterminál S. Pravidla mohou být pouze tvaru X-->Y_1,..,Y_m, kde m>= 1 a pokud X je neterminál ze skupiny i, pak Y_j jsou neterminály či terminály ze skupiny i + 1. Cílem práce je navrhnout. implementovat a otestovat bezeztrátovou kompresní metodu založenou na myšlence hierarchické komprese. |
| Seznam odborné literatury |
| 1) Pokorný, J., Žemlička, M.: Základy implementace souboru a databází 2. vydání, Praha, Karolinum 2004.
2) Lánský, J., Žemlička, M.: Compression of a Dictionary. In: Snášel, V., Richta, K., and Pokorný, J.: Proceedings of the Dateso 2006 Annual International Workshop on DAtabases, TExts, Specifications and Objects. CEUR-WS, Vol. 176, pg. 11-20. 3) Lánský, J., Žemlička, M.: Text Compression: Syllables. In: Richta, K., Snášel, V., Pokorný, J.: Proceedings of the Dateso 2005 Annual International Workshop on DAtabases, TExts, Specifications and Objects. CEUR-WS, Vol. 129, pg. 32-45. 4) Kieffer, J. C., Yang, E. H.: Effcient Universal Lossless Data Compression Algorithms Based on a Greedy Sequential Grammar Transform. IEEE Transactions on Information Theory, 46:755-777, 2000. |