守株阁

搜索引擎返回了 Top-10 结果，每条是一个 docID 和 BM25 分数。用户看到的却不应该是 doc#4237, score=2.091。用户需要标题、URL、一段能说明"为什么这条结果和查询相关"的摘要，以及查询词在摘要中的高亮。 本篇在搜索结果之上补齐四项能力：查询相关摘要、关键词高亮、HTML 转义（防止 XSS）、以及翻页。 存储字段 倒排索引不存原文 倒排索引记录的是"词项 → 文档列表"，查询时能找到匹配的 docID 和词频，但无法还原文档原文。摘要和高亮需要原文。 两种方案： 存储字段（Stored Fields）：索引时把需要展示的字段（标题、URL、正文）存入独立的正向存储。按 docID 随机访问。 外部存储：把原文放在数据库或文件系统中，用 docID 查询时回查。 教学实现用存储字段——把标题、URL、正文摘要在索引时写入一个按 docID 排列的文件，查询时按 offset 定位。 1234567891011121314151617181920212223242526record StoredDoc...

前面十一篇建立的索引有一个隐含假设：文档集合是静态的。建完索引就不变了。但实际场景中，文档会增加、修改、删除。一篇文档改了标题，搜索结果应该反映新标题；一篇文档被删除，搜索不应该返回它。 在倒排索引上直接修改代价很高——删除一篇文档意味着遍历它包含的每个词项的 posting list，逐一移除对应的 docID。10,000 篇文档的索引里删除一篇，可能要修改上千个 posting list。 本篇解决三个问题：怎样标记删除、怎样安全地提交新版本索引、怎样在崩溃后恢复到一致状态。 标记删除：Tombstone 不直接修改 Posting List 直接从 posting list 中移除 docID 需要： 找到该文档包含的所有词项（需要正向索引或重新分析文档） 在每个词项的 posting list 中定位并删除对应 docID 如果 posting list 用了 delta 编码，删除一个元素需要重新编码后续所有 gap 这个操作的代价与文档包含的词项数成正比——对一篇包含 1,500 个不同词项的文档，要修改 1,500 个 posting list。如果频繁删除...

上一篇把索引从内存搬到了磁盘。现在对一个两词查询 “Java GC”，BM25 需要遍历两个词项的全部 posting list、对每个候选文档计算精确分数、维护 Top-K 堆。“Java” 的 posting list 有 5,000 条，“GC” 有 800 条——OR 查询的候选集最多 5,800 个文档，每个都要算一次 BM25。 但用户只看前 10 条结果。为了找到 Top-10，穷举 5,800 个文档是否必要？ 答案是不必要。如果已经找到了分数很高的 10 篇文档，后面的文档只要能证明"它不可能比当前第 10 名更高"，就可以直接跳过。这就是查询剪枝的核心思路。 穷举的成本 穷举 Top-K 流程回顾 第 09 篇的 Top-K 算法对所有候选文档计算 BM25： 1234567for (int docId : candidateDocs) { double score = bm25(queryTerms, docId); if (heap.size() < k || score > heap.peek()....

前面九篇的倒排索引和 BM25 有一个隐含假设：所有文档在内存里放得下。50 篇文档确实没问题。但把数据集扩展到 10,000 篇、每篇平均 2,000 词时，仅 (词项, docID) 对就可能有几千万条，单次排序的内存需求轻松超过 JVM 默认堆。 这不是"用更大的机器"就能解决的问题。即使加到 32 GB 内存，真实语料还是可能更大。需要一种策略：把内存装不下的数据分批处理，每一批写成磁盘上的段文件（segment），最后把所有段合并成完整索引。 分批建立索引 朴素方案的瓶颈 第 07 篇的索引构建把所有文档一次性塞进 HashMap： 123456Map<String, List<Integer>> index = new HashMap<>();for (Document doc : allDocs) { for (String term : analyze(doc.content())) { index.computeIfAbsent(term, k -> new ...

前面的章节用布尔查询找到匹配的文档，但所有结果按 docId 返回——排在前面的不是最相关的文档，只是最先被索引的文档。搜索 “Java 垃圾回收” 时，一篇通篇讲 GC 调优的文章应该排在只在页脚提了一句 “Java” 的文章前面。 评分排序需要量化"相关性"。BM25（Best Matching 25）是目前最广泛使用的词法检索评分函数，Lucene、Elasticsearch、Solr 的默认评分都基于 BM25。它的输入只有三样：词频、文档长度和文档频率——全部可以从倒排索引中直接获取。 从 TF 到 TF-IDF 词频（Term Frequency） 直觉上，一个词在文档中出现次数越多，这篇文档与该词越相关。这就是词频（TF）。 但原始词频有问题：一个词出现 10 次不意味着相关性是出现 1 次的 10 倍。从 1 次到 2 次的信息增益远大于从 9 次到 10 次。对数平滑是常见处理： 12tf_log(t, d) = 1 + ln(tf(t, d)) 如果 tf > 0 = 0 ...

上一篇的倒排索引只支持单词查询和最基本的 AND/OR。搜索 “Java 内存模型” 时，AND 查询能找到同时包含 “java”、“内存”、“模型” 三个词的文档，但也会命中一篇标题是"Java 并发编程"、正文某处提到"内存不足"、另一处提到"设计模型"的文档——三个词散布在不同段落，根本不是"Java 内存模型"这个概念。 短语查询（phrase query）要求词项不仅共现，还必须按指定顺序出现在相邻位置。这需要用到第 06 篇记录的 position 信息。 本篇在倒排索引上增加三项能力：短语查询、带优先级的布尔查询语法、以及字段过滤。 短语查询：Positional Intersection 核心思路 短语 “Java 内存模型” 经过分析器产出三个词项，position 分别为 0、1、2。在目标文档中，这三个词项也必须出现在连续的 position 上（允许 position 差恰好等于词项在查询中的间距）。 算法分两步： 对短语中所有词项的倒排列表做 AND（交集），找到同时包含...

上一篇把文本切成了词项流。但词项流只是一个线性序列——要回答"哪些文档包含’Java’"这个问题，仍然需要扫描所有文档的词项流。1000 篇文档还能忍受，10 万篇就不行了。 倒排索引（inverted index）把"文档包含哪些词"的关系翻转成"每个词出现在哪些文档中"。查询时只需要查一次词典，就能拿到所有包含该词的文档列表，不需要扫描任何一篇文档的全文。 从正排到倒排 正排索引（forward index）是文档到词项的映射： 123doc1 → [java, 内存, 模型, gc, 调优]doc2 → [java, 线程, 池, 并发]doc3 → [python, 内存, 管理] 查询 “java” 需要扫描全部 3 篇文档。 倒排索引把方向翻转： 12345678910java → [doc1, doc2]内存 → [doc1, doc3]模型 → [doc1]gc → [doc1]调优 → [doc1]线程 → [doc2]池 → [doc2]并发 → [doc2]...

前五篇完成了文档的采集、导入和评测基线。文档以纯文本的形式进入系统，但搜索是以词为单位进行的——查询 “Java 内存模型” 需要把这五个字拆成能和索引匹配的词项。英文有空格做天然分隔，中文没有；版本号 3.14.1 不应该在小数点处断开；NullPointerException 既需要保留完整形式也需要拆成子词。 本篇设计一个分析器（Analyzer），将原始文本转换为可索引的词项流，记录每个词项的位置和偏移量。 分析器的三阶段模型 文本分析拆成三步： 1原始文本 → Tokenizer → Token Filter → 词项流（Term Stream） Tokenizer 把连续文本切成一个个 token。Token Filter 对 token 做后处理：小写化、停用词移除、同义词展开。每个 token 携带四项信息： 123456public record Token( String term, // 词项文本 int position, // 在词项流中的序号（0-based） int startOffset, // 在原始...

上一篇实现的爬虫能够抓回 HTML 页面，但抓回来的原始 HTML 里充满了导航栏、侧边栏、页脚、广告和脚本标签。把这些噪声和正文一起送入索引，搜索"Java 内存模型"可能命中一堆导航菜单里的"Java"字样。 本篇解决三个问题：从 HTML 中提取干净的正文，将 URL 统一为规范形式以避免同一页面被当作不同文档，以及识别内容相同或高度相似的页面以避免重复索引。 从 HTML 到正文 噪声标签移除 HTML 页面中不是所有标签都承载正文内容。<nav>、<header>、<footer>、<aside>、<script>、<style> 以及带有常见 CSS 类名（.sidebar、.menu、.ad）的元素通常是噪声。jsoup 的选择器可以一次性移除： 123456Document doc = Jsoup.parse(html);doc.select( "nav, header, footer, aside, script, style, &q...

前三篇建立了文档导入和评测基线，数据来源是本地 fixture 文件。真实搜索引擎的数据来自网页。抓取网页看起来只是发 HTTP 请求再解析 HTML，但如果不加约束，爬虫会在几分钟内失控——压垮目标站点、陷入无限循环、抓回内网敏感数据，或在中断后丢失全部进度。 本篇的目标：写一个有明确边界的爬虫，能从种子 URL 出发，按广度优先发现页面，遵守 robots.txt，控制并发和重试，拒绝危险地址，并在中断后恢复。 边界从哪里来 "有边界"在爬虫语境下指四类约束： 抓取范围：只抓白名单内的域名。种子 URL 页面上提取的链接如果指向其他站点，直接丢弃。URL 深度设上限（例如 5 层），防止动态生成的无限路径耗尽队列。 礼貌约束：同一站点的请求间隔不低于 1 秒，同站并发不超过 2 个连接。robots.txt 声明的 Crawl-delay 优先于默认值。全局并发受线程池限制。 资源约束：单个响应体不超过 5 MB，连接超时 10 秒，读取超时 30 秒，单个 URL 最多重试 3 次。整个爬取任务可以设总页面数上限。 安全约束：在发起 HTTP 请求之前...