編集距離についての説明及びPythonでの実装

アルゴリズムの説明

編集距離(レーベンシュタイン距離)はつまりある文字列をもう一つの文字列に変えるためかかるステップ数
そのステップは、
・一文字を削除する
・任意の一文字を挿入する
・文字一文字を他の文字と置き換える
のいずれかである

まずレーベンシュタイン距離のアルゴリズムを理解しよう

例えば文字列cafeとcoffeeの場合だと
cafe→caffe→coffe→coffee
こんな感じですね

最初はまず表を作りましょう

		c	o	f	f	e	e
c
a
f
e

初期値を入れましょう
対象文字列が空の時（対象文字列はこれからちょっとづつ増やす）、もちろんレーベンシュタイン距離は文字列の長さと等しい
なので

		c	o	f	f	e	e
	0	1	2	3	4	5	6
c	1	*
a	2
f	3
e	4

(3,3)の「＊」から本番のアルゴリズム始まります
これから残ったセルは、すべてこの下の最小値になります
・もしこのセルにある列の一番上の文字と、このセルにある行の一番左の文字が同じであれば、このセルの値は左上のセルの値と等しい、そうじゃなければ左上のセルの値＋１になる
・左のセルの値＋１
・上のセルの値＋１

ここでは、(3,3)の場合だと
・(3,3)にある列の一番上の文字"c"と行の一番左の文字"c"が同じなので0になる
・(2,3)になるため1になる
・(3,2)になるため1になる
この上の三つの値の最小値を取るため、(3,3）が0になる

		c	o	f	f	e	e
	0	1	2	3	4	5	6
c	1	0
a	2
f	3
e	4

このように、すべてのセルを埋めよう

		c	o	f	f	e	e
	0	1	2	3	4	5	6
c	1	0	1	2	3	4	5
a	2	1	1	2	3	4	5
f	3	2	2	1	2	3	4
e	4	3	3	2	2	2	3

この表を得る。この表の一番右下の値がレーベンシュタイン距離になる

Python 3.5.2による実装

このアルゴリズムをプログラムにまとめると

levenshtein.py

class Levenshtein:
#ここで配列を立ち上げて、初期値を入れる
    def initArray(self,str1,str2):
        distance = []
        for i in range(len(str1)+1):
            distance.append([0]*(len(str2)+1))
            distance[i][0] = i
        for j in range(len(str2)+1):
            distance[0][j] = j
        return distance
#セルに値を入れる
    def editDist(self,str1,str2,distance):
        dist = [0]*3
        for i in range(1,len(str1)+1):
            for j in range(1,len(str2)+1):
                dist[0] = distance[i-1][j-1] if str1[i-1]==str2[j-1] else distance[i-1][j-1]+1
                dist[1] = distance[i][j-1]+1
                dist[2] = distance[i-1][j]+1
                distance[i][j]=min(dist)
        return distance[i][j]

    def __init__(self,str1,str2):
        self.str1 = str1
        self.str2 = str2
        Levenshtein.distance = self.initArray(str1,str2)
        Levenshtein.dist = self.editDist(str1,str2,Levenshtein.distance)

if __name__ == '__main__':
    str1 = 'coffee'
    str2 = 'cafe'
    leven = Levenshtein(str1,str2)
    print(leven.dist)