UNF Digital Commons
Approximate String Matching With Dynamic Programming and Suffix Trees
Abstract
dc:description.abstractThe importance and the contribution of string matching algorithms to the modern society cannot be overstated. From basic search algorithms such as spell checking and data querying, to advanced algorithms such as DNA sequencing, trend analysis and signal processing, string matching algorithms form the foundation of many aspects in computing that have been pivotal in technological advancement. In general, string matching algorithms can be divided into the categories of exact string matching and approximate string matching. We study each area and examine some of the well known algorithms. We probe into one of the most intriguing data structure in string algorithms, the suffix tree. The lowest common ancestor extension of the suffix tree is the key to many advanced string matching algorithms. With these tools, we are able to solve string problems that were, until recently, thought intractable by many. Another interesting and relatively new data structure in string algorithms is the suffix array, which has significant breakthroughs in its linear time construction in recent years. Primarily, this thesis focuses on approximate string matching using dynamic programming and hybrid dynamic programming with suffix tree. We study both approaches in detail and see how the merger of exact string matching and approximate string matching algorithms can yield synergistic results in our experiments.
Degree
thesis:*- Name thesis:degree_name
- Master of Science in Computer and Information Sciences (MS)
- Discipline thesis:degree_discipline
- Computing
- Grantor dc:publisher
- UNF Digital Commons
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Keng, Leng Hui
- Contributors dc:contributor
-
- Dr. Yap S. Chua
- Dr. Roger E. Eggen
- Dr. William F. Klostermeyer
Subjects
dc:subject × 5- UNF; University of North Florida; Department of Computer and Information Sciences; Dissertations
- Academic -- UNF -- Computer science; School of Computing
- Computer Sciences
- Dissertations
- Academic -- UNF -- Computer science; Computational linguistics; Computer algorithms; Database searching; Dynamic programming; Matching theory; Natural language processing (Computer science); Text processing (Computer science); Trees (Graph theory)
Rights
dc:rightsIdentifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.unf.edu/etd/196