The String-to-String Correction Problem

1974/01/01 by Robert A. Wagner, Michael J. Fischer · 19 citations
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Approximate string matching #Artificial intelligence #Bounded function #Combinatorics #Commentz-Walter algorithm #Computer science #Edit distance #Longest common subsequence problem #Longest increasing subsequence #Mathematics #Natural Language Processing Techniques #Pattern matching #Physics #Programming language #Software Testing and Debugging Techniques #String (physics) #String metric #String searching algorithm #Subsequence #Symbol (formal) #Theoretical physics

paper · pdf · doi:10.1145/321796.321811

openalex publication_date 1974/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03

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.

Cited by

• A guided tour to approximate string matching
• A fast algorithm for computing longest common subsequences
• Identifying Neuronal Lineages ofDrosophilaby Sequence Analysis of Axon Tracts
• Knowledge-driven understanding of images in comic books
• A faster algorithm computing string edit distances
• A linear space algorithm for computing maximal common subsequences
• A survey of longest common subsequence algorithms
• The Complexity of Some Problems on Subsequences and Supersequences
• Exact asymptotic results for the Bernoulli matching model of sequence alignment
• Approximating the number of differences between remote sets
• CHARMM: A program for macromolecular energy, minimization, and dynamics calculations
• On the complexity of the Extended String-to-String Correction Problem
• The shortest common supersequence problem over binary alphabet is NP-complete
• Consensus Measures for Unstructured Biomedical Text Annotations
• Longest Common Subsequence in k-length substrings
• Unzipping of two random heteropolymers: Ground-state energy and finite-size effects
• Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
• Longest common subsequence [wikipedia]
• Michael J. Fischer [wikipedia]