レーベンシュタインアルゴリズム
アルゴリズム
Input
文字列 $A,B$を $A=[a_{i}]=(a_{1}, a_{2} , \cdots, a_{n})$と $B=[b_{j}]=(b_{1}, b_{2} , \cdots, b_{m})$に表す。
Step 1. 初期化
行列 $M_{(n+1) \times (m+1)} = [m_{x y }]$を作り、$M_{11} ← 0$を代入する。そして$1$行と$1$列を以下のように埋める。 $$ M_{(i+1) 1} ← i \\ M_{ 1 (j+1)} ← j $$
Step 2. 動的計画法
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
$A$と$B$の最小編集距離は$m_{nm}$だ。
説明
編集距離とは、二つの文字列間の類似度を示す尺度で、$A$を$B$に変換するために何回かかるかを示すものです。その中でレーベンシュタイン距離levenstein distanceは、挿入insertion、削除deletion、置換replaceの三つの編集を許可し、転置transpositionは許可しない。
例
たとえば、‘cats’と’facts’という文字列があるとします。
- (置換) cats → fats
- (挿入) fats → facts
これにより、編集距離は$2$となることがわかります。
しかし、このような編集距離は非効率的な方法を使用することでどれだけでも長く測定できるのです。たとえば、cats → ats → fats → facts のようにです。レーベンシュタインアルゴリズムは、この距離をできるだけ小さく計算する方法を提供します。
コード
R
以下のRコードで例を解いたスクリーンショットです。
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で書いたものです。
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]