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

作为一个大多数前端开发人员，这是我不经常深入研究的计算机科学领域，但这是我的方案： 我有一个字符串的输入，分隔空格，说
"pinto beans"
 我有一系列搜索结果，包含如下结果： 
["beans, mung","beans, pinto","beans, yellow","beans, fava"]
 可能是最快的方式（最好是在javascript或php中）找到最“相关”的结果，例如大多数匹配，例如，在上面的例子中，我想对返回数组进行排序，以便将
"beans, pinto"
放在顶部，其余的都在下面，任何其他结果都会低于这些。 我的第一次尝试是做一些事情，比如将每个结果项与每个输入项匹配，并在每个输入项上增加匹配，然后按大多数匹配排序到最少。 这种方法需要我多次迭代整个结果数组，我觉得我缺乏CS知识让我没有最好的解决方案。 / *编辑：这是我最终处理问题的方式：* / 基于crazedfred的建议和他提到的博客文章（非常有用），我写了一些基本上使用trie方法和boyer-moore方法的组合的php，除了从字符串的开头搜索（因为我不喜欢） t想要匹配“superbean”中的“bean”。 基于我使用js库的事实选择php进行排名，并且在使用便利函数和库开销的同时获得真正的基准测试不会产生我之后的可测试结果，我不能保证它赢了在一个浏览器或另一个浏览器中爆炸。 这是测试数据： 搜索字符串：
lima beans
 结果数组（来自db）：
["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变量中，然后在空格中输入字符串。 然后，我预编译我的模式，将结果与以下内容进行比较： 
$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
相同的结果分数，因为该模式不是基于先前的匹配的条件。因为我正在寻找的结果和我期望的输入字符串不应该经常发生这种情况，所以我决定暂时保留它，以避免为这个快速的小脚本添加任何开销。但是，如果我最终觉得我的结果被它扭曲了，我会回到这里并发布关于我如何对该部分进行排序的帖子。     
2019-09-15 5 条评论
分享

没有找到相关结果

    已邀请:

    先对冈蒲

    由于您特别注意它可以使用多种语言，因此我将以伪代码保留我的答案，以便您可以适应您选择的语言。 由于您正在匹配阵列到阵列，因此性能将根据您的实现而有很大差异，因此尝试多种方法并准确考虑何时/如何/如何经常将其用于一个好主意。 简单的方法是保持数据不变并运行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的家伙梦想使用一些很棒的数据结构在恒定的时间内进行大量的字符串比较。从来没有尝试过，但它必须工作，因为他在非常低端的硬件上运行他的整个网站。如果你有兴趣，他会在这里写博客。 （注意：博客文章是关于过滤垃圾邮件，所以帖子中的一些文字可能只是NSFW。）     
    2019-09-15 0 0
    分享

    甲车劲

    我尝试建议JavaScript的解决方案，但它也适用于PHP。 这样您就不需要使用嵌套循环，只需使用排序函数和一些正则表达式。 像这样的东西： 
    var query = 'pinto beans';
var results = [ 'beans, mung','beans, pinto','beans, yellow','beans, fava' ];

// Evaluate a regular expression for your 
// query like /pinto|beans/g joining each
// query item with the alternation operator
var pattern = eval( '/' + query.split( ' ' ).join( '|' ) + '/g' );

// Define a function for custom sorting
function regsort( a, b ) {
    var ra = a.match( pattern );
    var rb = b.match( pattern );
    // return the indexing based on 
    // any single query item matched
    return ( rb ? rb.length : 0 ) - ( ra ? ra.length : 0 );
}

// Just launch the sorting
var sorted = results.sort( regsort );

// Should output the right sort:
// ["beans, pinto", "beans, mung", "beans, yellow", "beans, fava"]
console.log( sorted );
    我不确定这是否是处理您的请求的最快方法，但肯定它可以是避免嵌套循环+字符串比较的好方法。 希望这可以帮助！ 再见     
    2019-09-15 0 0
    分享

    辽躺

    非常有原始性 只是想把这个tid-bit排在前面。但这里有一个基于所用术语的简单排序实现。我会提前并提及单词变化（例如搜索“经验丰富”并且结果返回“季节性”）对排序没有影响（实际上，这些单词将会出于所有意图和目的，但是我认为由于它们的后缀而与“苹果”和“橙色”一样不同。 除此之外，这里有一种方法可以满足您的需求。我更多地使用它作为您如何实现的介绍，由您决定如何实现“scoreWord”功能。我也使用jQuery的.each（）方法，因为我很懒，但这可以用for语句轻松替换。 无论如何，这是一个版本，我希望它有所帮助。 
    var search = "seasoned pinto beans";
var results = ["beans, mung","beans, pinto","beans, yellow","beans, pinto, seasonal","beans, fava"];

// scoreWord
// returns a numeric value representing how much of a match this is to the search term.
// the higher the number, the more definite a match.
function scoreWord(result){
    var terms = search.toLowerCase().split(/W/),
        words = result.toLowerCase().split(/W/),
        score = 0;
    // go through each word found in the result
    $.each(words,function(w,word){
        // and then through each word found in the search term
        $.each(terms,function(t,term){
            // exact word matches score higher (a whole point)
            if (term==word)
                score++;
            // a word found in a word should be considered a partial
            // match and carry less weight (1/2 point in this case)
            else if (term.indexOf(word)!=-1||word.indexOf(term)!=-1)
                score+=0.5;
        });
    });
    // return the score
    return score;
}
// go through and sort the array.
results.sort(function(a,b){
    // grab each result's "score", them compare them to see who rates higher in
    // the array
    var aScore = scoreWord(a), bScore = scoreWord(b);
    return (aScore>bScore?-1:(aScore<bScore?1:0));
});
// they are officially "sorted" by relevance at this point.
        
    2019-09-15 0 0
    分享

    犯痪桂涛杭

    您可以预先计算将单词映射到许多结果的地图。 
    var results = ["beans, mung","beans, pinto","beans, yellow","beans, fava"];
var index = {};
for (var i = 0; i < results.length; i ++) {
    results[i].replace(/w+/g, function(a) {
        if (!index[a]) {
            index[a] = [i];
        } else {
            index[a].push (i);
        }
    });
}
    搜索时，您可以将查询拆分为单词。 
    function doSearch(searchString) {
    var words = [];
    var searchResults = [];
    var currentIndex;
    searchString.replace(/w+/g, function(a) {
        words.push (a);
    });
    将搜索结果构建为
    results
    数组的副本，但我将其放在对象中，以便它可以同时保存文本和分数。 
        for (var i = 0; i < results.length; i ++) {
        searchResults.push ({
            text: results[i],
            score: 0
        });
    }
    然后，对于每个搜索词，增加搜索结果中的分数。 
        for (var i = 0; i < words.length; i ++) {
        if ((currentIndex = index[words[i]])) {
            for (var j = 0; j < currentIndex.length; j ++) {
                searchResults[currentIndex[j]].score ++;
            }
        }
    }
    最后，按分数对其进行排序。 
        searchResults.sort (function(a, b) {
        return b.score - a.score;
    });
    return searchResults;
}
    做`doSearch（“pinto beans”），它返回一个搜索结果数组以及得分。 
    [{text:"beans, pinto", score:2}, {text:"beans, mung", score:1}, {text:"beans, yellow", score:1}, {text:"beans, fava", score:1}]
        
    2019-09-15 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.048651933670044