Robert A. Wagner
Michael J. Fischer
Abstract
The string-to-string correction problem is to determine the distance between two strings as measured by the minimum cost sequence of “edit operations” needed to change the one string into the other. The edit operations investigated allow changing one symbol of a string into another single symbol, deleting one symbol from a string, or inserting a single symbol into a string. An algorithm is presented which solves this problem in time proportional to the product of the lengths of the two strings. Possible applications are to the problems of automatic spelling correction and determining the longest subsequence of characters common to two strings.
- 1 MOaGAN, H.L. Spelling correctioa in systems programs. Comm. ACM I$, 2 (Feb. 1970), 90-94. Google Scholar
Index Terms
- The String-to-String Correction Problem
Recommendations
Shortest string containing all permutations
In this paper, we consider the problem of constructing a shortest string of {1,2,...,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less ...
String Noninclusion Optimization Problems
For every string inclusion relation there are two optimization problems: find a longest string included in every string of a given finite language, and find a shortest string including every string of a given finite language. As an example, the two well-...
Inferring an indeterminate string from a prefix graph
An indeterminate string (or, more simply, just a string) x = x 1 . . n ] on an alphabet Σ is a sequence of nonempty subsets of Σ. We say that x i 1 ] and x i 2 ] match (written x i 1 ] x i 2 ] ) if and only if x i 1 ] x i 2 ] . A feasible array is an ...
Comments