中文句子没有空格，所以结构分析的第一步是分词。而分词本身就有歧义——同一个字串能断成好几种。 这一节先用量化打分把分词定下来，再用一张二维表把树拼出来。两件事都是动态规划： 把重复的子问题记下来，只算一次。
上一节的回溯能找全所有树，可句子一长就撑不住。 十二个词要两万六千次调用，再长一点就彻底不可用。 这一节的两件工具就是给这件事收场的：维特比让分词不用猜方向，CYK 让解析从指数掉到三次方。 它们后面站的是同一个想法——分治加记忆。
一、分词：切错一步，后面全错
英文单词之间有空格，中文没有。所以任何中文句法分析的前一步，都是先把字串切成词。 最小的办法是最大匹配：拿词表从头扫，能匹配多长就切多长。 麻烦在于方向——从前往后切和从后往前切，结果常常不一样。 拿一句分词界的经典例句试：「结婚的和尚未结婚的」。 这句话的坑在于「和尚」和「尚未」共用了一个「和」字。
| 切法 | 结果 |
|---|---|
| 正向最大匹配 | 结婚 ／ 的 ／ 和尚 ／ 未 ／ 结婚 ／ 的 |
| 逆向最大匹配 | 结婚 ／ 的 ／ 和 ／ 尚未 ／ 结婚 ／ 的 |
| 正向那个把「和尚 未」切了出来，逆向那个切出了「尚未」。 | |
| 人一眼就知道是后者——可规则不知道。 | |
| 规则只问一件事：这个词在词表里有没有。 | |
| 它不问「这样切整句通不通」。 | |
| 这就是纯规则方法的死穴，也是后面所有统计方法的入口。 |
二、全切分加打分：把猜方向换成算总分
既然方向不可靠，那就把所有断法都列出来，再给每条打分。这一步叫全切分， Demo 里那句话一共 12 种断法。 打分用的是最朴素的统计：每个词的词频取对数，整句相加。 分数越高，说明这条断法里的词越常用。 这就是一元语言模型的用法——先别急着嫌它简陋， 它已经把「和尚 未」这种明显别扭的切法压下去了。
| 方法 | 总得分 | 切出来的结果 |
|---|---|---|
| 维特比（全局最优） | -9.6606 | 和 ／ 尚未 |
| 正向最大匹配 | -11.6755 | 和尚 ／ 未 |
| 逆向最大匹配 | -9.6606 | 和 ／ 尚未 |
| 维特比的分数和逆向那条一模一样，说明它确实找到了最优。 | ||
| 而正向那条低了 2.0149——差的正是「和尚 未」对「尚未」。 | ||
| 「未」在词表里出现 40 次，看着不少；可它是高频单字， | ||
| 跟「尚」组成「尚未」才是一个整词。 | ||
| 词频打分自己就能分辨这件事，不需要人告诉它方向。 | ||
| 维特比的做法可以画成一张有向图：每个字是一个位置，每条可能的词是一条边， | ||
| 边的长度是「这个词的词频取负对数」。 | ||
| 找最高分的断法，就是找从句子开头到结尾的最短路。 |
三、CYK：一张二维表顶掉回溯
分词定下来，接下来才是句法。上一节的回溯是自上而下试，这一次换成自下而上填表。 表的样子很朴素：第 i 行第 j 列，记「从第 i 个词到第 j 个词这一段，能当哪些成分」。 对角线是单个词的词性，往右上角一步步拼。 拼的规则就是文法本身。 想知道第 1 到第 6 个词能不能是 S，就找一个断点，看左边能不能是 NP、右边能不能是 VP。
| 位置 | 能当的成分 |
|---|---|
| 1 到 1 | N、NP |
| 2 到 4 | VP |
| 3 到 4 | NP |
| 1 到 6 | S |
| 右上角那一格出现 S，就说明整句解析成功。 | |
| 而它是靠左下那些小格子拼出来的——一个格子只算一次。 | |
| 这就是它比回溯便宜的原因：回溯会把「第 3 到第 5 个词能不能是 NP」问几十遍， | |
| 填表只算一遍，之后全是查表。 |
四、代价对比：三次方对指数
Demo 第 4 段把同一件事量了一遍：固定文法，逐字加长句子，数「两段能不能拼」的判断次数。
| 词数 | 判断次数 | log 除以 log n |
|---|---|---|
| 4 | 60 | 2.95 |
| 6 | 210 | 2.98 |
| 8 | 504 | 2.99 |
| 10 | 990 | 3.00 |
| 12 | 1716 | 3.00 |
| 16 | 4080 | 3.00 |
| 20 | 7980 | 3.00 |
| 最后一列稳定在 3 上下，这就是 O(n 的三次方)。 | ||
| 词数翻倍，代价涨八倍——难，但可用。 | ||
| 跟上一节对照着看更清楚：12 个词的时候，CYK 只做 1716 次判断， | ||
| 而不带记忆的回溯要 26614 次。 | ||
| 这还只是 12 个词，再多几个，回溯那一列就上万、上十万了。 | ||
| 指数和多项式之间没有折中。 | ||
| 这也是为什么 1970 年代的编译器能在普通机器上做语法检查， | ||
| 而「把所有可能都试一遍」只能留在教科书里。 |
五、动手 Demo：先切成词，再叠成树
这一节的 Demo 分四步走：正向与逆向最大匹配对撞、全切分加维特比打分、CYK 填表、 代价曲线。 分词器、维特比、CYK 都是手写的，一共不到一百行，没有用任何现成库。 这样每一步的中间结果都能打出来看。
def fmm(s): # 正向最大匹配：从左往右，能长就长
out, i = [], 0
while i < len(s):
for L in range(min(MAXLEN, len(s) - i), 0, -1):
if s[i:i + L] in FREQ:
out.append(s[i:i + L]); i += L; break
else:
out.append(s[i]); i += 1
return out
def cyk(tags): # 自底向上填一张二维表
T = [[set() for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
T[i][i + 1].add(tags[i])
for lhs, rhs in UNI: # 「N 也算 NP」这种一元规则
if rhs in T[i][i + 1]:
T[i][i + 1].add(lhs)
for L in range(2, n + 1): # 覆盖的词数从 2 涨到 n
for i in range(0, n - L + 1):
j = i + L
for k in range(i + 1, j): # 每个断点试一遍
for lhs, b, c in BIN:
if b in T[i][k] and c in T[k][j]:
T[i][j].add(lhs)
return T
实跑输出：
--------------------------------------------------------------------
先切成词，再叠成树
--------------------------------------------------------------------
==============================================================
[1] 第一步是分词，而分词本身就有歧义
拿一句经典的话试：
句子：结婚的和尚未结婚的
词表：结婚(80)、的(200)、和(150)、尚(5)、未(40)、和尚(30)、尚未(60)、结(6)、婚(4)
正向最大匹配：结婚 ／ 的 ／ 和尚 ／ 未 ／ 结婚 ／ 的
逆向最大匹配：结婚 ／ 的 ／ 和 ／ 尚未 ／ 结婚 ／ 的
**两条规则只差一个方向，切出来的结果就不同。**
**正向那个切出了「和尚 未」，逆向那个切出了「尚未」。**
**人一眼就知道是后者，可规则不看意思，只看词表里有没有这个词。**
[2] 把所有可能的分法都列出来，再挑一条最好的
**全切分**：一个字串能怎么断，全部枚举。这句话有 12 种断法。
**维特比**：给每种断法打分（各词词频取对数再相加），取最高的一条路。
维特比结果：结婚 ／ 的 ／ 和 ／ 尚未 ／ 结婚 ／ 的
总得分：-9.6606
正向最大匹配的得分：-11.6755
逆向最大匹配的得分：-9.6606
**打分之后就不用猜方向了：谁的分数高选谁。**
**这就是「用统计代替规则」的最朴素的样子。**
[3] 切完之后，把它们叠成一棵树
拿 11.1 那七条文法，句子「张三 看见 那只 狗 用 望远镜」：
词性：N V Det N P N
CYK 的做法是自底向上填一张表。表里第 i 行第 j 列填的是
「从第 i 个词到第 j 个词这一段，能当成哪些成分」：
起＼止 1 2 3 4 5 6
1 N,NP — — S — S
2 V — VP — VP
3 Det NP — NP
4 N,NP — NP
5 P PP
6 N,NP
**右上角那个格子（第 1 到第 6 个词）里有 S，说明整句解析成功。**
**而它是怎么来的？靠左下那些小格子拼出来的。**
**先看「哪一段能当 NP」，再看「两段拼起来能不能当 VP」，一路拼到最后。**
**每一步都是查表，一个格子只算一次。**
**这就是 11.1 最后提到的「把中间结果记住」——只不过这里的记忆表是二维的。**
[4] 两种算法的代价：回溯 vs 查表
同一个句子，CYK 一共做了 210 次「两段能不能拼」的判断。
而 11.1 那个带记忆的回溯，调用次数是同量级的；不带记忆的就差远了。
词数 n CYK 的判断次数 大约是 n 的几次方
4 60 2.95
6 210 2.98
8 504 2.99
10 990 3.00
12 1716 3.00
16 4080 3.00
20 7980 3.00
**指数稳定在 3 上下，这正是 CYK 的复杂度 O(n 的三次方)。**
**12 个词的时候它还只有几千次判断，可 11.1 的不带记忆回溯已经两万多次。**
**句子再长一点，差距就拉开到没法比。**
四段连起来：**分词是结构分析的前一步，本身就有歧义**；
**打分能替你选一条路**；**选好之后靠二维表把树拼出来**；
**而这张表让复杂度从指数掉到三次方。**
第 1 段那两行切法要对着看：字一个没变，只是扫描方向反了。 结果一个是「和尚 未」，一个是「尚未」——这就是歧义落在分词层的具体样子。 第 2 段是这一节的核心技巧：把「选哪条路」变成「算哪条分高」。 维特比 -9.6606 与逆向一致，正向 -11.6755 输在「和尚 未」上。 注意它比正向只高了 2 分，说明打分能救回来，但救得不算轻松。 第 3 段那张表要斜着看：从对角线往右上角一层层填， 右上角出现 S，整句就通了。 格子里的「—」不是空，是「这一段拼不出这个成分」。 第 4 段那个「log 除以 log n」是判断复杂度的土办法： n 变了多少次方，代价就涨多少倍。 七行数据全落在 3.00 附近，才算真的量出了三次方。
30 秒实验
- 把第 1 段的句子换成「南京市长江大桥」，重跑。 两种切法给出「南京市／长江大桥」和「南京／市长／江大桥」——同一个坑，换一句话还会踩。
- 往第 1 段的词表里加一个「尚未结婚」（词频 3），重跑。 维特比会选它——长词一旦进表，打分立刻偏向整词，这就是词表质量为什么这么要紧。
- 把第 3 段的文法删掉 NP → NP PP 这一条，重跑 CYK。 右上角的 S 还在，但中间几格的成分变少了—— 表变小了，是因为可选结构少了，不是因为句子变简单。
常见误区
- 以为「分词只是预处理，不影响后面」。切错一个词， 整个句法树都会挂在错的成分上，CYK 后面填得再好也救不回来。
- 以为「最大匹配越长越好」。正向最大匹配专挑长词， 可真句子里「和」「的」这类单字才是常态。长度不是判断标准，通顺才是。
- 以为「CYK 什么文法都能用」。它要求文法先化成乔姆斯基范式—— 每条规则要么是「一个成分变两个成分」，要么是「一个成分变一个词」。 原始文法得先做等价变换，这一步不少教材直接跳过。
- 以为「三次方已经很慢了」。相对指数它快得离谱， 但 n=100 时也是百万级操作。真实系统要么限句长，要么换更快的算法。
自测三问（点开对答案）
1. 为什么正向最大匹配会切出「和尚 未」？ —— 因为**它从前往后贪心，遇到能匹配的最长词就切**。 **扫到「和尚」时词表里有，就直接切走了，剩下的「未结婚的」只能把「未」单切。** **贪心只看当下最长，不看整句是否通顺——这是所有贪心算法的通病。** 2. 维特比和 Dijkstra 是什么关系？ —— **同一个算法在不同场景下的名字。**把每个字当节点、 **每种切法当一条边、词频的负对数当边长，维特比就是求最短路。** **区别只在 DAG 上做，不需要优先队列，从左往右一遍扫完即可。** 3. CYK 为什么是三次方？ —— 因为**要填的格子是「起止两个下标」，一共 n 的平方个；** **每个格子又要试所有断点，最坏 n 种。** **乘起来就是 n 的三次方。**Demo 第 4 段那七行数据，量的就是这个乘积。结构分析管的是「拆开看」，下一节反过来：让它自己往下写。 不写文法、不填表，只统计「一个字后面最常跟什么」。 这门手艺今天叫语言模型，也是所有大模型的地基。
- ☐ （本节完，下一节 11.4 文本生成）