レーベンシュタイン距離

レーベンシュタイン距離とは、2つの言葉がどのくらい似ているかを表す指標。

例えば

“apple”と”play”のレーベンシュタイン距離は5

“sitting”と”kitten”のレーベンシュタイン距離は3

レーベンシュタイン距離を考えるときは、こんな感じの表を作る。

それぞれのマスにレーベンシュタイン距離を書いていく。

それぞれの一番最初の行と列はどんなときでもこう↓

レーベンシュタイン距離をそれぞれ入力していくとこうなる↓

結果、”sitting”と”kitten”のレーベンシュタイン距離は右下の数字「3」となる。

実際に表を書くと気づくけど、レーベンシュタイン距離は、二つの文字列の長さの差と、置換する文字列の数で決まる。

これをpythonで書くと

def levenshtein(s1,s2):
    n,m = len(s1), len(s2)
    
    dp = [[0] * (m+1) for _ in range(n+1)]    #表の骨組み作成
    
    #print(dp)   #確認用
    
    for i in range(n+1):     #いつでもこう
        dp[i][0] = i
    for j in range(m+1):
        dp[0][j] = j
    
    #print(dp)   #確認用
    
    for i in range(1,n+1):
        for j in range(1,m+1):
            cost = 0 if s1[i-1] == s2[j-1] else 1 #置換するなら0、しないなら1
            dp[i][j] = min(dp[i-1][j] +1,
                           dp[i][j-1] +1,
                           dp[i-1][j-1] +cost)
    return dp[n][m]

このレーベンシュタイン距離は、スペルミスとか近似文字列照合とかに使われるらしい。

https://takuti.me/note/levenshtein-distance/