如何精准匹配电影的双语字幕
功能需求
本人手里现在有如下两个字幕文件，一个英文版本，一个中文版本。
英文版本已经入库，现在需要将中文版本的字幕也导入数据库，并每句台词尽量与英文对应起来。
初始算法
一开始我用的算法比较简单，就是读取中文字幕文件，根据时间那一行数据的开始时间（只匹配时分秒，不考虑毫秒），去数据库搜索同一开始时间的英文台词。
从上面字幕文件可以看出，虽然台词翻译可以对应起来，但台词时间并不是完全一致的。
如上思路并不能够精准匹配到对应的字幕。
例如下图里，中文字幕00:04:48,960-->00:04:50,860这一行，根据开始时间00:04:48去匹配英文字幕，匹配到的则是：You've been away too long，很明显跟中文字幕“你好 诺兰博士 -很高兴你们能回来”意思不对应。
为了避免时间过于精确而导致无法匹配到对应的英文字幕，搜索条件改成了从以下3个时间去匹配：
- 中文台词开始时间 - 1秒
- 中文台词开始时间
- 中文台词开始时间 + 1秒
初始算法的缺点
实践下来，初始算法改进后，很多台词是能匹配上的，但是仍然有很多地方匹配得不对。
如图，中文字幕第40句台词，开始时间00:04:45，根据初始算法的搜索条件，就会匹配到英文字幕的第44行（开始时间-1秒）和第46行（开始时间+1秒），程序就无法精准匹配到对应行：到底是第44行还是第46行呢？
如果先将匹配数据都存储起来，然后再人工调整。可行倒是可行，只是台词文件一般几千乃至几万多行，是很摧残人的。
本文为翟码农个人博客算法笔记分类下的原创文章，转载请注明出处：http://www.zhai14.com/blog/how-to-match-bilingual-subtitle-files-precisely.html
改良后的算法
要想尽量匹配精准，只有从字幕的时间数据上去下功夫了。
如图，涵盖两种情形。
实际分析，分为如下4种情形：
- 中文字幕时间范围包含英文字幕时间范围（对应示例图里①）
- 中文字幕时间范围在英文字幕时间范围之内，即被包含
- 中文字幕时间范围与英文字幕时间范围满足右相交条件
- 中文字幕时间范围与英文字幕时间范围满足左相交条件（对应示例图里②）
采用这种算法后，需要注意如下两点：
- 》第3种情形，一定要在第4种情形的判断之前，而且相交的时间范围要大于英文字幕时间范围的一半（肯定是相交的时间范围越大，才表示匹配越精准）；上一句匹配上了，那就对应上一句；然后才对应下一句。
- 》如果4种情形都没有匹配上，就按英文字幕的序号入库空数据；这样方便人工看到空台词记录，再来确定是否需要补录。
最终匹配效果
可以看出，对应序号的台词，译文都基本精准匹配上了，无需人工再做太多的额外处理了。
初始算法代码摘选
$arrTime = explode('-->', $line);
//根据时间，找到英文字幕对应的seq_index
$arrStartTime = explode(",", $arrTime[0]);
$after = DateUtil::getCustomDatetime(strtotime($arrStartTime[0])+1, "H:i:s");
$before = DateUtil::getCustomDatetime(strtotime($arrStartTime[0])-1, "H:i:s");
$arrRange = array($before, $arrStartTime[0], $after);
$info = $serviceSubtitle->findRowByData(array('time_point_start' => $arrRange, 'movie_id' => $movieId));
改良后算法代码摘选
public function findMatchedSubtitle($movieId, $arrTime)
{
//根据时间，找到英文字幕对应的seq_index
$arrStartTime = explode(",", $arrTime[0]);
$arrEndTime = explode(",", $arrTime[1]);
// echo "start time(his):".$arrStartTime[0]."<br>";
$startSecondTime = DateUtil::getSecondTimeOfHisFormat($arrStartTime[0]);
// echo "start time(second):".$startSecondTime."<br>";
$startTime = $startSecondTime*1000 + intval($arrStartTime[1]);
$endSecondTime = DateUtil::getSecondTimeOfHisFormat($arrEndTime[0]);
$endTime = $endSecondTime*1000 + intval($arrEndTime[1]);
// echo $startTime."--------".$endTime."<br>";
//情形1：包含
$info = Db::table($this->primaryTable)
->where('status', '=', 1)
->where('movie_id', '=', $movieId)
->where('start_time', '>=', $startTime)
->where('end_time', '<=', $endTime)
->find();
if($info){
return $info;
}
//情形2：被包含
$info = Db::table($this->primaryTable)
->where('status', '=', 1)
->where('movie_id', '=', $movieId)
->where('start_time', '<=', $startTime)
->where('end_time', '>=', $endTime)
->find();
if($info){
return $info;
}
//情形3：右相交
$info = Db::table($this->primaryTable)
->where('status', '=', 1)
->where('movie_id', '=', $movieId)
->where('start_time', '<=', $startTime)
->where('end_time', '>', $startTime)
->where('end_time', '<=', $endTime)
->where("end_time -".$startTime.">".$startTime."-start_time") //确保台词时间匹配范围超过一半以上
->find();
if($info){
return $info;
}
//情形4：左相交
$info = Db::table($this->primaryTable)
->where('status', '=', 1)
->where('movie_id', '=', $movieId)
->where('start_time', '>=', $startTime)
->where('start_time', '<', $endTime)
->where('end_time', '>=', $endTime)
// ->where($endTime."-start_time > end_time -".$endTime) //确保台词时间匹配范围超过一半以上
->find();
if($info){
return $info;
}
return array();
}