php :加速比对，10k +记录

Question

在我的MySQL表中，我有一个字段名，它是惟一的。然而，字段的内容是在不同的地方收集的。因此，由于拼写错误，我可能有两条名称非常相似的记录，而不是第二条记录被丢弃。

现在我想找到那些与另一个非常相似的条目。为此，我循环遍历我的所有记录，并通过再次循环所有记录来将名称与其他条目进行比较。问题是有超过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?

如果您习惯于使用复杂的(Ish) SQL，那么可以将繁重的任务委托给MySQL，并且至少可以获得一些性能，因为您不需要将全部16k行都放入MySQL运行时中。

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

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

3.5做一些工作onInsert

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

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

Answer 2

levenshtein的问题是它只比较字符串a和字符串b。我曾经构建了一个拼写校正器，将所有字符串a放入一个大trie中，并将其用作字典。然后，它将在该字典中查找任何字符串b，找到所有最近匹配的单词。我先用Fortran (!)，然后用Pascal。这在一种更现代的语言中是最简单的，但我怀疑php不会让它变得容易。