boy*_*ple 2 algorithm fuzzy-search
假设我有一个名单。不幸的是，有一些重复，但不清楚哪些是重复的。
Tom Riddle
Tom M. Riddle
tom riddle
Tom Riddle, PhD.
我正在考虑使用Levenshtein distance，并且肯定会想到其他算法来一次比较 2 个名字。
但是在名称列表中，无论字符串距离算法如何，我最终都会生成一个比较输出网格 ( n^2)。
我怎样才能避免这种O(n^2)情况？
你想要做的就是模糊搜索。让我引导您完成主题。
首先，设置一个倒排索引（维基百科的）的n-gram（维基百科）。也就是说，将一个单词 like"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 合并算法，它需要先对倒排索引中的单词列表进行排序，因此请确保在构造时对其进行排序。
现在，您将获得与查询至少有一个n-gram相同的所有单词的列表。
我们已经大大减少了可能的记录集。但我们还可以做得更好。对于每个单词，维护它与查询共有多少n-gram的数量。您可以在合并列表时轻松做到这一点。
考虑以下阈值：
max(|x|, |y|) - 1 - (delta - 1) * n
x您的查询在哪里，y您要比较的候选词。n对于价值正克你都用过，3如果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，所以我们接受它。