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

2026 大纲 六（八）字符串模式匹配 的延伸阅读，本篇内容不在大纲范围内。

先说清楚：这一篇不用复习

本篇不在 2026 大纲范围内

倒排索引、BM25、分词都不在 2026 大纲里，不需要复习。复习时间紧张就直接跳过，跳过不会在大纲范围内留下任何缺口。

大纲范围内的三篇是：串的基本概念、BF 算法、KMP 算法。（八）这一条要求掌握的全部内容都在那三篇里。

那为什么还要写这一篇？因为学完 KMP 之后，一个很自然的问题是：这东西真的有人用吗？ 有——但不是以你想的方式。

这一篇要说的是：你在本站右上角敲下搜索词的那一瞬间，背后跑的其实不是 KMP，而是一条你已经学完了全部零件的链路——散列表负责查词、二路归并负责求交、堆负责取前十条。看完它，你会更清楚这些零件各自在解决什么问题。这是理解上的收获，不是要准备的内容。

全文搜索是另一类问题，查找章的算法用不上

先把需求说清楚：给定一份语料库（一堆文档，每篇有标题和正文）和一个查询串 query，返回所有"包含"该 query 的文档，按相关性排序，越快越好。

这跟查找章里的"在一批关键字里找等值元素"是两回事：

场景	关键字形态	比较语义	可用算法
六（一）～（七）的查找	单值（数字、字符串整体）	==（或按序比大小）	顺序查找、折半查找、树形查找、散列表
全文搜索	整篇文档的字符流	"是否含某段连续子串" / "是否含某个词项"	BF、KMP、倒排索引

顺序查找和折半查找在这里直接失效，原因很具体。顺序查找比的是"关键字是否等于给定值"，而文档正文不是一个关键字，doc.body == "哈希" 永远为假。折半查找的问题更本质：它要求有序且能按序比大小，而"含子串"这个性质在按字典序排好的文档序列上不具有单调性——含 "哈希" 的文档不会聚成一段连续区间，二分的前提直接不成立。

所以只剩下模式匹配这条路。

在线扫描路线：给 BF / KMP 套一层外循环

最直接的做法是把 BF 套进"遍历所有文档"的外层循环：

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

设 $N$ 篇文档、每篇长 $n$、query 长 $m$。单篇 $O(n\cdot m)$（候选起始位置约 $n$ 个，每个位置最坏比 $m$ 次，来历见 BF 算法），整个语料 $O(N\cdot n\cdot m)$。代入这个博客的实际规模——百余篇文章、平均每篇约 5000 字符、query 取 4 个字，最坏约

$$100\times 5000\times 4=2000000\text{ 次字符比较}$$

在普通笔记本上是几十毫秒级。能用，但用户每敲一个字都要等这么久，体感已经明显卡顿。

换成 KMP：主串指针永不回退，单篇降到 $O(n+m)$，整个语料 $O(m+N\cdot n)$。换算一下：$100\times 5000=500000$ 次比较，约为 BF 的四分之一——这个 4 正是 $m$ 的值，符合 $O(Nnm)\to O(Nn)$ 的预期。

这里有个值得单独指出的工程细节：next 数组只依赖模式串，与被扫描的文档无关，所以它应该在外层循环之前算一次，而不是每篇文档重算。写成循环内重算就成了 $O(N\cdot (n+m))$——量级上因为 $m\ll n$ 看不出差别，但这是 KMP"预处理与扫描分离"这一结构的直接推论。（本站搜索框的实现为了让三种算法各自独立、便于对照，next 是在每篇文档内重算的。）

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

1. 每次 query 都要重扫所有文档。 $O(N\cdot n)$ 里的 $N\cdot n$ 就是整个语料的总字符数——响应时间随语料规模线性增长，语料翻倍就慢一倍。
2. 没有评分。 BF 和 KMP 给出的是"命中 / 不命中"二值答案，而用户想要的是"最相关的排在最上面"。

工业级搜索的解决办法是：把循环倒过来。

倒排索引：把"遍历文档"换成"查词项"

BF 和 KMP 的循环是"对每篇文档：扫一遍全文，看是否含 query"；倒排索引的循环是"对 query 的每个词项：直接查哪些文档含这个词"。后者听起来像废话——"直接查"是怎么做到的？答案在散列表。

索引构造（离线，只做一次）：把每篇文档分词，对每个词项建立 词项 → 包含该词项的文档 ID 列表 的映射：

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

这就是倒排索引——"倒排"是相对于"文档 → 词项列表"（正排）而言的。底层数据结构就是散列表：词项作 key，文档列表作 value，用拉链法处理 key 冲突，平均 $O(1)$ 查找。这正是散列表那一节学的东西，只不过 value 从"一个记录"换成了"一个文档 ID 列表"。

构造索引的复杂度是 $O(\text{语料总词数})$——它要把每篇文档完整扫一遍，并不比 KMP 扫描便宜。关键在于它只做一次：发生在用户输入之前（页面冷启动时建好，常驻内存），之后每次查询都不再需要碰原文。

"用一次昂贵的预处理，换后续每次的廉价查询"——这个思路和 KMP 预先求 next 数组是同一个套路，只是尺度大了几个数量级。 这句话是本篇唯一真正想留下的东西。

查询（每次 query 都跑）：

1. 把 query 分词
2. 对每个词项查散列表，各得到一个"倒排列表"
3. 求并集（OR）或交集（AND），得到候选文档集合
4. 对每个候选打分，按分数排序
5. 返回前 k 条

第 2 步每个词项 $O(1)$。整个查询的开销只跟词项数与命中文档数有关，跟语料总规模几乎无关——语料翻倍，KMP 的耗时翻倍，倒排索引基本不变。在这个博客的数据量上，单次查询通常落在 0.5–2 ms。

第 3 步和第 5 步，也全是学过的零件

求交集 / 求并集 = 二路归并。 倒排列表按文档 ID 升序存放（这是刻意的），于是两个列表求交、求并都可以用两个指针同步前移的方式一次扫完：

i, j 分别指向两个有序列表的表头
  A[i] == B[j] → 收入交集，i++, j++
  A[i] <  B[j] → i++
  A[i] >  B[j] → j++

复杂度 $O(|A|+|B|)$，与二路归并排序里的 merge 是同一套骨架，区别只在"相等时怎么处理"。倒排列表之所以要排序存放，就是为了让求交能用归并而不是嵌套循环（后者是 $O(|A|\cdot |B|)$）。

取前 k 条 = 堆。 候选可能成千上万，但只需最相关的前 10 条，用一个大小为 $k$ 的小顶堆扫一遍候选，$O(C\log k)$ 远优于全排序的 $O(C\log C)$。

打分用 BM25（了解即可），形状大致是

$$\text{score}(d,q)=\sum _{t\in q}\text{IDF}(t)\cdot f(\text{tf}(t,d),|d|)$$

核心思想三条：词频高的文档得分高（tf）；罕见词权重高（IDF，搜"数据结构的哈希"时"的"几乎不提供信息）；长文档要惩罚（同样出现 5 次，5000 字的文章比 500 字的相关性低）。

这三条顺带解释了为什么倒排索引能排序而 BF / KMP 不能：打分需要"某词在某文档中出现了几次""该词一共出现在几篇文档里"这类统计量，而它们正是建索引时顺手统计好的；在线扫描路线只知道"找到 / 没找到"。

三条路线放在一起看

算法	单次查询耗时（本站量级）	查询复杂度	预处理	排序能力	对应学过的知识
BF 朴素匹配	约 30–60 ms	$O(N\cdot n\cdot m)$	无，$O(1)$ 空间	只有命中／未命中	BF 算法
KMP	约 5–15 ms	$O(m+N\cdot n)$	next 数组 $O(m)$	只有命中／未命中	KMP 算法
倒排索引 + BM25	约 0.5–2 ms	与语料规模基本无关	建索引，$O$(语料总词数)，且占内存	按相关性排序	散列表、二路归并、堆

读这张表必须带上三条限定，否则会得出错误结论：

1. 具体毫秒数会因机器、浏览器和当前语料快照而变，只有数量级的差距是稳定的。
2. 三者的命中集合并不完全相同。 BF / KMP 判的是"正文里有没有这段连续子串"；倒排索引判的是"分词之后有没有命中词项"。它们不是同一个函数的三种实现，只能比耗时量级，不能当成等价替换。
3. 倒排索引不是免费的：它用空间和一次离线构造，换来每次查询的速度与排序能力；语料一更新，索引就要重建或增量更新。

想自己试试：打开这个博客右上角的搜索按钮（或按 Ctrl / ⌘ + K），会看到三个算法切换按钮，默认用倒排索引；切到 KMP 或 BF，搜索框会用同一个 query 立刻重跑一次，并显示命中条数、算法名、耗时与倍数。适合体感对比的 query：「哈希」（常见词，耗时差距最直观）、「KMP」（英文短串，差距会被它在各篇正文中出现位置的靠前／靠后放大）、一串重复度高的字（人为构造的极端 query，对应 BF 那篇里最坏情形的构造）。

顺带一个实现细节：本站的分词是中文按单字切、英文按空白切并转小写，所以搜中文短语时倒排索引的命中会比"严格含子串"更宽松——它命中的是"这几个字都出现过"，而不是"这几个字连着出现过"。这正是上面第 2 条限定的具体表现。

那为什么大纲不教倒排索引

两层原因。① 它绕不开分词，而中文分词本身是个独立的工程领域（词典、统计、歧义消解各成流派），塞进一门基础课，考的就不再是数据结构了。② 大纲的目标是基础数据结构本身，倒排索引是散列表的应用，且与工程实践绑得很紧（索引更新、压缩、分片、持久化）。基础课负责给零件，不负责给成品。

而理解倒排索引所需要的零件，你已经全部学完了：

零件	在倒排索引里干什么	出处
散列表（拉链法）	词项 → 倒排列表的映射	散列表：拉链法
数组 / 链表	存放倒排列表本身	线性表
二路归并	多个倒排列表求交 / 求并	二路归并排序
堆	从大量候选里取 top-k	堆
KMP	精确短语匹配、高亮片段定位	KMP 算法

考点速记

这一篇整篇都不在大纲范围内，在 408 真题里不单独成题，也不会作为任何一道题的知识点出现。 下面三条是理解上的收获：

1. "用一次昂贵的预处理，换后续每次的廉价查询"是同一个思想在两种尺度上的体现——小尺度是 KMP 预先算出 next 数组，大尺度是搜索引擎预先建好倒排索引。看懂这条，本篇的目的就达到了。
2. 在线扫描路线有两个绕不过去的缺陷：每次查询都要重扫全部语料、只有二值命中而无法排序；倒排索引把"遍历文档"换成"查词项"，代价是一次离线构造与常驻内存。
3. 模式匹配与查找章的等值查找是两类问题，比较语义不同，后者的算法在全文场景下直接失效。

不过第 3 条里有一处混淆值得留意，因为它会渗回大纲范围内的查找章：

易错：以为折半查找能用来做"含子串"的检索。 折半的前提是待查性质在有序序列上单调，而"含某段子串"不具备这个性质——含 "哈希" 的文档在字典序里不会聚成连续区间。查找章里"折半查找的适用条件"问的就是这件事。

易错：把倒排索引的"命中"当成"含连续子串"。 分词之后命中的是词项，两个字分散在文章各处也算命中，与模式匹配的语义不同。

教材出处

• 严蔚敏、李冬梅、吴伟民《数据结构（C 语言版）》（第 2 版），第 4 章 4.3.3 节开头，印刷第 91–92 页：指出子串定位运算"应用非常广泛，比如在搜索引擎、拼写检查、语言翻译、数据压缩等应用中，都需要进行串匹配"——本篇正是沿着"搜索引擎"这一条往下走。
• 同书印刷第 97 页：「KMP 算法的最大特点是指示主串的指针不需回溯，整个匹配过程中，对主串仅需从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读入边匹配，而无需回头重读。」——这正是把 KMP 用于扫描大规模语料时的价值所在。
• 同书 4.6 节案例 4.1「病毒感染检测」，印刷第 105–106 页：把 BF 算法用在真实问题（在患者 DNA 序列中检测环状病毒 DNA 序列）上的完整实现，是"模式匹配算法落到应用"的教材内示例。

倒排索引、BM25、中文分词均不在上述教材范围内，本篇这几节没有教材出处，按事实标注。

相关知识

KMP 算法、朴素模式匹配（BF）、串的基本概念（本篇的三个前置，也是大纲范围内的三篇）｜ 散列表：拉链法（倒排索引的底层）、散列表：开放定址法｜ 二路归并排序（倒排列表求交 / 求并）｜ 堆（从候选集里取 top-k）

相关文章

• 串的基本概念
• 朴素模式匹配（BF 算法）
• KMP 算法