algorithm - 找到比 O(n^2) 更好的相似名称

Question

假设我有一份名单。不幸的是，有一些重复项，但其中哪些是重复项并不明显。

Tom Riddle
Tom M. Riddle
tom riddle
Tom Riddle, PhD.

我正在考虑使用Levenshtein 距离，并且肯定会想到其他算法来一次比较 2 个名称。

但在名称列表中，无论字符串距离算法如何，我最终都会生成一个比较输出网格 (n^2)。

如何避免 O(n^2) 情况？

Answer 1

简介

你想做的是Fuzzy search .让我引导您完成这个主题。

首先，设置n-grams ( Wikipedia ) 的倒排索引 ( Wikipedia )。也就是说，将 "hello" 这样的词拆分成，例如 3-grams:

"$$h", "$he", "hel", "ell", "llo", "lo$", "o$$"

并有一个映射，将每个 n-gram 映射到包含它的单词列表:

"$$h" -> ["hello", "helloworld", "hi", "huhu", "hey"]
"$he" -> ["hello", "helloworld", "hey"]
...
"llo" -> ["hello", "helloworld", "llowaddup", "allo"]
...

您数据库中的所有单词现在都由它们的 n-gram 索引。这就是为什么它被称为倒排索引。

这个想法是，给定一个查询，计算该查询与数据库中的所有单词共有多少个 n-gram。这可以快速计算。之后，您可以使用它来跳过对大量记录的昂贵编辑距离的计算。这显着提高了速度。这是所有搜索引擎(或多或少)使用的标准方法。

让我首先以完全匹配 为例解释一般方法。之后我们将稍微修改它并进行模糊匹配。

---

精确匹配

在查询时，计算查询的 n-gram，获取列表并计算交集。

就像如果你得到 "hello" 你计算克数并得到:

"$$h", "$he", "hel", "ell", "llo", "lo$", "o$$"

您获取所有这些 n-gram 的所有列表:

List result;
foreach (String nGram) in (query.getNGrams()) {
    List words = map.get(nGram);
    result = result.intersect(words);
}

交集包含与这些克完全匹配的所有单词，这只是“hello”。

请注意，使用散列法(如 HashSet)可以更快地计算出精确匹配。

---

模糊匹配

不是交叉列表，而是合并它们。为了有效地合并，你应该使用任何 k-way merge algorithm ，它要求倒排索引中的单词列表事先进行排序，因此请确保在构造时对其进行排序。

您现在得到一个列表，其中包含至少一个与查询相同的 n-gram 的所有单词。

我们已经大大减少了可能的记录集。但我们可以做得更好。对于每个单词，维护它与查询共有的 n-gram 数量。您可以在合并列表时轻松做到这一点。

考虑以下阈值:

max(|x|, |y|) - 1 - (delta - 1) * n

其中 x 是您的查询，y 是您要与之比较的候选词。 n 是您使用的 n-gram 的值，例如 3 if 3-gram。 delta 是您允许的错误数的值。

如果计数低于那个值，你直接知道编辑距离是

ED(x, y) > delta

所以你只需要考虑计数超过上述阈值的词。仅针对那些您计算编辑距离的词 ED(x, y)。

通过这种方式，我们极大地减少了可能的候选集，并且只计算少量记录的昂贵编辑距离。

---

例子

假设您得到查询 "hilari"。让我们使用 3-gram。我们得到

"$$h", "$hi", "hil", "ila", "lar", "ari", "ri$", "i$$"

我们搜索倒排索引，合并具有这些克的单词列表，得到 "hillary"、"haemophilia"、"solar"。连同这些词，我们计算了它们共有多少克:

"hillary"      -> 4 ("$$h", "hi", "hil", "lar")
"haemophilia"  -> 2 ("$$h", "hil")
"solar"        -> 1 ("lar")

根据阈值检查每个条目。设 delta 为 2。我们得到:

4 >= max(|"hilari"|, |"hillary"|) - 4     = 3
2 <  max(|"hilari"|, |"haemophilia"|) - 4 = 6
1 <  max(|"hilari"|, |"solar"|) - 4       = 2

只有 "hillary" 高于阈值，丢弃其余的。计算所有剩余记录的编辑距离:

ED("hilari", "hillary") = 2

不超过 delta = 2，所以我们接受它。