搜索多个部分词组，使一个原始词组无法匹配多个搜索词组

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

实现此行为I used a 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]。最后我计算了两者的交集，return结果[5, 6]，显然是错误的（应该是[6]）。

你会如何解决这个问题？

Answer 1

如果定义了一组短语并且不包含长短语，也许您可以创建不是 1 个 trie，而是 n 个尝试，其中 n 是一个短语中的最大单词数。

在第 i 个 trie 中存储短语的第 i 个单词。我们称它为带有标签 'i'.

的特里树

要处理包含 m 个词的查询，让我们考虑以下算法：

对于每个短语，我们将存储 trie 的最低标签，即从该短语中找到的单词。让我们将其表示为 d[j]，其中 j 是短语索引。首先对于每个短语 j，d[j] = -1.
尝试 n 次搜索第一个单词。
对于每个短语 j，找到大于 d[j] 的 trie 的标签，以及从哪里找到这个短语中的单词。如果有多个这样的标签，请选择最小的一个。让我们将这样的标签表示为 c[j].
如果没有这样的索引，就无法匹配到这个词组。你可以用 d[j] = n + 1 标记这种情况。
如果存在 c[j] 且 c[j] > d[j]，则分配 d[j] = c[j]。
重复剩下的每个单词。
匹配 -1 < d[j] < n 的所有短语。

这不是很理想。为了提高性能，您应该只存储 d 数组的可用值。在第一个词之后，只存储与这个词匹配的短语。此外，删除索引 j 而不是赋值 d[j] = n + 1。仅处理已存储的短语索引。

Answer 2

您可以将其解决为 Graph Matching Problem in a Bipartite Graph。

对于每个文档，查询对定义图：

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 }

直观地说：查询中的每个术语都有一个顶点，文档中的每个术语都有一个顶点，文档术语和查询术语之间有一条边，前提是查询术语与文档术语匹配。你已经用你的 trie 解决了这部分。

你得到了一个二分图，只有 "query vertices" 和 "document vertices" 之间的边（而不是相同类型的两个顶点之间）。

现在，调用一个 matching problem for bipartite graph，并得到一个最佳匹配 {(t1_1,t2_1), ... , (t1_k,t2_k)}。

您的算法应该 return 一个文档 d 用于查询 q 并且查询中包含 m 个术语，如果（且仅当）所有 m 条款得到满足，这意味着 - 你在 k=m.

处有最大匹配

在您的示例中，query="prog p" 和 document="Programming Jokes" 的图，您将得到具有匹配的二分图：（或与 Programming,p matched - doesn't不管哪个)

并且，对于相同的查询，document="Programming Puzzles"，您将获得具有匹配项的二分图：

如您所见，对于第一个示例 - 没有涵盖所有术语的匹配项，您将 "reject" 文档。对于第二个示例 - 您能够匹配所有字词，并且您将 return 它。

对于性能问题，您可以仅对部分短语执行建议的算法，这些短语已被您的初始方法过滤掉（所有术语都匹配的文档的交集）。

Answer 3

重点观察

我们可以利用这样一个事实，即 query 中的两个词可以匹配 phrase 中的同一个词，前提是只有一个查询词是另一个查询词的前缀（或者如果它们相同）。因此，如果我们按字典降序处理查询词（前缀在 "superwords" 之后），那么我们可以 安全地 从第一个匹配的短语中删除词。这样做我们就不可能将同一个短语单词匹配两次。正如我所说，它是安全的，因为前缀匹配 superset 的短语词，它们的 "superwords" 可以匹配，以及一对查询词，其中一个不是另一个的前缀，始终匹配 disjoint 组词组。

我们不必从短语或 trie "physically" 中删除单词，我们可以做到 "virtually"。

算法的实现

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节点中存储phrase word count不是很记忆高效的。但是通过实施 compressed trie 可以将最坏情况下的内存复杂度降低到 O(n·m)，n 是所有短语中不同单词的数量，m 是总数短语数。
为了简单起见，我通过添加所有短语来初始化 answer。但一种更省时的方法是通过添加初始化 answer 查询词匹配最少的词组短语。然后与查询词匹配的词组相交第二最少的短语数。等等...

问题中引用的the Implementation的相关差异

在trie节点中，我不仅存储了subtrie匹配的短语引用（ids），还存储了这些短语中匹配单词的数量。所以，匹配的结果不仅是匹配的词组引用，还有这些词组中匹配词的个数。
我按降序字典顺序处理查询词。
我从当前匹配结果中减去超前缀（以当前查询词为前缀的查询词）的个数（使用变量superprefixCount），一个短语被认为与当前查询词匹配仅当其中匹配单词的结果数大于零时。与最初的实现一样，最终结果是匹配短语的交集。

正如你所看到的，变化很小，渐近复杂度（时间和内存）没有改变。

Answer 4

经过一番思考，我想到了与dened相似的想法——除了匹配短语的索引外，每个前缀都会指代它在该短语中作为前缀的单词数量——那么这个数字可以是在查询过程中减少了它在其他查询词中的超前缀的数量，并且返回的结果只包括那些至少与查询相同数量的匹配词。

我们可以通过添加（对于英语）最多大约 26 选 2 + 26 选 3 甚至额外的 26 选 4 特殊元素到特里来实现额外的小调整以避免大量交叉检查指的是有序的首字母交集。当插入一个短语时，trie 中引用 2 和 3 首字母组合的特殊元素将收到其索引。然后可以对来自较大查询词的匹配结果进行交叉检查。例如，如果我们的查询是“Geo i”，"Geo" 的匹配结果将针对特殊的 trie 元素 "g-i" 进行交叉检查，希望其匹配结果明显少于"i".

此外，根据具体情况，有时可以更有效地并行处理大型交叉检查（例如，通过位集 &）。

搜索多个部分词组，使一个原始词组无法匹配多个搜索词组

Searching for multiple partial phrases so that one original phrase can not match multiple search phrases

javascript

algorithm

autocomplete

autosuggest

data-structures

重点观察

算法的实现

可能的优化

问题中引用的the Implementation的相关差异