Název: Comparison of Tree Edit Distance Algorithms
Překlad názvu: Comparison of Tree Edit Distance Algorithms
Autoři: Ivkin, Egor ; Nečaský, Martin (vedoucí práce) ; Lokoč, Jakub (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2012
Jazyk: eng
Abstrakt: [eng] [cze]
The aim of this thesis is the comparison of the Tree Edit Distance methods, in the context of detecting structural similarity between two XML Schema documents. The methods search the minimum number of edit operations leading from one tree to another. We have analysed and implemented a wide range of the existing tree edit distance approaches. It is important to understand that the distance computed by the algorithms is affected by the set of used edit operations, therefore the strength in detecting XML Schema similarity differs in each approach. The first part of this work contains the description of the used approaches and necessary notations. The second part provides implementation details and analysis of the described methods, which consists of theoretical comparison and empirical evaluation on real and synthetic xml data. The resulting implementation is available in the form of Java SE application. Cílem této práce je srovnání Tree Edit Distance metod v rámci zjišťování strukturální podobnosti mezi XML Schema dokumenty. Tyto metody vyhledávají minimální počet editačních operací, pomocí kterých jeden strom je převáděn na druhý. Zanalyzovali a implementovali jsme celou řadu existujících Tree Edit Distance algoritmů. Je důležité si uvědomit, že vzdálenost počítána algoritmy je ovlivněna množinou použitých editačních operací proto kvalita při odhalování XML Schema podobnost se liší v každém postupů. První část této práce obsahuje popis použitých postupů a potřebné zápisy. Druhá část obsahuje detaily implementace a analýzu popsaných metod, která sestává teoretické analýzy a porovnávání výsledků běhů nad reálnými i syntetickými XML daty. Výsledná implementace je k dispozici ve formě Java aplikace.
Klíčová slova: podobnost; Tree Edit Distance; XML; XML schema; similarity; Tree Edit Distance; XML; XML schema

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/42050

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


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