The Levenshtein distance algorithm computes the minimum number of single-character insertions, deletions and substitutions needed to transform one string into another, using dynamic programming to fill a table where each cell represents the edit distance between a prefix of the first string and a prefix of the second, built up from the base case of comparing against empty prefixes. The technique runs in O(m times n) time and space for strings of length m and n, with later refinements reducing the space requirement. Vladimir Levenshtein, a Soviet mathematician, introduced the distance measure in 1965, and it underlies applications from spell checking to DNA sequence comparison.
Facts
Time ComplexityTheta(mn) time and Theta(mn) space for the full matrix, for strings of lengths m and n 1 Credited ToVladimir Levenshtein, 1965 1 Classification
Design Technique Sources
1. Levenshtein distance, Wikipedia
Dynamic programming section
The full matrix takes Θ ( m n )
Introduction
The distance is named after Soviet mathematician Vladimir Levenshtein, who introduced it in 1965 in the context of error-correcting codes.
entity record, description (design-technique)
The Levenshtein distance algorithm computes the minimum number of single-character insertions, deletions and substitutions needed to transform one string into another, using dynamic programming to fill a table where each cell represents the edit distance between a prefix of the first string and a prefix of the second, built up from the base case of comparing against empty prefixes.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.