Gale和Church的句对齐演算法解析

Gale和Church在1993年提出了一个基于长度进行句对齐的演算法，并在附录里公开了C源代码。这篇论文相当经典，以至于之后的关于句对齐的论文大多数要引用它。论文的题目是 A Program for Aligning Sentences in Bilingual Corpora。

对齐分两步。第一步是段落对其，第二步是在段落内部进行句对齐。段落对齐重要，不过简单，问题在于段落内部的句对齐。所以本文只解析已知段落对齐，怎样在段落内进行句对齐。首先定义几个概念，所有论文中出现的符号都对应定义里的符号。

• 句子 一个短的字元串。
• 段落 语文里的自然段。分为源语言L1的段落和目标语言L2的段落，或称原文段落和译文段落。段落由一个序列的连续句子组成。
• 片段 一个序列的连续的句子，是段落的子集。对应论文中的portion of text。
• 片段对 原文片段和译文片段组成的对。
• 分别对应片段对中原文部分和译文部分的字元总数。
• 假设源语言中的一个字元在目标语言中对应的字元数是一个随机变数，且该随机变数服从正态分布 。
• 论文中定义为 。每一个片段对都有自己的一个 。
• 对齐模式 或称匹配模式，描述一个句块对由几个原文句子和几个译文句子组成。比如1-2表示一个原文句子翻译成两个译文句子的对齐模式。
• match 对齐模式的概率分布。
• 距离（distance measure） 衡量片段对两个片段之间的距离。距离度量是对 的估计。当一个片段对确定后，我们就知道它的mathc和 。距离越大，此片段对对齐的概率越小。
• 片段对序列 一个序列的片段对，这些片段对的原文部分的集合是原文段落的一个划分，译文部分的集合是译文段落的一个划分。
• 距离和 距离和是片段对序列中所有片段对的距离的和。
• 对齐序列 距离和最小的片段对序列。

对齐演算法的输入是某一对相互对齐的段落，输出是对齐序列。

接下来就变成了动态规划问题，类似最小编辑距离。片段对序列那么多，哪个是对齐序列呢？如果用穷举法，计算量太大，显然不现实。换个角度想，假设我们已经知道了对齐序列，用 表示该对齐序列的距离和，其中 是原文段落最后一个句子的index， 是译文段落最后一个句子的index。对齐序列的距离和可以表示成最后一个片段对的距离加上去掉最后一个片段对的剩下的片段对序列的距离和（可以认为对齐序列的子序列也是对齐序列）。最后一个片段对有六种对齐模式，所以要对每种模式分情况讨论，选择结果最小的那个。动态规划的递归式就是这么来的。