Levenshtein Distance

machine-learning

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 $a,b$ is given by ${\text{lev}}_{a,b}(|a|,|b|)$ where:

$${\text{lev}}_{a,b}(i,j)=\{\begin{array}{ll}\max (i,j)& \text{if }\min (i,j)=0\\ \min \{\begin{array}{l}{\text{lev}}_{a,b}(i-1,j)+1\\ {\text{lev}}_{a,b}(i,j-1)+1\\ {\text{lev}}_{a,b}(i-1,j-1)+1_{(a_i\ne b_j)}\end{array}& \text{otherwise}\end{array}$$

where $1_{(a_i\ne b_j)}$ 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:

$$\text{RELEVANT}\stackrel{\text{insert}}{⟶}\text{RELEVPANT}$$

Deletion

The removal of a character from the sequence.

$$\text{RELEVANT}\stackrel{\text{delete}}{⟶}\text{ELEVAN}$$

Substitution

$$\text{RELEVANT}\stackrel{\text{substitute}}{⟶}\text{RELEPHNT}$$

Metric Axioms

The Levenshtein distance satisfies all axioms of a metric, including the triangle inequality.

Computational Complexity

The distance is typically computed in $O(nm)$ time using dynamic programming (e.g., the Wagner–Fischer algorithm).

Example

$$\begin{array}{rl}& \text{RELEVANT}\\ \cancel{\text{R}}& \text{ELE}\text{PH}\text{ANT}\end{array}$$

• $0\text{insertion}$
• $1\text{deletion}$
• $2\text{substitution}$

Levenshtein Distance: $1+2=3$