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

所以我目前正在使用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

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

回答

相关问题