Suffix Graphs and Lossless Data Compression

• Název práce v češtině: Sufixové grafy a bezeztrátová komprese dat
• Název v anglickém jazyce: Suffix Graphs and Lossless Data Compression
• Klíčová slova: Sufixový strom, DAWG, CDAWG, posuvné okno, bezztrátová komprese dat
• Klíčová slova anglicky: Suffix tree, DAWG, CDAWG, sliding window, lossless data compression
• Akademický rok vypsání: 2004/2005
• Typ práce: disertační 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í: 01.10.2004
• Datum zadání: 01.10.2004
• Datum a čas obhajoby: 23.09.2013 11:00
• Datum odevzdání elektronické podoby: 24.05.2013
• Datum odevzdání tištěné podoby: 24.05.2013
• Datum proběhlé obhajoby: 23.09.2013
• Oponenti: doc. Mgr. Jiří Dvorský, Ph.D.

Zásady pro vypracování

Efektivita algoritmů komprese dat je ovlivněna typem datových struktur, které jsou použity při jejich implementaci. Některé z nich jsou přitom úspěšně využívány pro realizaci jak statistických, tak slovníkových metod bezztrátové komprese dat. Jedním konkrétním příkladem je sufixový strom, který byl původně navržen jako datová struktura, umožňující asymptoticky optimálně řešit řadu úloh o řetězcích. Jeho vlastností bylo však v minulosti úspěšně využito i k implementaci několika kompresních metod různého typu (ZL77, PPM, Burrows-Wheelerova transformace). Tato skutečnost naznačuje, že může být nadějné prozkoumat možnosti opačného přístupu, tedy využití vlastností sufixového stromu k návrhu nového kompresního algoritmu. Autor by se měl zaměřit i na další datové struktury a operace nad nimi, které by mohly být vhodné pro bezztrátovou kompresi dat. Nadějnými kandidáty se zdají být struktury příbuzné sufixovému stromu, jako sufixové pole, sufixový trie, DAWG či CDAWG.

Seznam odborné literatury

[1] Janet A. Blumer: How much is that DAWG in the window? a moving window algorithm for the directed acyclic word graph , J. Algorithms 8(1987), 451-469.
[2] S. Bunton: On-Line Stochastic Processes in Data Compression, disertační práce , Dept. of Comp. Science and Engineering, University of Washington, Seattle 1996.
[3] M. Crochemore, W. Rytter: Jewels of Stringology, World Scientific, 2002.
[4] E. R. Fiala, D. H. Greene: Data compression with finite windows, Communications of the ACM 32(1989), 490-505.
[5] S. Inenaga, A. Shinohara, M. Takeda, S.Arikawa: Compact directed acyclic word graphs for a sliding window, J. Discrete Algorithms 2 (2004), 25-51.
[6] N. J. Larsson: Structures of String Matching and Data Compression, disertační práce, Department of Computer Science, Lund University 1999.
[7] A. Moffat, A. Turpin: Compression and Coding Algorithms. Kluwer Academic Publishers, 2002.