優化許多單詞Levenshtein距離的速度

Question

我有一個單元格數組字典，其中包含很多單詞（約15000）。

我想爲所有的單詞對計算函數strdist（計算Levenshtein距離）。我嘗試了兩種方式，但都很慢。什麼是更有效的解決方案？

這是我的代碼（dict_keys是長度爲m的我的單元陣列）：

1）

matrix = sparse(m,m); 
for i = 1:m-1; 
    matrix(i,:) = cellfun(@(u) strdist(dict_keys{i},u), dict_keys); 
end 

2）

matrix = sparse(m,m); 
for i = 1:m-1; 
    for j = i+1:m 
    matrix(i,j) = strdist(dict_keys{i},dict_keys{j}); 
    end 
end 

Answer 1

函數 'strdist' 不是一個內置的MATLAB功能，所以我想你從File Exchange拿走了。這也是爲什麼你的方法在時間上大致相等，cellfun內部只是擴展成一個循環。

如果strdist是對稱的，即strdist（a，b）== strdist（b，a），則可以保存一半的計算。這似乎是這種情況，所以只計算第二個循環中的所有j<i的情況（你正在這樣做）。

否則，您可以在C中實現strdist作爲mex函數，並且可能會看到一些顯着的速度改進。 Levenshtein距離的C實現可以在例如rosettacode.org處找到。

或深入瞭解算法如何計算兩個字符串的距離，並查看是否可以對其進行矢量化並從二次方更少地減少運行時間。但是，這可能不是很容易。

最後，如果您擁有並行計算工具箱許可證和多核CPU，您可以輕鬆地並行處理代碼，因爲strdist調用彼此完全獨立。

Answer 2

像Levenshtain自動機有幾種更快的方法。見

1. http://en.wikipedia.org/wiki/Levenshtein_automaton
2. http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata
3. https://www.google.com.ng/search?q=Fast+approximate+search+in+large+dictionaries（許多不同的文件，還可以通過（反向）引用去從試卷上鏁。