文字列の類似度を計算するレーベンシュタイン距離を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]

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

コメント

タイトルとURLをコピーしました