倒排索引与分词算法：索引构建、词典优化、中文分词难点
本章是搜索算法工程师面试的核心关卡。面试官通过倒排索引与中文分词，考察你对搜索引擎底层架构的理解深度、工程优化能力以及处理中文自然语言的特有坑点。掌握以下内容，可应对大厂80%的相关问题。
面试策略：先讲原理（倒排结构 & TF-IDF），再讲构建细节（全量/增量），最后落地时遇到的词典瓶颈与中文歧义——层层递进最拿分。
面试问答卡片
问题1：请简述倒排索引的原理及其构建步骤
面试官考察点：基本概念理解 + 有无实际构建经验（全量/增量/合并）
回答框架：定义→结构（词典+倒排表）→构建三步（分词→排序/去重→写盘）→更新策略（全量 rebuild / 增量 merge）。
简短示例回答：倒排索引是“词→文档ID”的映射。构建时先对文档分词得到 term，再排序去重生成词典，最后将每个 term 对应的 docid 列表写入倒排文件。更新时采用全量重建或分段合并（如 lucene 的段合并策略）。
可能追问：跳表对倒排表有什么用？如何压缩倒排列表（Frame of Reference / 差分编码）？
避坑提醒：别只背概念，要提到工程细节（如内存不足时如何分段写磁盘、合并时的 IO 优化）。
问题2：倒排索引的词典如何优化？常用数据结构有哪些？
面试官考察点：对内存/查询速度的平衡理解，是否了解 Trie、FST、Hash 的优缺点
回答框架：内存优先选 Hash → 前缀查询选 Trie → 存储与查询均衡选 FST → 前缀排序用 B+ Tree。
简短示例回答：词典需支持快速判断 term 是否存在。Hash 最快但无法前缀搜索；Trie 支持前缀但内存较大；FST（有限状态转换器）通过共享前缀压缩存储，比 Trie 省 5-10 倍空间，lucene 使用 FST。B+ Tree 适合磁盘场景。
可能追问：FST 如何构建？能否做到实时更新？Trie 的内存优化方案（双数组 Trie）？
避坑提醒：不要只说一种结构，要对比场景；提到实际项目中选择 FST 的原因（内存<2G时效果最好）。
问题3：中文分词相比英文分词的难点是什么？如何解决？
面试官考察点：对自然语言处理基本难题的认知 + 工程落地方案
回答框架：三大难点（歧义切分、未登录词、分词粒度）→ 解决方法（词典+统计+ML）。
简短示例回答：难点在于歧义（如“南京市长江大桥”）、未登录词（新词/人名）和粒度需求。通常用词典匹配结合 HMM/CRF，线上用 DAG + 动态规划求最大概率路径；未登录词可加用户词典或利用字节对编码（BPE）。
可能追问：如何评估分词质量（P/R/F1）？增量更新用户词典时是否需重建索引？
避坑提醒：一定要区分“分词”和“标注”的不同；不要漏掉工程上的性能优化（如缓存常用分词结果）。
项目案例模板：电商商品搜索倒排索引优化
| 项目名称 | 商品标题实时搜索倒排索引系统 |
| 业务背景 | 电商站内搜索，每天亿级搜索量，要求<200ms响应，支持中文模糊匹配和同义词扩展 |
| 规模指标 | 商品数 3000 万，索引词典规模 500 万 term，日增量 5 万商品 |
| 技术栈 | Lucene + 自研 FST 词典 + IK 分词器 + Redis 缓存 + Kafka 增量流 |
| 核心难点 | ①中文标题分词歧义多，导致召回缺失；②词典加载占内存（原始 FST 过 2G），需压缩；③频繁增量更新时索引合并影响写入性能 |
| 面试高频追问 | FST 内存占用怎么从 2G 降到 800M？增量 merge 时如何保证搜索可用？同义词如何管理与扩展？ |
| 可迁移回答话术 | “我们采用分层词典+双数组 Trie 压缩前缀，将内存降低 60%；增量段使用写时复制+后台合并，保证查询不被锁卡住；分词方面自定义用户词典覆盖行业词，并加入最小切分算法缓解歧义。” |
💡 迁移技巧：当你被问到“倒排索引在实际项目中的挑战”时，直接套用以上案例结构——先说明业务规模，再列举一个具体难点，最后给出量化改进——这是大厂面试官最喜欢的回答模式。