所以我目前正在使用第二弦 http://secondstring.sourceforge.net/对于模糊字符串匹配，我有一个大字典可以比较（字典中的每个条目都有一个关联的非唯一标识符）。我目前正在使用 hashMap 来存储这本字典。
当我想要进行模糊字符串匹配时，我首先检查该字符串是否在 hashMap 中，然后迭代所有其他潜在键，计算字符串相似度并存储具有最高相似度的 k,v 对。根据我使用的词典，这可能需要很长时间（12330 - 1800035 个条目）。有什么办法可以加快速度或使其更快吗？我目前正在编写一个记忆函数/表作为加快速度的一种方法，但是其他人能想到更好的方法来提高速度吗？也许是不同的结构或我缺少的其他东西。
提前谢谢了，
Nathan
您正在寻找的是与 Levenshtein Distance 算法相结合的 BKTree (BK-Tree)。 BKtree 中的查找性能取决于您的搜索的“模糊”程度。其中模糊定义为搜索词与匹配项之间的距离（编辑）数量。
这是关于该主题的一个很好的博客：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
关于性能的一些注意事项：http://www.kafsemo.org/2010/08/03_bk-tree-performance-notes.html http://www.kafsemo.org/2010/08/03_bk-tree-performance-notes.html
注释http://en.wikipedia.org/wiki/Levenshtein_distance http://en.wikipedia.org/wiki/Levenshtein_distance算法。
另外，这是一个用 Java 编写的 BK-Tree。应该可以让您了解界面：http://code.google.com/p/java-bk-tree/ http://code.google.com/p/java-bk-tree/
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
