Java中的模糊字符串搜索库

Question

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

有许多算法可以找到类似的字符串,Levenshtein距离,Daitch-Mokotoff Soundex,n-gram等.

存在哪些Java实现？他们的利弊？我知道Lucene,任何其他解决方案或Lucene最好吗？

我找到了这些,有没有人有过这些经历？

• SimMetrics
• NGramJ

Answer 1

Commons Lang实施了Levenshtein距离.

Commons Codec有soundex和metaphone的实现.

Answer 2

如果你主要比较短字符串并想要一些便携和轻量级的东西,你可以使用众所周知的python算法fuzzywuzzy 移植到Java.

你可以在这里阅读更多相关信息

Answer 3

您可以使用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将搜索模式与可能匹配的每个子字符串进行比较更为有效.

备注:

• Bitap算法似乎主要用于相对较小的字母表,例如纯ASCII.事实上,我链接的Simon Watiau版本会抛出ArrayIndexOutOfBoundsException非ASCII字符(> = 128),因此您必须将这些字符过滤掉.

• 我尝试在应用程序中使用Bimap按名称搜索内存中的人员列表.我发现Levenhstein距离为2会产生太多误报.Levenhstein距离为1可以更好地工作,但它无法检测到您交换两个字母的错字,例如"William"和"Willaim".我可以想出几种方法来解决这个问题,例如

  1. 仅在精确搜索未找到匹配项时进行模糊搜索(并向用户显示有关此内容的消息)
  2. 调整Bitap使用Damerau-Levenshtein距离,其中交换距离为1而不是2.根据维基百科,这是可能的,但我找不到Java中的现有实现.
  3. 而不是"包含"做一个"startsWith".在模糊搜索工具包含Damerau -莱文斯坦的前缀版本,但它给了我一个ArrayIndexOutOfBoundsException
  4. 调整算法以引入搜索结果排名,其中精确匹配得分更高

  如果您打算做2或4,最好使用像Lucene这样的正确的全文搜索库.

• 有关模糊搜索的更多信息,请访问此博客.它的作者还创建了一个在Java中实现所谓的BitapOnlineSearcher,但需要您使用java.io.Reader与字母一起上课.它的Javadoc是用俄语写的.

Answer 4

SimMetrics可能就是您所需要的:http://sourceforge.net/projects/simmetrics/

它有几种算法来计算编辑距离的各种风格.

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

Answer 5

对于 Lucene，我将添加 SOLR http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters

Answer 6

我认为Apache Lucene是唯一的方法。我不知道有什么更好的搜索库。

Apache Lucene(TM) 是一个完全用 Java 编写的高性能、全功能文本搜索引擎库。该技术几乎适用于任何需要全文搜索的应用程序，尤其是跨平台的应用程序。