找到比 O(n^2) 更好的相似名称
Finding similar names better than O(n^2)
假设我有一份名单。不幸的是，有一些重复项，但其中哪些是重复项并不明显。
Tom Riddle
Tom M. Riddle
tom riddle
Tom Riddle, PhD.
我正在考虑使用 Levenshtein 距离，并且肯定会想到其他算法来一次比较 2 个名称。
但在名称列表中，无论字符串距离算法如何，我最终都会生成一个比较输出网格 (n^2)。
如何避免 O(n^2) 的情况？
简介
你想做的事情被称为Fuzzy search。让我引导您完成这个主题。
首先，设置一个倒排索引 (Wikipedia) of n-grams (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 索引。这就是为什么它被称为 inverted 索引。
我们的想法是，给定一个查询，计算该查询与数据库中的所有单词共有多少个 n-gram。这可以快速计算。之后，您可以使用它来跳过对大量记录的昂贵编辑距离的计算。 显着 提高了速度。这是所有搜索引擎（或多或少）使用的标准方法。
首先让我以完全匹配为例来解释一般方法。之后我们稍微修改一下，进入模糊匹配。
完全匹配
在查询时，计算查询的 n-gram，获取列表并计算交集。
就像如果你得到 "hello" 你计算克数并得到：
"$$h", "$he", "hel", "ell", "llo", "lo$", "o$$"
您获取所有这些 n-grams:
的所有列表
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-grams 的值，例如 3 if 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，所以我们接受。
这会很难。接受你会犯错误，不要让完美成为优秀的敌人。
首先删除敬语（Mr、Mrs、Sir、Dr、PhD、Jr、Sr、）。删除常见的名字（基于名字列表）和首字母并将所有字符转换为大写。为剩下的任何内容创建一个 签名 — 使用 Soundex 或类似的东西，或者简单地删除所有元音和双辅音。按签名排序以将相似的名称放在一起，然后 运行 仅对具有相同签名的名称进行完整比较。这将排序的时间复杂度降低到 O(n log n) 加上一点 O(k²) 每组 k 个签名。
其他答案将其视为抽象字符串问题。如果那是您想要的，那么我认为他们会提供很好的建议。我假设您想使用名称如何工作的特定知识，例如，"Mr. Thomas Riddle, Esq" 和 "Riddle, Tom" 将匹配 "Tom Riddle"，但 "Tom Griddle"不会。
一般来说，对于这类问题，您定义某种规范化函数并寻找规范化为同一事物的术语。在这种情况下，您的名字的规范表示似乎应该包括名字和姓氏的小写版本，去掉任何头衔，并且 "de-nicknamed" 使用昵称到正式名称的映射（假设您希望 "Tom" 和 "Thomas" 匹配）。此函数将产生 "Tom Riddle" -> {first: "tom", last: "riddle"}、"Riddle, Tom" -> {first: "tom", last: "riddle"}、"Tom Riddle, Esq" -> {first: "tom", last: "riddle"} 等，但 "Tom Griddle" -> {first: "tom", last: "griddle"}.
一旦你有了名称规范化功能，你就可以创建一个映射（例如 hashmap 或 BST），将规范名称与非规范名称列表相关联。对于每个非规范化名称，在映射中找到与其规范形式对应的列表并将其插入到那里。完成后，所有包含一个以上元素的列表都是您的副本。
假设我有一份名单。不幸的是，有一些重复项，但其中哪些是重复项并不明显。
Tom Riddle
Tom M. Riddle
tom riddle
Tom Riddle, PhD.
我正在考虑使用 Levenshtein 距离，并且肯定会想到其他算法来一次比较 2 个名称。
但在名称列表中，无论字符串距离算法如何，我最终都会生成一个比较输出网格 (n^2)。
如何避免 O(n^2) 的情况？
简介
你想做的事情被称为Fuzzy search。让我引导您完成这个主题。
首先，设置一个倒排索引 (Wikipedia) of n-grams (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 索引。这就是为什么它被称为 inverted 索引。
我们的想法是，给定一个查询，计算该查询与数据库中的所有单词共有多少个 n-gram。这可以快速计算。之后，您可以使用它来跳过对大量记录的昂贵编辑距离的计算。 显着 提高了速度。这是所有搜索引擎（或多或少）使用的标准方法。
首先让我以完全匹配为例来解释一般方法。之后我们稍微修改一下，进入模糊匹配。
完全匹配
在查询时，计算查询的 n-gram，获取列表并计算交集。
就像如果你得到 "hello" 你计算克数并得到：
"$$h", "$he", "hel", "ell", "llo", "lo$", "o$$"
您获取所有这些 n-grams:
的所有列表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-grams 的值，例如 3 if 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，所以我们接受。
这会很难。接受你会犯错误，不要让完美成为优秀的敌人。
首先删除敬语（Mr、Mrs、Sir、Dr、PhD、Jr、Sr、）。删除常见的名字（基于名字列表）和首字母并将所有字符转换为大写。为剩下的任何内容创建一个 签名 — 使用 Soundex 或类似的东西，或者简单地删除所有元音和双辅音。按签名排序以将相似的名称放在一起，然后 运行 仅对具有相同签名的名称进行完整比较。这将排序的时间复杂度降低到 O(n log n) 加上一点 O(k²) 每组 k 个签名。
其他答案将其视为抽象字符串问题。如果那是您想要的，那么我认为他们会提供很好的建议。我假设您想使用名称如何工作的特定知识，例如，"Mr. Thomas Riddle, Esq" 和 "Riddle, Tom" 将匹配 "Tom Riddle"，但 "Tom Griddle"不会。
一般来说，对于这类问题，您定义某种规范化函数并寻找规范化为同一事物的术语。在这种情况下，您的名字的规范表示似乎应该包括名字和姓氏的小写版本，去掉任何头衔，并且 "de-nicknamed" 使用昵称到正式名称的映射（假设您希望 "Tom" 和 "Thomas" 匹配）。此函数将产生 "Tom Riddle" -> {first: "tom", last: "riddle"}、"Riddle, Tom" -> {first: "tom", last: "riddle"}、"Tom Riddle, Esq" -> {first: "tom", last: "riddle"} 等，但 "Tom Griddle" -> {first: "tom", last: "griddle"}.
一旦你有了名称规范化功能，你就可以创建一个映射（例如 hashmap 或 BST），将规范名称与非规范名称列表相关联。对于每个非规范化名称，在映射中找到与其规范形式对应的列表并将其插入到那里。完成后，所有包含一个以上元素的列表都是您的副本。