7.7 栈解码 221

7.7 栈解码

解码的目的是根据模型以及输入，找到模型得分最高的推导，即：

d = argmax

score(d,t,s) (7.21)

然而想要找到得分最高的翻译推导并不是一件简单的事情。对于每一句源语言

句子，可能的翻译结果是指数级的。由于机器翻译解码是一个 NP 完全问题

[240]

，简

单的暴力搜索显然不现实。因此，在机器翻译中会使用特殊的解码策略来确保搜索

的效率。本节将介绍基于栈的自左向右解码方法。它是基于短语的模型中的经典解

码方法，非常适于处理语言生成的各种任务。

首先，看一下翻译一个句子的基本流程。如图7.23所示，首先需要得到译文句子

的第一个单词。在基于短语的模型中，可以从源语言端找出生成句首译文的短语，之

后把译文放到目标语言端，例如，源语言的“有”对应的译文是“There is”。这个过

程可以重复执行，直到生成完整句子的译文。但是，有两点需要注意：

• 源语言的每个单词（短语）只能被翻译一次。

• 译文的生成需自左向右连续进行。

s：

桌子上

有一个苹果

t：

(a) 初始化状态

s：

桌子上

有一个苹果

t：

There is

(b) 找到译文第一个词

s：

桌子上

有一个苹果

t：

There is

an apple

s：

桌子上

有一个苹果

t：

There is

an apple

on the table

(d) 找到译文第三个词

图 7.23 按目标语言短语自左向右生成的翻译实例

第一点对应了一种覆盖度模型（Coverage Model）；第二点定义了解码的方向，这

样可以确保 n-gram 语言模型的计算是准确的。这样，就得到了一个简单的基于短语

的机器翻译解码框架。每次从源语言句子中找到一个短语，作为译文最右侧的部分，

重复执行直到整个译文被生成出来。

222 Chapter 7. 基于短语的模型肖桐朱靖波

7.7.1 翻译候选匹配

在解码时，首先要知道每个源语言短语可能的译文都是什么。对于一个源语言

短语，每个可能的译文也被称作翻译候选。实现翻译候选的匹配很简单。只需要遍历

输入的源语言句子中所有可能的短语，之后在短语表中找到相应的翻译即可。比如，

图7.24展示了句子“桌子/上/有/一个/苹果”的翻译候选匹配结果。可以看到，不同的

短语会对应若干翻译候选。这些翻译候选会保存在所对应的范围（被称为跨度）中。

这里，跨度 [a, b] 表示从第 a +1 个词开始到第 b 个词为止所表示的词串。比如，“upon

the table

”是短语“桌子

上

有”的翻译候选，即对应源语言跨度

[0,3]

。

s：

桌子

上

有一个

苹果

table

0-1

desk

0-1

1-2

have

2-3

there is

2-3

one

3-4

apple

4-5

apples

4-5

on table

0-2

on the table

0-2

one apple

3-5

an apple

3-5

upon there

1-3

upon the table

0-3

there is an apple

2-5

have an apple...

2-5

图 7.24 一个句子匹配的短语翻译候选

7.7.2 翻译假设扩展

接下来，需要使用这些翻译候选生成完整的译文。在机器翻译中，一个很重要

的概念是翻译假设（Translation Hypothesis）。它可以被当作是一个局部译文所对应的

短语翻译推导。在解码开始时，只有一个空假设，也就是任何译文单词都没有被生

成出来。接着，可以挑选翻译选项来扩展当前的翻译假设。

图7.25展示了翻译假设扩展的过程。在翻译假设扩展时，需要保证新加入的翻译

候选放置在旧翻译假设译文的右侧，也就是要确保翻译自左向右的连续性。而且，同

一个翻译假设可以使用不同的翻译候选进行扩展。例如，扩展第一个翻译假设时，可

以选择“桌子”的翻译候选“table”；也可以选择“有”的翻译候选“There is”。扩

展完之后需要记录输入句子中已翻译的短语，同时计算当前所有翻译假设的模型得

分。这个过程相当于生成了一个图的结构，每个节点代表了一个翻译假设。当翻译

假设覆盖了输入句子所有的短语，不能被继续扩展时，就生成了一个完整的翻译假

设（译文）。最后需要找到得分最高的完整翻译假设，它对应了搜索图中的最优路径。

7.7 栈解码 223

null

P =1

table

there is

P =0.2

P =0.3

P=0.5

one

an apple

table

on the table

apple

4-5

1-2

P =0.1

P =0.4

P =0.3

P =0.4

P =0.2

翻译路径：

图 7.25 翻译假设扩展

7.7.3 剪枝

假设扩展建立了解码算法的基本框架。但是，当句子变长时，这种方法还是面

临着搜索空间爆炸的问题。对于这个问题，常用的解决办法是剪枝，也就是在搜索

图中排除掉一些节点。比如，可以使用束剪枝，确保每次翻译扩展时，最多生成 k 个

新的翻译假设。这里 k 可以被看做是束的宽度。通过控制 k 的大小，可以在解码精

度和速度之间进行平衡。这种基于束宽度进行剪枝的方法也被称作直方图剪枝。另

一种思路是，每次扩展时只保留与最优翻译假设得分相差在 δ 之内的翻译假设。δ 可

以被看作是一种与最优翻译假设之间距离的阈值，超过这个阈值就被剪枝。这种方

法也被称作阈值剪枝（Threshold Pruning）。

不过，即使引入束剪枝，解码过程中仍然会有很多冗余的翻译假设。有两种方

法可以进一步加速解码：

• 对相同译文的翻译假设进行重新组合；

• 对低质量的翻译假设进行裁剪。

对翻译假设进行重新组合又被称作假设重组（Hypothesis Recombination）。其核

心思想是，把代表同一个译文的不同翻译假设融合为一个翻译假设。如图7.26所示，

对于给定的输入短语“一个苹果”，系统可能将两个单词“一个”、“苹果”分别翻

译成“an”和“apple”，也可能将这两个单词作为一个短语直接翻译成“an apple”。

虽然这两个翻译假设得到的译文相同，并且覆盖了相同的源语言短语，但是却是两

个不同的翻译假设，模型给它们的打分也是不一样的。这时，可以舍弃两个翻译假

设中分数较低的那个，因为分数较低的翻译假设永远不可能成为最优路径的一部分。

这也就相当于把两个翻译假设重组为一个假设。

即使翻译假设对应的译文不同也可以进行假设重组。图7.26的下半部分给出了

一个这样的实例。在两个翻译假设中，第一个单词分别被翻译成了“it”和“he”，紧

接着它们后面的部分都被翻译成了“is not”。这两个翻译假设是非常相似的，因为它

们译文的最后两个单词是相同的，而且翻译假设都覆盖了相同的源语言部分。这时，

也可以对这两个翻译假设进行假设重组：如果得分较低的翻译假设和得分较高的翻

224 Chapter 7. 基于短语的模型肖桐朱靖波

null

P =1

apple

1 2

P =0.3

P =0.5

an apple

1-2

P =0.5

null he

is not

0 1

1 2

P =1

P =0.3 P =0.4

P =0.2

is not

P =0.2

原假设

（a）译文相同时的假设重组

null

P =1

apple

1 2

P =0.3

P =0.5

null he

is not

0 1

1 2

P =1

P =0.3 P =0.4

P =0.2

an apple

1-2

P =0.5

is not

P =0.2

舍弃概率

较低假设

舍弃概率

较低假设

重组假设

（b）译文不同时的假设重组

图 7.26 假设重组示例

译假设都使用相同的翻译候选进行扩展，且两个翻译假设都覆盖相同的源语言单词，

分数低的翻译假设可以被剪枝掉。此外，还有两点需要注意：

• n-gram 语言模型将前 n −1 个单词作为历史信息，所以当两个假设最后 n −1

个单词不相同时，不能进行假设重组，因为后续的扩展可能会得到不同的语言

模型得分，并影响最终的模型得分。

• 调序模型通常是用来判断当前输入的短语与前一个输入短语之间的调序代价。

因此当两个翻译假设对应短语在源语言中的顺序不同时，也不能被重新组合。

然而在实际处理中，并不需要“删掉”分数低的翻译假设，而是将它们与分数高

的翻译假设连在了一起。对于搜索最优翻译，这些连接可能并没有什么作用，但是

如果需要分数最高的前两个或前三个翻译，就可能需要用到这些连接。

翻译假设的重组有效地减少了解码过程中相同或者相似翻译假设带来的冗余。

因此这些方法在机器翻译中被广泛使用。包括第八章将要介绍的基于句法的翻译模

型解码中，也可以使用假设重组进行系统加速。

7.7.4 解码中的栈结构

当质量较差的翻译假设在扩展早期出现时，这些翻译假设需要被剪枝掉，这样

可以忽略所有从它扩展出来的翻译假设，进而有效地减小搜索空间。但是这样做也

存在着一定的问题：

• 删除的翻译假设可能会在后续的扩展过程中被重新搜索出来；

7.7 栈解码 225

• 过早地删除某些翻译假设可能会导致无法搜索到最优的翻译假设。

所以最好的情况是尽早删除质量差的翻译假设，这样就不会对整个搜索结果产

生过大影响。但是这个“质量”从哪个方面来衡量，也是一个需要思考的问题。理想

的情况就是从早期的翻译假设中，挑选一些可比的翻译假设进行筛选。

目前比较通用的做法是将翻译假设进行整理，放进一种栈结构中。这里所说的

“栈”是为了描述方便的一种说法。它实际上就是保存多个翻译假设的一种数据结

构

。当放入栈的翻译假设超过一定阈值时（比如 200），可以删除掉模型得分低的翻

译假设。一般，会使用多个栈来保存翻译假设，每个栈代表覆盖源语言单词数量相

同的翻译假设。

比如，第一个堆栈包含了覆盖一个源语言单词的翻译假设，第二个堆栈包含了

覆盖两个源语言单词的翻译假设，以此类推。利用覆盖源语言单词数进行栈的划分

的原因在于：翻译相同数量的单词所对应的翻译假设一般是“可比的”，因此在同一

个栈里对它们进行剪枝带来的风险较小。

在基于栈的解码中，每次都会从所有的栈中弹出一个翻译假设，并选择一个或

者若干个翻译假设进行扩展，之后把新得到的翻译假设重新压入解码栈中。这个过

程不断执行，并可以配合束剪枝、假设重组等技术。最后在覆盖所有源语言单词的

栈中得到整个句子的译文。图7.27展示了一个简单的栈解码过程。第一个栈（0 号栈）

用来存放空翻译假设。之后通过假设扩展，不断将翻译假设填入对应的栈中。

null

P =1

there is

...

tabel

P =0.2 P =0.5

have

...

there is

...

an apple

4-5

P =0.5 P =0.5

未译词

已译 1 词已译 2 词已译 3 词

假设堆栈

0 号栈包含空假设

通过假设扩展产生新的假设

并不断地被存入假设堆栈中

图 7.27 栈解码示例

虽然被称作栈，实际上使用一个堆进行实现。这样可以根据模型得分对翻译假设进行排序。