基於預先計算的哈希比較字符串距離

我有一個大的列表（超過200,000）我想要比較給定的字符串的字符串。給定的字符串是由用戶插入的，因此它可能稍微不正確。基於預先計算的哈希比較字符串距離

我希望做的是創建一些預先計算的哈希每個字符串添加到列表。這個哈希將包含諸如字符串長度，所有字符的添加等信息。

我的問題是，這樣的事情已經存在了嗎？肯定會有東西讓我避免在列表中的每個字符串上運行Levenshtein distance？

或者還有第三個選項我還沒有想過呢？

2010-08-12 Brad

聽起來像你想使用某種模糊散列。有很多可用的哈希函數可以做這樣的事情。經典的「SOUNDEX」算法甚至可能工作。另一個想法 - 如果你估計出現錯誤輸入的可能性很低，那麼你可能實際上沒有99.9％的直接命中時間，回到SOUNDEX可能會捕獲剩餘的90％的情況，然後在剩下的0.01％的時間內搜索整個列表。

也值得檢查這個討論： How to find best fuzzy match for a string in a large string database

來源

2010-08-12 23:41:40 mikera

基於預先計算的哈希比較字符串距離

回答

相關問題