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

data-structures java

2022-09-04 21:14:58

因此，我目前正在使用SecondString进行模糊字符串匹配，其中我有一个大字典可以进行比较（字典中的每个条目都有一个关联的非唯一标识符）。我目前正在使用哈希地图来存储此字典。

当我想做模糊字符串匹配时，我首先检查字符串是否在hashMap中，然后我迭代所有其他潜在的键，计算字符串相似性并存储具有最高相似度的k，v对/ s。根据我使用的字典，这可能需要很长时间（ 12330 - 1800035条目）。有没有办法加快速度或使其更快？我目前正在编写一个备忘录函数/表格作为加速这一点的一种方式，但是其他人能想到更好的方法来提高它的速度吗？也许是不同的结构或我错过的其他东西。

提前致谢，

内森

答案 1

你想要的是一个BKTree（BK-Tree）与Levenshtein Distance算法相结合。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/

答案 2

或者你也可以使用Java Fuzzy HashMap（一种对java hashMap的扩展，允许模糊搜索）：http://sourceforge.net/projects/fuzzyhashmap/ 我认为它正是你需要的。在这里，您可以获得数据结构的完整描述：http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5565628