Java中的模糊字符串搜索库
java
nlp
5
0

我正在寻找一种用于模糊字符串搜索的高性能Java库。

有很多算法可以查找相似的字符串,Levenshtein距离,Daitch-Mokotoff Soundex,n-gram等。

存在哪些Java实现?对他们有利有弊?我知道Lucene,任何其他解决方案还是Lucene最好?

我找到了这些,有人有经验吗?

参考资料:
Stack Overflow
收藏
评论
共 6 个回答
高赞 时间 活跃
收藏
评论

您可能需要SimMetrics: http//sourceforge.net/projects/simmetrics/

它有几种算法可以计算各种编辑距离。

Lucene是一个非常强大的全文本搜索引擎,但是FT搜索与模糊字符串匹配并不完全相同(例如,给定一个字符串列表,找到与某些候选字符串最相似的字符串)。

收藏
评论

如果您主要是比较短字符串,并且想要一些轻便且轻便的东西,则可以使用移植到Java的著名python算法Fuzzywuzzy。

您可以在这里了解更多信息

收藏
评论

您可以尝试Completely库,该库依赖于文本预处理来创建内存中索引,以有效回答大型数据集中的(模糊)搜索。与Lucene和其他功能齐全的文本搜索库不同,该API很小,易于上手。

收藏
评论

您可以使用Apache Lucene,但是根据使用情况,这可能太重了。对于非常简单的模糊搜索,使用起来可能有点复杂,并且(如果我错了,请更正我)它需要您建立索引。

如果您需要简单的在线(不维护索引)算法,则可以使用模糊Bitap算法 。我在这里找到了Java实现。它的代码适合一个相对简短的方法,带有几乎不言自明的签名:

public static List<Integer> find(String doc, String pattern, int k)

Apache Commons StringUtils具有用于模糊字符串匹配的Levenshtein算法的实现。可以将其视为String.equals的模糊版本,Bitap类似于String.indexOf的模糊版本,并且仍使用Levenshtein距离度量。通常,与天真地使用Levenshtein来比较搜索模式与每个可能匹配的子字符串相比,效率更高。

注意事项

  • 对于相对较小的字母,例如纯ASCII,Bitap算法似乎最有用。实际上,我链接到的Simon Watiau版本对非ASCII字符(> = 128)抛出ArrayIndexOutOfBoundsException ,因此您必须将其过滤掉。
  • 我尝试在应用程序中使用Bimap来按名称搜索内存中的人员列表。我发现Levenhstein距离2会产生太多误报。 Levenhstein距离为1会更好,但无法检测到您在交换两个字母(例如“ William”和“ Willaim”)时出现的错字。我可以想到几种解决方法,例如

    1. 仅当精确搜索未找到匹配项时才进行模糊搜索(并向用户显示有关此信息)
    2. 调整Bitap以使用Damerau-Levenshtein距离,其中交换的距离为1而不是2。根据Wikipedia ,这是可能的,但是我找不到Java中的现有实现。
    3. 而不是“包含”执行“ startsWith”。 模糊搜索工具包含Damerau-Levenshtein的前缀版本,但它给了我ArrayIndexOutOfBoundsException
    4. 调整算法以引入搜索结果排名,其中精确匹配得分更高

    如果您要执行2或4,则最好还是使用像Lucene这样的适当的全文本搜索库。

  • 有关模糊搜索的更多信息,请参见此博客 。它的作者还用Java创建了一个名为BitapOnlineSearcher实现 ,但要求您将java.io.Reader与Alphabet类一起使用。它的Javadoc是用俄语编写的。
收藏
评论

Commons Lang实现了Levenshtein距离

Commons Codec具有soundexmetaphone的实现。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号