4. 倒排索引与TF-IDF核心原理
倒排索引与TF-IDF是搜索算法的基石，面试中高频考察构建流程、查询处理、公式推导及BM25变种对比。掌握本讲内容，可应对90%的搜索算法初面问题。
TF-IDF 与 BM25 核心对比
| 维度 | TF-IDF | BM25 |
|---|---|---|
| 公式 | TF·log(N/DF) | ∑ log(N/DF)·(k₁+1)TF/(k₁·(1-b+b·dl/avgdl)+TF) |
| 词频饱和 | 线性增长，无上限 | 非线性，通过 k₁ 控制饱和速度 |
| 文档长度归一化 | 无 | 通过 b 和文档长度比实现 |
| IDF 平滑 | 原始 IDF（可能出现负值） | 改进 IDF 公式，避免负值 |
| 可调参数 | 无 | k₁∈[1.2,2.0]，b∈[0.75,0.8] |
📝 面试问答1：倒排索引构建与查询处理
- 面试问题
- 请详细说明倒排索引的构建过程，并描述一次查询从输入到结果返回的完整处理流程。
- 面试官考察点
-
- 是否理解词典（Term Dictionary）与倒排列表（Posting List）的分层结构
- 是否考虑压缩（如Frame of Reference）和跳表优化
- 是否具备工程化视角（内存/磁盘、增量更新）
- 回答框架
-
- 阶段一：文档预处理（分词、去停用词、词干还原）
- 阶段二：构建Term -> (DocID, TF, Position) 倒排表
- 阶段三：查询时，分词后对每个term检索倒排列表，取交集/并集
- 阶段四：按TF-IDF/BM25打分排序，返回TopK
- 示例回答
- （约80字）倒排索引构建分三步：文档预处理（分词、去停用词）、生成（Term→DocID+TF+Position）映射、合并排序并写入磁盘。查询时解析用户query，对每个term拉取倒排列表，通过跳表求交集，最后BM25打分排序返回TopK。
- 可能追问
- 如何优化大文档集的索引更新（增量 vs 全量）？
- 如何压缩倒排列表降低存储？
- 怎么处理查询时的高并发？
- 避坑提醒
- 不要遗漏查询阶段的打分排序、不要忘记提及跳表或位图优化、避免仅口述理论而无工程细节。
📝 面试问答2：TF-IDF公式推导与缺陷
- 面试问题
- 请写出TF-IDF公式，并推导其合理性。你认为它有哪些主要缺点？
- 面试官考察点
-
- 能否清晰写出数学表达式并解释每个符号含义
- 是否理解IDF的“信息量”含义
- 能否主动指出线性TF、文档长度差异、罕见词权重爆炸等问题
- 回答框架
-
- 公式：TF-IDF = TF(t,d) × IDF(t) = f(t,d)/max(f) × log(N/df(t))
- 合理性：TF越大词越重要，IDF惩罚高频词、提升稀有词区分度
- 缺点：TF无饱和上限，长文档易受堆砌；IDF未平滑时可能出现负值；未考虑文档长度差异
- 示例回答
- （约80字）TF-IDF = TF×IDF，其中TF=词频/文档总词数（或log归一化），IDF=log(文档总数/包含该词的文档数)。缺陷有三：TF线性增长导致关键词在长文档中虚高；IDF对罕见词降权不足；完全忽略文档长度归一化。
- 可能追问
- 如何改进IDF？举例说明。
- 谈谈BM25如何解决TF饱和问题？
- 给出一个实际场景中TF-IDF失效的例子。
- 避坑提醒
- 不要只背公式而不讲物理意义；避免说IDF使用log(1+N/df)是唯一平滑方式，面试官期待你比较不同平滑策略。
📝 面试问答3：BM25变种与参数调优
- 面试问题
- BM25相比TF-IDF有哪些具体改进？请写出BM25公式并解释k₁、b参数的物理含义。你还知道哪些BM25改进变种？
- 面试官考察点
-
- 是否深入理解BM25中的词频饱和度、文档长度归一化
- 对参数调优经验（默认值、场景差异）
- 对学术界最新变种（如BM25F、BM25+等）的知晓度
- 回答框架
-
- 改进点：TF饱和、文档长度归一化、IDF平滑
- 公式：Score=D∑log(N/df)·(k₁+1)TF/(k₁(1-b+b·dl/avgdl)+TF)
- k₁控制TF饱和速度（通常1.2–2.0），b控制长度归一化程度（0–1，常用0.75）
- 变种：BM25F（多域加权）、BM25+（改进短文档）、BM25-adpt（自适应参数）
- 示例回答
- （约100字）BM25在TF-IDF基础上引入k₁和b：k₁越大TF饱和越晚，适用于长文本搜索；b越大文档长度惩罚越强。典型默认k₁=1.2、b=0.75。变种如BM25F支持多字段权重，BM25+通过固定+1项避免短文档得分过低。
- 可能追问
- 如何为不同业务（如新闻搜索 vs 问答匹配）选择k₁和b？
- BM25的TF饱和函数为什么用分数形式而不是log？
- 描述BM25F的多域权重分配策略。
- 避坑提醒
- 不要只罗列公式而不讲直觉解释；避免回答“参数随意设置”，应说出面向场景的调参思路（短文本b接近0，长文本b接近1）。