logo标签列表

Java模糊字符串搜索库

javanlpfuzzy-search
85

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

有许多算法可用于查找相似的字符串，如Levenshtein距离、Daitch-Mokotoff Soundex、n-gram等。

存在哪些Java实现？它们各自的优缺点是什么？我知道Lucene，还有其他解决方案吗？还是Lucene最好？

我发现了这些东西，有人有使用它们的经验吗？

8个回答
45
4
不能对其他内容发表评论，但我发现commons-langs中的Levenshtein距离在模糊相等性检查方面很有用，而不是模糊包含。不幸的是，您仍然需要编写自己的算法来使用它。这仍然需要一些正确的努力（您必须匹配源字符串中的不同长度），以及良好的性能（使用bitap可能比您仅使用Levenshtein距离编写的算法要快得多）。 - Henno Vermeulen
@HennoVermeulen，请问您能否与我们分享您是否找到了任何解决方案？Java有没有实现 Bitap 算法的代码？ - hereForLearing
我的回答包含一个链接到Java实现（事实上，这是我在谷歌搜索“Java bitap”时找到的第一个）。 - Henno Vermeulen
1
对于那些寻找简单模糊搜索的人，实际上返回匹配子字符串而不是分数的，这里有一个要点：https://gist.github.com/shathor/8ad04d8923d6c07fd2f4a06e9543bebf。 编辑：@sukhmel我在此评论中更新了链接（删除了旧链接）。如果再次发生，要点应该在我的存储库中可用：https://gist.github.com/shathor - Terran
22
如果你主要比较短字符串并且需要使用轻量级，易于移植的算法，你可以使用广为人知的Python算法“fuzzywuzzy”，现在已经移植到Java中。点此查看更多详情。
你可以在这里了解更多信息。
3
使用fuzzywuzzy的经验非常积极。将一个拥有超过250,000个对象的集合中的多个字符串与一个包含30,000个对象的集合进行比较。模糊匹配高效且有效，API易于使用。 - The Gilbert Arenas Dagger
很棒的库，我已经将它集成到我们当前的Android项目中，初步结果非常有希望。 - A.Alqadomi
3
需要注意的是，Python和Java版本均采用GPL许可证。 - Asthor
2
由于我无论如何搜索都找不到这个，导入它的方法是（一旦您在类路径上有了jar）- import me.xdrop.fuzzywuzzy.*; - Siddhartha
13

您可以使用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版本在非ASCII字符（≥128）上会抛出ArrayIndexOutOfBoundsException，所以您需要将其过滤掉。

  • 我尝试在一个应用程序中使用Bimap按名称搜索内存中的人员列表。我发现Levenhstein距离为2会产生太多误报。Levenhstein距离为1效果更好，但无法检测交换两个字母的拼写错误，例如“William”和“Willaim”。我可以想到一些解决方法，例如：

    1. 只有在精确搜索找不到匹配项时才进行模糊搜索（并向用户显示此消息）
    2. 调整Bitap使用Damerau-Levenshtein距离，其中交换距离为1而不是2。根据维基百科，这是可能的，但我找不到Java中现有的实现。
    3. 不要使用“contains”，而要使用“startsWith”。模糊搜索工具包含Damerau-Levenshtein的前缀版本，但它给了我一个ArrayIndexOutOfBoundsException
    4. 调整算法以引入搜索结果排名，其中精确匹配得分更高

    如果您要执行第2或第4项，则无论如何最好使用像Lucene这样的适当全文搜索库。

  • 有关模糊搜索的更多信息可以在此博客上找到。该作者还创建了一个名为BitapOnlineSearcher的Java实现，但需要您与Alphabet类一起使用java.io.Reader。其Javadoc用俄语编写。

有没有一种方法可以使Bitap搜索仅针对具有相同字母数量的单词，例如如果我搜索具有k=2的“Name”，则“Namo”和“Mamo”被接受但不是“Nam”？ - hereForLearing
10

SimMetrics可能是你需要的：http://sourceforge.net/projects/simmetrics/

它有几种算法可以计算不同类型的编辑距离。

Lucene是一个非常强大的全文搜索引擎，但FT搜索不完全等同于模糊字符串匹配（例如，给定一组字符串，找到最相似的候选字符串）。

2
simmetrics似乎是GPL v2，因此不兼容商业开发软件。 - Dan Haywood
在GitHub上有一个“重写”，它有一个开放的问题来解决许可问题：https://github.com/Simmetrics/simmetrics/issues/5 - peater
@DanHaywood 截至版本3.2.3，许可证已更改为Apache Version 2.0。 - M.P. Korstanje
1
从版本3.2.3开始，@pppeater的许可证已更改为Apache Version 2.0。 - M.P. Korstanje
3
你可以尝试使用Completely库，它依靠文本预处理创建内存索引，以有效地回答大型数据集中的(模糊)搜索。与Lucene和其他完整特性的文本搜索库不同，API小巧易用，容易入手。
2

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

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

1
你可以尝试使用 bitap。我曾经使用 ANSI C 编写的 bitap 进行过测试，速度相当快，这里还有一个 Java 实现 http://www.crosswire.org。
请提供代码的直接链接和相关文档。 - svarog
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接