第3章 搜索引擎核心技术：倒排索引原理与优化、分词算法、排序策略
本章聚焦搜索引擎三大核心支柱：倒排索引的构建与调优、分词算法选型与效果评估、排序策略的数学模型与工程实现。掌握这些内容是面试搜索引擎研发岗位的基础门槛。
📌 核心流程步骤：倒排索引构建与查询通常遵循以下6步：
- 文档预处理：分词、去停用词、提取词干，生成词项序列。
- 倒排表构建：以词项为key，收集文档ID与词频信息，形成有序链表。
- 压缩存储：对倒排列表采用VByte、Simple9等编码减少磁盘占用。
- 查询词项定位：通过词典（哈希/B树）找到对应倒排列表起始位置。
- 文档ID归并：多词项查询时通过跳表或指针归并求交集/并集。
- 排序返回：结合BM25等模型计算分数，截断Top-K返回。
🎯 面试问答1
面试问题：请解释倒排索引的原理及其构建过程。
面试官考察点：
- 是否理解词项 → 文档ID映射的核心思想
- 是否清楚构建全流程（分词、去重、排序）
- 能否区分正排索引与倒排索引
回答框架：
- 定义：倒排索引以词项为键，文档ID列表为值
- 构建步骤：先对文档分词、去停用词、词干化 → 建立<词项, docID+词频>映射 → 按docID排序 → 写入磁盘
- 查询时：通过词典定位词项，获取倒排列表，多词项进行合并
简短示例回答：倒排索引将每个词项映射到包含它的文档ID列表。构建时先对文档分词并去除停用词，再对每个词项收集docID与词频，最后按docID排序形成有序链表。查询时通过词典找到对应链表，并利用跳表快速合并多个词项的结果。
可能追问：如何处理短语查询？答：在倒排列表中同时存储位置信息，用位置差值判断相邻关系。
⚠ 避坑提醒：不要混淆“正排索引（文档→词项）”与“倒排索引（词项→文档）”。面试中常有人将两者说反。回答时先明确方向。
🎯 面试问答2
面试问题：倒排索引有哪些常见的优化策略？
面试官考察点：
- 是否了解工业级高性能索引的工程手段
- 能否结合数据分布和查询模式给出方案
回答框架：
- 压缩：VByte、PForDelta、Roaring Bitmap 降低存储与IO
- 加速：跳表（skip list）加速合并；对高频词缓存整个倒排列表
- 分片：按文档ID范围分片，支持并行查询
- 索引分层：短期新数据单独索引，定期合并
简短示例回答：针对存储，采用VByte编码压缩倒排列表，减少磁盘占用与读取量；针对查询，为每个倒排列表建立跳表，使合并复杂度从O(m+n)降至O(log m + log n)；同时热词倒排列表常驻内存缓存。
可能追问：VByte与Simple9的适用场景区别？答：VByte变长编码适合差值分布不均，Simple9定长编码在均匀分布下压缩率更高。
⚠ 避坑提醒：不要只堆名词（“用字典压缩”），要说明具体算法和原因。例如“VByte通过高位表示是否结束，对差值小的数字更友好”。
🎯 面试问答3
面试问题：搜索引擎中的排序策略（如BM25）是如何工作的？
面试官考察点：
- 是否理解BM25的数学原理与超参数含义
- 能否对比TF-IDF优劣
回答框架：
- BM25基于概率检索模型，公式包含：IDF（逆文档频率）、TF（词频饱和）、文档长度归一化
- 超参数k1控制词频饱和度，b控制长度惩罚力度
- 与TF-IDF相比，BM25对高频词有衰减，对长文档更公平
简短示例回答：BM25得分 = IDF(q) × [TF(q,d)×(k1+1)] / [TF(q,d)+k1×(1-b+b×(dl/avgdl))]。其中IDF减少常见词影响，k1使多次出现仍有收益但不无限增长，b让长文档不过度累积分数。
可能追问：b值为何一般设为0.75？答：经验值，使长度惩罚适中，可根据实际数据微调。
⚠ 避坑提醒：很多面试者只背公式，忽略“为什么k1>0”和“长度惩罚的意义”。要强调BM25解决了TF-IDF中无限叠加词频的缺陷。
📊 补充：常见中文分词算法对比
| 算法类型 | 原理简述 | 优点 | 缺点 |
|---|---|---|---|
| 基于词典 （正向最大匹配） |
从左到右匹配词典中最长词 | 速度快，实现简单 | 未登录词、歧义处理差 |
| 基于统计 （HMM/CRF） |
利用标注序列模型切分 | 识别新词，歧义好 | 需要标注数据训练 |
| 基于深度学习 （BERT分词） |
预训练模型 + 字标注 | 语义理解强，准确率高 | 推理慢，计算资源大 |
💡 面试提示：搜索引擎通常采用词典+统计结合的混合分词方案，兼顾速度与准确率。提到“双数组Trie”作为词典结构是加分项。