依存句法分析核心算法：转移系统与Eisner算法

可视化演示

第1节：任务概览——每个句子都有一张组织架构图

公司 HR 拿到一张员工清单，最核心的任务不是把名字背下来，而是搞清楚“谁向谁汇报”。NLP 里的依存句法分析也一样：给出一句话，我们要构建一棵“句法汇报树”，让每个词都清楚地知道自己的抬头是什么、直属上级是谁。这张图一旦画好，后面做信息抽取、情感分析、机器翻译时，机器就不会抓瞎。

把这棵树形式化来看：句子里的每个词都是树上的一个节点，词与词之间画一条带箭头的弧，表示“谁支配谁”。弧上还会贴一个关系标签，比如“主谓关系”“动宾关系”。所有结点再加上一个特殊的虚拟节点 ROOT（对应公司的创始人），整棵树的根就是它。ROOT 的存在很有用：它充当“总指挥”，让句子中那个核心谓语（比如“爱”）可以有一个合法的上级。

形式化说，一个依存句法结构可以写成有向图：

回到比喻里：HR 只需要在员工脑袋上方贴一张小纸条，写上“你的老板是谁、你们是什么关系”，整家公司的汇报体系就瞬间清晰了。依存句法分析要产出的，正是这样一套“贴纸条”的结果。

第2节：依存树结构——四条铁律

一个合格的汇报结构，不是随便画几条线就行。想象你给公司画组织架构图，如果出现“我管你、你管他、他又管我”的循环，或者某个人同时有两个直属老板，第二天公司就会乱成一锅粥。依存句法树也一样，必须满足几条硬性规则，否则它就不是一棵合法的树。

首先，整棵树必须只有一个根，就是 ROOT，没有老板的人只能有一个。其次，除 ROOT 外的每一个词，必须有且仅有一个头部（老板），这叫“单亲约束”。再次，整棵树的弧的数量必须等于节点数减一，因为树是连通的，不能有环。最后还有一条更强的约束叫“投影性”：把弧画在句子下方，如果所有弧都不会跨越彼此，那这棵树就具有投影性。

$$|A| = |V| - 1, \qquad \text{indeg}(r) = 0,\ \forall w \in V \setminus \{r\}: \text{indeg}(w) = 1$$

1. 弧数等于节点数减一：$|A| = |V| - 1$ 是树的连通性保证。如果 $V$ 有 $n$ 个节点，恰好 $n-1$ 条弧，且彼此连通，那么结构一定没有环，是一棵树。

$$|A| = |V| - 1$$

2. 唯一根节点：$\text{indeg}(r) = 0$ 表示根节点（ROOT）的入度为 0，即没有任何词支配它。它是整棵树的最高层。

$$\text{indeg}(r) = 0$$

3. 每个非根节点恰好一个老板：$\forall w \in V \setminus \{r\}: \text{indeg}(w) = 1$ 表示除 ROOT 外每个词都恰好有一条进入的弧，也就是只有一个头。

$$\forall w \in V \setminus \{r\}: \text{indeg}(w) = 1$$

投影性这条约束对算法影响很大：Arc-Standard 默认只能处理投影结构，Arc-Eager 也主要处理投影结构；而现实中的汉语、英语偶尔会有少量非投影现象（比如口语里的“把这本书，我读完了”），这就成了两套转移系统的隐性边界。

第3节：Arc-Standard——稳扎稳打的“先囤人后连线”

有一种 HR 做事特别谨慎：新员工到了以后，不让立刻指定汇报关系，而是全部先请进一间大会议室（栈）里站好，后面排队的候选人（缓冲区）继续等着。只有当栈里最靠近门口的两个人已经不会再被中间插进来的人打扰时，HR 才放心地宣布他们之间的上下级关系。这就是 Arc-Standard 的处事风格：不到火候不连线。

Arc-Standard 是一个经典的转移系统，它用一个栈维护已经出场的词，用一个缓冲区维护还没出场的词。每一步只做三件事之一：把缓冲区第一个人请进栈（SHIFT）；让栈顶的人当老板，收编他左边那个当从属，然后让从属离开栈（LEFT-ARC）；或者让次栈顶的人当老板，收编栈顶这个从属，然后让从属离开栈（RIGHT-ARC）。算法一直重复到栈里只剩 ROOT、缓冲区清空为止。

Arc-Standard 的聪明之处是它的“忍”：它不会在中间还隔着未处理词的时候就急着画弧，所以画出来的弧天然不交叉，保证投影性。代价是每个词都会被压栈再出栈，过程更有章法，但没法处理需要“跨过中间词”的语序。它的解码步数大约是 $2n$ 步，是一个线性时间的效率标兵。

第4节：Arc-Eager——风风火火的“见人就连线”

另一类 HR 完全相反，急性子：新员工刚从缓冲区露面，她立刻就想办法建立汇报关系，能连就连，绝不拖延。比如她是 HR 专员“爱”的直属部下，刚一见到“爱”出现在缓冲区，就马上把“爱”和自己的上级线连好。这种风格虽然快，但也容易出问题：可能连线之后发现，后面还有人需要这个人来管，所以这套系统多了一个动作叫 REDUCE（归约），专门用来把“已经找到老板、不再被需要”的人从栈里请出去。

Arc-Eager 的动作比 Arc-Standard 多一个，一共四类：SHIFT、LEFT-ARC、RIGHT-ARC、REDUCE。它最大的不同是，弧不一定只在栈内两个人之间建立，而是可以连接“栈顶”和“缓冲区第一个”这两个人。因此在句子读入到一半时，整个汇报结构就已经飞速成型了。

回到“我 爱 红茶”的例子上：Arc-Eager 会先让“爱”刚出现在缓冲区时，就把栈里的“我”收编；然后 ROOT 立刻任命“爱”为核心负责人；最后“爱”再把缓冲区里的“红茶”纳入麾下。整个过程一气呵成，不需要像 Arc-Standard 那样把所有人都闷在会议室里憋到最后。也正因为它这么“急”，所以需要 REDUCE 来兜底清理。

第5节：Eisner 算法——全局最优的“规划委员会”

如果说前两个 HR 是现场临场发挥，那么 Eisner 算法就是总部派来的“规划委员会”。它不着急立刻拍板任何一条汇报线，而是拿到完整句子后，把所有可能的分区方式都推演一遍：把句子切成左、右两个连续小区间，分别算出每个区间内部最优的组织方案，再把两个区间的最优方案合并，加上一条跨区间的汇报弧。从小到大，慢慢拼出整棵最优树。

Eisner 属于“基于图”的解析路线：它先让一个打分模型给每个候选弧打一个“默契分”（score），再用动态规划找出总分数最高的那棵树的组合方式。动态规划在这里像个备忘录，把每个小区间的最优分数记下来，避免重复计算。这正是它和贪心转移系统最本质的差别：转移系统边走边决策，只保证当前步最优；Eisner 却保证全局最优。

Eisner 之所以高效，是因为它把指数级的树组合压缩成了多项式级别：每个括号（子区间）只需记住“最左当老板”和“最右当老板”两张表，合并时只考虑一个分裂点。最终它能拿到全局最优的依赖树，而不是一个“差不多就行”的贪心解。

第6节：算法选型——你的公司该用哪一套？

现在你已经见过三位风格迥异的 HR：Arc-Standard 稳、Arc-Eager 快、Eisner 精。可到了真实业务中，你不能全都要，得看场景说话。假设你的聊天机器人要对每一条用户消息实时做句法解析，延迟每多 1 毫秒用户都能感觉到，这时候 Arc-Eager 这种线性解码速度就非常吃香。反过来，如果你是离线分析一整个语料库，要求尽可能高的准确率，那 Eisner 的全局最优就值得那 O(n³) 的等待。

从形式化角度来说，转移系统的解码时间随句子长度线性增长，Eisner 则是立方增长。句子短时二者差别不大，句子一长，差距就非常显著。现代工业界常用方案是：用神经网络（如 BiLSTM、Transformer）给每一步打分，然后接一个像 Arc-Eager 这样的转移解码器，在保证速度的同时把准确率拉得很高；而基于图的 Eisner 则常常被当作“重武器”，用在学术评测、离线标注等高精度场景。

回到公司的比喻里：创业公司几十号人，HR 现场连线完全够用；可到了集团总部要规划上万人的组织架构，不派一个精算委员会全局推演，迟早会出大乱子。理解了这层本质，你就不会被“哪个算法更先进”这种话术迷惑，而是会冷静地问一句：我的业务到底更在乎速度，还是更在乎最终报表的准确率？

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""简易 Arc-Eager 依存解析器演示：用一份手写得分表模拟神经网络的打分层，再用“贪心动作选择”逐步建立依存树。""" def score_arc(words, h, d):    """返回弧 h->d 的分数，分数越高越倾向建立。"""    rules = {        ('爱', '我'): 9,        ('爱', '红茶'): 8,        ('ROOT', '爱'): 7,        ('我', '爱'): 2,        ('红茶', '爱'): 1,    }    return rules.get((words[h], words[d]), 0) def arc_eager_parse(words):    n = len(words)    heads = [-1] * n            # heads[i] = i 的头部词下标    has_head = [False] * n      # 该词是否已经找到了头    stack = [0]                 # ROOT 下标=0 先进栈    buf = list(range(1, n))     # 缓冲区：待入栈的词下标     while buf or len(stack) > 1:        if not stack:            stack.append(buf.pop(0))            continue        s = stack[-1]           # 栈顶词        b = buf[0] if buf else -1         best, best_act = -1e9, None         # 尝试 LEFT-ARC：缓冲区第一个 b 当头部，栈顶 s 当从属        if b != -1 and not has_head[s]:            val = score_arc(words, b, s)            if val > best:                best, best_act = val, ('left',)         # 尝试 RIGHT-ARC：栈顶 s 当头部，缓冲区第一个 b 当从属        if b != -1 and not has_head[b]:            val = score_arc(words, s, b)            if val > best:                best, best_act = val, ('right',)         # 尝试 REDUCE：栈顶 s 已找到头，移除        if has_head[s]:            if 0 > best:                best, best_act = 0, ('reduce',)         # 尝试 SHIFT：把缓冲区第一个 b 压入栈        if b != -1 and best_act is None:            best_act = ('shift',)         # 执行动作        if best_act[0] == 'left':            heads[s] = b            has_head[s] = True            stack.pop()        elif best_act[0] == 'right':            heads[b] = s            has_head[b] = True            stack.append(b)            buf.pop(0)        elif best_act[0] == 'reduce':            stack.pop()        else:            stack.append(b)            buf.pop(0)     return heads if __name__ == '__main__':    words = ['ROOT', '我', '爱', '红茶']    heads = arc_eager_parse(words)    for i in range(1, len(words)):        print('{0} 的头是 {1}'.format(words[i], words[heads[i]]))

1. rules = {('爱', '我'): 9, ...}手写“默契分”表，代表每个候选弧的得分，用于模拟神经网络预测结果。
2. has_head = [False] * n记录每个词是否已经有了老板，这是 Arc-Eager 判断 REDUCE 能否执行的关键状态。
3. stack = [0]栈中先放入 ROOT（下标 0），它是整个解析过程的起点。
4. buf = list(range(1, n))缓冲区保存所有还未进入会议室的员工下标，按顺序等待处理。
5. if b != -1 and not has_head[s]:LEFT-ARC 的合法条件：缓冲区有人，并且栈顶还没有老板，才能被新的缓冲区词收编。
6. heads[s] = b执行左边弧：把栈顶 s 的头部记为 b，也就是“b 是 s 的老板”。
7. stack.append(b); buf.pop(0)执行右边弧后，缓冲区第一个词 b 成为新栈顶（它是被收编的下属），并从缓冲区移除。
8. while buf or len(stack) > 1:只要缓冲区还有人，或栈里除了 ROOT 之外还有员工，解析就需要继续。

常见误区

面试题