Java中的模糊字符串搜索库

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

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

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

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

SimMetrics

NGramJ

JodaStephen.. 38

Commons Lang实施了Levenshtein距离.

Commons Codec有soundex和metaphone的实现.

1> JodaStephen..：

---

Commons Lang实施了Levenshtein距离.

Commons Codec有soundex和metaphone的实现.

---

不能评论其他人,但我发现公共场所Levenshtein的距离对于模糊等式检查很有用,而不是模糊包含.不幸的是,您仍然需要编写自己的算法来使用它.这仍然需要花费一些精力才能正确完成(你必须匹配源字符串中的不同长度)并且具有良好的性能(bitap可能比仅使用Levenshtein距离编写的速度快得多).

2> ᴘᴀɴᴀʏɪᴏᴛɪs..：

---

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

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

---

使用fuzzywuzzy获得了非常积极的体验.将250,000多个对象集合中的几个字符串与30,000个集合中的字符串进行比较.模糊匹配是高效和有效的,api是用户友好的.

3> Henno Vermeu..：

---

您可以使用Apache Lucene,但根据用例,这可能是太重了.对于非常简单的模糊搜索,使用它可能有点复杂(如果我错了,请纠正我)它需要您构建索引.

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

public static List 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".我可以想出几种方法来解决这个问题,例如

仅在精确搜索未找到匹配项时进行模糊搜索(并向用户显示有关此内容的消息)

调整Bitap使用Damerau-Levenshtein距离,其中交换距离为1而不是2.根据维基百科,这是可能的,但我找不到Java中的现有实现.

而不是"包含"做一个"startsWith".在模糊搜索工具包含Damerau -莱文斯坦的前缀版本,但它给了我一个ArrayIndexOutOfBoundsException

调整算法以引入搜索结果排名,其中精确匹配得分更高

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

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

4> Darren..：

---

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

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

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

---

然而,simmetrics看起来是GPL v2,因此与商业开发的软件不兼容.