大型数组比较

Question

我在SQL数据库中有约25,000个不同的名称，并希望对所有这些名称执行编辑距离比较，以便规范化例如John Doe和Jhon Doe等名称。

当数据库中仅有大约1000个名称时，我曾将所有不同的名称存储在一个数组中。然后，我会在该数组上使用两个for循环，从而将数组中的每个元素与其他元素进行比较。当编辑距离给出大于0.9的匹配时，我会执行SQL查询，在所有记录中用一个值替换另一个值。

由于我的数据库规模更大，这种方法已经不再可行。你们会怎么做？

附：我也想了解任何多线程解决方案，因为现在这个过程太慢了。

附：我正在使用Java编码。

- Freek8

---

这些名称在同一张表中吗？你使用哪个函数来比较这些名称？ - carpamon

这个在数据库端可能实现吗？如果可以的话，我更喜欢这种方式。否则，类似于fork/join的概念可能会有用。 - kosa

这基本上是一个大的名称数组，需要与自身进行比较。我认为这在数据库端不可能实现，因为我需要计算每个名称组合之间的度量值，以确定它们是否相似（以纠正拼写错误等）。 - Freek8

Answer 1

无论如何，成对匹配是最有效的方法。

如果您需要更快地执行记录链接，请尝试使用字符串距离度量，该度量所需的计算量比编辑距离（Bonacci距离，Jaro-Winkler距离等）少。

您还可以将另一个指标用作预处理步骤，然后计算编辑距离以确认或拒绝匹配。

- Sergey Kalinichenko

---

我正在使用Jaro-Winkler算法进行编辑距离计算。问题不在于jw距离计算所需的时间，而在于记录数量。我正在寻找一种将工作分割成不同线程的方法。 - Freek8

@Freek8 噢，我以为Levenshtein距离被称为“编辑距离”（但维基百科说我错了，有很多"编辑距离"）。无论您使用什么指标，您都需要进行N *（N-1）/ 2次检查；唯一可以使您的过程更快的事情是更快地计算指标。 - Sergey Kalinichenko

你认为ChrisJ的Soundex方法怎么样？我可以通过Soundex将所有记录分组，然后每组只需进行JW距离计算。也许我可以为每个组分配一个单独的线程！ - Freek8

@Freek8 我会尝试一下，看看效果如何。你可能会得到比常规编辑距离更少的匹配，但我不确定你在那方面有多少选择。 - Sergey Kalinichenko

谢谢！用我的旧方法，我会遇到内存问题，或者需要很长时间。我要试试这个新方法。 - Freek8

@Freek8 你应该接受ChrisJ的答案，因为他是提出Soundex算法的人。祝好运！ - Sergey Kalinichenko

Answer 2

你可以计算每个名字的soundex，并将其存储在数据库中。你甚至可以在数据库端完成这项工作，例如使用MySQL SOUNDEX函数。

计算每个名称的soundex后，你只需要按相同的soundex分组即可。

编辑：

如果soundex对于你的应用程序来说太粗糙，你可以通过比较它们的soundex来首先选择候选人，并在每组候选人上使用你通常的度量标准。

- ChrisJ

---

我并不是很喜欢Soundex，但我喜欢你使用它来选择候选人的想法。特别是因为有一个可用的mysql soundex函数。 - Freek8