string distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, pa...
详细信息
string distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing theory, speech recognition, and computational biology, to name a few. Here we consider a classic string distance problem, the NP-complete string-to-string correction problem, first studied by Wagner some 35 years ago. In this problem, we are asked whether it is possible to transform string x into string y with at most k operations on x, where permitted operations are single-character deletions and adjacent character exchanges. We prove that string-to-string correction is fixed-parameter tractable, for parameter k, and present a simple fixed-parameter algorithm that solves the problem in O(2(k)n) time. We also devise a bounded search tree algorithm, and introduce a bookkeeping technique that we call charge and reduce. This leads to an algorithm whose running time is O(1.618 1(k)n). (C) 2011 Published by Elsevier B.V.
The string editing problem for input strings x and y consists of transforming x into y by performing a series of weighted edit operations on x of overall minimum cost. An edit operation on x can be the deletion of a s...
详细信息
The string editing problem for input strings x and y consists of transforming x into y by performing a series of weighted edit operations on x of overall minimum cost. An edit operation on x can be the deletion of a symbol from x, the insertion of a symbol in x or the substitution of a symbol of x with another symbol. This problem has a well-known O(|x
Given a set of strings, the problem of finding a string that minimises its distance to the set is directly related with problems frequently encountered in areas involving Pattern recognition or computational biology. ...
详细信息
Given a set of strings, the problem of finding a string that minimises its distance to the set is directly related with problems frequently encountered in areas involving Pattern recognition or computational biology. Based on the Levenshtein (or edit) distance, different definitions of distances between a string and a set of strings can be adopted. In particular, if this definition is the sum of the distances to each string of the set, the string that minimises this distance is the (generalised) median string. Finding this string corresponds in speech recognition to giving a model for a set of acoustic sequences, and in computational biology to constructing an optimal evolutionary tree when the given phylogeny is a star. Only efficient algorithms are known for finding approximate solutions. The results in this paper are combinatorial and negative. We prove that computing the median string corresponds to a NP-complete decision problems, thus proving that this problem is NP-hard. (C) 2000 Elsevier Science B.V. All rights reserved.
Given a source and a target string, their swap-delete-edit distance is the minimum number of interchange-consecutive-symbols and delete operations applied to the source string to make it equal the target string. We sh...
详细信息
Given a source and a target string, their swap-delete-edit distance is the minimum number of interchange-consecutive-symbols and delete operations applied to the source string to make it equal the target string. We show that the swap-delete-edit distance of strings over alphabets of bounded size can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.
暂无评论