algorithm - 挿入、削除、置換の違いは何ですか

Question

レーベンシュタイン距離に関するプログラミングの問題に取り組もうとしています。そして、私のシートに記載されている定義によると、レンヴェシュタイン距離は2つの文字列間の置換、挿入、および削除の数に等しいと述べています。しかし、置換は単に削除してから挿入するだけではありませんか? ここで何が欠けていますか？

Answer 1

はい、挿入と削除を使用して置換の効果を得ることができます。しかし、挿入と削除のみに制限すると、この方法で作成したそのような「置換」ごとに、1 ではなく 2 のコストがかかります。これは一部のアプリケーションでは現実的かもしれませんが、置換のコストが同じであると想定する方が妥当な場合もあります/コストが 2 倍/可能性が半分ではなく、挿入または削除と同じくらい可能性があります。

[編集]

実際、標準のレーベンシュタイン距離よりもはるかに一般的な編集距離を発明することは可能であり、時には有用です。挿入、削除、および置換に任意のコストを与えることができます。操作のセットを拡張して、転置も含めることもできますab(ba一部の固定コストの場合) またはブロック操作 (一部の固定コストの場合、「位置 i から始まる長さ j の部分文字列のコピーを挿入する」)。もちろん、転置の効果は、削除と挿入を使用する特別な「転置」移動なしで達成できますが、これもまた、削除または挿入のみの移動よりもコストがかかる結果になります。辞書に載っていない単語を入力したときに、その人が「意味する」可能性が最も高い英語の単語を見つけたいというアプリケーションの場合、転置のコストが低い距離を使用することをお勧めします。よくあるタイプミス。