Original title: Přibližné vyhledávání řetězců v předzpracovaných dokumentech
Translated title: Approximate String Matching in Preprocessed Documents
Authors: Toth, Róbert ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
Document type: Master’s theses
Year: 2014
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [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.
Keywords: approximate string matching; inexact searching; offline algorithms; searching allowing errors; suffix arrays; suffix trees; text indexing; text indexing algoritms; indexační algoritmy; indexování textu; offline algoritmy; přibližné vyhledávání řetězců; suffixové stromy; vyhledávání s chybami

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/53365

Permalink: http://www.nusl.cz/ntk/nusl-236122


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses