使用二叉搜索樹和散列創建字典

我即將創建一個「智能」字典，如果用戶的單詞不在字典中，可能會生成類似單詞。使用二叉搜索樹和散列創建字典

該詞典以讀取帶有單詞的文件開始，應該將該單詞添加到二叉樹和散列表中。哈希表用於確定單詞或類似單詞是否在字典中，哈希表將具有布爾效應，因此我們可以快速查看二進制搜索樹是否包含該單詞。哈希表必須是我們字典長度的十倍左右，因爲我們還在哈希表中包含了類似的詞。由於Java相對較新，我希望能夠提供一些關於如何製作散列函數的提示和建議，這對於我的情況來說是非常理想的。

public String [] similarOne(String word) { 

    char [] word_array = word.toCharArray(); 
    char [] tmp; 

    String [] words = new String[word_array.length-1]; 

    for(int i = 0; i < word_array.length - 1; i++) { 
     tmp = word_array.clone(); 
     words[i] = swap(i, i+1, tmp); 
    } 
    return words; 
} 

public String swap(int a, int b, char [] word) { 
    char tmp = word[a]; 
    word[a] = word[b]; 
    word[b] = tmp; 

    return new String(word); 
}

來源

2010-09-28 user265767

這很大程度上取決於您是否嘗試匹配具有共同開始的單詞或處理拼寫錯誤等。首先，您的意思是「用戶的工作不在字典中」。這個詞拼寫錯了嗎？這個詞是拼寫正確還是複數？你的意思是美國和英國英語之間的映射嗎？ – 2010-09-28 16:09:25

你是什麼意思的「類似的單詞」？你的意思是一個聽起來相似的詞嗎？那有類似的定義嗎？這裏的一個關鍵問題是相似性是否是傳遞性的。也就是說，如果A與B類似，B類似於C，那麼這是否意味着A必須與C類似？如果是這樣，那麼將所有類似詞彙映射到一個共同標記的東西將適用於您。如果不是，如果說「快」與「快」類似，「快」與「緊」類似，但「快」與「緊」不相似，那麼數據結構必須更加複雜。 – Jay 2010-09-28 16:31:56

你的意思是「散列表會產生布爾效應，所以我們可以在二叉搜索樹中快速查找」？我不確定你是否認爲散列表使用樹 - 它沒有 - 或者如果你的意圖是有一個散列表和一個二叉樹，它們之間有某種相關性。 – Jay 2010-09-28 16:42:06

Google for'java metaphone'and'java soundex'。例如，您可以嘗試使用Metaphone編碼的結果作爲散列鍵。

來源

2010-09-28 16:24:55

我建議你應該使用Trie或patricia-trie。我不知道你通過類似words.But我猜它的意思是像谷歌suggest.I已經寫了一個小program以前這確實自動完整。它與patricia-trie有依賴關係，所以必須包含它。你可以用它作爲參考。

來源

2010-09-29 05:18:03 Emil

請檢查此鏈接.http：//rmandvikar.blogspot.com/2008/10/trie-examples.html – Emil 2010-09-29 05:59:29

http://sujitpal.blogspot.com/2007/02/three-autocomplete-implementations.html – Emil 2010-09-29 06:08:40

使用二叉搜索樹和散列創建字典

回答

相關問題