電脳ヨーグルト(技術ブログ)

勉強したことを淡々とメモしていきます

2つの文字列の編集距離を求める関数

こんにちは電脳ヨーグルト(@q0x2tv1)です。

今回は編集距離について書いていきます。

2つの文字列がどの程度異なっているのかを調べる基準として編集距離というものがあります。具体的には1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数のことです。

編集距離については以下の記事で詳しく述べられています。

qiita.com

# 編集距離関数
def edit_distance(s1, s2):
    s1 = '#%s' % s1
    s2 = '#%s' % s2
    n1 = len(s1)
    n2 = len(s2)
    d = [[None for _ in range(n2)] for _ in range(n1)]
    for i in range(n1):
        d[i][0] = i
    for j in range(n2):
        d[0][j] = j
    for i in range(1, n1):
        for j in range(1, n2):
            mismatch = 0 if s1[i] == s2[j] else 1
            d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + mismatch)
    return d[-1][-1]

s1 = "castle" # 城
s2 = "cattle" # 牛

# 関数呼び出し s1とs2の編集距離を求める
edit_dis = edit_distance(s1, s2)
print(edit_dis)