时间复杂度：O(m * n)

空间复杂度：O(m * n)

实际运行时，单个1MB的文本需要大约15分钟，并且这种做法无法并行。

但是这种做法可以在匹配比较稀疏的时候有一种优化来实现期望O(nlogn)的时空复杂度，但是我暂时还没测试，https://www.bilibili.com/read/cv25046174

给定两个语言的文本，假设它们已经得到某种程度上的划分（比如已经按句子分开或者按段落分开）。但是由于语言差异，我们不能简单地根据句子或者段落顺序直接一一对齐。比如英文的两句话在对应的中文里是一句话。

这种方法首先将相对可靠的源文本（比如已经成好段的英文文本）进行机器翻译，翻成目标语言后，将两种语言以更细的粒度进行拆分，拆成单词或者字符。

这里给个例子：

这是已成段的两段英文文本：

5. The Advisory Committee notes from paragraph 9 of the statement submitted by the Secretary-General that the conference-servicing requirements for the biennial meeting of States referred to in paragraph 2 above are estimated at $362,600, and that the conference-servicing requirements for three sessions of the group of governmental experts referred to in paragraph 3 above are estimated at $715,100. Since provision for conference services was made under the relevant sections of the proposed programme budget for the biennium 2002-2003, no additional appropriation would be required for conference-servicing costs.
6. Related resource requirements would comprise two new posts (one P-4 and one General Service), five work-weeks of consultancy services and resources for the travel of up to 20 experts. The total estimated cost of these additional requirements would amount to $559,800, as follows: $456,100 under section 4, Disarmament; $59,900 under section 27 D, Office of Central Support Services; and $43,800 under section 32, Staff assessment, offset by an equivalent amount under income section 1, Income from staff assessment (A/C.5/56/13, para. 16).

这是对应的未成段的中文文本（9行）：

5. 咨询委员会从秘书长的说明第 9 段注意到，上文第 2 段所述两年一度国际会
议所需会议事务费用估计为 362 600 美元，上文第 3 段所述政府专家组三届会议
所需会议事务费用估计为 715 100 美元。由于 2002-2003 两年期方案概算有关各
款已为会议事务编列了经费，因此不需为会议事务费用追加拨款。
6. 所需有关资源将用于新设两个员额（一个 P－4 和一个一般事务员额）、咨询事
务五个工作周以及至多 20 名专家的旅费。这些所需的额外经费总额估计为 559 800
美元，细目如下：第 4 款（裁军）456 100 美元；第 27 D 款（中央支助事务厅）59 900
美元；第 32 款（工作人员薪金税）43 800 美元，但为收入第 1 款（工作人员薪金税
收入）的同等数额所抵消（A/C.5/56/L.13，第 16 段）。

这是英文段落机器翻译后得到的中文段落（两段）：

5.咨询委员会从秘书长提交的说明第9段注意到，上文第2段提及的两年期国家会议所需会议事务估计为362 600美元，上文第3段提及的政府专家组三届会议所需会议服务估计为715100美元。由于会议事务经费是在2002-2003两年期拟议方案预算的有关款次下编列的，因此不需要为会议事务费用追加批款。
6.所需有关资源将包括两个新员额（一个P-4和一个一般事务人员）、五个工作周的咨询服务和最多20名专家的旅费。这些额外所需经费的估计费用总额为559 800美元，如下：第4款（裁军）项下的456 100美元$第27 D款（中央支助事务厅）项下59900美元；第32款（工作人员薪金税）项下43800美元，由收入第1款（工作工作人员薪金税后收入）项下的相等数额抵销（A/C.5/56/13，第16段）。

我们现在将得到的两份中文文本按字拆开，并且记录每个字来自哪行，然后我们把英翻中的换行干掉拼成一段文字序列，中文目标文字也把换行干掉，拼成文字序列。现在我们可以直接把两个被“拍平”的文字序列丢去做最长公共子序列（LCS），得到每个中文（未成段）目标文字序列中的每个字的下标对应于英翻中文字序列的下标。

在本例中，我们运行lcs得到的下标是这一坨东西：

[0, 1, -1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, -1, 15, -1, 16, 17, 18, 19, 20, 21, 22, 23, -1, 24, -1, 25, -1, -1, 28, 29, -1, -1, 31, -1, 33, 34, 35, 36, 37, 38, 39, 40, -1, -1, 41, 42, 43, -1, 44, 45, 46, 47, 48, 49, 50, -1, 51, 52, 53, 54, 55, 56, -1, 57, -1, 58, -1, -1, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, -1, 74, -1, -1, 75, 76, 77, -1, 78, 79, 80, -1, 81, 82, 83, -1, 84, 85, 86, 87, 88, -1, 95, 96, 97, 98, 99, 100, 101, 102, 103, -1, 104, 105, 106, 108, 109, -1, 110, 112, 113, -1, 114, -1, -1, -1, -1, -1, -1, 116, 117, -1, -1, -1, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, -1, 133, 134, 135, 136, -1, 137, 138, 139, 140, 141, 142, 143, -1, -1, -1, -1, 144, 145, 147, 148, 149, 150, 151, -1, 152, -1, 154, -1, 155, 156, 157, 158, 159, 160, 161, 163, -1, 164, 165, -1, -1, -1, -1, 166, 167, 168, 169, 170, -1, -1, -1, 176, -1, 177, 178, -1, 179, 180, 181, 182, 183, 184, 185, 186, 187, 190, 191, 194, -1, -1, -1, 197, 199, 200, -1, -1, 201, -1, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, -1, -1, 212, 213, 214, 215, -1, 216, -1, 217, 218, 219, 220, 221, 224, 225, 226, 227, 228, 229, 230, -1, 231, 232, -1, 233, -1, 234, 235, 236, 237, -1, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 249, 250, -1, 251, 252, 253, 254, 255, 256, 257, -1, 258, 259, -1, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 271, 272, -1, 273, 274, 275, -1, 276, 277, 278, -1, -1, 280, 281, 282, -1, 283, -1, 284, 285, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 299, -1, 300, 301, 302, -1, 303, -1, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, -1, -1, 314, 315, 316, 317, -1, 318, 319, -1, 320, 321, 322]

由于上一步中，我们提前记下了每个字对应于哪行。所以我们可以根据这个下标映射表得到已成段文本能够大致覆盖未成段文本的区间：

{0: [0, 3], 1: [4, 8]}

我们将每个段落对应到的未成段文本的区间中的换行拿掉，即可得到按照段落粒度对齐的双语文本。

这个过程中会存在一些例外，例如完全对不上的句子出现，这种情况下，我们可以计算每个已成段文本的匹配命中率，具体实现可以用本段已匹配字符数/本段落总字符数来得到。我们放弃匹配率过低的段落，让它悬空不参与对齐。

具体代码实现：https://github.com/liyongsea/parallel_corpus_mnbvc/blob/25aa431b678b86c94999d704cbe76155301ac4e2/alignment/script/alignment_by_translate_en2zh.py