Název:
Přibližné vyhledávání řetězců v předzpracovaných dokumentech
Překlad názvu:
Approximate String Matching in Preprocessed Documents
Autoři:
Toth, Róbert ; Košař, Vlastimil (oponent) ; Kaštil, Jan (vedoucí práce) Typ dokumentu: Diplomové práce
Rok:
2014
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze][eng]
Tato práce se zabývá problémem přibližného vyhledávání řetězců, označovaným též jako vyhledávání s chybami. Práce se zaměřuje na oblast offline algoritmů, které umožňují po jednorazovém předspracování textu velmi rychlé vyhledávaní díky indexu, který si nad textem vytvoří. Nejprve bude definován problém samotný a demonstrována rozmanitost jeho využití, následována krátkým shrnutím rozdílných přístupů k této problematice. Poté budou detailně probrány některé algoritmy založené na použití suffixových stromů a představen nový hybridní algoritmus. Algoritmy budou implementovány v jazyce C a jejich výkonnost detailně otestována v sérii experimentů se zaměřením na určení reálného přínosu nového algoritmu do této oblasti.
This thesis deals with the problem of approximate string matching, also called string matching allowing errors. The thesis targets the area of offline algorithms, which allows very fast pattern matching thanks to index created during initial text preprocessing phase. Initially, we will define the problem itself and demonstrate variety of its applications, followed by short survey of different approaches to cope with this problem. Several existing algorithms based on suffix trees will be explained in detail and new hybrid algorithm will be proposed. Algorithms wil be implemented in C programming language and thoroughly compared in series of experiments with focus on newly presented algorithm.
Klíčová slova:
indexační algoritmy; indexování textu; offline algoritmy; přibližné vyhledávání řetězců; suffixové stromy; vyhledávání s chybami; approximate string matching; inexact searching; offline algorithms; searching allowing errors; suffix arrays; suffix trees; text indexing; text indexing algoritms
Instituce: Vysoké učení technické v Brně
(web)
Informace o dostupnosti dokumentu:
Plný text je dostupný v Digitální knihovně VUT. Původní záznam: http://hdl.handle.net/11012/53365