在地圖中匹配近似字符串鍵

有誰知道是否有一種很好的方法來創建一個從字符串到字符串的近似字符串鍵的映射？也就是說，如果我做到以下幾點：在地圖中匹配近似字符串鍵

map.put("Fuzzy", "string") 
map.put("Fuzy", "bear")

我想要得到的地圖是：

[ "Fuzzy":{ "string", "bear" } ]

（還有可能是有什麼需要注意的是「熊」，從「Fuzy」問世，但這是次要問題）。當然，字符串之間的近似值（距離）可能是一個參數。在這種情況下，距離爲1，但可能更多或更少。

據我所知，Trie可能是一個很好的開始，但我不想實施某些事情並發現它已經完成。

當然，天真的解決方案只是循環地圖中的所有鍵，但我希望效率比這更好。

謝謝！

來源

2012-03-20 mayhewsw

我建議實施hashCode和equals函數，以便它們返回要存儲在地圖中的對象的Soundex。

然後，你應該能夠很快查找單詞。

更新：我只注意到，它看起來像我們所談論的Python：所以你必須AFAIK覆蓋__hash__功能（也有上how to implement hashmaps in python好的帖子）

來源

2012-03-20 12:34:00 devsnd

我以前沒有聽說過Soundex--這是個好主意！我會嘗試的。我實際上在使用Java，我就像地圖的Python輸出一樣。 – mayhewsw 2012-03-20 12:40:32

這裏有一個FuzzyHashMap實現，雖然我還沒有嘗試過：

http://sourceforge.net/projects/fuzzyhashmap/

以及一個BK-Tree的實現看上去相關：

https://code.google.com/p/java-bk-tree/

來源

2013-09-19 20:41:18

FuzzyHashMap的問題是，如果「模糊」位於前四個字符中，則不起作用。它也有一個Soundex功能，但是這有同樣的問題。雖然BK樹看起來很有趣。 – mayhewsw 2013-11-02 20:06:53

我有一個類似的要求，所以我實現了我自己的HashMap。

在我的要求中，鍵在插入時是精確的，但在搜索字符串中可能有錯誤。

我的散列函數：

哈希碼存儲的第一部分哈希碼的關鍵第二部分的長度存儲這兩個部分的鍵

比特寬度的所有字符的總和是固定的。所以我們爲給定的密鑰長度分別獲得一個桶。長度爲1的第一桶存儲密鑰，長度2，的第二桶存儲鍵等

現在，當發現（）被調用， 1.它檢查精確匹配。如果找到，返回。否則，轉到下一步。 2.存在三種可能的錯誤：扭曲的字符，缺少的字符，額外的字符 3.檢查扭曲的字符。失真不會改變長度，所以我們需要搜索同一個桶。如果一個字符失真，那麼散列值可以增加或減少MAX_CHAR_CODE的最大值。因此，從期望的哈希碼的位置，向後和向前搜索MAX_CHAR_CODE索引。大多數值將是NULL。當找到非NULL值時，比較鍵，同時允許一個字符失真。 4.檢查缺少的字符。如果缺少一個字符，新的密鑰長度將比實際的小。所以我們需要在下一個桶中進行搜索。散列碼的總和部分將會減少最多MAX_CHAR_CODE。因此，從下一個桶中的當前位置搜索，MAX_CHAR_CODE將前向放置。當找到非NULL值時，比較鍵，同時允許丟失一個char。 5.其他字符。非常類似於4.

來源

2014-09-30 07:37:19

在地圖中匹配近似字符串鍵

回答

相關問題