Самый быстрый способ найти соответствующие результаты в массиве из входного массива

Question

Как разработчик, в основном интерфейсный, это область компьютерных наук, в которую я не часто вникаю, но вот мой сценарий:

У меня есть ввод строки, splitна пробелах, скажем, "pinto beans"

У меня есть массив результатов для поиска, который содержит такие результаты, как: ["beans, mung","beans, pinto","beans, yellow","beans, fava"]

, что может быть самым быстрым способом (предпочтительно в JavaScript или PHP), чтобы найти наиболее «релевантные» результаты, то есть большинство совпадений, например, в приведенном выше случае, я хотел бы отсортировать возвращаемый массив так, чтобы "beans, pinto" ставился вверху, а остальные - ниже, а все остальныерезультаты будут ниже этих.

Моей первой попыткой было бы сделать что-то вроде сопоставления каждого элемента результата с каждым входным элементом и увеличения совпадений для каждого, а затем сортировки по большинству совпадений с наименьшим.

Этот подход потребовал бы от меня повторения по всему массиву результатов много раз, и я чувствую, что мое отсутствие знаний по CS оставляет меня без лучшего решения здесь.

/ * РЕДАКТИРОВАТЬ: Вот как я закончил с этой проблемой: * /

Основываясь на предложении crazedfred и сообщении в блоге, которое он упомянул (что было ОЧЕНЬ полезно), я написал несколько php, которые в основном используют комбинацию изметод три и метод Бойера-Мура, кроме поиска в начале строки (поскольку я не хочу сопоставлять "bean" в "superbean").

Я выбрал 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, которая собирает результаты поиска вместе, и постоянное ускорение работы Бойера-Мура.

Вот 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 результатов: ~ 5 мс 2 входных слова, (один символ, одно целое) 126 результатов: ~ 9 мс

Очевидно, что слишком много переменных поставлено на карту, чтобы эти результаты могли много значить для ВАС, но в качестве примера ядумаю, это довольно впечатляюще.

Если кто-то видит что-то не так с приведенным выше примером или может придумать лучший способ, чем это, я бы хотел услышать об этом.Единственное, о чем я могу думать, может быть, сейчас это вызывает проблемы, если бы я искал термин lean bimas, я бы получил тот же результат, что и lima beans, потому что шаблон не является условным на основании предыдущих совпадений.,Поскольку результаты, которые я ищу, и ожидаемые строки ввода не должны приводить к такому случаю, я решил оставить все как есть, чтобы избежать дополнительных затрат на этот быстрый маленький скрипт.Однако, если я в итоге почувствую, что мои результаты искажаются этим, я вернусь сюда и напишу о том, как я отсортировал эту часть.

Answer 1

Я пытаюсь предложить решение для 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 );

Я не уверен, что это самый быстрый способ обработки вашего запроса, но наверняка это может быть хорошим решением, чтобы избежать сравнения вложенных циклов + строк.

Надеюсь, это поможет! Ciao

Answer 2

Поскольку вы специально отметили, что это может быть на нескольких языках, я оставлю свой ответ в псевдокоде, чтобы вы могли адаптироваться к выбранному вами языку.

Поскольку вы сопоставляете массив с массивом, производительность будет сильно варьироваться в зависимости от вашей реализации, поэтому попробуйте несколько способов и точно определите, когда / как / как часто это будет использоваться в качестве хорошей идеи.

Простой способ - оставить данные как есть и выполнить поиск 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

Если вы сначала отсортировали массивы (алгоритм сортировки, такой как squicksort, реализован для вас на многих языках, проверьте документацию!), Тогда фактическое сопоставление происходит быстрее. Используйте любое сравнение строк на вашем языке:

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 для выполнения огромных сравнений строк в постоянное время с использованием некоторых потрясающих структур данных. Сам никогда не пробовал, но это должно сработать, так как он весь сайт работает на очень низком оборудовании. Он написал об этом здесь , если вам интересно. (Примечание: сообщение в блоге посвящено фильтрации спама, поэтому некоторые слова в сообщении могут быть слегка недоверчивыми.)

Answer 3

Вы можете предварительно вычислить карту, которая отображает слово для многих результатов.

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 (" бобы пинто "), он возвращает массив результатов поиска, а также оценку.

[{text:"beans, pinto", score:2}, {text:"beans, mung", score:1}, {text:"beans, yellow", score:1}, {text:"beans, fava", score:1}]

Answer 4

ОЧЕНЬ ПРИМИТИВНО

Просто хотел убрать этот момент с ног на голову. Но вот простая реализация сортировки на основе используемых терминов. Я буду честен и упомяну, что варианты слов (например, поиск «закаленный» и результат возвращается как «сезонный») не будут влиять на сортировку (на самом деле, эти слова будут, во всех смыслах и целях, но думают так же, как и «яблоко» и «апельсин» из-за их суффикса).

Учитывая это, вот один из способов сделать то, что вы ищете. Я использую это больше как просто введение в то, как вы можете реализовать, это зависит от вас, как вы хотите реализовать функцию "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.