Nat*_*ton 12 java data-structures
所以我目前正致力于使用SecondString进行模糊字符串匹配,其中我有一个要比较的大字典(字典中的每个条目都有一个关联的非唯一标识符).我目前正在使用hashMap来存储这个字典.
当我想进行模糊字符串匹配时,我首先检查字符串是否在hashMap中,然后迭代所有其他可能的键,计算字符串相似性并存储具有最高相似度的k,v对/ s .根据我使用的字典,这可能需要很长时间(12330 - 1800035条目).有没有办法加快速度或加快速度？我目前正在编写一个记忆功能/表格来加快速度,但其他人是否可以想出一种更好的方法来提高速度呢？也许是一个不同的结构或其他我想念的东西.
提前谢谢了,
弥敦道
eSn*_*iff 11
您正在寻找的是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/