Master's Thesis

Data compression using dynamic Markov coding

Final Thesis 1.26 MB Appendix 5.67 MB

Author of thesis: Ing. Lucie Smíšková

Acad. year: 2025/2026

Supervisor: doc. Ing. Zdeněk Vašíček, Ph.D.

Reviewer: Ing. Marcela Zachariášová, Ph.D.

Abstract:

This thesis focuses on lossless data compression using dynamic Markov coding (DMC). In the first part of this text, we describe several entropy encoding methods and discuss the topic of dynamic Markov coding. We briefly explain the binary version of DMC and examine in greater detail the extension to a non binary alphabet, which is the core of this thesis. This work also includes the design and implementation of a compression algorithm that combines DMC and an arithmetic coder. We devote a significant portion of the work to performing experiments using different parameters and evaluating their influence on compression. Finally, we present an evaluation and compare our wort to other implementations.

Keywords:

Lossless compression, Dynamic Markov coding, Arithmetic coding, Entropy encoder, Text compression, Parameter optimization

Date of defence

22.06.2026

Result of the defence

Defended (thesis was successfully defended)

znamkaBznamka

Grading

B

Process of defence

Studentka nejprve prezentovala výsledky, kterých dosáhla v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Studentka následně odpověděla na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studentky na položené otázky rozhodla práci hodnotit stupněm B.

Topics for thesis defence

  1. Je vybraný dataset vhodná reprezentatívna vzorka pre riešený problém?
  2. Na základe výsledkov experimentov, kde bolo vidieť, že niektoré zvolené súbory alebo podčasti súborov sú väčšou či menšou výzvou pre implementovaný algoritmus, doplnili by ste dataset o nejaké ďalšie konkrétne dáta?
  3. Jaká je aplikační oblast Vašeho řešení? V jakých situacích se dá využít?
  4. Jaký je rozsah Vaší implementace?

Language of thesis

English

Faculty

Fakulta informačních technologií

Department

Department of Computer Systems

Study programme

Information Technology and Artificial Intelligence (MITAI)

Specialization

Mathematical Methods (NMAT)

Composition of Committee

doc. Mgr. Adam Rogalewicz, Ph.D. (předseda)
doc. RNDr. Milan Češka, Ph.D. (místopředseda)
Ing. Martin Hrubý, Ph.D. (člen)
Ing. Aleš Smrčka, Ph.D. (člen)
Dr. Ing. Petr Peringer (člen)
Ing. Jaroslav Rozman, Ph.D. (člen)

Supervisor’s report
doc. Ing. Zdeněk Vašíček, Ph.D.

Celkově hodnotím přístup studentky k řešení diplomové práce jako pečlivý a svědomitý. Studentka dokázala uchopit netriviální téma a přispět k hlubšímu porozumění generalizované verze kompresního algoritmu. Celkově nemám k přístupu výtek, pouze doporučuji věnovat více pozornosti plánování času a vytváření dostatečných časových rezerv.

Evaluation criteria Verbal classification
Informace k zadání

Svým charakterem se jedná o experimentální diplomovou práci, která vyžaduje hlubší znalosti technik z oblasti komprese, algoritmizace a datových struktur. Cíle práce byly naplněny.
Aktivita při dokončování

Implementace a experimentální část byla dokončena v dostatečném předstihu. Obsah technické zprávy byl průběžně konzultován, avšak definitivní podobu již nebylo možné z časových důvodů konzultovat, neboť některé části byly dokončovány na poslední chvíli.
Publikační činnost, ocenění
Práce s literaturou

Studentka pracovala s literaturou doporučenou i dalšími zdroji, které získávala samostatně.
Aktivita během řešení, konzultace, komunikace

Studentka byla aktivní po oba semestry a na řešení pracovala průběžně. Jednotlivé kroky byly konzultovány a na konzultace byla vždy řádně připravena. Vzhledem k experimentálnímu charakteru zadání bylo nutné několikrát nalézt vhodnější přístup, přičemž v této otázce byla studentka velmi proaktivní a přinášela vlastní návrhy.
Points proposed by supervisor: 90

Grade proposed by supervisor: A

Reviewer’s report
Ing. Marcela Zachariášová, Ph.D.

Z hľadiska vedeckého prístupu a softvérového inžinierstva ide o poctivo spracované a plne adekvátne inžinierske dielo. Analýza slepých uličiek nebinárneho DMC má vysokú akademickú hodnotu. Hodnotím známkou A. 

Evaluation criteria Verbal classification Points
Rozsah splnění požadavků zadání

Evaluation level: zadání splněno

Zadanie je splnené. Je ťažké určiť, čo z implementovaných techník je súčasťou zadania a čo je rozšírenie (zadanie je v tomto pomerne voľné), ale každopádne hodnotím, že študentka  navrhla a implementovala veľké množstvo parametrov, ktoré môžu ovplyvniť kvalitu kompresie (viz strana 43) a všetky ich experimntálne ohodnotila a spravila z nich fundované závery. Toto hodnotím ako veľmi kvalitný výstup. 
Rozsah technické zprávy

Evaluation level: je v obvyklém rozmezí

Rozsah práce je v poriadku.
Prezentační úroveň technické zprávy

Kapitoly na seba vhodne nadväzujú a sú informačne bohaté. Študentka vysvetľuje vhodne všetku potrebnú terminológiu. 

 95
Formální úprava technické zprávy

Zopár preklepov, strana 7: chyba vo vzorci: size_of_the_input/size_of_the_input, Picture vs. Figure, "Read buffer size" namiesto "Buffer size" na strane 43, niekoľko-stranová dopredná referencia na obrázok 4.4. Ocenila by som väčšie obrázky a grafy, napr. text v obrázku 5.1, a potom grafy v experimentálnej evaluácii. Nevidím dôvod, prečo nebola využitá celá šírka textu.  

 85
Práce s literaturou

V rámci zamerania práce študentka pracovala s vhodnou literatúrou. Očakávala som možno viac referencí na vedecké publikácie s podobným zameraním.

 90
Realizační výstup

Realizačný výstup je v poriadku, dataset je vhodne zvolený, experimentálna časť je rozsiahla. I napriek tomu, že výsledné kompresné pomery pri texte zaostali za ostatnými riešeniami, rozsah a hĺbka následnej evaluácie sú nadštandardné. Študentka namerané dáta podrobila kritickej analýze, správne diagnostikovala teoretické limity algoritmu (tzv. escape symbol bottleneck) a vďaka integrácii s delta kódovaním dokázala pri komplexných fotografických dátach (formáty PGM a PPM) poraziť gzip aj pôvodné binárne DMC. 

 95
Využitelnost výsledků

Práca prináša nové poznatky. Študentka sa nezameriavala len na replikáciu existujúceho riešenia, ale navrhla netriviálne rozšírenie dynamického Markovovho kódovania z binárnej abecedy na bajtovú. To so sebou prináša problém v podobe explózie stavového priestoru a počtu hrán.

Pre reguláciu rastu modelu študentka navrhla a implementovala hybridnú techniku (kombináciu lazy a klasického klonovania stavov) a mechanizmy dynamického obmedzovania a prehadzovania hrán. Riešenie problému „escape“ symbolov patrí v kompresii medzi najzložitejšie teoretické úlohy.
Náročnost zadání

Evaluation level: obtížnější zadání

Prácu hodnotím ako náročnejšiu, z pohľadu spracovania teórie aj z pohľadu návrhu a implementácie. 
Topics for thesis defence:
  1. 1. Je vybraný dataset vhodná reprezentatívna vzorka pre riešený problém? 2. Na základe výsledkov experimentov, kde bolo vidieť, že niektoré zvolené súbory alebo podčasti súborov sú väčšou či menšou výzvou pre implementovaný algoritmus, doplnili by ste dataset o nejaké ďalšie konkrétne dáta?
Points proposed by reviewer: 90

Grade proposed by reviewer: A

Responsibility: Mgr. et Mgr. Hana Odstrčilová