查找所有子串的編輯距離的算法

給出2個字符串s和t。我需要找到s編輯距離（Levenshtein距離）到t的每個子串。實際上我需要知道s中每個i位置對於從位置i開始的所有子串的最小編輯距離是多少。查找所有子串的編輯距離的算法

例如：

t = "ab"  
s = "sdabcb"

我需要得到類似的東西：

{2,1,0,2,2}

說明：

1st position: 
distance("ab", "sd") = 4 (2*subst) 
distance("ab", "sda") = 3(2*delete + insert) 
distance("ab", "sdab") = 2 (2 * delete) 
distance("ab", "sdabc") = 3 (3 * delete) 
distance("ab", "sdabcb") = 4 (4 * delete) 
So, minimum is 2 

2nd position: 
distance("ab", "da") = 2 (delete + insert) 
distance("ab", "dab") = 1 (delete) 
distance("ab", "dabc") = 2 (2*delete) 
.... 
So, minimum is 1 

3th position: 
distance("ab", "ab") = 0 
... 
minimum is 0

等等。

當然，我可以使用強力算法來解決這個任務。但是有更快的算法嗎？

感謝您的幫助。

來源

2011-11-15 Ivan Bianko

我知道你的答案'{2,1，** 0,2 **，2}'是錯誤的，因爲相鄰的數字最多可以相差1：如果存在子字符串s [i..j ]'，最小編輯距離爲'k'到't'，那麼子串[[i + 1] ... j]在字符串的最開始插入's [i]'。在你的例子中，對於第四個位置，距離（「ab」，「b」）= 1「（1插入），對於第五個」距離（「ab」，「cb」）= 1「。 –

的瓦格納 - 菲捨爾算法爲您提供了「免費」的所有前綴的答案。

http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm

瓦格納 - 費歇爾矩陣的最後一列包含從s每個前綴到t編輯距離。

，以便在您的問題第一次破裂，每個i，運行瓦格納 - 菲捨爾和最後一行中選擇最小的元素。

我會很好奇，想看看是否有人知道（或可以找到）一個更好的辦法。

來源

2011-11-15 17:05:35 Nemo

謝謝，但我的意思是這個解決方案作爲蠻力......我希望存在更好的解決方案（相關時間複雜度）。 –

我懷疑沒有一個例子，任何人都會明白你的答案。 – Elmue

查找給定字符串中的子字符串非常簡單。您採用正常的Levenshtein算法並稍微修改它。

FIRST： 而是用0,1,2,3,4,5填充矩陣的第一排，... 你用零填充它完全。（綠色矩形）

SECOND： 然後運行算法。

THIRD： 不是返回最後一行的最後一個單元格，而是搜索最後一行中的最小值並返回它。（紅色矩形）

實施例： 針：「ABA」，乾草堆：「C ABBA C」 - >結果= 1（轉換ABBA - > ABA）

我發現在這裏：http://ginstrom.com/scribbles/2007/12/01/fuzzy-substring-matching-with-levenshtein-distance-in-python/

我測試了它和它的作品。

這比通過字符串逐個字符的提示要快得多，就像您在問題中所做的那樣。您只能創建一次矩陣。

來源

2016-06-14 06:29:43 Elmue

查找所有子串的編輯距離的算法

回答

相關問題