【Python応用】レーベンシュタイン距離を算出するプログラム

ここでは、Pythonにおけるレーベンシュタイン距離の算出する方法について解説しています。

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

レーベンシュタイン距離(Levenshtein distance)とは、2つの文字列の差異を距離として数値化するものです。編集距離(Edit Distance)とも言われています。

スペルミス修正、類似語句の探索に用いられているものになります。

例えば「トキメキ」と「トクベツ」があるとします。このトキメキをトクベツにするのに何回文字操作が必要かというのがレーベンシュタイン距離となります。

プログラム

def calc_distance(a, b):
    if a == b: return 0
    a_k = len(a)
    b_k = len(b)
    if a == "": return b_k
    if b == "": return a_k
#1---格納するための表
    matrix = [[] for i in range(a_k+1)]
#2---初期化
    for i in range(a_k+1):
        matrix[i] = [0 for j in range(b_k+1)]
#3---0時の初期値を設定
    for i in range(a_k+1):
        matrix[i][0] = i
    for j in range(b_k+1):
        matrix[0][j] = j
#4---表を埋める
    for i in range(1, a_k+1):
        ac = a[i-1]
        for j in range(1, b_k+1):
            bc = b[j-1]
            cost = 0 if (ac == bc) else 1
            matrix[i][j] = min([
                matrix[i-1][j] + 1,
                matrix[i][j-1] + 1,
                matrix[i-1][j-1] + cost
            ])
    return matrix[a_k][b_k]

#5---入力値
print(calc_distance("トキメキ", "トクベツ"))

上記がプログラムになります。内容は表を作成して文字列a、bを埋めて、文字を挿入・削除・置換のうち最小となる値を表に入れて算出しています。

それでは解説していきます。

#1---格納するための表
    matrix = [[] for i in range(a_k+1)]

1の部分では文字列aを格納しています。

#2---初期化
    for i in range(a_k+1):
        matrix[i] = [0 for j in range(b_k+1)]
#3---0時の初期値を設定
    for i in range(a_k+1):
        matrix[i][0] = i
    for j in range(b_k+1):
        matrix[0][j] = j

2の部分では表を0で初期化しています。続いて3の部分では文字列a、ｂ共に0時の初期値を設定しています。

#4---表を埋める
    for i in range(1, a_k+1):
        ac = a[i-1]
        for j in range(1, b_k+1):
            bc = b[j-1]
            k_len = 0 if (ac == bc) else 1
            matrix[i][j] = min([
                matrix[i-1][j] + 1,
                matrix[i][j-1] + 1,
                matrix[i-1][j-1] + k_len
            ])
    return matrix[a_k][b_k]

4の部分では表を埋めています。以下がイメージになります。

#5---入力値
print(calc_distance("トキメキ", "トクベツ"))

最後に関数として呼び出して終了です。

結果

3

出力結果は3です。レーベンシュタイン距離を算出できたことが確認できました。

様々な文字列で試してみると面白そうですね。