CodeBrick 博客

Appearance

拓展：从 KMP 到工业级全文搜索 ​

学完 BF 和 KMP，408 大纲的串这一章就算结束了。但有个朴素的疑问应该会冒出来：

所有搜索引擎、所有 IDE 的全局搜索、所有文档站的 Ctrl+K，背后用的真的是 KMP 吗？

不是。它们用的是 倒排索引（Inverted Index）——一个把 408 大纲里看似无关的两章（§3 串、§6 查找/哈希表）合起来才构造得出的数据结构。

这篇拓展把这条链路打通：BF 在全文搜索里能干什么、KMP 比 BF 快了多少、为什么倒排索引能再快上百倍。文末有一个可交互的实测——把这个博客顶部的搜索框打开，里面三个算法按钮就是这篇文章的活体教材。

一、先把"全文搜索"的需求说清楚 ​

给定：

  • 一份语料库（corpus）——一堆文档，每篇有标题和正文
  • 一个查询串（query）——用户输入的几个字

要求：

  • 返回所有"包含"该 query 的文档（包含的定义可以是子串、可以是分词后命中）
  • 按相关性排序
  • 越快越好（用户在键盘上每打一个字，就想看到新结果）

注意这跟 408 §6 查找章节里讲的"在有序的关键字数组里找等值元素"完全是两回事：

场景关键字形态比较语义典型算法
408 §6 查找单值（数字、字符串等值）==顺序查找、折半查找、BST
全文搜索文档的全文流"是否含子串" / "是否含某个分词"BF、KMP、倒排索引

所以顺序查找做不了全文搜索——它的比较是等值，不是"子串包含"。能做全文扫描的，是 408 §3 串章节里的两个老朋友：BF 和 KMP。

二、BF 做全文搜索：把每篇文档扫一遍 ​

最朴素的做法：

text
对语料库中每篇文档 doc：
    对 doc.body 中每个位置 i：
        从 i 开始逐字符比较 pattern
        若全部相等，则 doc 命中

这就是把 BF 模式匹配套在外层"遍历所有文档"的循环里。复杂度：

  • 单篇文档：O(n · m)，n 是文档长度，m 是 query 长度
  • 整个语料：O(N · n · m)，N 是文档数

ds-blog 大概有 100 多篇文章，平均每篇 5000 字符，query 4 字符，最坏要做 100 × 5000 × 4 = 2,000,000 次字符比较。在普通笔记本上是几十毫秒级。

三、KMP 做全文搜索：把单篇扫描提速 ​

KMP 的本质是：主串指针永不回退。失配时按 next 数组让模式指针回退到合适位置，主串指针 i 始终向前走。

把 KMP 套进同样的外层循环：

text
对语料库中每篇文档 doc：
    预处理 pattern 得 next 数组（O(m)）
    用 KMP 扫描 doc.body（O(n)）
  • 单篇文档：O(n + m)
  • 整个语料：O(N · (n + m))

把上面的 BF 数字换算一下：100 × (5000 + 4) ≈ 500,000 次比较，提速 4 倍。

听起来不错，但还有两个本质问题没解决：

  1. 每次 query 都要重扫所有文档。无论用户输入什么，每次都要把整个语料从头扫到尾。
  2. 没有评分。BF 和 KMP 给的答案是"命中 / 不命中"二值的，但用户想要的是"最相关的在最上面"。

工业级搜索是怎么解决的？把循环倒过来。

四、倒排索引：把循环倒过来 ​

BF 和 KMP 的循环是：

text
对每篇文档：扫一遍文本看是否含 query

倒排索引的循环是：

text
对 query 的每个词项：直接查"哪些文档含这个词"

后者听起来像废话——「直接查」是怎么做到的？答案在 408 §6 的哈希表章节：

4.1 索引构造（离线一次） ​

把每篇文档分词，对每个词项建立一个映射：

text
词项 → 包含该词项的文档 ID 列表

举例（简化版）：

text
"哈希"   → [doc-hash-chaining, doc-hash-open-addressing, doc-bst]
"冲突"   → [doc-hash-chaining, doc-hash-open-addressing]
"二叉树" → [doc-bst, doc-avl, doc-rbt, doc-preorder, ...]
"kmp"    → [doc-kmp, doc-bf]
...

这就是倒排索引——名字里的"倒排"是相对于"文档 → 词项列表"（即正排）而言的。

底层数据结构？哈希表。词项作为 key，文档列表作为 value。这就是 408 §6 哈希表章节学的那个东西——拉链法处理 key 冲突，O(1) 查找。

构造索引是一次性预处理，发生在用户输入之前（页面冷启动时建好一次，常驻内存）。

4.2 查询（每次 query 都跑） ​

用户输入 query 后：

text
1. 把 query 分词
2. 对每个词项查哈希表，得到一组"候选文档列表"
3. 求并集（OR）或交集（AND），得到候选文档集合
4. 用 BM25 之类的公式对每个候选打分，按分数倒排
5. 返回前 N 条

每个词项查哈希表是 O(1)。整个查询的复杂度只跟结果数量有关，跟语料总规模几乎无关。

ds-blog 这点数据量上，单次 query 通常在 0.5–2 ms 之间——比 KMP 快十倍以上，比 BF 快几十倍。

4.3 BM25 评分简介 ​

简单提一下排序公式 BM25（不在 408 大纲，了解即可）：

text
score(doc, query) = Σ (词频项 × 词权重)

核心思想：

  • 词频高的文档得分高：query 词在这篇文档里出现得越多越相关
  • 罕见词权重高：query 中越罕见的词越能区分文档（这叫 IDF，逆文档频率）
  • 长文档惩罚：同样的词频，短文档比长文档相关性更高

google、ES、minisearch 都用 BM25 的变种。

五、三种算法在 ds-blog 上的对比 ​

下面这张表是这个博客实际测量的（数据量：~100 篇文章，平均长度 ~5 KB，query「哈希」）：

算法单次查询耗时复杂度排序能力教学对应章节
BF 朴素匹配~30–60 msO(N · n · m)❌ 只有命中/未命中§3 串/BF
KMP~5–15 msO(N · (n + m))❌ 只有命中/未命中§3 串/KMP
倒排索引（minisearch + BM25）~0.5–2 msO(查询词数 · k)✅ 按相关性排序§6 查找/哈希表

具体数字会因机器、浏览器、当前语料快照而变。重点是数量级差异——这不是几个百分点的优化，是质变。

六、回到搜索框：这页博客的搜索功能就是上面三个算法 ​

打开这个博客右上角的搜索按钮（或按 Ctrl/⌘ + K），你会看到三个算法切换按钮：

text
算法： [• 倒排索引]  [ KMP ]  [ BF 朴素匹配 ]

默认用倒排索引。切到 KMP 或 BF，搜索框会用同一个 query 立刻重跑一次，并在结果上方告诉你：

  • 命中了多少条
  • 当前算法叫什么
  • 耗时多少毫秒
  • 跟倒排索引比起来是慢了几倍

试试搜索这些 query 体感对比：

  • 「哈希」——常见词，所有算法都能命中很多文档，最容易看出耗时差
  • 「KMP」——英文短串，BF 和 KMP 的差距会被语料中"KMP"出现位置靠前/靠后放大
  • 「就是这就是」——人造的极端 query，BF 在 KMP 的 next 数组上完败的经典例子

七、为什么大纲不教倒排索引？ ​

合理的疑问。

408 §6 教了哈希表，§3 教了 KMP，但没有把它们捏在一起讲倒排索引。原因有两层：

  1. 倒排索引涉及分词。中文分词在工程上是个独立大题（jieba、ik、HanLP 各家流派），不适合放进 4 道大题的考研框架里。
  2. 大纲的设计意图是基础数据结构本身。倒排索引是哈希表的应用，跟工业实践绑得更紧。

但你应该知道：你已经具备了所有理解倒排索引的零件——

  • 哈希表的拉链法（处理同一个词项映射到多个文档）
  • 链表 / 数组（存倒排列表）
  • 堆（top-k 排序）

这些 ds-blog 都有专门的章节，组装起来就是 ElasticSearch 的核心。

八、延伸阅读（站内） ​

编者注（拓展阅读）：本篇不属于 408 大纲考点，是给"学到这里产生了好奇心"的考生准备的延伸。考试不会考倒排索引和 BM25，但如果你后面会走工程方向、读研做信息检索方向、或者只是想理解你每天在用的搜索引擎，这一篇是大纲到工业实践的一座小桥。