Sparse Retrieval (BM25 / TF-IDF): 解释倒排索引的结构与查询流程。

Core Concept: 倒排索引是'词 → 文档列表（含词频与位置）'的映射；查询时取各词列表求交/并，再按打分公式排序。

数学机理：<strong>倒排索引（inverted index）</strong> 的结构——(1) <strong>词典（term dictionary）</strong>——所有词的集合（按字典序排序）；可用 <strong>FST（有限状态转换器）/ 前缀树</strong>压缩存储（节省内存、支持前缀查询）。(2) <strong>倒排列表（posting list）</strong>——对每个词，存储'包含它的文档 id 列表'（通常<strong>按 doc id 升序</strong>排列，便于求交）；每项可含 (a) <strong>文档 id</strong>；(b) <strong>词频（tf）</strong>（用于打分）；(c) <strong>位置列表</strong>（用于短语查询与邻近性）。(3) <strong>压缩</strong>——posting list 可用 <strong>delta 编码</strong>（存 doc id 的差值，值更小）+ <strong>变长整数编码</strong>（VByte/Simple9）压缩；这使索引大小大幅减小。<strong>查询流程</strong>——(1) <strong>分词与词干化</strong>——把查询切成词、做词干化/同义词扩展；(2) <strong>取 posting list</strong>——对每个词取倒排列表；(3) <strong>集合运算</strong>——(a) <strong>AND</strong>（所有词都要出现）——<strong>求交</strong>（利用升序排列，用'跳跃指针'或'galloping search'加速）；(b) <strong>OR</strong>（任一出现）——求并；(c) <strong>短语查询</strong>——先用 AND 求交，再用<strong>位置信息</strong>验证'词是否相邻且按序'；(4) <strong>打分排序</strong>——按 BM25 等公式打分，取 top-k；常用<strong>堆（heap）</strong>维护 top-k（避免全排序）；(5) <strong>优化</strong>——(a) <strong>WAND / Block-Max WAND</strong>——利用'上界'提前跳过不可能进 top-k 的文档（大幅加速）；(b) <strong>按 IDF 排序处理</strong>（先处理罕见词以快速缩小候选）。<strong>与其他结构的关系</strong>——(a) <strong>正排索引</strong>（doc → 词）——用于'按文档取内容'（如展示摘要、计算特征）；(b) <strong>倒排索引</strong>——用于'按词找文档'（检索）；(c) 实际系统两者都有。<strong>工程实现</strong>——Lucene（Elasticsearch 的底层）是倒排索引的成熟实现（含 FST 词典、压缩 posting list、WAND 优化、跳表等）。<strong>为什么仍重要</strong>——倒排索引是'稀疏检索'的物理基础；即使稠密检索流行，它仍是混合检索的一路。

深度剖析与工程权衡：① <strong>'posting list 按 doc id 升序'是求交加速的前提</strong>——它使'归并式求交'与'跳跃指针'可行；面试中能指出是深度理解的标志。② <strong>'位置信息'支撑短语查询</strong>——没有位置就只能做'词袋'检索；有位置才能做'精确短语'（如精确短语 machine learning）与'邻近性'打分。③ <strong>'WAND 类优化'是关键工程手段</strong>——它们利用'上界'跳过大量文档（可加速数倍）；这是工业级检索的标配。④ <strong>'FST 词典'压缩</strong>——它把词典压缩到很小（且支持前缀查询）；这是 Lucene 的核心技术之一。⑤ <strong>'AND vs OR'的取舍</strong>——AND 精度高但召回低（漏掉部分匹配）；OR 反之；实践中常用'OR + 打分排序'（而非严格 AND）。⑥ <strong>面试要点</strong>——被问'倒排索引怎么工作'，应给出'<strong>词典 + posting list（doc id/tf/位置）+ 求交/求并 + 打分排序</strong>'与'<strong>压缩（delta + 变长编码）与优化（WAND）</strong>'；能指出'位置信息支撑短语查询'是深度理解的标志。