搜索多个部分短语,使一个原始短语无法匹配多个搜索短语

Question

给定一组预定义的短语,我想根据用户的查询执行搜索.例如,请考虑以下一组短语:

index      phrase
-----------------------------------------
0          Stack Overflow
1          Math Overflow
2          Super User
3          Webmasters
4          Electrical Engineering
5          Programming Jokes
6          Programming Puzzles
7          Geographic Information Systems 

预期的行为是:

query         result
------------------------------------------------------------------------
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

为了实现这种行为,我使用了一个trie.trie中的每个节点都有一个索引数组(最初为空).

要在trie中插入一个短语,我首先将其分解为单词.例如,Programming Puzzles有index = 6.因此,我添加6到以下所有节点:

p
pr
pro
prog
progr
progra
program
programm
programmi
programmin
programming
pu
puz
puzz
puzzl
puzzle
puzzles

问题是,当我搜索查询prog p,我第一次得到指数的列表,prog这是[5, 6].然后,我得到指数的列表p是[5, 6]为好.最后,我计算两者之间的交集,并返回结果[5, 6],这显然是错误的(应该是[6]).

你会如何解决这个问题？

Answer 1

关键观察

我们可以利用这样一个事实：仅当一个查询词是另一个查询词的前缀（或者它们相同）时，查询中的两个单词才能匹配短语中的相同单词 。因此，如果我们按字典顺序降序处理查询单词（前缀位于其“超级单词”之后），那么我们可以安全地从第一个匹配的短语中删除单词。这样做我们就不可能将同一个短语单词匹配两次。正如我所说，它是安全的，因为前缀匹配短语单词的超集，它们的“超级单词”可以匹配，并且一对查询单词，其中一个不是另一个的前缀，总是匹配不相交的短语单词集。

我们不必“物理地”从短语或特里树中删除单词，我们可以“虚拟地”进行。

算法的实现

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 节点中的内存效率不是很高。但是通过实现压缩 trie可以将最坏情况的内存复杂度降低到O(nm)，其中n是所有短语中不同单词的数量，m是短语的总数。

• 为了简单起见，我answer通过添加所有短语来初始化。但更省时的方法是answer通过添加与最少数量的短语匹配的查询词所匹配的短语来进行初始化。然后与匹配第二少的短语的查询词的短语相交。等等...

与问题中引用的实现的相关差异

1. 在 trie 节点中，我不仅存储与 subtrie 匹配的短语引用（ids），还存储这些短语中匹配单词的数量。因此，匹配的结果不仅是匹配的短语引用，还包括这些短语中匹配的单词的数量。
2. 我按字典顺序降序处理查询词。
3. 我从当前匹配结果中减去超级前缀（当前查询词作为前缀的查询词）的数量（通过使用变量superprefixCount），并且仅当短语中匹配单词的结果数量时，才认为该短语与当前查询词匹配。大于零。与原始实现一样，最终结果是匹配短语的交集。

正如我们所看到的，变化是最小的，并且渐近复杂性（时间和内存）没有改变。