Gale和Church的句對齊演算法解析

Gale和Church在1993年提出了一個基於長度進行句對齊的演算法，並在附錄裏公開了C源代碼。這篇論文相當經典，以至於之後的關於句對齊的論文大多數要引用它。論文的題目是 A Program for Aligning Sentences in Bilingual Corpora。

對齊分兩步。第一步是段落對其，第二步是在段落內部進行句對齊。段落對齊重要，不過簡單，問題在於段落內部的句對齊。所以本文只解析已知段落對齊，怎樣在段落內進行句對齊。首先定義幾個概念，所有論文中出現的符號都對應定義裏的符號。

句子一個短的字元串。
段落語文裏的自然段。分為源語言L1的段落和目標語言L2的段落，或稱原文段落和譯文段落。段落由一個序列的連續句子組成。
片段一個序列的連續的句子，是段落的子集。對應論文中的portion of text。
片段對 原文片段和譯文片段組成的對。
分別對應片段對中原文部分和譯文部分的字元總數。
假設源語言中的一個字元在目標語言中對應的字元數是一個隨機變數，且該隨機變數服從正態分佈。
論文中定義為 $（l_2?l_1c)/sqrt{l_1s^2}$ 。每一個片段對都有自己的一個。
對齊模式 或稱匹配模式，描述一個句塊對由幾個原文句子和幾個譯文句子組成。比如1-2表示一個原文句子翻譯成兩個譯文句子的對齊模式。
match 對齊模式的概率分佈。
距離（distance measure） 衡量片段對兩個片段之間的距離。距離度量是對的估計。當一個片段對確定後，我們就知道它的mathc和。距離越大，此片段對對齊的概率越小。
片段對序列 一個序列的片段對，這些片段對的原文部分的集合是原文段落的一個劃分，譯文部分的集合是譯文段落的一個劃分。
距離和 距離和是片段對序列中所有片段對的距離的和。
對齊序列 距離和最小的片段對序列。

對齊演算法的輸入是某一對相互對齊的段落，輸出是對齊序列。

接下來就變成了動態規劃問題，類似最小編輯距離。片段對序列那麼多，哪個是對齊序列呢？如果用窮舉法，計算量太大，顯然不現實。換個角度想，假設我們已經知道了對齊序列，用表示該對齊序列的距離和，其中是原文段落最後一個句子的index，是譯文段落最後一個句子的index。對齊序列的距離和可以表示成最後一個片段對的距離加上去掉最後一個片段對的剩下的片段對序列的距離和（可以認為對齊序列的子序列也是對齊序列）。最後一個片段對有六種對齊模式，所以要對每種模式分情況討論，選擇結果最小的那個。動態規劃的遞歸式就是這麼來的。