插入，刪除和替換之間有什麼區別

Question

我正要解決有關Levenshtein距離的編程問題。根據我在表格中給出的定義，它指出Lenveshtein距離等於兩個字符串之間的替換，插入和刪除的數量。然而，不會只是一個刪除，然後插入？我在這裏錯過了什麼？

Answer 1

您可以使用插入加刪除來實現替換效果，是的。但是，如果僅限於自己的插入和刪除，則以這種方式創建的每個這樣的「替換」將花費您2而不是1.對於某些應用程序來說這可能是現實的，但有時候假設替代花費相同/與插入或刪除一樣可能，而不是成本的兩倍/可能的一半。

[編輯]

事實上，它是可能的，有時是有用的發明而非標準的Levenshtein距離更普遍編輯距離。您可以給任何費用插入，刪除和替換。您甚至可以擴展該操作集以包括換位（對於某些固定成本，更改ab至ba）或阻止操作（「從位置i開始插入長度爲j的子串的副本」以獲得某些固定成本）。換位的效果當然可以在沒有使用刪除加插入的特殊「換位」移動的情況下實現，但是這再次導致移動成本比單獨刪除或插入花費更多。如果你的應用是你想找到一個人在輸入一個不在字典中的單詞時最有可能「意味着」的英文單詞，那麼你可能更願意使用一個轉移成本較低的距離，因爲這是一個常見的打字錯誤。