从零构建现代搜索引擎（08）：短语、布尔查询与过滤

上一篇的倒排索引只支持单词查询和最基本的 AND/OR。搜索 “Java 内存模型” 时，AND 查询能找到同时包含 “java”、“内存”、“模型” 三个词的文档，但也会命中一篇标题是"Java 并发编程"、正文某处提到"内存不足"、另一处提到"设计模型"的文档——三个词散布在不同段落，根本不是"Java 内存模型"这个概念。

短语查询（phrase query）要求词项不仅共现，还必须按指定顺序出现在相邻位置。这需要用到第 06 篇记录的 position 信息。

本篇在倒排索引上增加三项能力：短语查询、带优先级的布尔查询语法、以及字段过滤。

短语查询：Positional Intersection

核心思路

短语 “Java 内存模型” 经过分析器产出三个词项，position 分别为 0、1、2。在目标文档中，这三个词项也必须出现在连续的 position 上（允许 position 差恰好等于词项在查询中的间距）。

算法分两步：

1. 对短语中所有词项的倒排列表做 AND（交集），找到同时包含所有词项的文档
2. 对每个候选文档，检查各词项的 position 列表是否存在满足间距要求的组合

Position 检查

两个词项在同一文档中的 position 列表都是排序的。检查 “term_i 出现在 term_j 之前恰好 k 个位置” 等价于：在 term_j 的 position 列表中查找 term_i 的某个 position + k。

双指针法：

boolean hasPhrase(int[] positions1, int[] positions2, int gap) {
    int i = 0, j = 0;
    while (i < positions1.length && j < positions2.length) {
        int diff = positions2[j] - positions1[i];
        if (diff == gap) return true;
        if (diff < gap) j++;
        else i++;
    }
    return false;
}

对三个及以上词项的短语，逐对检查相邻词项的 position 间距是否为 1。更准确的做法是找到一组 position 使得 pos[0] + 1 == pos[1]、pos[1] + 1 == pos[2]……

boolean checkPhrase(List<int[]> termPositions) {
    int[] anchors = termPositions.get(0);
    for (int anchor : anchors) {
        boolean match = true;
        for (int t = 1; t < termPositions.size(); t++) {
            int target = anchor + t;
            if (Arrays.binarySearch(termPositions.get(t), target) < 0) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

时间复杂度：对每个锚点做 (n-1) 次二分查找，总计 O(p × n × log(q))，其中 p 是第一个词项的 position 数量，n 是短语长度，q 是最长 position 数组的长度。

中文短语的特殊情况

中文 bigram 分词下，“搜索引擎” 产出 token “搜索”(pos=0)、“索引”(pos=1)、“引擎”(pos=2)。短语查询 “搜索引擎” 分析后也产出相同的 bigram 序列和 position。两边用同一个分析器，position 匹配自然成立。

但 bigram 的问题在于：文档中 “搜索” 和 “引擎” 之间如果夹了别的字（如"搜索的引擎"），bigram 序列变成 “搜索”、“索的”、“的引”、“引擎”，position 间距不再是 2，短语查询不会误命中。这是 bigram 的一个优点——虽然单词查询有噪声（"京大"问题），但短语查询天然具有位置约束。

布尔查询语法

查询语法设计

支持以下语法：

java                        → 单词查询
"Java 内存模型"              → 短语查询
java AND 内存                → 两个词项的交集
java OR python              → 两个词项的并集
java AND NOT python         → 排除
(java OR python) AND 内存   → 括号分组

运算符优先级：NOT > AND > OR。括号覆盖默认优先级。

递归下降解析

用递归下降解析器（recursive descent parser）将查询字符串转换为查询树：

sealed interface Query {
    record Term(String term) implements Query {}
    record Phrase(List<String> terms) implements Query {}
    record And(Query left, Query right) implements Query {}
    record Or(Query left, Query right) implements Query {}
    record Not(Query inner) implements Query {}
}

解析器的每个方法对应一条语法规则：

Query parseOr() {
    Query left = parseAnd();
    while (match("OR")) {
        left = new Query.Or(left, parseAnd());
    }
    return left;
}

Query parseAnd() {
    Query left = parseNot();
    while (match("AND")) {
        left = new Query.And(left, parseNot());
    }
    return left;
}

Query parseNot() {
    if (match("NOT")) {
        return new Query.Not(parsePrimary());
    }
    return parsePrimary();
}

Query parsePrimary() {
    if (match("(")) {
        Query q = parseOr();
        expect(")");
        return q;
    }
    if (currentToken().startsWith("\"")) {
        return parsePhrase();
    }
    return new Query.Term(consume());
}

这个解析器天然不会无限递归——每个方法消耗至少一个 token 后才递归，或者调用优先级更高的方法。括号通过回到 parseOr() 实现嵌套。

非法语法处理

对不合法的输入要有合理的降级：

输入	处理
AND java	AND 前缺少操作数 → 忽略 AND，当作 java
java AND	AND 后缺少操作数 → 忽略 AND，当作 java
java (	未闭合括号 → 报错或忽略括号
""	空短语 → 返回空结果
空字符串	返回空结果

策略是宽容解析：尽量从不完整的输入中提取有意义的查询，而不是直接拒绝。

查询执行

对查询树做后序遍历，递归执行：

List<Integer> execute(Query query) {
    return switch (query) {
        case Query.Term t -> searchTerm(t.term());
        case Query.Phrase p -> searchPhrase(p.terms());
        case Query.And a -> and(execute(a.left()), execute(a.right()));
        case Query.Or o -> or(execute(o.left()), execute(o.right()));
        case Query.Not n -> not(execute(n.inner()));
    };
}

NOT 查询返回的是"不包含该词项的所有文档"。实现上需要全量文档 ID 列表减去命中列表。单独使用 NOT 会返回几乎所有文档，通常 NOT 与 AND 组合使用：java AND NOT python。

过滤

字段过滤

搜索结果可以按文档元数据过滤：语言、来源、日期范围。过滤不影响评分，只缩小候选集。

interface Filter {
    boolean matches(int docId);
}

record LanguageFilter(String lang, String[] docLanguages)
        implements Filter {
    public boolean matches(int docId) {
        return lang.equals(docLanguages[docId]);
    }
}

对教学场景，后过滤（先查询再过滤）足够。候选集不大，遍历一次检查 filter 的成本可以忽略。

过滤与布尔查询的区别

过滤是二值的（匹配/不匹配），不影响评分。布尔查询中的 AND NOT 操作的是词项匹配，不是元数据。

搜索 “java” 且只看中文文档：用过滤实现 search("java").filter(lang="zh")，而不是 search("java AND 中文")——后者要求文档正文里包含"中文"这个词。

验证

场景	查询	预期行为
短语顺序	“Java 内存模型”	只命中三词相邻出现的文档
短语不匹配	“模型 内存 Java”	顺序不对，不命中
括号	(java OR python) AND 内存	先做 OR 再做 AND
NOT	java AND NOT python	排除包含 python 的文档
非法语法	AND java、空字符串	降级或返回空，不崩溃
过滤	search(“java”) + lang=zh	只返回中文文档
过滤 + 布尔	“java AND 内存” + lang=zh	布尔和过滤独立生效

当前局限

• 没有评分——匹配的文档按 docId 返回，不按相关性排序
• 短语查询不支持 slop（允许词项之间有间隔）
• NOT 单独使用返回几乎所有文档，需要限制使用方式
• 查询语法是自定义的，不兼容 Lucene 查询语法——第 15 篇迁移时对齐

练习

1. 构造两篇文档：一篇包含 “Java 内存模型”（连续出现），另一篇分别在不同段落包含 “Java”、“内存”、“模型”。验证短语查询只命中第一篇
2. 实现 slop 参数："Java 内存模型"~2 允许词项之间最多插入 2 个其他词项
3. 构造一个触发运算符优先级差异的查询：a OR b AND c，验证结果等于 a OR (b AND c) 而不是 (a OR b) AND c
4. 在过滤器中加入日期范围过滤，验证结合布尔查询的正确性

延伸阅读

• Introduction to Information Retrieval, Chapter 2.4: Positional postings and phrase queries
• Introduction to Information Retrieval, Chapter 1.3: Processing Boolean queries
• Lucene 源码：org.apache.lucene.search.PhraseQuery