Return to search

An FPT Algorithm for STRING-TO-STRING CORRECTION

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

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/3498
Date24 August 2011
CreatorsLee-Cultura, Serena Glyn
ContributorsStege, Ulrike, Serra, Micaela
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.0018 seconds