我们在什么时候停止呢？当 t 变得很大时，评分就不会再变化了。最迟当 start(sub) 大于任何参考字幕行时，因为在那之后，重叠的评分将始终为零。我们将 max_t 称为所有错误字幕都移至参考字幕之后的时间点。此时最佳总评分为 get_rating(max_t, number_of_incorrect_subtitles)。

Now we have all get_rating(0, 1) to get_rating(max_t, 1). To compute get_rating(0, 2), which means that 0 <= start(sub0) <= 0 and 0 <= start(sub1) <= 0. We already have the rating for sub0 in form of get_rating(0, 1). We only need to add the overlapping rating for sub1. To get get_rating(1, 2) we can either use get_rating(0, 2) (we leave sub1 where it is), or move start(sub1) to 1, which allows start(sub0) to be in 0 <= start(sub0) <= start(sub1) = 1. The best rating for sub0 for that range has been computed with get_rating(1, 1), we only need to add the overlapping rating for start(sub1) == 1. We proceed similarly to get get_rating(t+1, 2): leave the sub1 like it was for get_rating(t,2) or reposition the subtitle to start(sub1) == t+1 and use get_rating(t+1,1) + overlapping_rating(sub1,t+1).

按照相同的原则，我们继续处理 subN

• 初始化 get_rating(0, n) = get_rating(0, n - 1) + overlapping_rating(subN, 0)
• 为 get_rating(t+1, n) 选择最大值
  • get_rating(t, n)，这意味着“保留 subN”
  • get_rating(t+1, n-1) + overlapping_rating(t+1, subN)，这意味着重新定位 subN

Until now we didn't use the split_penalty. We need to add the split penalty when start(subN) - start(subN+1) is a specific value (the original distance diff(N)). The trick here is seeing that we only need to consider the "repostion choice". The only time get_rating(_, n-1) is consulted after the inital phase is when subN gets repositioned. subN will then start at t+1 and we consult get_rating(t+1, n-1). So if subN-1 were positioned at t+1-diff(N-1) for get_rating(t+1-diff(N-1), n-1) we'd be able to get the split_penalty. This is exactly the thing we will do when we are in a phase n: We will not only have the "leave choice" or "reposition choice" but also the "nosplit choice". If we compute get_rating(t, n), we can also compare the two other values with get_rating(t-diffN, n-1) + overlapping_rating(t-diffN, subN) + split_penalty. The get_rating(t-diffN, n-1) + overlapping_rating(t-diffN, subN) is again the best rating where start(subN) = t-diffN. We are allowed to add the split_penalty because in the next phase n+1, subN+1 will start at t when get_rating(t-diffN, n) is looked up. So the final rating algorithm is

• 将 get_rating(t, 0) 初始化为 0
• 初始化 get_rating(0, n) = get_rating(0, n - 1) + overlapping_rating(subN, 0)
• 为 get_rating(t+1, n) 选择最大值
  • get_rating(t, n)，这意味着“保留 subN”
  • get_rating(t+1, n-1) + overlapping_rating(t+1, subN)，这意味着重新定位 subN 和
  • get_rating(t+1-diffN, n-1) + overlapping_rating(t+1-diffN, subN) + split_penalty，这意味着对 subN 进行无分割重新定位

为了得到最终的排列，我们为每个阶段保存n和t+1，其中subN被定位的位置（可以是t+1，t+1-diffN或上一个位置）。如果我们为n = number_of_incorrect_subtitles和t = max_t查找这个值，我们就知道最后一个字幕subN应该在哪个位置。然后我们就知道start(subN)。然后使用get_rating(start(subN), n-1)计算所有之前字幕的最佳排列。因此，我们使用n' = n-1和t' = start(subN)在该表中查找subN-1的位置。这样我们就得到了所有不正确字幕的所有修正位置，任务就完成了！

尽管这个算法可以工作（并且在aligner的早期版本中实现了），但它既不快也不节省空间。让我们以一个45分钟= 2700000毫秒< max_t的字幕文件为例，它大约有n = 900个字幕（这些是现实中的值）。我们构建了一个包含max_t * n = 2430000000 个条目的表。在阶段n-1之后，我们可以丢弃阶段n的评分，但我们总是需要存储字幕subN的位置。假设我们需要4个字节来存储它们：那么我们就有了一个包含2430000000 * 4字节= 9720000000字节= 9 GB数据的表放在RAM中！！！即使是填充零也可能需要一些明显的时间。但事实证明，我们可以使用delta encoding将这个表压缩到小于2 MB（大多数情况下；可能是我看到过的最好的压缩之一）。其经验基础是，从t到t+1的选择几乎从未改变（一个阶段大约是10到1000次）。如果我们总是选择

• "保留选择"，则位置对于每个t+1总是t+1（增加1）
• "nosplit-reposition选择"，则位置总是t+1-diffN（增加1）
• "重定位选择"，位置不会从 t - 1 (常量) 改变。