php - 从输入数组中查找数组中相关结果的最快方法

Question

作为一名主要的前端开发人员，这是我不经常深入研究的计算机科学领域，但这是我的场景:

我有一个字符串的输入，用空格分割，比如 "pinto beans"
我有一系列要搜索的结果，其中包含以下结果:["beans, mung","beans, pinto","beans, yellow","beans, fava"]
什么可能是最快的方法(最好在 javascript 或 php 中)找到最“相关”的结果，也就是大多数匹配，例如，在上述情况下，我想对返回数组进行排序，以便 "beans, pinto"放在顶部，其余的放在下面，任何其他结果都将低于这些结果。

我在这方面的第一次尝试是将每个结果项与每个输入项进行匹配，并在每个项上增加匹配项，然后按最多匹配到最少匹配进行排序。

这种方法需要我多次遍历整个结果数组，而且我觉得我缺乏 CS 知识使我在这里没有最佳解决方案。

/* 编辑:这是我最终处理问题的方式:*/

根据 crazedfred 的建议和他提到的博客文章(非常有帮助)，我写了一些 php，它基本上结合使用了 trie 方法和 boyer-moore 方法，除了从字符串的开头搜索(因为我不不想匹配“ super bean ”中的“ bean ”)。

我选择 php 作为排名基于我使用 js 库的事实，并且在使用便利函数和库开销的同时获得真正的基准测试不会产生我所追求的可测试结果，我不能保证它会赢不会在一种浏览器或另一种浏览器中爆炸。

下面是测试数据:

搜索字符串:lima beans
结果数组(来自数据库):["Beans, kidney","Beans, lima","Beans, navy","Beans, pinto","Beans, shellie","Beans, snap","Beans, mung","Beans, fava","Beans, adzuki","Beans, baked","Beans, black","Beans, black turtle soup","Beans, cranberry (roman)","Beans, french","Beans, great northern","Beans, pink","Beans, small white","Beans, yellow","Beans, white","Beans, chili","Beans, liquid from stewed kidney beans","Stew, pinto bean and hominy"]
首先，我将搜索字符串和结果数组都放入 php 变量中，在 explode() 之后将字符串放在空格上。

然后，我预编译我的模式以将结果与:

$max = max(array_map('strlen',$input));
$reg = array();
for($m = 0; $m < $max; $m++) {
    $reg[$m] = "";
    for($ia = 0; $ia < count($input); $ia++) {
        $reg[$m]. = $input[$ia][$m];
    }
}

这给了我类似的东西:["lb","ie","ma","an","s"]
然后，我基本上采用每个结果字符串(按空格拆分)，并将不区分大小写的字符类与相应的字符号匹配。如果在比较过程中的任何时候我没有得到任何匹配，我就会跳过这个词。这意味着如果只有 1 个结果以“b”或“l”开头，我将只对每个 WORD 进行一次比较，这非常快。基本上，我正在参与将搜索编译在一起的 trie 的一部分，以及 Boyer-Moore 内容的不断加速。

这是 php - 我试过 while s，但使用 foreach 获得了明显更好的结果es:

$sort = array();
foreach($results as $result) {
    $matches = 0;
    $resultStrs = explode(' ', $result);
    foreach($resultStrs as $r) {
        $strlen = strlen($r);
        for($p = 0; $p < $strlen; $p++) {
            if($reg[$p])
                preg_match('/^['.$reg[$p].']/i',$r[$p],$match);
            if($match==true) {
                $matches++;
            } else {
                break 2;
            }
        }
    }
    $sort[$result] = $matches;
}

这会输出一个数组，其中包含键上的结果，以及我们在值上总共获得了多少个字符匹配。

我这样说的原因是为了避免会破坏我的数据的关键冲突，更重要的是，我可以快速做一个 asort并按顺序得到我的结果。

这个顺序是相反的，在键上，所以在上面的代码块之后，我运行:

asort($sort);
$sort = array_reverse(array_keys($sort));

这给了我一个正确索引的结果数组，从最相关到​​最不相关。我现在可以把它放在我的自动完成框中。

因为速度是这个实验的重点，这是我的结果 - 显然，它们部分取决于我的计算机。

2 个输入词，40 个结果:~5ms
2个输入词，(一个单字，一个全)126个结果:~9ms

显然，这些结果涉及的变量太多，对您来说意义不大，但作为一个例子，我认为这非常令人印象深刻。

如果有人发现上面的例子有问题，或者能想到比这更好的方法，我很想听听。我现在唯一能想到的可能会引起问题的是，如果我要搜索术语 lean bimas ，我会得到与 lima beans 相同的结果分数，因为模式不是基于先前匹配的条件。因为我正在寻找的结果和我期望的输入字符串不应该经常发生这种情况，所以我决定暂时保持原样，以避免给这个快速的小脚本增加任何开销。然而，如果我最终觉得我的结果被它扭曲了，我会回到这里并发布我如何对这部分进行排序。

Answer 1

由于您特别指出它可能有多种语言，因此我将以伪代码形式保留我的答案，以便您可以适应您选择的语言。

由于您正在匹配数组到数组，因此性能将根据您的实现而有很大差异，因此尝试多种方法并准确考虑何时/如何/多久使用一次是个好主意。

简单的方法是保留数据原样并运行 O(n^2) 搜索:

for (every element in array X)
    for (every element in array Y)
        if (current X == current Y)
            add current X to results

return results

如果您先对数组进行排序(在许多语言中都为您实现了诸如快速排序之类的排序算法，请查看您的文档!)，那么实际匹配会更快。使用您的语言具有的任何字符串比较:

Sort array X
Sort array Y

Let A = first element of X
Let B = first element of Y

while (A and B are in array)
    if (A > B)
        Next B
    else if (A < B)
        Next A
    else  //match!
        Add A to results
        Next A
        Next B

//handle case where one array is larger (trivial loop)

return results

现在上述解决方案的重要部分是数组的排序是否比普通的 O(n^2) 排序节省了时间。通常，在数组中移动元素很快，而字符串比较则不然，因此可能值得。再次，尝试两者。

最后，有一个疯狂的算法，Mailinator 的家伙梦想使用一些很棒的数据结构在恒定时间内进行大量的字符串比较。我自己从未尝试过，但它必须工作，因为他在非常低端的硬件上运行他的整个站点。他写了博客 here如果你有兴趣。 (注:博文是关于过滤垃圾邮件的，所以文中的一些词可能略有NSFW。)