java - Java中字符串的模糊字符串匹配

Question

我有一个非常大的字符串列表存储在 NoSQL 数据库中。传入查询是一个字符串，我想检查这个字符串是否在列表中。在完全匹配的情况下，这非常简单。 NoSQL DB 可能将字符串作为主键，我将检查是否有任何记录将该字符串作为主键。但我还需要检查模糊匹配。

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

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

Answer 1

由于您已经发现的原因，模糊匹配很复杂。出于性能原因，计算搜索词与数据库词的每个组合的距离度量是不切实际的。

这个问题的解决方案通常是使用 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 和其他站点的其他地方进行了讨论。我建议用谷歌搜索这个词并阅读它。