蟒蛇模糊levenshtein比得到提前退出？

我想比較100k的字符串彼此。我無法進一步減小問題的大小（即集合中的＃字符串）。我正在使用Levenshtein比率進行比較。如果比率大於0.9，我想將2個字符串存儲在列表中。我的問題是關於運行時優化。由於0.9是我的標準，有沒有辦法將此值傳遞給Levenshtein.ratio（），並期望在負面情況下提前退出？如果存在提前退出的方式，則可以保存一些運行時。 Levenshtein算法在計算完整距離（s）之前早點取得比率是否可行？蟒蛇模糊levenshtein比得到提前退出？

E.g

import Levenshtein 
Levenshtein.ratio('lot of runtime','why not an early exit in this case by taking the intended ratio')

有什麼樣：

Levenshtein.ratio('lot of runtime','why not an early exit in this case by taking the intended ratio', 0.9)

來源

2013-01-14 syam

爲什麼你關心Python的細節，如果它是重要的算法？我不知道這個模塊「Levenshtein」是如何實現的，但是可以修改它的一個動態編程實現以在完成處理之前停止。 – mmgp

我不這麼認爲當前的實現支持它。您可能不想分叉並相應地改變以支持它，因爲它應該直接實施。 – Abhijit

唉，Levenshtein =='python-Levenshtein'這是寫在C. –

是的，就像你postulating提前退出是可能的。

Levenshtein模塊的源代碼是免費提供的，因此您可以自行添加該功能。

還有另一個你可能想要考慮的優化：三角不等式。如果字符串A與字符串B相似20％，而字符串B與字符串C相似90％，那麼您知道字符串A與字符串C不會有90％的相似性。這是不可能的，所以您沒有實際上計算AC Levenshtein距離。

來源

2013-01-14 18:19:43 Borealid

蟒蛇模糊levenshtein比得到提前退出？

回答

相關問題