提高模糊字符串匹配字典的性能

所以我目前正在使用SecondString進行模糊字符串匹配，在那裏我有一個大型的字典來比較（字典中的每個條目都有一個關聯的非唯一標識符）。我目前使用一個hashMap來存儲這個字典。提高模糊字符串匹配字典的性能

當我想進行模糊字符串匹配時，首先檢查字符串是否在hashMap中，然後遍歷所有其他潛在的密鑰，計算字符串相似度並存儲k，v對/ s具有最高的相似性。根據我使用的字典，這可能需要很長時間（12330 - 1800035條目）。有什麼方法可以加快速度或提高速度？我目前正在編寫一個memoization函數/表格來加速這個過程，但是其他人能否想到一個更好的方法來提高速度呢？也許是一個不同的結構或我錯過的其他東西。

提前許多感謝，

彌敦道

來源

2011-02-09 Nathan Harmston

作爲一個技術問題，這屬於[StackOverflow]（http://stackoverflow.com/）。 – 2011-02-09 13:49:45

你想找的是BKTree（BKTree）與萊文斯坦距離算法相結合。 BK樹中的查找性能取決於搜索的「模糊」程度。模糊定義爲搜索詞與匹配之間的距離（編輯）數量。

下面是關於這個問題的一個很好的博客： http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

對性能的一些注意事項：在http://en.wikipedia.org/wiki/Levenshtein_distance算法 http://www.kafsemo.org/2010/08/03_bk-tree-performance-notes.html

注意事項。

另外，這裏是用Java編寫的BK-Tree。應該給你一個界面的想法：http://code.google.com/p/java-bk-tree/

來源

2011-02-10 07:48:27 eSniff

或者你也可以使用Java模糊HashMap（擴展到Java哈希映射，允許模糊搜索）：http://sourceforge.net/projects/fuzzyhashmap/我認爲這正是你需要的。在這裏，你有數據結構的完整描述：http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5565628

來源

2011-04-28 08:42:43

有一點需要注意 - 如果搜索關鍵字少於5個字符，它將不會返回任何內容。您可以修改源代碼，但有一條評論說，在測試少於5個字母的鍵時，它的準確性較差。 – 2013-04-01 23:15:27

看到的解釋和不同的模糊匹配字符串比較這個優秀的文章：可用 http://ntz-develop.blogspot.com/2011/03/fuzzy-string-search.html

Java源代碼在 https://code.google.com/p/fuzzy-search-tools/

來源

2013-03-01 07:16:38 isapir

提高模糊字符串匹配字典的性能

回答

相關問題