Název: Kompaktní sufixový automat v posuvném okně
Překlad názvu: Compact directed acyclic word graph in a sliding window
Autoři: Filip, Ondřej ; Dvořák, Tomáš (vedoucí práce) ; Senft, Martin (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2011
Jazyk: cze
Abstrakt: [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.

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/38712

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-482104


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce