Definition
Levenshtein Distance
The Levenshtein distance (or edit distance) is a string metric for measuring the difference between two sequences. Formally, the Levenshtein distance between two strings
is given by where: where
is the indicator function. It represents the minimum number of single-character edits required to change one sequence into the other.
Permissible Operations
Insertion
The addition of a character to the sequence:
Deletion
The removal of a character from the sequence.
Substitution
Metric Axioms
The Levenshtein distance satisfies all axioms of a metric, including the triangle inequality.
Computational Complexity
The distance is typically computed in
Example
Levenshtein Distance: