编辑距离在文本对齐与自动编辑领域的应用

2019-06-28 09:48:00
CJL
原创
403

参考文档:

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%以上,极大的缩减了人工成本。





发表评论
评论通过审核后显示。
流量统计