📂Algorithm

Levenshtein Algorithm

Algorithm

Input

Let us represent the strings $A,B$ as $A=[a_{i}]=(a_{1}, a_{2} , \cdots, a_{n})$ and $B=[b_{j}]=(b_{1}, b_{2} , \cdots, b_{m})$.

---

Step 1. Initialization

Create a matrix $M_{(n+1) \times (m+1)} = [m_{x y }]$ and assign $M_{11} ← 0$. Then fill row $1$ and column $1$ as follows. $$ M_{(i+1) 1} ← i \\ M_{ 1 (j+1)} ← j $$

---

Step 2. Dynamic Programming

for $i = 1, 2, \cdots , n$ and $j=1,2, \cdots , m$

　　if $a_{i}==b_{j}$

　　　　$M_{i,j} ← M_{(i-1)(j-1)}$

　　else

　　　　$M_{i,j} ← \min \left\{ M_{(i-1)(j)}, M_{(i)(j-1)}, M_{(i-1)(j-1)}\right\} + 1 $

---

Output

The minimum edit distance between $A$ and $B$ is $m_{nm}$.

Explanation

The edit distance is a measure showing the similarity between two strings, indicating how many steps it takes to change $A$ into $B$. Among these, the levenstein distance allows three edits—insertion, deletion, and replace—but does not allow transposition.

Example

For instance, suppose we have the strings ‘cats’ and ‘facts’. Then

1. (replace) cats → fats2. (insertion) fats → facts

we can see that it is modified twice in total, so the edit distance is $2$.

However, such an edit distance can be measured to be arbitrarily long, because there are also inefficient methods such as cats → ats → fats → facts. The Levenshtein algorithm is a method to find this so that the edit distance becomes the smallest.

Code

R

The screenshot above shows the example solved with the R code below.

LED<-function(A,B)
{
  A<-strsplit(A,'')[[1]]
  B<-strsplit(B,'')[[1]]
  lA<-length(A)
  lB<-length(B)
  
  M<-matrix(NA,ncol=lA+1,nrow=lB+1,dimnames = list(c('',B),c('',A)))
  M[1,]<-0:lA
  M[,1]<-0:lB
  
  for(i in (1:lB)+1)
  {
    for(j in (1:lA)+1)
    {
      if (B[i-1]==A[j-1])
      {
        M[i,j]<-M[i-1,j-1]
      }
      else
      {
        M[i,j]<-min(M[i-1,j-1],M[i,j-1],M[i-1,j])+1
      }
    }
  }
 
  return(list(distance=c(M[lB+1,lA+1]),matrix=M))
}
 
LED("cats","facts")

Python

The following is the same code written in Python.

def ED(a,b) :
    a = ":".join(a)
    A = a.split(":")
    a = len(A)
    b = ":".join(b)
    B = b.split(":")
    b = len(B)
    M = [[j for i in range(a+1)] for j in range(b+1)]
    M[0] = [i for i in range(a+1)]
    for i in (range(1,b+1)) :
        for j in (range(1,a+1)) :
            if B[i-1]==A[j-1] :
                M[i][j] = M[i-1][j-1]
            else :
                M[i][j] = min(M[i-1][j-1],M[i][j-1],M[i-1][j]) + 1
    return M[b][a]