Parameterized string correction decision problems investigate the possibility of
transforming a given string X into a target string Y using a fixed number of edit
operations, k. There are four possible edit operations: swap, delete, insert and substi-
tute. In this work we consider the NP--complete STRING-TO-STRING CORREC-
TION problem restricted to deletes and swaps and parameterized by the number
of allowed operations. Specifically, the problem asks whether there exists a trans-
formation from X into Y consisting of at most k deletes or swaps. We present a
fixed parameter algorithm that runs in O(2k(k + m)), where m is the length of the
destination string. Further, we present an implementation of an extended version of
the algorithm that constructs the transformation sequence ! of length ay most k,
given its existence. This thesis concludes with a discussion comparing the practical
run times obtained from our implementation with the proposed theoretical results.
Efficient string correction algorithms have applications in several areas, for example
computational linguistics, error detection and correction, and computational biology. / Graduate
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/3498 |
| Date | 24 August 2011 |
| Creators | Lee-Cultura, Serena Glyn |
| Contributors | Stege, Ulrike, Serra, Micaela |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0017 seconds