1974 TheStringToStringCorrectionProblem
- (Wagner & Fischer, 1974) ⇒ Robert A. Wagner, and Michael J. Fischer. (1974). “The String to String Correction Problem.” In: [[journal::Journal of the ACM] (JACM), 21(1). doi:10.1145/321796.321811
Subject Headings: String Distance Function, Longest Common Subsequence, Approximate String Matching, Sequence Alignment.
Notes
Cited By
- ~2,072 http://scholar.google.com/scholar?q=%22The+String+to+String+Correction+Problem%22+1974
- http://search.cpan.org/~davidebe/Text-WagnerFischer-0.04/WagnerFischer.pm
- This module implements the Wagner-Fischer dynamic programming technique, used here to calculate the edit distance of two strings. The edit distance is a measure of the degree of proximity between two strings, based on "edits": the operations of substitutions, deletions or insertions needed to transform the string into the other one (and vice versa). A cost (weight) is needed for every of the operation defined above:
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
- 1. (Morgan, 1970) ⇒ Howard L. Morgan. (1970). “Spelling Correction in Systems Programs.” In: Communications of the ACM, 13(2).
,
| Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1974 TheStringToStringCorrectionProblem | Robert A. Wagner Michael J. Fischer | The String to String Correction Problem | http://www.birc.dk/~cstorm/courses/AiB/e04/www-aibsa/papers/WagnerFisher EditDist.pdf | 10.1145/321796.321811 |