這個算法是否正確執行？

我目前正在執行一個BK-Tree來進行拼寫檢查。我正在使用的字典非常大（數百萬字），這就是爲什麼我無法承受任何低效率。但是，我知道我寫的查找函數（可以說是整個程序中最重要的部分）可以做得更好。我希望能找到一些有關這方面的幫助。下面是我寫的查詢：這個算法是否正確執行？

public int get(String query, int maxDistance) 
{ 
    calculateLevenshteinDistance cld = new calculateLevenshteinDistance(); 
    int d = cld.calculate(root, query); 
    int tempDistance=0; 

    if(d==0) 
     return 0; 

    if(maxDistance==Integer.MAX_VALUE) 
     maxDistance=d; 

    int i = Math.max(d-maxDistance, 1); 
    BKTree temp=null; 

    for(;i<=maxDistance+d;i++) 
    { 
     temp=children.get(i); 
     if(temp!=null) 
     { 
      tempDistance=temp.get(query, maxDistance); 
     } 
     if(maxDistance<tempDistance) 
      maxDistance=tempDistance; 
    } 

    return maxDistance; 
}

我知道，我正在運行的循環不必要大量的時間，我們可以修剪的搜索空間，使查找更快。我只是不確定如何做到最好。

來源

2010-10-05 efficiencyIsBliss

@Mitch - 這可能是事實......但只是以被接受爲藉口回答的人開始變得有點老了。人們不應該回答有幫助嗎？ – 2010-10-05 16:38:29

@efficiencyIsBliss - 我回答問題，因爲我需要接受我的答案。祝你好運。 – IVlad 2010-10-05 16:51:39

@Justin，我明白你來自哪裏。但是我認爲，從社區知識庫的角度來看，可以認爲這是好的，鼓勵公民參與最佳實踐。對於發生在SO上的隨機Google員工，與沒有這種答案的人相比，帶有檢查回答的問題更有用。 – 2010-10-05 16:53:39

你的循環看起來通常是正確的，如果有一點拜占庭。但是，嘗試改進停止條件（使用tempdistance/maxdistance）是不正確的：BK樹的結構要求您瀏覽當前節點的levenshtein距離dk到d + k內的所有節點，如果要查找所有節點結果，所以你不能像這樣修剪它。

是什麼讓你覺得你在探索太多的樹？

您可以在L evenshtein Automata上找到我的後續文章，因爲它們比BK樹更有效率。但是，如果您正在構建拼寫檢查器，我建議遵循Favonius的建議，並檢查this article如何編寫一個。它比天真的字符串距離檢查更適合拼寫糾正。

來源

2010-10-06 12:39:15

我意識到d + k到d + k部分，我實現了它，但它給了我不正確的結果，這就是爲什麼我完全擺脫它。這就是爲什麼我很確定我沒有有效地修整搜索空間。你能解釋一下這部分嗎？ d和k是否保持不變，或者它們是否隨着樹上的每次迭代而改變？ – efficiencyIsBliss 2010-10-07 01:46:47

「k」是閾值，並保持不變。 'd'是搜索項和當前節點之間的距離，取決於您正在評估的節點。 – 2010-10-07 11:16:49

爲了減少搜索空間，我們可以改變k以反映迄今爲止發現的最小距離嗎？如果我們知道我們看到的第一個單詞與我們的單詞相距5英寸，那麼查看可能在6或更高距離處的單詞沒有意義，對吧？ – efficiencyIsBliss 2010-10-09 21:48:27

這個算法是否正確執行？

回答

相關問題