レーベンシュタイン距離(WLD)

二つの文字列の非類似度を定義する。ある記号列str1とstr2がり、str2をa個入れ替えてb個挿入し、c個削除することでstr1が得られるとき、そのときのレーベンシュタイン距離は以下になる。

\( WLD(str1,str2) = min(p a+q b+r c) \)

ここで、p,q,rは重みパラメータである。この問題を解くために動的計画法（問題を分割し、答えを記憶しながら問題を解く方法）を使う。

#! /usr/bin/env python
import numpy as np

def match(a,b):
    if a==b:
        return 0
    else:
        return 1

def wld(str1,str2):
    str1_len=len(str1)
    str2_len=len(str2)
    D=np.zeros((str1_len+1,str2_len+1))
    distance=0
    p=1;                   #weight 
    q=1;                   #weight 
    r=1;                   #weight 

    for i in range(1,str1_len+1):
        D[i,0]=D[i-1,0]+1*r
    for i in range(1,str2_len+1):
        D[0,i]=D[0,i-1]+1*q
    for i in range(1,str1_len+1):
        for j in range(1,str2_len+1):
            m1=D[i-1,j-1]+match(str1[i-1],str2[j-1])*p
            m2=D[i,j-1]+1*q
            m3=D[i-1,j]+1*r
            print i,j,"==>",m1,m2,m3,min([m1,m2,m3])
            D[i,j]=min([m1,m2,m3])
    return D(str1_len,str2_len)

print wld("book","sooks")