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 Time Complexity
Time Complexity (category)Quadratic Time -- O(n^2) 2 Connections
Credited To
Source Levenshtein distance, Wikipedia
In Field
Source Levenshtein distance, Wikipedia
Invented By
Source Levenshtein distance, Wikipedia
Uses 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.
Credited To: Vladimir Levenshtein, Lead section
named after Soviet mathematician Vladimir Levenshtein, who introduced it in 1965
Invented By: Vladimir Levenshtein, Lead section
named after Soviet mathematician Vladimir Levenshtein, who introduced it in 1965
In Field: Algorithms and Complexity Theory, Lead sentence
Levenshtein distance is a string metric for measuring the difference between two sequences.
In Group: Edit Distance and Sequence Alignment Algorithms, Lead section
string metric for measuring the difference between two sequences
View the Source2. Levenshtein Distance Algorithm (Wikipedia)
Wikipedia infobox: time complexity quadraticQuote, Wikipedia infobox: time complexity quadratic
quadratic
Reader 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.