Python 編集距離

今日は、Python の編集距離について学習します。 また、文字列の挿入、削除、置換、および再帰的な実装についても検討します。

Python で距離を編集

編集距離は、ストリングから別のストリングへの転置に必要な量です。 この転置は、文字列の文字の再帰、置換、挿入、および削除によって行われます。

ある単語を別の単語に変換するために必要な文字の削除、挿入、および置換の数は、2つの単語がどれだけ厳密に編集されたかによって異なります。

Python では、Levenshtein 距離として扱われます。これは、比較する 2つの文字列が同じ長さである必要がないためです。 レーベンシュタイン 距離は大きな影響を与えます。

レーベンシュタイン 距離は、直感的に理解するのが簡単です。 1 文字の変更の合計数によって、2つの間の距離が決まります。

出力距離は、2つの単語を同一にするために必要な変更の数を示します。 出力距離が小さいほど、必要な変更は少なくなります。

文字列の挿入、削除、置換、再帰の実装について、以下のコード例を使って編集距離を理解してみましょう。

文字列の挿入

次のコードでは、単語 machine の i と n の間に t が挿入されています。

コード例:

w = "Machine"
w = w[:5] + "t" + w[5:]
print(w)

出力：

Machitne

文字列の削除

次のコードでは、単語 machine の a と h の間の c が削除されています。

コード例:

w = "Machine"
w = w[:2] + w[3:]
print(w)

出力：

Mahine

文字列の置換

次のコードでは、単語 machine の a と h の間の c が a に置き換えられています。

コード例:

w = "Machine"
w = w[:2] + "a" + w[3:]
print(w)

出力：

Maahine

文字列の再帰的実装

次の出力に示すように、machine と learning の間の編集距離は 5 です。

ユーザーから任意の文字列入力を受け取ることができ、Levenshtein 距離は次の Python メソッドで再帰的に実装されます。

この再帰的手法は、同じ部分文字列の レーベンシュタイン 距離が繰り返し計算されるため、非効率的です。

コード例:

w1 = input("Type here for word 1: ")
w2 = input("Type here for word 2: ")

len1 = len(w1)
len2 = len(w2)

a = [[0] * (len2 + 1) for _ in range(len1 + 1)]

for m in range(0, len1 + 1):
    a[m][0] = m

for n in range(0, len2 + 1):
    a[0][n] = n

for m in range(1, len1 + 1):
    for n in range(1, len2 + 1):
        if w1[m - 1] == w2[n - 1]:
            a[m][n] = a[m - 1][n - 1]
        else:
            a[m][n] = min(a[m][n - 1], a[m - 1][n], a[m - 1][n - 1]) + 1
print(a[m][n])

出力：

Type here for word 1: machine
Type here for word 2: learning
5