php : speed up levensthein comparing, 10k + 记录

Question

在我的 MySQL 表中，我有字段名称，它是唯一的。然而，字段的内容聚集在不同的地方。所以有可能我有 2 条记录具有非常相似的名称，而不是第二条记录由于拼写错误而被丢弃。

现在我想找到那些与另一个非常相似的条目。为此，我遍历所有记录，并通过再次遍历所有记录将名称与其他条目进行比较。问题是有超过 15k 条记录需要太多时间。有没有办法更快地做到这一点？

这是我的代码:

for($x=0;$x<count($serie1);$x++)
    {
    for($y=0;$y<count($serie2);$y++)
        {
        $sim=levenshtein($serie1[$x]['naam'],$serie2[$y]['naam']);
        if($sim==1)
            print("{$A[$x]['naam']} --> {$B[$y]['naam']} = {$sim}<br>");
        }
     }
 }

Answer 1

序言:这样的任务总是很耗时，而且总会有一些对漏掉。尽管如此，还是有一些想法:

1。实际上，该算法可以(稍微)改进

假设 $series1 和 $series2 具有相同顺序的相同值，您不需要在内部循环中遍历整个第二个数组时间。在这个用例中，您只需要评估每个值对一次 - levenshtein('a', 'b') 就足够了，您不需要 levenshtein('b', 'a ') 以及(你也不需要 levenstein('a', 'a'))

在这些假设下，您可以这样编写您的函数:

for($x=0;$x<count($serie1);$x++)
{
   for($y=$x+1;$y<count($serie2);$y++) // <-- $y doesn't need to start at 0
    {
      $sim=levenshtein($serie1[$x]['naam'],$serie2[$y]['naam']);
      if($sim==1)
        print("{$A[$x]['naam']} --> {$B[$y]['naam']} = {$sim}<br>");
    }
 }

2。也许 MySQL 更快

网络中有 levenshtein() 实现作为 MySQL 函数的示例。这里有一个关于 SO 的例子:How to add levenshtein function in mysql?

如果您熟悉复杂的 SQL，您可以将繁重的工作委派给 MySQL 并至少获得一点性能，因为您没有将整个 16k 行提取到 PHP 运行时。

3。不要一次做所有事情/保存你的结果

当然，您必须为每条记录运行一次该函数，但在初次运行后，您只需检查自上次运行以来的新条目。安排一个每天/每周/每月一次的 chronjob.. 检查所有新记录。您的表中需要一个 inserted_at 列，并且仍然需要将新名称与所有其他名称条目进行比较。

3.5 在Insert上做一些工作

a) 如果等待是可以接受的，一旦插入新记录就进行检查，以便将其写入日志或直接反馈给用户。 (切线:对于像 http://gearman.org/ 这样的异步任务队列，这可能是一个很好的用例 -> 在后台启动一个新的检查进程，立即返回插入的成功消息)

b) PHP 还有另外两个函数可以帮助搜索几乎相似的字符串:metaphone()和 soundex() .这些函数生成抽象哈希值，表示字符串在说话时的发音。您可以在每次插入时生成(一个或两个)这些哈希值，将它们作为单独的字段存储在您的表中，并使用简单的 SQL 函数来查找具有相似哈希值的记录