|
|
Suffix Graphs and Lossless Data Compression
Senft, Martin ; Dvořák, Tomáš (vedoucí práce) ; Dvorský, Jiří (oponent) ; Smyth, William F. (oponent)
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áš Dvorˇák, CSc., Katedra software a výuky informatiky Abstrakt: Sufixový strom a prˇíbuzné datové struktury umožnˇují asymptoticky optimálneˇ rěšit rˇadu úloh o rětežcích a jejich vlastností lze též využít k imple- mentacimetodbezztrátovékompresedat. Cílemprácejeprozkoumatmožnosti opacňéhoprˇístupu,tedy využití vlastností sufixovýchgrafu˚ k návrhukompres- ních algoritmu˚. Práce popisuje univerzální konstrukcňí algoritmus pro sufixo- vý trie,sufixový strom,DAWGa CDAWG,doprovázený analýzousimulaceim- plicitních sufixových hran, která prˇináší dveˇ praktické alternativy k tradicňímu rěšení. Protožekompresnímetody vyžadují udržování textuvposuvnémokneˇ, je trěba rozebrat chování sufixových grafu˚ v této situaci. V práci je oveřěno, že pouze sufixový strom je schopen udržovat posuvné okno v amortizovaneˇ kon- stantním cˇase, zatímco CDAWG (podobneˇ jako DAWG) vyžaduje cˇas úmeřný délce okna, což rěší hypotézu Inenagy a kol. Na tomto základeˇ je popsána trˇí- da kompresních algoritmu˚, založených pouze na popisu konstrukce sufixové- ho grafu nad komprimovaným textem. Zatímco neˇkteré z algoritmu˚ odpoví- dají klasickým slovníkovým cˇi kontextovým...
|
host ::
RSS.