Kompaktní sufixový automat v posuvném okně
| Název práce v češtině: | Kompaktní sufixový automat v posuvném okně |
|---|---|
| Název v anglickém jazyce: | Compact directed acyclic word graph in a sliding window |
| Akademický rok vypsání: | 2009/2010 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | češ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í: | 12.11.2009 |
| Datum zadání: | 12.11.2009 |
| Datum potvrzení stud. oddělením: | 07.06.2011 |
| Datum a čas obhajoby: | 20.06.2011 09:00 |
| Datum odevzdání elektronické podoby: | 27.05.2011 |
| Datum odevzdání tištěné podoby: | 27.05.2011 |
| Datum proběhlé obhajoby: | 20.06.2011 |
| Oponenti: | Mgr. Martin Senft, Ph.D. |
| Zásady pro vypracování |
| Kompaktni sufixový automat (CDAWG) je sufixová datové struktura, kterou lze obdržet ztotožněním izomorfních podstromů sufixového stromu [2]. Ve srovnání se sufixovým stromem je tedy prostorově úspornější, postrádá však některé jeho užitečné vlastnosti. Pro aplikace v oblasti komprese dat je užitečná reprezentace textu v posuvném okně, které lze v případě sufixového stromu aktualizovat v amortizovaně konstantním čase [5], CDAWG však vyžaduje čas úměrný velikosti okna [6].
Cílem práce je implementace algoritmu [6], udržujícího CDAWG pro text v posuvném okně, a experimentální ověření jeho časové i prostorové složitosti na standardním datovém korpusu [3]. Přes nepříznivou časovou složitost v nejhorším případě by totiž mohlo být chování algoritmu v průměrném případě příznivější; podobný výsledek je znám pro přibuznou datovou strukturu DAWG [1]. Zajímavé by bylo též srovnámí s aproximativním algoritmem [4], který sice pracuje v asymptoticky optimálním čase, v jednom kroku však může ztratit až polovinu znaků v posuvném okně. |
| Seznam odborné literatury |
| [1] J. Blumer, How much is that DAWG in the window? Journal of Algorithms 8(1987), 451-469, http://dx.doi.org/10.1016/0196-6774(87)90045-9
[2] M. Crochemore, C. Hancart, T. Lecroq, Algorithms on Strings, Cambridge University Press, 2007 [3] P. Ferragina, G. Navarro, Pizza & Chili Corpus, http://pizzachili.dcc.uchile.cl/index.html [4] S. Inenaga, A. Shinohara, M. Takeda, S. Arikawa, Compact Directed Acyclic Word Graphs for a Sliding Window, Journal of Discrete Algorithms 2(2004), 33-51, http://dx.doi.org/10.1016/S1570-8667(03)00064-9 [5] M. Senft, Suffix Tree for a Sliding Window: An Overview, In: Šafránková, J. (ed.) WDS 2005, 41-46, Matfyzpress, Praha 2005 [6] M. Senft, T. Dvořák, Sliding CDAWG Perfection, Lecture Notes in Computer Science 5280(2008), 109-120, http://dx.doi.org/10.1007/978-3-540-89097-3_12 |
| Předběžná náplň práce |
| Cílem práce je implementace algoritmu, udržujícího kompaktni sufixový automat pro text v posuvném okně, a experimentální ověření jeho časové i prostorové složitosti na standardním datovém korpusu. |
| Předběžná náplň práce v anglickém jazyce |
| An implementation and experimental evaluation of an algorithm which maintains Compact Directed Acyclic Word Graph for a text in a sliding window. |