知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - 倒排索引与分词 ## 什么是倒排索引 倒排索引(Inverted Index)是搜索引擎的核心数据结构,实现"词 → 文档"的快速查找。 ### 正排索引 vs 倒排索引 ``` 正排索引(Forward Index):文档 → 词 文档1: "苹果手机很好用" 文档2: "华为手机也不错" 文档3: "苹果笔记本" 搜索"手机" → 需要遍历所有文档,逐个匹配 → O(n) 倒排索引(Inverted Index):词 → 文档 "苹果" → [文档1, 文档3] "手机" → [文档1, 文档2] "华为" → [文档2] "笔记本" → [文档3] 搜索"手机" → 直接定位到文档1、文档2 → O(1) ``` ### 倒排索引的数据结构 ``` 倒排索引由三部分组成: 1. Term Dictionary(词项字典) 所有去重后的词项,按字典序排序,用 FST(有限状态转换器)存储 2. Posting List(倒排列表) 每个词项对应的文档 ID 列表,以及词频、位置等信息 3. Term Frequency / Position(词频和位置信息) 文档中该词出现了几次、出现在哪些位置 示例:两个文档 文档1: "The quick brown fox jumped over the lazy dog" 文档2: "The quick brown fox jumped over the quick dog" 倒排索引: Term │ Doc 1 (freq) │ Doc 2 (freq) ─────────┼───────────────┼─────────────── brown │ [1] │ [1] dog │ [1] │ [1] fox │ [1] │ [1] jumped │ [1] │ [1] lazy │ [1] │ - over │ [1] │ [1] quick │ [1] │ [2] the │ [2] │ [2] 存储结构(Posting List 内存布局): Term: "quick" ├── DocFreq: 2(出现在 2 个文档中) └── Posting List: ├── DocID: 1, TermFreq: 1, Positions: [2] └── DocID: 2, TermFreq: 2, Positions: [2, 7] ``` ### 倒排索引的压缩 ``` Posting List 通常非常长(比如词 "the" 可能出现在数百万文档中),需要压缩存储。 ES/Lucene 使用的压缩技术: 1. FOR(Frame of Reference)编码 存储差值而不是绝对值: DocIDs: [100, 115, 120, 142] → 差值: [100, 15, 5, 22] → 取最大差值需要的位数(5bit),所有值用 5 位存储 2. Roaring Bitmap 用于 Filter 查询的快速交集运算 将 Posting List 分成高 16 位和低 16 位 高 16 位相同的归为一组,每组内用 bitmap 或数组存储 交集计算: 两个 Posting List 的交集 = 两个 Roaring Bitmap 的 AND 操作 比直接合并 Posting List 快得多 3. Skip List(跳表) Posting List 太长时,在内部建跳表索引 合并多个 Posting List 时可以快速跳过不匹配的文档 ``` > **核心机制:** ES 的搜索过程本质上是找到各词项的 Posting List,然后做交集/并集/差集运算。比如搜索"苹果 AND 手机",就是取"苹果"的 Posting List 和"手机"的 Posting List 做交集。 ## 分词(Analysis) 分词是将文本拆分为词项(Term)的过程,是倒排索引构建的第一步。 ### Analyzer 的组成 ``` Analyzer(分析器)由三部分组成: 1. Character Filters(字符过滤器) 在分词前对原始文本做预处理 - HTML Strip:去除 HTML 标签 - Mapping:替换字符(如 ①→1) - Pattern Replace:正则替换 2. Tokenizer(分词器) 将字符串按规则切分为 Token - Standard:按词边界分词,去除标点 - IK(中文):基于词典的中文分词 - Whitespace:按空白字符分词 - Keyword:不分词,整个字符串作为一个 Token - Pattern:按正则表达式分词 3. Token Filters(Token 过滤器) 对每个 Token 做加工处理 - Lowercase:转小写 - Stop:去除停用词(的、是、the、a 等) - Synonym:同义词扩展 - Stemmer:词干提取(running → run, dogs → dog) 完整的分析过程: 输入: "<p>The Quick Brown Foxes</p>" │ Character Filter: HTML Strip ▼ "The Quick Brown Foxes" │ Tokenizer: Standard ▼ ["The", "Quick", "Brown", "Foxes"] │ Token Filter: Lowercase ▼ ["the", "quick", "brown", "foxes"] │ Token Filter: Stemmer ▼ ["the", "quick", "brown", "fox"] 最终写入倒排索引的 Term: the, quick, brown, fox ``` ### 中文分词 ``` 中文分词的难点:词与词之间没有空格分隔 原文: "中华人民共和国" 错误分词(一元分词,按字分): "中" "华" "人" "民" "共" "和" "国" 正确分词(IK 分词器): "中华人民共和国" / "中华" / "人民" / "共和国" IK 分词器两种模式: ik_smart(粗粒度): "南京市长江大桥" → ["南京市", "长江大桥"] ik_max_word(细粒度,召回率更高): "南京市长江大桥" → ["南京市", "南京", "市长", "长江大桥", "长江", "大桥"] 搜索时通常用 ik_smart 分词查询词,避免无意义匹配 索引时用 ik_max_word 分词文档,提高召回率 IK 分词器 vs 一元分词: ┌──────────┬──────────────┬──────────────────┬────────────┐ │ 方案 │ 索引大小 │ 召回率 │ 精度 │ ├──────────┼──────────────┼──────────────────┼────────────┤ │ 一元分词 │ 大 │ 极高 │ 低 │ │ IK 分词 │ 中 │ 较高 │ 高 │ └──────────┴──────────────┴──────────────────┴────────────┘ ``` ## 相关性评分 搜索结果需要按相关性排序,ES 默认使用 BM25 算法。 ### TF-IDF(Lucene 旧版本默认) ``` TF-IDF = 词频(TF) × 逆文档频率(IDF) TF(Term Frequency):词在文档中出现的频率 TF = 词在文档中出现次数 / 文档总词数 IDF(Inverse Document Frequency):词在全部文档中的稀有程度 IDF = log(总文档数 / 包含该词的文档数) 通俗理解: - 一个词在一篇文档中出现次数越多 → TF 越高 → 越相关 - 一个词在越少的文档中出现 → IDF 越高 → 越重要 - "的"在每个文档都出现 → IDF 很低 → 不重要的词 ``` ### BM25(ES 5.0+ 默认) ``` BM25 是 TF-IDF 的改进版,解决了 TF 无限增长导致评分失控的问题。 BM25 的核心改进: 1. TF 饱和控制 TF-IDF: 出现 100 次的文档得分是出现 1 次的 100 倍 BM25: 出现 10 次之后得分基本不再增长 效果: 阻止长文档靠堆砌关键词获得虚高得分 2. 文档长度归一化 短文档中匹配到关键词更难得 → 得分更高 长文档中匹配到关键词更常见 → 得分适当降低 例: 搜索"Redis" 文档A(1000字): "Redis 是一个..." TF=5 → 得分高(短文档高密度匹配) 文档B(10000字): "...提到 Redis ..." TF=5 → 得分低(长文档中同等 TF 相对常见) BM25 公式: Score = Σ IDF(qi) × (TF(d,qi) × (k1 + 1)) / (TF(d,qi) + k1 × (1 - b + b × |d|/avgDl)) 参数: k1: TF 饱和参数(默认 1.2,越大 TF 上限越大) b: 文档长度归一化强度(默认 0.75,越大长度惩罚越重) ``` > **面试要点:** > - TF-IDF:简单直观,但 TF 会无限增长 > - BM25:解决了 TF 饱和问题,加了文档长度归一化,效果更好 > - 两者的 IDF 部分核心思想相同:越稀有的词越重要 ## 常见 Analyzer 对比 | 分析器 | 适用语言 | 分词方式 | 特点 | |--------|---------|---------|------| | Standard | 通用 | Unicode 标准分词 | ES 默认,英文好用,中文不行 | | IK | 中文 | 词典分词 | 中文最常用,支持 ik_smart / ik_max_word | | Jieba | 中文 | 词典+HMM | Python 生态,ES 通过插件支持 | | Kuromoji | 日文 | 词典分词 | 日文分词 | | Nori | 韩文 | 词典分词 | 韩文分词(ES 官方) | | Keyword | 通用 | 不分词 | 精确匹配场景(ID、标签、状态码) | | Whitespace | 通用 | 空白字符 | 简单场景 | ## 面试常见问题 **Q:什么是倒排索引?** A:倒排索引是"词 → 文档"的映射。它维护每个词项(Term)出现在哪些文档中、位置、频率。搜索时直接通过词找到文档列表,再对列表做交集/并集/差集运算。与正排索引(文档 → 词)相反,倒排索引让全文搜索从 O(n) 降到 O(1)。 **Q:分词器(Analyzer)由哪几部分组成?** A:① Character Filter(字符预处理,去 HTML 标签等)→ ② Tokenizer(切词)→ ③ Token Filter(Token 加工,转小写、去停用词、词干提取)。整个过程把原始文本变成 Term 写入倒排索引。 **Q:ES 相关性评分用的什么算法?默认是哪个?** A:ES 5.0 之前默认用 TF-IDF,5.0 之后默认用 BM25。BM25 的核心改进:① TF 饱和控制(关键词出现 10 次后不再线性增长得分)② 文档长度归一化(短文档中匹配到关键词得分更高)。 **Q:中文分词怎么选?** A:生产环境几乎都选 IK 分词器。索引时用 ik_max_word(细粒度,提高召回),搜索时用 ik_smart(粗粒度,避免无意义匹配)。不推荐一元(逐字)分词,索引体积太大且精度低。 --- 下一篇:[03 - 搜索 DSL](./03-search-dsl.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入