时间戳

首页 > 解决方案 > 找到比 O(n^2) 更好的相似名称

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

问题描述

假设我有一个名字列表。不幸的是，有一些重复，但其中哪些是重复的并不明显。

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

我正在考虑使用Levenshtein distance，并且肯定有其他算法可以同时比较两个名称。

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

我怎样才能避免这种O(n^2)情况？

标签： algorithmfuzzy-search

解决方案

介绍

您想要做的就是所谓的模糊搜索。让我引导你完成这个话题。

首先，设置一个n-gram ( Wikipedia ) 的倒排索引( Wikipedia ) 。也就是说，将一个单词拆分为，例如-grams："hello"3

"$$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 合并算法，但它需要先对倒排索引中的单词列表进行排序，因此请确保在构造时对其进行排序。

您现在获得了与查询至少有一个n-gram的所有单词的列表。

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

考虑以下阈值：

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

x您的查询在哪里，y您要比较的候选词在哪里。n是您使用的n-gram3的值3-gram，例如。delta是你允许多少错误的价值。

如果计数低于该值，则直接知道编辑距离为

ED(x, y) > delta

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

这样，我们极大地减少了可能的候选集，并且仅在少量记录上计算昂贵的编辑距离。

例子

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

"$$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的，所以我们接受它。

推荐阅读