velikost textu

Suffix Graphs and Lossless Data Compression

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Suffix Graphs and Lossless Data Compression
Název v češtině:
Sufixové grafy a bezeztrátová komprese dat
Typ:
Disertační práce
Autor:
Mgr. Martin Senft, Ph.D.
Školitel:
doc. RNDr. Tomáš Dvořák, CSc.
Oponenti:
Doc. Mgr. Jiří Dvorský, Ph.D.
Prof. William F. Smyth, Ph.D.
Id práce:
42521
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra softwaru a výuky informatiky (32-KSVI)
Program studia:
Informatika (P1801)
Obor studia:
Softwarové systémy (4I2)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
23. 9. 2013
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
Sufixový strom, DAWG, CDAWG, posuvné okno, bezztrátová komprese dat
Klíčová slova v angličtině:
Suffix tree, DAWG, CDAWG, sliding window, lossless data compression
Abstrakt:
Název práce: Sufixové grafy a bezeztrátová komprese dat Autor: Martin Senft Katedra: Katedra software a výuky informatiky Vedoucí doktorské práce: doc. RNDr. Tomáš Dvořák, CSc., Katedra software a výuky informatiky Abstrakt: Sufixový strom a příbuzné datové struktury umožňují asymptoticky optimálně řešit řadu úloh o řetězcích a jejich vlastností lze též využít k imple- mentaci metod bezztrátové komprese dat. Cílem práce je prozkoumat možnosti opačného přístupu, tedy využití vlastností sufixových grafů k návrhu kompres- ních algoritmů. Práce popisuje univerzální konstrukční algoritmus pro sufixo- vý trie, sufixový strom, DAWG a CDAWG, doprovázený analýzou simulace im- plicitních sufixových hran, která přináší dvě praktické alternativy k tradičnímu řešení. Protože kompresní metody vyžadují udržování textu v posuvném okně, je třeba rozebrat chování sufixových grafů v této situaci. V práci je ověřeno, že pouze sufixový strom je schopen udržovat posuvné okno v amortizovaně kon- stantním čase, zatímco CDAWG (podobně jako DAWG) vyžaduje čas úměrný délce okna, což řeší hypotézu Inenagy a kol. Na tomto základě je popsána tří- da kompresních algoritmů, založených pouze na popisu konstrukce sufixové- ho grafu nad komprimovaným textem. Zatímco některé z algoritmů odpoví- dají klasickým slovníkovým či kontextovým metodám bezztrátové komprese, jiné jsou zcela originální. Výklad je doplněn pilotní implementací navržených algoritmů a experimentálním vyhodnocením na standardních datových kor- pusech. Klíčová slova: sufixový strom, CDAWG, konstrukce, posuvné okno, komprese dat
Abstract v angličtině:
Title: Suffix Graphs and Lossless Data Compression Author: Martin Senft Department: Department of Software and Computer Science Education Supervisor of the doctoral thesis: doc. RNDr. Tomáš Dvořák, CSc., Depart- ment of Software and Computer Science Education Abstract: Suffix tree and its variants are widely studied data structures that enable an efficient solution to a number of string problems, but also serve for implementation of data compression algorithms. This work explores the opposite approach: design of compression methods, based entirely on prop- erties of suffix graphs. We describe a unified construction algorithm for suf- fix trie, suffix tree, DAWG and CDAWG, accompanied by analysis of implicit suffix link simulation that yields two practical alternatives. Since the com- pression applications require maintaining text in the sliding window, an in- depth discussion of sliding suffix graphs is needed. Filling gaps in previously published proofs, we verify that suffix tree is capable of perfect sliding in amortised constant time. On the other hand, we show that this is not the case with CDAWG, thus resolving a problem of Inenaga et al. Building on these investigations, we describe a family of data compression methods, based on a description of suffix tree construction for the string to be compressed. While some of these methods resemble classical lossless compression like PPM or dictionary techniques, others appear to be brand-new. Our algorithms are illustrated with a proof-of-concept implementation and experimental evalu- ation on standard data corpora. Keywords: suffix tree, CDAWG, construction, sliding window, data com- pression
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Martin Senft, Ph.D. 840 kB
Stáhnout Příloha k práci Mgr. Martin Senft, Ph.D. 788 kB
Stáhnout Abstrakt v českém jazyce Mgr. Martin Senft, Ph.D. 10 kB
Stáhnout Abstrakt anglicky Mgr. Martin Senft, Ph.D. 10 kB
Stáhnout Posudek vedoucího doc. RNDr. Tomáš Dvořák, CSc. 108 kB
Stáhnout Posudek oponenta Doc. Mgr. Jiří Dvorský, Ph.D. 1.64 MB
Stáhnout Posudek oponenta Prof. William F. Smyth, Ph.D. 169 kB
Stáhnout Záznam o průběhu obhajoby doc. Ing. Jaroslav Křivánek, Ph.D. 161 kB