提高模糊字符串匹配字典的性能
所以我目前正致力于使用SecondString进行模糊字符串匹配，其中我有一个要比较的大字典（字典中的每个条目都有一个关联的非唯一标识符）。 我目前正在使用hashMap来存储这个字典。
当我想进行模糊字符串匹配时，我首先检查字符串是否在hashMap中，然后迭代所有其他可能的键，计算字符串相似性并存储具有最高相似度的k，v对/ s 。 根据我使用的字典，这可能需要很长时间（12330 – 1800035条目）。 有没有办法加快速度或加快速度？ 我目前正在编写一个记忆function/表格来加快速度，但其他人是否可以想出一种更好的方法来提高速度呢？ 也许是一个不同的结构或其他我想念的东西。
提前谢谢了，
弥敦道
您正在寻找的是BKTree（BK树）与Levenshtein距离算法相结合。 BKtree中的查找性能取决于搜索的“模糊”程度。 模糊定义为搜索词和匹配之间的距离（编辑）数。
这是一个关于这个主题的好博客： 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://en.wikipedia.org/wiki/Levenshtein_distance算法的说明。
此外，这是一个用Java编写的BK树。 应该让您了解界面： http ： //code.google.com/p/java-bk-tree/
或者您也可以使用Java模糊HashMap（扩展到允许模糊搜索的java hashMap）： http ： //sourceforge.net/projects/fuzzyhashmap/我认为这正是您所需要的。 在这里您可以完整地了解数据结构： http ： //ieeexplore.ieee.org/xpl/freeabs_all.jsp？narumber = 5565628
看到这篇优秀的文章，用于解释和比较不同的模糊字符串匹配： http ： //ntz-develop.blogspot.com/2011/03/fuzzy-string-search.html
java源代码，请访问https://code.google.com/p/fuzzy-search-tools/