VBA で文字列の類似性を測る(レーベンシュタイン距離)

こんにちは。
仕事の自動化にやりがいと達成感を感じるガッくんです。

この記事の目次

目的

機械学習やディープラーニングがトレンドなのに今さらですが、レーベンシュタイン距離を使う機会があったので、まとめておきます。
というかレーベンシュタイン距離の方が良い精度だったものでレーベンシュタイン距離を使いました。

関数

ソースコード
〜レーベンシュタイン距離〜

レーベンシュタイン距離を簡単に言うと『何回編集すると同じ文字列になるか』で、編集回数を求めます。

Function LevenshteinDistance(strA, strB)
   
    x = Len(strA)
    y = Len(strB)
    ReDim d(x, y)
    ReDim str1(x)
    ReDim str2(y)
   
    For n = 1 To x
        str1(n - 1) = Mid(strA, n, 1)
    Next n
   
    For n = 1 To y
        str2(n - 1) = Mid(strB, n, 1)
    Next n
   
    For i = 0 To x
        d(i, 0) = i
        For j = 1 To y
            d(i, j) = 0
        Next j
    Next i
   
    For j = 0 To y
        d(0, j) = j
    Next j
   
    cost = 0
    For i = 1 To x
        For j = 1 To y
            If str1(i - 1) = str2(j - 1) Then
                cost = 0
            Else
                cost = 1
            End If
            d(i, j) = WorksheetFunction.Min(d(i - 1, j) + 1, d(i, j - 1) + 1, d(i - 1, j - 1) + cost)
        Next j
    Next i
   
    LevenshteinDistance = d(x, y)
   
End Function

使い方

実際にレーベンシュタイン距離を算出してみます。

Sub 使い方()
   
    str1 = "今日は晴れですね"
    str2 = "今日は曇りだよね"
   
    MsgBox LevenshteinDistance(str1, str2)
   
End Sub

上記の使い方では最後のMsgBoxで『4』と表示されます。

コメント

とても短い文の類似度、 DNA の類似度なんかはレーベンシュタイン距離が適していると思います。

とても短い文は単語などのトレンドが出来るほど文が長くないので、他の類似度計算方法だと微妙な場合もあります。
また、構文的に似ているかどうかもレーベンシュタイン距離には影響するので、短い文には適しているものと思います。

DNA の類似度については編集距離そのものがまさに類似度なので、レーベンシュタイン距離を適用する事もあるようです。

以上