1974 TheStringToStringCorrectionProblem

From GM-RKB
Jump to: navigation, search

Subject Headings: String Distance Function, Longest Common Subsequence, Approximate String Matching, Sequence Alignment.

Notes

Cited By

Quotes

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.

References


 AuthorvolumeDate ValuetitletypejournaltitleUrldoinoteyear
1974 TheStringToStringCorrectionProblemRobert A. Wagner
Michael J. Fischer
The String to String Correction Problemhttp://www.birc.dk/~cstorm/courses/AiB/e04/www-aibsa/papers/WagnerFisher EditDist.pdf10.1145/321796.3218111974