用户在搜索框里输入的查询经常不是最理想的检索条件：拼错了字、只打了半个词、用了口语化的说法。前一篇优化了分词和字段权重，本篇在查询到达索引之前对它做预处理——拼写纠错、前缀补全、查询改写——再加入一个与查询无关的信号：链接结构。

前缀补全

问题

用户在搜索框中输入 “java 内” 时，如果等到用户按下回车才开始搜索，就错过了一个引导用户的机会。前缀补全在用户还在打字时就列出可能的完整查询，减少输入量，同时引导用户使用索引中实际存在的词汇。

Trie 实现

最基础的前缀补全用 Trie（前缀树）：

class TrieNode {
    final Map<Character, TrieNode> children = new HashMap<>();
    boolean isTerminal;
    int frequency;
    String term;
}

class PrefixSuggester {
    private final TrieNode root = new TrieNode();

    void insert(String term, int frequency) {
        TrieNode node = root;
        for (char c : term.toCharArray()) {
            node = node.children.computeIfAbsent(c, k -> new TrieNode());
        }
        node.isTerminal = true;
        node.frequency = frequency;
        node.term = term;
    }

    List<String> suggest(String prefix, int limit) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return List.of();
        }
        PriorityQueue<TrieNode> heap = new PriorityQueue<>(
            Comparator.comparingInt(n -> n.frequency));
        collectTerminals(node, heap, limit);
        return heap.stream()
            .sorted(Comparator.comparingInt((TrieNode n) -> n.frequency).reversed())
            .map(n -> n.term)
            .toList();
    }

    private void collectTerminals(TrieNode node, PriorityQueue<TrieNode> heap, int limit) {
        if (node.isTerminal) {
            heap.offer(node);
            if (heap.size() > limit) heap.poll();
        }
        for (TrieNode child : node.children.values()) {
            collectTerminals(child, heap, limit);
        }
    }
}

构建 Trie 的数据来源：索引中所有 term 的文档频率，或者文档标题。标题比 term 更适合作为补全候选——用户搜索框中看到的应该是有意义的短语，不是被分词器拆开的单个 token。

从标题构建补全索引

void buildSuggestionIndex(IndexReader reader) {
    StoredFields storedFields = reader.storedFields();
    for (int i = 0; i < reader.maxDoc(); i++) {
        Document doc = storedFields.document(i);
        String title = doc.get("title");
        if (title != null) {
            suggester.insert(title.toLowerCase(), 1);
            String[] words = title.split("\\s+");
            for (int j = 0; j < words.length; j++) {
                String suffix = String.join(" ",
                    Arrays.copyOfRange(words, j, words.length));
                suggester.insert(suffix.toLowerCase(), 1);
            }
        }
    }
}

Trie 的局限与 Lucene suggest 模块

Trie 的问题：

问题	影响
内存占用	每个字符一个节点，中文 Trie 非常宽（数千子节点）
无模糊匹配	用户拼错一个字就找不到候选
无权重衰减	所有 term 权重固定，不能反映时效性

Lucene 的 suggest 模块用 FST（有限状态转换器）替代 Trie：

AnalyzingInfixSuggester suggester = new AnalyzingInfixSuggester(
    FSDirectory.open(suggestPath), analyzer);

InputIterator inputIterator = new DocumentTitleIterator(reader);
suggester.build(inputIterator);

List<Lookup.LookupResult> results = suggester.lookup(prefix, 10, true, false);

AnalyzingInfixSuggester 支持中缀匹配——输入 “检索” 可以匹配 “信息检索原理”。FST 的内存效率远高于 Trie。

教学场景先用 Trie 理解原理，再切换到 Lucene suggest 验证效果差异。

拼写纠错

编辑距离

两个字符串之间的编辑距离（Levenshtein distance）是将一个字符串变成另一个所需的最少单字符操作数（插入、删除、替换）。

1	`"serach" → "search" 编辑距离 = 1（交换 ra → ar 需要 2 步，但 serach→search 只需替换一个字符位置）`

动态规划求解：

int editDistance(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a.charAt(i-1) == b.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i-1][j-1],
                    Math.min(dp[i-1][j], dp[i][j-1]));
            }
        }
    }
    return dp[m][n];
}

候选生成

对用户输入的每个 token，在索引词典中找编辑距离 ≤ 2 的所有 term：

List<String> spellCandidates(String token, int maxDistance) {
    List<String> candidates = new ArrayList<>();
    Terms terms = reader.terms("body");
    TermsEnum termsEnum = terms.iterator();
    BytesRef term;
    while ((term = termsEnum.next()) != null) {
        String termStr = term.utf8ToString();
        if (editDistance(token, termStr) <= maxDistance) {
            candidates.add(termStr);
        }
    }
    candidates.sort(Comparator.comparingInt(c -> editDistance(token, c)));
    return candidates;
}

暴力遍历所有 term 太慢。优化方案：

长度过滤：编辑距离 ≤ k 的两个字符串长度差 ≤ k
前缀过滤：共享前缀越长，编辑距离越小
Lucene DirectSpellChecker：利用 term 词典的 FST 结构剪枝

DirectSpellChecker spellChecker = new DirectSpellChecker();
spellChecker.setMaxEdits(2);
spellChecker.setMinPrefix(1);

SuggestWord[] suggestions = spellChecker.suggestSimilar(
    new Term("body", misspelledToken), 5, reader);

“Did you mean” 逻辑

不是每次都纠错——只在原始查询结果太少时才提示：

SearchResult searchWithSpellCheck(String query, int page, int size) {
    SearchResult result = search(query, page, size, null);

    if (result.totalHits() < 3) {
        String corrected = correctQuery(query);
        if (corrected != null && !corrected.equals(query)) {
            SearchResult correctedResult = search(corrected, page, size, null);
            if (correctedResult.totalHits() > result.totalHits()) {
                correctedResult.setSuggestion("您是不是要搜索：" + corrected);
                return correctedResult;
            }
        }
    }
    return result;
}

阈值 3 是经验值：少于 3 条结果时用户很可能拼错了或用了非标准说法。

中文拼写纠错

中文没有字母级编辑距离。两种替代方案：

拼音编辑距离：将中文转为拼音后计算编辑距离。“信息检索” → “xinxi jiansuo”。用户可能输入 “信息捡索”（"捡"和"检"同音），拼音距离为 0。
同音字/形近字替换表：预定义常见的混淆对。

教学场景简化处理：中文 term 只做前缀补全，不做编辑距离纠错。英文 term 用标准编辑距离。

查询改写

停用词处理

中文查询中常带有"的"、“了”、“是”、"在"等功能词。它们在几乎所有文档中都出现，对检索没有区分度，反而会拉低有意义 term 的权重。

Set<String> STOP_WORDS = Set.of("的", "了", "是", "在", "和", "与", "及",
    "将", "对", "中", "为", "这", "那", "有", "不", "也", "都", "就",
    "the", "a", "an", "is", "are", "was", "were", "in", "on", "at",
    "to", "for", "of", "with", "by");

String removeStopWords(String query) {
    return Arrays.stream(query.split("\\s+"))
        .filter(w -> !STOP_WORDS.contains(w.toLowerCase()))
        .collect(Collectors.joining(" "));
}

Lucene 分析器链中也可以加入 StopFilter 实现同样的效果。区别在于：查询改写阶段去停用词可以在用户界面展示改写后的查询；分析器层面去停用词对用户不可见。

查询松弛

当原始查询返回零结果时，逐步放松条件：

SearchResult searchWithRelaxation(String query, int page, int size) {
    SearchResult result = search(query, page, size, null);
    if (result.totalHits() > 0) return result;

    String relaxed = removeStopWords(query);
    if (!relaxed.equals(query)) {
        result = search(relaxed, page, size, null);
        if (result.totalHits() > 0) {
            result.setNote("已忽略部分常见词");
            return result;
        }
    }

    String noPhrase = query.replace("\"", "");
    if (!noPhrase.equals(query)) {
        result = search(noPhrase, page, size, null);
        if (result.totalHits() > 0) {
            result.setNote("已取消短语限制");
            return result;
        }
    }

    return result;
}

改写候选限制

每个查询最多生成 3 个改写变体。理由：

过多变体会召回大量噪声文档
用户无法理解搜索引擎为什么返回了看似无关的结果
改写应该是对用户意图的合理猜测，不是暴力扩展

链接质量信号：PageRank

从链接图提取结构

第 04-05 篇爬取的网页中包含 <a href> 链接。这些链接构成一个有向图：页面 A 链接到页面 B 表示 A 的作者认为 B 有参考价值。

class LinkGraph {
    private final Map<String, Integer> urlToId = new HashMap<>();
    private final List<String> idToUrl = new ArrayList<>();
    private final List<List<Integer>> outLinks = new ArrayList<>();
    private final List<List<Integer>> inLinks = new ArrayList<>();

    int addUrl(String url) {
        return urlToId.computeIfAbsent(url, u -> {
            int id = idToUrl.size();
            idToUrl.add(u);
            outLinks.add(new ArrayList<>());
            inLinks.add(new ArrayList<>());
            return id;
        });
    }

    void addLink(String from, String to) {
        int fromId = addUrl(from);
        int toId = addUrl(to);
        outLinks.get(fromId).add(toId);
        inLinks.get(toId).add(fromId);
    }
}

PageRank 算法

核心公式：

1	`PR(i) = (1-d)/N + d × Σ_{j→i} PR(j)/OutDegree(j)`

d = 0.85 是标准阻尼因子。含义：用户有 85% 的概率沿着链接继续浏览，15% 的概率跳到随机页面。

幂迭代实现：

double[] computePageRank(LinkGraph graph, double d, double epsilon, int maxIter) {
    int N = graph.size();
    double[] pr = new double[N];
    double[] next = new double[N];
    Arrays.fill(pr, 1.0 / N);

    for (int iter = 0; iter < maxIter; iter++) {
        double danglingSum = 0;
        for (int j = 0; j < N; j++) {
            if (graph.outDegree(j) == 0) {
                danglingSum += pr[j];
            }
        }

        for (int i = 0; i < N; i++) {
            next[i] = (1 - d) / N + d * danglingSum / N;
            for (int j : graph.inLinks(i)) {
                next[i] += d * pr[j] / graph.outDegree(j);
            }
        }

        double diff = 0;
        for (int i = 0; i < N; i++) {
            diff += Math.abs(next[i] - pr[i]);
        }

        double[] temp = pr;
        pr = next;
        next = temp;

        if (diff < epsilon) {
            break;
        }
    }
    return pr;
}

Dangling nodes

没有出链的页面（如 PDF、图片页面）会让 PageRank 质量"泄漏"。上面的实现将 dangling node 的 PR 均匀分配给所有页面——等价于这些页面链接到所有页面。

收敛性

幂迭代在 Web 规模的图上通常 50-100 次迭代收敛。教学语料的小图（数百到数千节点）10-20 次就够了。

将 PageRank 融入搜索评分

方案比较

方案	公式	优点	缺点
线性加权	`α × BM25 + β × log(PR)`	简单	BM25 和 PR 量纲不同，α/β 难调
乘性融合	`BM25 × (1 + γ × log(PR))`	PR 只做微调	γ 敏感
Lucene FeatureField	索引时存储静态分数，查询时用 FeatureQuery boost	与 Lucene 评分框架集成	需要额外字段

教学场景用 Lucene 的 FeatureField：

// 索引时
document.add(new FeatureField("features", "pagerank", (float) pageRankScore));

// 查询时
Query textQuery = buildTextQuery(queryStr);
Query prBoost = FeatureField.newLogQuery("features", "pagerank", 1.0f, 1.0f);

BooleanQuery finalQuery = new BooleanQuery.Builder()
    .add(textQuery, BooleanClause.Occur.MUST)
    .add(prBoost, BooleanClause.Occur.SHOULD)
    .build();

FeatureField.newLogQuery 对 PageRank 取对数后作为 boost 加入总分。对数压缩了 PageRank 的跨度——最高和最低 PR 的页面之间可能差几个数量级，直接用原始值会让 PR 完全主导评分。

改善与误伤分析

在开发集上比较加入 PageRank 前后的结果：

void analyzePageRankImpact(QuerySet devSet) {
    for (AnnotatedQuery q : devSet.queries()) {
        List<String> beforeTop5 = searchTop5(q.text(), false);
        List<String> afterTop5 = searchTop5(q.text(), true);

        if (!beforeTop5.equals(afterTop5)) {
            double beforeNdcg = computeNdcg(beforeTop5, q.relevance(), 10);
            double afterNdcg = computeNdcg(afterTop5, q.relevance(), 10);

            String verdict = afterNdcg > beforeNdcg ? "改善" :
                           afterNdcg < beforeNdcg ? "误伤" : "持平";
            System.out.printf("%s: '%s' nDCG %.4f → %.4f\n",
                verdict, q.text(), beforeNdcg, afterNdcg);
        }
    }
}

预期结果：

改善案例：权威页面（被多个页面链接）在多个相关文档竞争时排名提升
误伤案例：内容高度相关但链接数少的页面（如新发布的文章）被链接数多但内容一般的页面挤掉
教学语料的链接图可能很稀疏，PageRank 的区分度可能不明显

验证

场景	操作	预期
前缀补全	输入 “java 内”	返回含 “java 内存” 的候选
拼写纠错	搜索 “serach engine”	提示 “您是不是要搜索：search engine”
零结果松弛	搜索 “高性能的并发框架”	去停用词后搜索，返回并发相关结果
PageRank 生效	搜索通用概念	被广泛链接的页面排名靠前
无点击数据	所有功能	全部可复现，不依赖用户行为数据
改写限制	任何查询	最多 3 个改写变体

当前局限

前缀补全没有个性化——所有用户看到相同的候选
拼写纠错只处理英文 term，中文依赖拼音方案（本篇未实现）
查询改写是基于规则的，没有学习机制
PageRank 在小链接图上的区分度有限
没有点击数据做反馈——生产搜索引擎最重要的信号恰恰是点击

练习

用索引中所有标题构建 Trie，输入 5 个前缀测试补全结果
对 “javaa”、“seach”、“indx” 三个拼错词生成纠错候选
从爬取的网页中提取链接图，运行 PageRank 至收敛，打印 Top-10 页面
比较加入 PageRank 前后开发集上 5 个查询的排序变化
构造一个查询改写反而有害的案例，记录原因

从零构建现代搜索引擎（17）：查询理解与链接质量信号