ArchivIA Università degli Studi di Catania
 

ArchivIA - Archivio istituzionale dell'Universita' di Catania >
Tesi >
Tesi di dottorato >
Area 01 - Scienze matematiche e informatiche >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10761/186

Issue Date: 4-May-2011
Authors: Giaquinta, Emanuele
Title: Advancements in finite-state methods for string matching
Abstract: This thesis illustrates some advancements in finite-state methods for solving the string-matching problem and some of its variants. Finite-state automata are central building blocks in string matching algorithms. In particular, the ones relevant for the present study are the Knuth-Morris-Pratt and the suffix automaton as well as their generalizations for the multiple-string-matching problem, i.e., the Aho-Corasick automaton and the automaton induced from the DAWG (Directed Acyclic Word Graph) for a set of strings. In this work I present novel encodings, based on the bit-parallelism technique, of the nondeterministic versions of the aforementioned automata and also illustrate two methods to parallelize a recent algorithm based on the nondeterministic suffix automaton. I further discuss the approximate-string-matching problem. I also show a new simple result concerning the pattern-matching-with-swaps problem and present a new distance function that is defined in terms of edit operations which involve strings rather than single characters. I also present an algorithm, based on dynamic programming and on the DAWG, to solve the approximate-string-matching problem under this distance. I finally discuss the compressed-string-matching problem and present novel results that concern searching in texts encoded with Huffman codes and with the Burrows-Wheeler transform.
Appears in Collections:Area 01 - Scienze matematiche e informatiche

Files in This Item:

File SizeFormatVisibility
phd_thesis.pdf1,41 MBAdobe PDFView/Open


Items in ArchivIA are protected by copyright, with all rights reserved, unless otherwise indicated.


Share this record
Del.icio.us

Citeulike

Connotea

Facebook

Stumble it!

reddit


 

  Browser supportati Firefox 3+, Internet Explorer 7+, Google Chrome, Safari

ICT Support, development & maintenance are provided by the AePIC team @ CILEA. Powered on DSpace Software.