Java中的字符串模糊匹配

Question

Java中的字符串模糊匹配

3

我有一个非常庞大的字符串列表存储在NoSQL数据库中。查询输入是一个字符串，我想检查该字符串是否存在于列表中。对于完全匹配，这很简单。该NoSQL数据库可能将字符串作为主键，并且我只需要检查是否有任何记录具有该字符串作为主键。但是我还需要检查模糊匹配。

有一种方法是遍历列表中的每个字符串，并检查输入字符串与列表中的字符串的Levenshtein距离，但是这种方法将导致O(n)复杂度，而列表的大小非常大（1000万），甚至可能会增加。这种方法将导致我的解决方案延迟更高。

有没有更好的方法来解决这个问题？

- Devil

搜索模糊字符串总是很复杂的。它会导致高复杂度，我认为没有真正好的解决方案可以避免这种情况。在搜索之前，是否有可能纠正模糊字符串？但是你使用哪个非关系型数据库呢？其中一些提供了模糊字符串的搜索功能。或者你可以尝试使用像ElasticSearch这样的搜索引擎。 - GAlexMES

1

为什么不使用像Soundex或Metaphone这样的语音算法呢？你可以试一试。 - Abu Sufian

Apache commons-text库提供了一些例程，例如余弦距离，但听起来您至少想要使用嵌入式Lucene。即使使用Lucene Levenshtein距离搜索也具有很高的成本，尽管Lucene已经改进了这一点。 - David George

标准方法是使用n-gram。有关更多详细信息，请参见下面的答案。 - rghome

3个回答

1

首先，如果您正在进行搜索操作，那么建议使用搜索引擎（ElasticSearch是默认选择），它们非常擅长此项任务，避免重复造轮子。

其次，您需要的技术称为词干提取。除了保存原始字符串外，还应在数据库中保存规范化的字符串。使用相同的机制对搜索查询进行规范化。这样可以获得更好的搜索结果。显然，这是搜索引擎在后台使用的技术之一。

- Sean Patrick Floyd

1

他想要进行Levenshtein距离计算，所以词干提取并不能帮助他。这比词干提取更加复杂。 - rghome

@rghome 我看到他尝试过那种方法，但并不是必需的。 - Sean Patrick Floyd

谢谢您的建议。我的原始方法是使用Levenshtein距离，但如果有更好的方法，我也很愿意采用。对于原始方法，我需要解析完整列表。考虑到列表非常大，我正在思考是否可以进行优化，以避免每次查询都需要解析列表。 - Devil

词干提取不能帮助返回一个字母错误的结果，例如 water/woter。 - mishadoff

@mishadoff 是的，但这比他现在拥有的要好。请随意添加您自己更完整的答案。 - Sean Patrick Floyd

1

您是否考虑使用Solr（或Lucene）作为适合您的解决方案？

Lucene supports fuzzy searches based on the Levenshtein Distance, or Edit Distance algorithm. To do a fuzzy search use the tilde, "~", symbol at the end of a Single word Term. For example to search for a term similar in spelling to "roam" use the fuzzy search:
roam~
This search will find terms like foam and roams.

Starting with Lucene 1.9 an additional (optional) parameter can specify the required similarity. The value is between 0 and 1, with a value closer to 1 only terms with a higher similarity will be matched. For example:
roam~0.8 

https://lucene.apache.org/core/2_9_4/queryparsersyntax.html

- freedev

1

只是一个小提示：ElasticSearch和Solr在内部都使用了Lucene。@Devil - Bagus Tesa

谢谢您的建议！我从评论中了解到Lucene提供了精确匹配和模糊匹配，而Solr和Elastic Search都是基于Lucene的。在Solr或Elastic Search中是否也有超时功能，可以在固定时间后删除记录？此外，我希望延迟在两者中都不是问题。 - Devil

@Devil AFAIK目前还没有“按固定时间删除记录”的功能，但是您可以很容易地在您的文档中添加一个creation_timestamp字段，并过滤早于指定日期时间的结果和/或定期删除所有早于…的文档。 - freedev

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rghome · Accepted Answer

模糊匹配是很复杂的，正如你所发现的那样。对每个搜索词与数据库词汇的组合计算距离指标出于性能原因是不可行的。

解决这个问题的方法通常是使用n-gram索引。它可以作为单独的工具来提供结果，也可以作为筛选器来减少可能结果的数量，以便您需要计算更少的距离分数。

因此，如果您有一个单词"stack"，您将其分成n-gram（通常是三元组），例如"s"、"st"、"sta"、"ack"、"ck"、"k"。您在数据库中对这些进行索引，并与数据库行进行匹配。然后，您对输入执行相同的操作，并查找具有相同匹配n-gram的数据库行。

这很复杂，您的最佳选择是使用现有实现，例如Lucene/Solr，它将为您处理n-gram。我自己没有使用过它，因为我使用专有解决方案，但有一个与之相关的stackoverflow问题：Return only results that match enough NGrams with Solr。

一些数据库似乎实现了n-gram匹配。这里是一个Sybase页面的链接，提供了一些关于此的讨论： Sybase n-gram text index 不幸的是，对n-gram的讨论需要写一篇长帖子，而我没有时间。可能在stackoverflow和其他网站上有相关讨论。建议搜索这个词并了解更多信息。