[解決済み] 2文字列間の削除距離

質問事項

この問題のアルゴリズムがわからずに困っています。問題の説明と、正しい解答ではありませんが、なんとなく解いた方法を貼り付けます。 編集距離アルゴリズムに似ていて、同じようなアプローチを使いましたが、何かが違っていて、正確に把握することができません。

2つの文字列間の削除距離は、2つの文字列のASCII文字列の最小値の合計です。 2つの文字列で削除する必要がある文字の値です。 を使えば、同じ文字列になります。catと を削除すればよいので、99となります。 c'のASCII値は99です。 両者の最初の文字を削除する必要があるため、98＋99となります。 という単語があります。もちろん、2つの文字列の間の削除距離は、以下のようになることはできません。 ASCII値の合計よりも大きい値を指定することができるからです。 常に両方の文字列を完全に削除すればよいのです。そこで の削除距離を求める効率的な関数です。 文字列のアルゴリズムについては、ウィキペディアの記事を参照することができます。 編集距離 そのアルゴリズムは ここで要求されているアルゴリズムと同じですが、似ています。

これは私のコードです。ダイナミックプログラミングの手法を使いました。 最後の "else" の後の行を変更する必要があると思いますが、間違いがあれば遠慮なく訂正してください。

def delete_distance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                m[i][j] = ord(s1[i-1]) + ord(s2[j-1]) + min(m[i-1][j-1], m[i-1][j], m[i][j-1])
    return m[len(s1)][len(s2)]

delete_distance('cat', 'cbat') の出力が197なので、間違っていることがわかります。正しい結果は98のはずです。なぜなら、ASCII値98を持つbを削除すればよいからです。

どのように解決するのですか？

前回のKen Y-Nさんの回答にもありましたが、elseの部分は最低でも3つの演算コストが必要です。 この回答で唯一変わったのは、あなたの問題に合うように言い直したことです。

3つの操作とは

• S1 削除
• S2 削除
• S1 & S2両方削除

以下はうまくいくはずです〜。

def delete_distance(s1, s2):
    m = [[0 for j in range(len(s2)+1)] for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        for j in range(len(s2)+1):
            if i == 0:
                m[i][j] = sum(bytearray(s2[:j]))
            elif j == 0:
                m[i][j] = sum(bytearray(s1[:i]))
            elif s1[i-1] == s2[j-1]:
                m[i][j] = m[i-1][j-1]
            else:
                s1del = ord(s1[i-1])
                s2del = ord(s2[j-1])
                s1s2del = s1del + s2del
                m[i][j] = min(m[i-1][j-1] + s1s2del, m[i-1][j] + s1del, m[i][j-1] + s2del)
    return m[len(s1)][len(s2)]

お役に立てれば幸いです。