76

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

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

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

我找到了这些，有人有经验吗？

4

8 回答 8

41

Commons Lang 有一个Levenshtein distance的实现。

Commons Codec 有soundex和metaphone的实现。

于 2008-11-29T14:58:12.067 回答
18

如果您主要是比较短字符串并想要一些可移植和轻量级的东西，您可以使用移植到 Java的著名的 python 算法 blurwuzzy 。

你可以在这里阅读更多关于它的信息

于 2016-09-14T17:54:33.570 回答
11

您可以使用 Apache Lucene，但根据用例，这可能太重了。对于非常简单的模糊搜索，使用起来可能有点复杂（如果我错了，请纠正我）它需要你建立一个索引。

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

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

Apache CommonsStringUtils实现了用于模糊字符串匹配的 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。根据wikipedia，这是可能的，但我在 Java 中找不到现有的实现。
    3. 而不是“包含”做一个“startsWith”。模糊搜索工具包含 Damerau-Levenshtein 的前缀版本，但它给了我一个ArrayIndexOutOfBoundsException
    4. 调整算法以引入精确匹配得分更高的搜索结果排名

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

  • 更多关于模糊搜索的信息可以在这个博客上找到。它的作者还在Java 中创建了一个名为的实现BitapOnlineSearcher，但需要您java.io.Reader与 Alphabet 类一起使用。它的 Javadoc 是用俄语编写的。
于 2015-10-14T12:43:57.323 回答
9

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

它有几种算法用于计算各种类型的编辑距离。

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

于 2008-12-18T17:18:51.650 回答
4

到 Lucene 我会添加 SOLR http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters

于 2011-10-28T22:21:43.100 回答
2

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

于 2016-09-19T16:18:03.940 回答
1

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

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

于 2008-11-29T13:40:29.510 回答
1

你可以试试bitap。我正在玩用 ANSI C 编写的 bitap，它非常快，在http://www.crosswire.org中有 java 实现。

于 2010-04-06T14:48:02.377 回答