ASR2:计算编辑距离

编辑距离(Edit distance)是衡量两个字符串之间相似度的方法,两个字符串的编辑距离就是字符串A经过几次修改能得到字符串B,修改包括:插入(Insertion),删除(Deletion),替换(Substitution)。为什么要学习计算编辑距离呢?因为之后计算两段语音特征之间的距离时用到了和计算编辑距离类似的思想:动态规划(DP)。

如图所示,图中每个点有一个cost,第i行j列的点的cost就代表此时A字符串的前i个字符与B字符串前j个字符的距离,每个点可以向三个方向延伸,向上代表插入,cost加一,向右代表删除,cost加一,向右上延伸时,如果A字符串的第i+1个字符与B字符串第j+1个字符相同,则cost不变,否则代表替换,cost+1。这样,最右上角的点的cost就是两个字符串的编辑距离。

但是这样算还有一个小问题:当两个字符串首字母相同时这样能得到正确的结果,但是首字母不同时就可能出错。比如’a’和’ba’的编辑距离明显是1,但是用这种方法算结果是2,解决方法很简单,就是在每个字符串前面加一个相同的字符,这样就能正确计算编辑距离了。

再考虑这样一种情况:要计算’abc’分别与’abd’,’acd’,’abf’的距离,正常情况要分别算三次。但是这三个字符串有很多相同的部分,其实有很多重复的计算。怎么减少计算复杂度呢?这用到了字典树(Lexical Tree),下次再说。

lufo /
Published under (CC) BY-NC-SA tagged with speech_recognition