レーベンシュタイン距離-Levenshtein distanceとは

レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される[1]。名称は、1965年にこれを考案したロシアの学者ウラジーミル・レーベンシュタイン (露: Влади́мир Левенште́йн) にちなむ。

とWikipediaにあります。

ひとつ例をあげてみます、　’grape’　と　’group’　で考えてみます。

1、2文字目までの　’gr’　は同じです。
'grape' 'group'
3文字目では　’a’　’o’　と違う文字なので同じものに置換しましょう。置換には1コストがかかります。
'gr a pe' 'gr o up' ==> 'grape' 'gr a up'
4文字目は　’p’　と　’u’　とで違う文字ですが、5文字目に　’p’　があるので、ここでは置換ではなく　’u’　を削除した方が手順を省略できそうです。削除に1コスト要します。
'gra p e' 'gra up' ==> 'grape' 'grap'
あとは足りない　’e’　の文字を挿入するだけです。挿入に1コストかかります。
'grape' 'grap' ==> 'grape' 'grape'

	'grape'	'group'	Operation	Cost
1	g	g	None	0
2	r	r	None	0
3	a	o	Replace	1
4	p	u	Delete	1
5	e	(p)	Insert	1
Total				3

となり、この二つの文字列のレーベンシュタイン距離は３となります。
今回はそれぞれの置換、挿入、削除の操作のコストを１としましたが、場合によってはコストを違った値に設定することもあるようです。

レーベンシュタイン距離はスペルチェックや、さらに応用するとDNA配列の類似性などにも活用されるらしいです。

実装

早速、実装していくのですが、今回はループを使ったものと再帰を利用した2つのパターンの方法を試してみたいと思います。
また実装には Pythonを使ってみます。

パターン１　二重ループ

LevenshteinDistance.py

def LevenshteinDistance(s1,s2):
    if len(s1) > len(s2):
        s1,s2 = s2,s1
    distances = range(len(s1) + 1)
    for index2,char2 in enumerate(s2):
        newDistances = [index2+1]
        for index1,char1 in enumerate(s1):
            if char1 == char2:
                newDistances.append(distances[index1])
            else:
                newDistances.append(1 + min((distances[index1],
                                             distances[index1+1],
                                             newDistances[-1])))
        distances = newDistances
    return distances[-1]
 
print(LevenshteinDistance("grape","group"))

先に全体のコードを記述しておきます。
順に追ってみていきます。

Definition

def LevenshteinDistance(s1,s2):
LevenshteinDistance　の名前で定義します。
2つのStringを受け取ります。

前準備

.py

if len(s1) > len(s2):
        s1,s2 = s2,s1

長さによって順番を調整します。
短い方がs1にアサインされます。

distance変数を作りrange(len(s1) + 1)をアサインする。
例えばs1が'grape'だと５文字＋１の０から５、

.py

range(0, 6)

が格納されます。

動的計画法

レーベンシュタイン距離を計算するには動的計画法がよく使われます。

動的計画法は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

テーブルで考えるとわかりやすいです。

		g	r	a	p	e
	0	1	2	3	4	5
g	1	0	1	2	3	4
r	2	1	0	1	2	3
o	3	2	1	1	2	3
u	4	3	2	2	2	3
p	5	4	3	3	2	3

対応する2つの文字列の編集距離がそのマスに当てはまります。
grapeの２文字目までとgroupの３文字目までを考えると

		g	r
	0	1	2
g	1	0	1
r	2	1	0
o	3	2	1
u
p

挿入、削除する場合、1を足して横か縦に進みます。
置換する場合、1を足して斜め下に、操作が必要ない場合何も足さずに斜め下
に進みます。

ループ処理

.py

for index2,char2 in enumerate(s2):
        newDistances = [index2+1]
        for index1,char1 in enumerate(s1):
            if char1 == char2:
                newDistances.append(distances[index1])
            else:
                newDistances.append(1 + min((distances[index1],
                                             distances[index1+1],
                                             newDistances[-1])))
        distances = newDistances

さきほど出てきたテーブルでの処理をループで実装しています。

.py

for index2,char2 in enumerate(s2):
        newDistances = [index2+1]

enumerateはリストや文字列をループしてくれて勝手にカウントしてくれるビルトインのファンクションです。
groupだと　0,g > 1,r > 2,o > 3,u > 4,p　といった具合です。

newDistancesはテーブルで考える、次に進むマスの空箱と思ってください。

.py

        for index1,char1 in enumerate(s1):
            if char1 == char2:
                newDistances.append(distances[index1])
            else:
                newDistances.append(1 + min((distances[index1],
                                             distances[index1+1],
                                             newDistances[-1])))

比較となるもう一方の文字列も同じようにenumerateを使ってループします。

.py

            if char1 == char2:
                newDistances.append(distances[index1])

比較する２つの文字が同じだとdistances[index1]がnewDistancesに入ります。
これはテーブルでのコスト無しで斜め下に進むやつです。

.py

            if char1 == char2:
                newDistances.append(distances[index1])
                print(distances[index1])

distances[index1]を出力してみると

0
0
2

となります。
今回での2つの文字列の場合、g、r、pが同じ文字なので３回、char1 == char2に当てはまることになります。

.py

            else:
                newDistances.append(1 + min((distances[index1],
                                             distances[index1+1],
                                             newDistances[-1])))

文字が同じ出ない場合、なんらかの操作をする必要があります。
削除、挿入、置換、３種類の操作を最小のコストで行えるルートをminによって選別します。そしてnewDistancesに入れます。
distances[index1]　は挿入
distances[index1+1]　は削除
newDistances[-1]　は置換
に対応します。初めの　＋１　は操作にかかるコストを表します。
1を足して各操作を行ったうちの最小値がnewDistances入り
distancesとなります。

これを繰り返し、最終的に
return distances[-1]
でdistancesの一番後ろにある値をリターンします。
テーブルでいう所の一番右下ですね。

パターン２　再帰

RecursiveLevenshteinDistance.py

def LevenshteinDistance(s, t):
	if s[0] == t[0]: return LevenshteinDistance(s[1:], t[1:])
	l1 = LevenshteinDistance(s, t[1:])
	l2 = LevenshteinDistance(s[1:], t)
	l3 = LevenshteinDistance(s[1:], t[1:])
	return 1 + min(l1, l2, l3)
    
print(ld('grape', 'group'))

コンパクトになりました。
仕組みは先ほどのコードとあまり変わらないのでサクッと紹介します。

再帰

Computer Scienceに置いての再帰とは

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science. Wikipedia

とあります。
大きな概念なので詳しくは調べてみて欲しいのですが１つ簡単な例をあげると

recursion.py

def recursion(n):
    if (n==0): return 0
    elif (n==1): return 1

    return recursion(n-1) + recursion(n-2)

print(recursion(10))

関数の中でまた関数が呼び出されています。

10から下に降りていくように計算されていきます。
10＋9＋……1　となります。

再帰は強力で難しいものなので自分でも調べてみてください。

中身

.py

if s[0] == t[0]: return LevenshteinDistance(s[1:], t[1:])

は文字が同じ場合の操作に対応します。
s[1:]は最初の文字を除いたものs=groupだとs[1:]=roup

a[start:stop]  # items start through stop-1
a[start:]      # items start through the rest of the array
a[:stop]       # items from the beginning through stop-1
a[:]           # a copy of the whole array

となります。
同じ文字があるとそこを除く、スキップする形になります。

.py

	l1 = LevenshteinDistance(s, t[1:])
	l2 = LevenshteinDistance(s[1:], t)
	l3 = LevenshteinDistance(s[1:], t[1:])
	return 1 + min(l1, l2, l3)

１つ１つ比べていき調べ終わったものを弾いていきます。
l1はtの文字をt[1:]で弾くので削除、
grape groupの３文字目からを考えるとs, t[1:]でape upとなりますね。
l2はsの文字をs[1:]で弾くので挿入、
l3はs[1:], t[1:]でどちらも弾くので置換、
が対応します。
そしてそれぞれの操作のコストが一番かからない値を選びます。