Поиск нескольких частичных фраз, чтобы одна оригинальная фраза не соответствовала нескольким поисковым фразам

Ответ 1

Наблюдение за ключами

Мы можем использовать тот факт, что два слова в запросе могут совпадать с одним словом во фразе, только если одно слово запроса является префиксом другого слова запроса (или если оно одинаково). Поэтому, если мы обрабатываем слова запроса в нисходящем лексикографическом порядке (префиксы приходят после их "сверхслов" ), мы можем безопасно удалять слова из фраз в первом совпадении. Таким образом, мы не имели возможности сопоставить одно и то же слово фразы дважды. Как я уже сказал, это безопасно, потому что префиксы соответствуют superset фразовых слов, которые могут соответствовать их "суперсловам", а пара слов запроса, где один не является префиксом другого, всегда соответствует disjoint набор слов фразы.

Нам не нужно удалять слова из фраз или "физически", мы можем сделать это "практически".

Реализация алгоритма

var PhraseSearch = function () {   
    var Trie = function () {
        this.phraseWordCount = {};
        this.children = {};
    };

    Trie.prototype.addPhraseWord = function (phrase, word) {
        if (word !== '') {
            var first = word.charAt(0);

            if (!this.children.hasOwnProperty(first)) {
                this.children[first] = new Trie();
            }
            var rest = word.substring(1);
            this.children[first].addPhraseWord(phrase, rest);
        }
        if (!this.phraseWordCount.hasOwnProperty(phrase)) {
            this.phraseWordCount[phrase] = 0;
        }
        this.phraseWordCount[phrase]++;
    };

    Trie.prototype.getPhraseWordCount = function (prefix) {
        if (prefix !== '') {
            var first = prefix.charAt(0);

            if (this.children.hasOwnProperty(first)) {
                var rest = prefix.substring(1);
                return this.children[first].getPhraseWordCount(rest);
            } else {
                return {};
            }
        } else {
            return this.phraseWordCount;
        }
    }

    this.trie = new Trie();
}

PhraseSearch.prototype.addPhrase = function (phrase) {
    var words = phrase.trim().toLowerCase().split(/\s+/);
    words.forEach(function (word) {
        this.trie.addPhraseWord(phrase, word);
    }, this);
}

PhraseSearch.prototype.search = function (query) {
    var answer = {};
    var phraseWordCount = this.trie.getPhraseWordCount('');
    for (var phrase in phraseWordCount) {
        if (phraseWordCount.hasOwnProperty(phrase)) {
            answer[phrase] = true;
        }
    }

    var prefixes = query.trim().toLowerCase().split(/\s+/);

    prefixes.sort();
    prefixes.reverse();

    var prevPrefix = '';
    var superprefixCount = 0;

    prefixes.forEach(function (prefix) {
        if (prevPrefix.indexOf(prefix) !== 0) {
            superprefixCount = 0;
        }
        phraseWordCount = this.trie.getPhraseWordCount(prefix);

        function phraseMatchedWordCount(phrase) {
            return phraseWordCount.hasOwnProperty(phrase) ? phraseWordCount[phrase] - superprefixCount : 0;
        }

        for (var phrase in answer) {
            if (answer.hasOwnProperty(phrase) && phraseMatchedWordCount(phrase) < 1) {
                delete answer[phrase];
            }
        }

        prevPrefix = prefix;
        superprefixCount++;
    }, this);

    return Object.keys(answer);
}

function test() {
    var phraseSearch = new PhraseSearch();

    var phrases = [
        'Stack Overflow',
        'Math Overflow',
        'Super User',
        'Webmasters',
        'Electrical Engineering',
        'Programming Jokes',
        'Programming Puzzles',
        'Geographic Information Systems'
    ];

    phrases.forEach(phraseSearch.addPhrase, phraseSearch);

    var queries = {
        's':       'Stack Overflow, Super User, Geographic Information Systems',
        'web':     'Webmasters',
        'over':    'Stack Overflow, Math Overflow',
        'super u': 'Super User',
        'user s':  'Super User',
        'e e':     'Electrical Engineering',
        'p':       'Programming Jokes, Programming Puzzles',
        'p p':     'Programming Puzzles'
    };

    for(var query in queries) {
        if (queries.hasOwnProperty(query)) {
            var expected = queries[query];
            var actual = phraseSearch.search(query).join(', ');

            console.log('query: ' + query);
            console.log('expected: ' + expected);
            console.log('actual: ' + actual);
        }
    }
}

Здесь можно проверить этот код: http://ideone.com/RJgj6p

Возможные оптимизации

• Сохранение количества слов фразы в каждом trie node - это не очень память эффективный. Но, реализуя сжатый trie, можно уменьшите сложность памяти наихудшего случая до O (n m), там n является количество разных слов во всех фразах, а m - общее количество количество фраз.

• Для простоты я инициализирую answer, добавив все фразы. Но более эффективный подход к времени - инициализировать answer путем добавления фразы, соответствующие слову запроса, соответствующему наименьшему числу фразы. Затем пересекаются с фразами соответствия слова запроса второе наименьшее количество фраз. И так далее...

Соответствующие отличия от Реализация Ссылка в вопросе

• В trie node Я храню не только ссылки на фразу (ids), которые соответствуют подтипу, но и количество совпадающих слов в этих фразах. Таким образом, результатом совпадения являются не только совпадающие фразовые ссылки, но и количество совпадающих слов в этих фразах.
• Я обрабатываю слова запроса в нисходящем лексикографическом порядке.
• Я вычитаю количество суперпрефиксов (слова запроса, из которых текущее слово запроса является префиксом) из текущих результатов совпадения (с использованием переменной superprefixCount), а фраза считается совпадающей с текущим словом запроса только тогда, когда результат число совпадающих слов в нем больше нуля. Как и в исходной реализации, конечным результатом является пересечение согласованных фраз.

Как можно видеть, изменения минимальны, а асимптотические сложности (как время, так и память) не изменяются.

Ответ 2

Если набор фраз определен и не содержит длинных фраз, возможно, вы можете создать не 1 trie, а n try, где n - максимальное количество слов в одной фразе.

В i-м магазине i-го слова фразы. Позвольте называть это trie с меткой "i".

Для обработки запроса с помощью m слов рассмотрим следующий алгоритм:

• Для каждой фразы мы будем хранить самую низкую метку trie, где было найдено слово из этой фразы. Обозначим его как d [j], где j - индекс фразы. Сначала для каждой фразы j, d [j] = -1.
• Искать первое слово в каждом из n попыток.
• Для каждой фразы j найдите метку trie, которая больше d [j], и где было найдено слово из этой фразы. Если есть несколько таких ярлыков, выберите самый маленький. Обозначим такую ​​метку как c [j].
• Если такого индекса нет, эту фразу нельзя сопоставить. Вы можете отметить этот случай с помощью d [j] = n + 1.
• Если существует такое c [j], что c [j] > d [j], чем назначить d [j] = c [j].
• Повторите все слова слева.
• Каждая фраза с -1 < d [j] n соответствует.

Это не очень оптимально. Чтобы повысить производительность, вы должны хранить только используемые значения массива d. После первого слова сохраните только фразы, соответствующие этому слову. Кроме того, вместо назначения d [j] = n + 1, удалите индекс j. Обработка только уже сохраненных индексов фразы.

Ответ 3

Вы можете решить его как Задача сопоставления графа в Двусторонний график.

Для каждого документа пара запросов определяет график:

G=(V,E) Where
V = {t1 | for each term t1 in the query} U { t2 | for each term t2 in the document}
E = { (t1,t2) | t1 is a match for t2 }

Интуитивно: у вас есть вершина для каждого термина в запросе, вершина для каждого термина в документе и край между термином документа и термином запроса, только если термин запроса совпадает с термином документа. Вы уже решили эту часть своей трюкой.

У вас есть двудольный граф, между "вершинами запроса" и "вершинами документа" (и не между двумя вершинами того же типа) есть только ребра.

Теперь вызовите задачу соответствия для двухстороннего графа и получите оптимальное соответствие {(t1_1,t2_1), ... , (t1_k,t2_k)}.

Ваш алгоритм должен возвращать документ d для запроса q с m в запросе, если (и только если) все m термины выполнены, что означает - вы имеете максимальное соответствие, где k=m.

В вашем примере график для запроса = "prog p" и document = "Программирование шуток", вы получите двудольный граф с соответствием: (или с помощью программирования, p соответствует - не имеет значения, какой)

И для одного и того же запроса и документа = "Программирование головоломок" вы получите двудольный граф с соответствием:

Как вы можете видеть, для первого примера - нет соответствия, которое охватывает все термины, и вы "отклоняете" документ. Для второго примера - вы смогли сопоставить все условия, и вы вернете его.

Для проблем с производительностью вы можете использовать предложенный алгоритм только для подмножества фраз, которые уже были отфильтрованы вашим первоначальным подходом (пересечение документов, которые соответствуют всем терминам).

Ответ 4

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

Мы можем выполнить дополнительную небольшую настройку, чтобы избежать больших перекрестных проверок, добавив (для английского языка) максимум приблизительно 26 выбрать 2 + 26 выбрать 3, и даже дополнительно 26 выбрать 4 специальных элемента для три, которые ссылаются на упорядоченные пересечения первой буквы. Когда вставлена ​​фраза, специальные элементы в trie, относящиеся к 2 и 3 комбинациям с первой буквой, получат свой индекс. Тогда результаты сопоставления с более крупными словами запроса могут быть перепроверены против них. Например, если наш запрос равен "Geo i", результаты сопоставления для "Geo" будут перекрестно проверены на специальный элемент trie, "g-i", который, надеюсь, будет иметь значительно меньшие результаты совпадения, чем "i".

Кроме того, в зависимости от конкретных обстоятельств большая перекрестная проверка может время от времени быть более эффективно обрабатываться параллельно (например, через биттет &).