文字列の類似度を計算するレーベンシュタイン距離をPython、VBAで実装
文字列が二つあったとき、これらがどれほど類似しているかを知るための指標の一つがレーベンシュタイン距離です。
厳密に言えば「どれほど相違しているかを示す指標」です。
ここにレーベンシュタイン距離を求める方法が擬似コードで示されているのでPythonとVBAで書いてみました。
レーベンシュタイン距離は相違を示す指標なので、二つの文字列の長い方の長さで割り1から減じた数値のほうが使いやすいです。
同じ文字列は1.0になります。
類似度を表す関数をsimirality、レーベンシュタイン距離を求める関数をlevenshteinとしました。
Python
def similarity(str0, str1):
ld = levenshtein(str0, str1)
return 1 - ld / max(len(str0), len(str1))
def levenshtein(str0, str1):
len_str0 = len(str0)
len_str1 = len(str1)
d = [[0 for j in range(len_str1 + 1)] for i in range(len_str0 + 1)]
for i in range(len_str0 + 1):
d[i][0] = i
for j in range(len_str1 + 1):
d[0][j] = j
for i in range(len_str0):
for j in range(len_str1):
cost = 0 if str0[i] == str1[j] else 1
d[i + 1][j + 1] = min(d[i][j + 1] + 1, d[i + 1][j], d[i][j] + cost)
return d[len_str0][len_str1]
ld = levenshtein(str0, str1)
return 1 - ld / max(len(str0), len(str1))
def levenshtein(str0, str1):
len_str0 = len(str0)
len_str1 = len(str1)
d = [[0 for j in range(len_str1 + 1)] for i in range(len_str0 + 1)]
for i in range(len_str0 + 1):
d[i][0] = i
for j in range(len_str1 + 1):
d[0][j] = j
for i in range(len_str0):
for j in range(len_str1):
cost = 0 if str0[i] == str1[j] else 1
d[i + 1][j + 1] = min(d[i][j + 1] + 1, d[i + 1][j], d[i][j] + cost)
return d[len_str0][len_str1]
VBA
Function similarity(str1, str2)
ld = levenshteinDistance(str1, str2)
If Len(str1) > Len(str2) Then
str_len = Len(str1)
Else
str_len = Len(str2)
End If
similarity = 1 - ld / str_len
End Function
Function levenshteinDistance(str1, str2)
x = Len(str1)
y = Len(str2)
ReDim d(x, y)
For i = 0 To x
d(i, 0) = i
Next i
For j = 0 To y
d(0, j) = j
Next j
For i = 1 To x
For j = 1 To y
If Mid(str1, i, 1) = Mid(str2, j, 1) Then
cost = 0
Else
cost = 1
End If
temp = d(i - 1, j) + 1
If temp > d(i, j - 1) + 1 Then
temp = d(i, j - 1) + 1
End If
If temp > d(i - 1, j - 1) + cost Then
temp = d(i - 1, j - 1) + cost
End If
d(i, j) = temp
Next j
Next i
levenshteinDistance = d(x, y)
End Function
ld = levenshteinDistance(str1, str2)
If Len(str1) > Len(str2) Then
str_len = Len(str1)
Else
str_len = Len(str2)
End If
similarity = 1 - ld / str_len
End Function
Function levenshteinDistance(str1, str2)
x = Len(str1)
y = Len(str2)
ReDim d(x, y)
For i = 0 To x
d(i, 0) = i
Next i
For j = 0 To y
d(0, j) = j
Next j
For i = 1 To x
For j = 1 To y
If Mid(str1, i, 1) = Mid(str2, j, 1) Then
cost = 0
Else
cost = 1
End If
temp = d(i - 1, j) + 1
If temp > d(i, j - 1) + 1 Then
temp = d(i, j - 1) + 1
End If
If temp > d(i - 1, j - 1) + cost Then
temp = d(i - 1, j - 1) + cost
End If
d(i, j) = temp
Next j
Next i
levenshteinDistance = d(x, y)
End Function
[ 2022年11月12日 | カテゴリー: Python | タグ: Python , VBA , 類似度 ]
« Excelでちょっと複雑な情報を取得する「Excel用API」 | Pythonの2次元リストを扱うときの注意 »
コメントを残す