levenshtein

edit_distance.py

def minimum (a,b,c):
  val1 = a
  if (b<a):
    val1 = b
  val2 = b
  if (c<b):
    val2 = c
  if val1<val2:
    return val1
  return val2


def edit_distance (s, t):
   m=len(s)+1
   n=len(t)+1
   d=[]
   for i in range(m):
      d.append([])
      for j in range(n):
        d[i].append(0)
   
   for i in range(1,m):
     d[i][0] = i
   
   for j in range(1,n):
     d[0][j] = j
   
   
   for i in range(1,m):
     for j in range(1,n):
       if (s[i-1:i] == t[j-1:j]):
         d[i][j]=d[i-1][j-1] #     // no operation required
       else:
         d[i][j]=minimum(d[i-1][j]+1, #deletion
                      d[i][j-1]+1,  #insertion
                      d[i-1][j-1]+1 #substitution
                    )
   
   return d[m-1][n-1]