Original title:
Kompaktní sufixový automat v posuvném okně
Translated title:
Compact directed acyclic word graph in a sliding window
Authors:
Filip, Ondřej ; Dvořák, Tomáš (advisor) ; Senft, Martin (referee) Document type: Bachelor's theses
Year:
2011
Language:
cze Abstract:
[cze][eng] Kompaktní sufixový automat (CDAWG) je prostorově šetrnější variantou datové struktury pro indexaci slov zvané sufixový strom. Cílem této práce je implementace algoritmů pro CDAWG v posuvném okně a porovnání jejich vlastností. Posuvné okno je výhodné v případech, kdy není možné v paměti udržovat indexovou strukuturu pro celá indexovaná data. Jeden přesný posun okna je možné provést v čase lineárním k délce okna. Rovněž existuje aproximativní algoritmus vyžadující pro posun okna pouze konstantní čas. Korektnost tohoto algoritmu ovšem byla v této práci vyvrácena.Compact directed acyclic word graph (CDAWG) is the space-efficient version of a text-indexing data structure called suffix tree. The goal of this work is an implementation and comparison of algorithms constructing CDAWG for text in a sliding window. Sliding window is favorable in cases when the index structure cannot be kept in memory for the whole indexed data. One exact move of the sliding window may be performed in linear time with respect to the length of the window. An approximative algorithm requiring only amortized constant time per one move has been developed, too. However, in this thesis, the correctness of this algorithm has been disproved.
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/38712