编辑距离在文本对齐与自动编辑领域的应用
- 2019-06-28 09:48:00
- CJL 原创
- 3973
参考文档：
https://blog.csdn.net/l294265421/article/details/50197223 从字符串编辑距离到字符串对齐
https://blog.csdn.net/qq_29311407/article/details/79802216 用js实现编辑距离算法（Edit Distance）
http://www.phpzy.com/php/24175.html PHP similar_text()、levenshtein()、lcs()支持中文汉字版，
目的：
实现由原始素材到给定目标文本的自动编辑与字幕对齐。
通过最小编辑路径可以达到一定的模糊匹配效果。间接获得剪辑内容的最优解。
思路：
1、通过视频或音频转换技术提取音频内容
2、通过语音识别接口获得文字的时间轴数据
3、通过编辑距离算法获得最小编辑距离作为最优解
4、通过编辑距离算法反推出最佳编辑路径，获得备选编辑信息
5、编辑视频：通过原始文本时间轴计算出目标时间分片，对相邻时间分片进行优化合并，提高流畅度
6、字幕对齐：通过原始文本时间轴计算出目标文本的时间轴位置，生成字幕文件
7、配合视频音频编辑工具进行视频音频的合成导出
实现：
最小编辑距离计算
公式：
在相同位置上两个字符串不同:cost=1；反则为0 matrix[m][n]=Math.min(matrix[m-1][n]+1,matrix[m][n-1]+1,matrix[m-1][n-1]+cost)
实现代码：
public int edit()
{
int max1 = str1.length();
int max2 = str2.length();
//建立数组，比字符长度大一个空间
array = new int[max2+1][max1+1];
for(int i=0;i<=max1;i++){
array[0][i] = i;
}
for(int j=0;j<=max2;j++){
array[j][0] = j;
}
for(int i=1;i<=max1;i++){
for(int j=1;j<=max2;j++){
array[j][i] = levenshtein(i,j,str1.charAt(i-1),str2.charAt(j-1));
// System.out.println("j=="+j+" i=="+i+" "+array[j][i]);
}
}
// System.out.println("*********"+array[max2][max1]);
return array[max2][max1];
}最佳编辑路径计算
通过最佳值反推出编辑路径
protected ArrayList<String> computePath(int i, int j)
{
ArrayList<String> paths = new ArrayList<>();
int current = array[j][i];
int con = 0;
if (j>0 && i>0) {
con = str1.charAt(i-1) == str2.charAt(j-1) ? 0 : 1;
}
String path = "" + i + "," + j + "|";
String action = "";
if(j>0 && i>0 && current == array[j-1][i-1]+con) {
ArrayList<String> childs = this.computePath(i-1, j-1);
for (String cp:childs) {
paths.add(cp+path);
action = con == 0 ? "同" : "替";
}
} else if(j>0 && current == array[j-1][i]+1) {
ArrayList<String> childs = this.computePath(i, j-1);
for (String cp:childs) {
paths.add(cp+path);
action = "增";
}
} else if(i>0 && current == array[j][i-1]+1) {
ArrayList<String> childs = this.computePath(i-1, j);
for (String cp:childs) {
paths.add(cp+path);
action = "删";
}
} else {
paths.add(path);
action = "-";
}
//打印编辑动作
String iS = (i>0 ? String.valueOf(str1.charAt(i-1)) : "").replace("\n", "\\n");
String jS = (j>0 ? String.valueOf(str2.charAt(j-1)) : "").replace("\n", "\\n");
// System.out.println("(" + i + " " + j + ")(" + iS + " " + jS + ")" + action);
return paths;
}样例输出：
(0 0)( )- (1 1)(脚 脚)同 (2 2)(起 起)同 (3 3)(水 水)同 (4 4)(泡 疱)替 (5 5)(是 是)同 (6 6)(个 个)同 (7 7)(很 很)同 (8 8)(笼 笼)同 (9 9)(统 统)同 (10 10)(的 的)同 (11 11)(说 说)同 (12 12)(法 法)同 (13 13)(， \n)替 (14 14)(大 大)同 (15 15)(部 部)同 (16 16)(分 分)同 (17 17)(情 情)同 (18 18)(况 况)同 (19 19)(下 下)同 (20 20)(是 是)同 (21 21)(指 指)同 (22 22)(足 足)同 (23 23)(底 底)同 (23 24)(底 \n)增 (24 25)(或 或)同 (25 26)(注 足)替 (26 27)(册 侧)替 (27 28)(原 缘)替 (28 29)(有 有)同 (29 30)(针 针)同 (30 31)(尖 尖)同 (30 32)(尖 \n)增
视音频转音频
安装FFmpeg，通过FFmpeg进行视频装换。
FFmpeg是一个功能强大的音视频处理软件，还可以在其他很多处理。
音频识别
通过讯飞语音识别接口进行语音识别和文字时间轴定位。
https://www.xfyun.cn/services/lfasr
字幕计算生成
使用语音识别的全部文本做原字符串，目标字幕稿为目标文本。
计算出来最佳编辑路径，通过每一句目标文稿起始位置查找到对应的原始文本位置，通过原始文本位置获得原始文本的时间轴信息。
通过时间轴信息便可计算出新的字幕稿的时间轴。进而生成字幕文件。
最终输出如下：
00:01:31:19 00:01:34:14 还可以是一些其他的一些情况 00:01:34:14 00:01:37:18 这就需要找专科医生明确诊断 00:01:37:18 00:01:39:18 并进行一个相应的治疗
效果
使用最短编辑距离优化去年开发的视频预剪辑工具后，字幕对齐效果大大提升，准确率可以达到99%以上，极大的缩减了人工成本。
