レーベンシュタイン距離

１．レーベンシュタイン距離とは

　レーベンシュタイン距離（Levenshtein distance）は、2つの文字列がどれぐらい似ているかを示す指標です。ある文字列を別の文字列に1文字ずつ変換していき、何度変換すればよいかを調べ、その中で最小限の変換回数のことをいいます。1文字の変換は、挿入、削除、置換の3種類を使います[1][2][3]。
　

２．計算の例１

　たとえば
a「みよしのの」とb「よしのやまの」の２つの文字列を調べると

１回目
a：みよしのの
b：みよしのやまの　　先頭に「み」追加
２回目
a：みよしのやの　　　途中に「や」追加
b：みよしのやまの
３回目
a：みよしのやまの　　途中に「ま」追加
b：みよしのやまの

と、３回の変換をすると、最小の変換回数で文字列が一致しますので、レーベンシュタイン距離は３です。

３．計算の例２

長い文字列でも同様に計算でき、以下のような場合にも利用できます。
「人を思ふ心はかりにあらねどもくもゐにのみもなきわたるかな」
（古今集585番　よみ人しらず）
と、
「人のおやの心はやみにあらねども子を思ふ道にまどひぬるかな」
（後撰集1102番　藤原兼輔）
は、前者を先行歌として後者は作歌されたと見られ、よく似ています[4]。この場合のレーベンシュタイン距離は17です。

４．計算の考え方

　レーベンシュタイン距離の算出は、次のように逐次的に行います。
なお、文字列aと文字列bがあり、先頭からi番目、j番目までの部分をa(1, i)、b(1, j)、そこまでの累積の距離をL(i, j)などと書きます。

１．長さiの文字列と、１文字長い文字列の距離は、１文字の挿入または削除で一致するので、距離の増分は+1。
２．a(1, i)とb(1, j)までの距離がL(i, j)であった時、a(1, i)とb(1, j+1)では、文字列bが１文字長くなっただけなので、距離の増分は+１になり、L(i, j+1) = L(i, j) + 1。
３．同様にa(1, i+1)とb(1, j)では、L(i+1, j) = L(i, j) + 1。
４．a(1, i)とb(1, j)までの距離がL(i, j)であった時、a(1, i+1)とb(1, j+1)では、i+1番目とj+1番目の文字を比較して、一致していれば距離の増分は+0、不一致なら増分は+1。L(i+1 , j+1) = L(i, j) +増分。

５．ソースコード

　これをVBAにしたものが以下です。
Private Function LSDist(sa As String, sb As String) As Long に２つの文字列を引数で渡すと距離を計算して返します。
下にExcelファイルを付けておきます。

Public Sub main()
   
    Dim a As String, b As String
    a = InputBox("文字列１を入力してください。")
    b = InputBox("文字列２を入力してください。")
    
    Dim lsd As Long
    lsd = LSDist(a, b)
    
    MsgBox a & vbCrLf & _
        "と" & vbCrLf & _
        b & vbCrLf & _
        "の" & vbCrLf & _
        "レーベンシュタイン距離" & vbCrLf & _
        lsd
End Sub


' レーベンシュタイン距離を計算
Private Function LSDist(sa As String, sb As String) As Long
    
    ' 文字列の長さを取得
    Dim lsa As Long
    Dim lsb As Long
    lsa = Len(sa)
    lsb = Len(sb)
    
    ' 初期化
    Dim i As Long, j As Long, cost As Long
    Dim delta As Long
    Dim d() As Long
    ReDim d(0 To lsa, 0 To lsb)
    
    '一方の文字列が空のとき
    j = 0
    For i = 0 To lsa
        d(i, j) = i
    Next
    i = 0
    For j = 0 To lsb
        d(i, j) = 0
    Next
    
    ' 文字列を比較して、レーベンシュタイン距離を計算
    For i = 1 To lsa
        For j = 1 To lsb
            cost = 1
            If Mid(sa, i, 1) = Mid(sb, j, 1) Then
                cost = 0
            End If
            
            delta = d(i - 1, j) + 1
            If delta > d(i, j - 1) + 1 Then
                delta = d(i, j - 1) + 1
            End If
            If delta > d(i - 1, j - 1) + cost Then
                delta = d(i - 1, j - 1) + cost
            End If
            d(i, j) = delta
        Next j
    Next i
    
    LSDist = d(lsa, lsb)
End Function

６．参考文献

１．「EXCEL VBA 類似データを検索・文字列の類似性を評価・あいまいなデータを検索（レーベンシュタイン距離）」、https://akira55.com/levenshteindistance/ 、2024.1.19 閲覧
２．「＜面白い技術＞文章がどれだけ似ているかを確認するための概念」、https://availsolutions.co.jp/blog/%E3%83%8F%E3%82%A6%E3%83%84%E3%83%BC/203 、2024.1.19 閲覧
３．「レーベンシュタイン距離」、https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2 、2024.1.19 閲覧
４．「和歌データからの類似歌発見」、竹田,福田,南里,山崎,玉利、統計数理(2000)第48巻第2号289–310、https://www.ism.ac.jp/editsec/toukei/pdf/48-2-289.pdf

レーベンシュタイン距離.xlsm

16.6 KB

ファイルダウンロードについて

ダウンロード

#Excel , #VBA , #レーベンシュタイン距離