レーベンシュタイン距離を使った文字列差分のアルゴリズム

はじめに

Qiitaの記事を見てVLOOKUPにレーベンシュタイン距離を使うというアイデアに感動しました。

レーベンシュタイン距離は文字列間の距離を出すものです。VLOOKUPは正確に一致した文字列を検索するものですが、あいまい検索できるVLOOKUPは便利です。VLOOKUPにレーベンシュタイン距離を使うことで、最も似た文字列をVLOOKUPできます。

最も似た文字列を探したいという状況で、文字列間の距離で検索したら、Qiitaの記事を見つけて感動しました。

さて、レーベンシュタイン距離を使ったVLOOKUPを使ってみると、文字列間の距離がとても離れた文字列のなかから、距離が最も近い文字列を選ぶことがありました。これは困った状況です。少し違っているが名寄せできる文字列なのか、まったく違う文字列なのかを区別したいわけです。

その解決のためにレーベンシュタイン距離を使った文字列差分を出すアルゴリズムを考えて、プログラムを作りました。本記事ではレーベンシュタイン距離を使った文字列差分を出すアルゴリズムとVBAのプログラムを示します。

本記事の対象者

• レーベンシュタイン距離を出すアルゴリズムをすでに知っている人。
• Excel関数のVLOOKUPをすでに知っている人。
• レーベンシュタイン距離を使った文字列差分を出すアルゴリズムを知りたい人。
• レーベンシュタイン距離を使った文字列差分を出すVBAのプログラムを見たい人。
• レーベンシュタイン距離を使ったVLOOKUPを高速化したい人。

アルゴリズム

次がアルゴリズムのフロー図です。

レーベンシュタイン距離を出すアルゴリズムは二次元配列の最も左上から最も右下に向けて値を埋めていく動的計画法ですが、文字列差分を出すアルゴリズムはその配列の最も右下から最も左上に向けて経路をたどるものです。

文字列差分を出すアルゴリズムは、レーベンシュタイン距離の配列の最も右下から開始して、上の値がマイナス1したものなら1つ上に移動し、左の値がマイナス1したものなら1つ左に移動し、左上の値がマイナス1したものなら1つ左上に移動し、そうでないならプラスマイナス0で1つ左上に移動するというものです。

最終的にはレーベンシュタイン距離の配列の最も左上に到達します。

マイナス1の移動をする際にその位置に対応した1文字を文字列差分に加えていきます。

Excel関数の仕様

文字列差分を返す関数LEVDIFFは、「第1引数の文字列 - 第2引数の文字列」の文字列差分を出します。

=LEVDIFF("文字列1", "文字列2")

第1引数の文字列から第2引数の文字列に向けて、置換と削除で移動する文字を出します。挿入で移動する文字は出しません。

Excelの関数は引数の順番を入れ替えられるので、挿入で移動する文字を出したい場合は、引数の順番を入れ替えて使います。

=LEVDIFF("文字列2", "文字列1")

VBAのプログラム

元のQiita記事にある関数LevenshteinDistanceの名前を変えて使いました。

レーベンシュタイン距離の配列を出した後の部分に、文字列差分を出すプログラムを追加しました。

Function LEVDIFF(ByVal str1 As String, ByVal str2 As String)
    'レーベンシュタイン距離の配列d()からstr1 - str2の文字列差分を出します。
    
    'https://qiita.com/yamashiroakihito/items/875077a7df89c0ad1c36 の関数LevenshteinDistanceを元にしました。
    Dim d()
    Dim lenStr1
    Dim lenStr2
    Dim i1
    Dim i2
    Dim cost
    Dim del
    Dim ins
    Dim rep
    Dim min

    lenStr1 = Len(str1)
    lenStr2 = Len(str2)

    ReDim d(lenStr1, lenStr2)
    For i1 = 0 To lenStr1
        d(i1, 0) = i1
    Next

    For i2 = 0 To lenStr2
        d(0, i2) = i2
    Next

    For i1 = 1 To lenStr1
        For i2 = 1 To lenStr2
           If Mid(str1, i1, 1) = Mid(str2, i2, 1) Then
                cost = 0
           Else
                cost = 1
           End If
           del = d(i1 - 1, i2) + 1   '文字の削除
           ins = d(i1, i2 - 1) + 1   '文字の挿入
           rep = d(i1 - 1, i2 - 1) + cost '文字の置換
           min = del
           If min > ins Then
                min = ins
           End If
           If min > rep Then
                min = rep
           End If
           d(i1, i2) = min
        Next
    Next
    
    'MIT License Copyright (c) 2024 Query Kuma
    'ここから下が配列d()からstr1 - str2の文字列差分を出す追加プログラムです。
    Dim s_result As String
    s_result = ""
    Dim n_temp As Long
    
    i1 = lenStr1
    i2 = lenStr2
    While i1 > 0 And i2 > 0
        n_temp = d(i1, i2)
        If d(i1 - 1, i2) = n_temp - 1 Then   '文字の削除
            s_result = Mid(str1, i1, 1) + s_result
            i1 = i1 - 1
        ElseIf d(i1, i2 - 1) = n_temp - 1 Then   '文字の挿入
            i2 = i2 - 1
        ElseIf d(i1 - 1, i2 - 1) = n_temp - 1 Then '文字の置換
            s_result = Mid(str1, i1, 1) + s_result
            i1 = i1 - 1
            i2 = i2 - 1
        Else '同じ文字
            i1 = i1 - 1
            i2 = i2 - 1
        End If
    Wend
    
    s_result = Left(str1, i1) + s_result
    
    LEVDIFF = s_result
    'ここまで
End Function

補足

標準化されたレーベンシュタイン距離の類似度

標準化されたレーベンシュタイン距離の類似度は 1 ー レーベンシュタイン距離 ÷ 長いほうの文字列長 で出します。類似度は0から1の間の値になります。

「あいうえ」と「あイウエ」の距離は3で、類似度は0.25です。「あいうえ」と「あいうえイウエ」の距離は同じく3ですが、類似度は0.57です。標準化されたレーベンシュタイン距離の類似度を指標にすることで、「あいうえ」に距離が近い文字列として後者の「あいうえイウエ」を選べます。

レーベンシュタイン距離を使ったVLOOKUPの元のプログラムはレーベンシュタイン距離が最小になるセルを見つけますが、標準化されたレーベンシュタイン距離の類似度が最大になるセルを見つけるようにしたほうがいいと思います。

レーベンシュタイン距離を使ったVLOOKUPの高速化

本題からそれますが、書いておきたいと思ったことはレーベンシュタイン距離を使ったVLOOKUPの高速化です。

レーベンシュタイン距離を出すVBA関数の高速化版のいくつかが10年以上前のStack Overflow記事にありました。

最初にワークシート関数版がありました。しかし、ワークシート関数(Application.WorksheetFunction.Min)を使わないことで50倍速くなったそうです。

次にByte版がありました。Mid(s1, i, 1) = Mid(s2, j, 1) の文字列比較が遅いらしく、Byte配列に文字列を入れてから比較し、さらに2番めのByte値を読み飛ばすことで17倍速くなったそうです。

しかし日本語の文字では2番めのByte値が固定値0ではないので、次のように変えて2番めのByte値も比較すべきだと思います。

-If bs1((i - 1) * 2) = bs2((j - 1) * 2) Then   ' *2 because Unicode every 2nd byte is 0
+If bs1((i - 1) * 2) = bs2((j - 1) * 2) And bs1((i - 1) * 2 + 1) = bs2((j - 1) * 2 + 1) Then

レーベンシュタイン距離を使ったVLOOKUPの時間を測ってみたら、次のようになりました。

	時間
Qiita版	約143秒
Stack OverflowのByte版	約46秒
Stack OverflowのByte修正版	約60秒

2番めのByte値も比較してもQiita版の約2.4倍の高速化を行えました。

別のデータで時間を測ってみたらStack Overflowのワークシート関数版はQiita版より3倍以上遅かったです。

謝辞

元のQiita記事はVLOOKUPにレーベンシュタイン距離を使うというアイデアに感動しました。またVBAのプログラムが読みやすく、文字列差分を出すプログラムを作るというアイデアを得られました。Stack Overflow記事は高速化の役に立ちました。謝辞を申し上げます。

さいごに

レーベンシュタイン距離を使った文字列差分を出すアルゴリズムを解説し、VBAのプログラムを示しました。

Stack Overflow記事にあったByte配列で高速化したプログラムを、2番めのByte値を読み飛ばさないように変えて時間を測ったら、レーベンシュタイン距離を使ったVLOOKUPで約2.4倍の高速化を行えました。