编辑间隔
字符串的编辑间隔，又称为 Levenshtein间隔，由俄罗斯的数学家Vladimir Levenshtein在1965年提出。是指经过字符间的操作，把字符串A转换成字符串B所需求的最少操作步骤数，普通来说，两个字符串的编辑间隔越小，则它们越相似。其中，字符操作包括：
删除一个字符 D 插入一个字符 I 编辑一个字符 S
例如：
从 12345 到 12346 需求一步（一次编辑） 从12345到123467则需求两步（5编辑为6，然后插入7）
Levenshtein 给出了编辑间隔的普通求法，就是经典动态规划成绩。这里给出Levenshtein间隔的性质，设d(x,y)表示字符串x到y的Levenshtein间隔，那么显然：
d(x,y) = 0 当且仅当 x=y，即字符串相等 d(x,y) = d(y,x) ，即从x变到y的最少步数就是从y变到x的最少步数 d(x,y) + d(y,z) >= d(x,z) ，即从x变到z所需的步数不会超过x先变成y再变成z的步数，也叫做三角形不等式。就好像一个三角形一样，两边之和必然大于第三边。
在自然言语处理中，编辑间隔是一个概念非常重要，例如在词典小程序中：假如用户不小心输错了单词，则可以列出字典里与它的Levenshtein间隔小于某个数N的单词，让用户选择正确的那一个，N通常取到 2或3。
求解编辑间隔
这里需求运用动态规划的思想，动态规划算法通常基于一个递推公式及一个或多个初始形状。 当前子成绩的解将由上一次子成绩的解推出。所以我们首要目的是找到某个形状和一个递推公式。
假设我们可以运用d[ x, y ]个步骤（运用二维数组描画，数组中每个值表示到目前为止两个子字符串的转换需求的操作数），表示将字符串 hyp[1...i] 转换为字符串 ref[ 1…j ] 所需最少步骤数。
为方便了解，我们先假如在最简单的状况下，即在 i=0 时，也就是说字符串hyp 为空，那么要转为对应的 d[0, j] ，hyp需求添加 j 个字符，即需求 j 步，使得hyp转化为ref；异样在 j 等于0时，即字符串ref为空，那么对应的 d[i, 0] 就是hyp删除 i个字符，即需求i步，使得hyp转化为ref。
再进一步，假如我们想要将 hyp[1...i] 经过最少次数的插入、删除、编辑操作转换为 ref[1...j]，存在以下三种状况：
假设我们可以在最少M步内将 hyp[1...i] 转换为 ref[1...j-1]，此时我们仅需求再将 hyp[1...i] 加上 ref[j] 就可以将 hyp[1...i] 转化为 ref[1...j]，这样hyp转换为ref就需求 M+1步。 假设我们可以在最少N步内将hyp[1...i-1]转换为 ref[1...j]，此时我们仅需求将 hyp 删除就可以将 hyp[1...i] 转化为 ref[1...j]，这样hyp转换为ref就需求 N+1步。 假设我们可以在最少Q步内将 hyp[1...i-1]转换为 ref[1...j-1]，这时我们就需求判别 hyp 和 ref[j] 对应的字符串能否相等。假如相等，那么我们只需求Q步就可以将 hyp[1...i] 转化为 ref[1...j]。假如x和y[j]不相等，那么我们需求将 hyp交换为ref[j]，这样需求Q+1步就可以将 hyp[1...i] 转化为 ref[1...j]。
这三种状况是在前一个形状可以以最少次数的添加，删除或者编辑操作，使得如今字符串hyp 和 字符串ref 只需求再停止一次操作或者不停止任何操作就可以完成hyp[1..i]到 ref[1..j]的转换。最后，我们为了保证所需的步骤最少，我们需求从下面三种状况中选择步骤最少的一种作为将 hyp[1..i]转换为 ref[1..j] 所需的最少步骤数—— 即 min(M+1，N+1，Q+temp)，其中 hyp==ref[j]时，temp=0，否则 temp=1。
这样我们就得出递推公式：
levenST[ i ][ j ] = min( levenST[ i-1 ][ j ] + 1, levenST[ i ][ j-1 ] + 1, levenST [i-1 ][ j-1 ] + temp);
递推公式需求三个初始形状，即levenST[i-1][j]， levenST[j-1]和levenST[i-1][j-1]，所以我们需求对数组 levenST[][]事行停止初始化，先求出最简单的形状下的levenshtein间隔。
最后，我们将两个字符串中一切字符都遍历对比完成之后，将hyp转换为ref所需最少步骤数就是d[m][n]。其中m为字符串hyp的长度，n为字符串ref的长度。
图解栗子
ref（reference）表示标注文本序列，hyp（hypothesis）表示预测文本序列，则可以计算 编辑间隔为 3，其中1次交换错误（S），1次删除错误（D），1次插入错误（I）。
1.构造初始化二维数组levenST[6][6]，横轴为ref（标注序列），纵轴为hyp（预测序列）。
2.从字符串HYP的第一个字末尾，依次与REF中的字母（y[1...j]）停止比较，然后得出相应地位levenST[1,j]上的最少转换步骤数，即编辑间隔，假如两个字母相等，则在从此地位的左（i ,j-1）+1，上（i -1,j）+1，左上（i -1,j-1）+0 三个数中获取最小的值写入（因左、上的值不能够低于左上的值，所以可以直接去左上的值）；若不等，则在从此地位的左（i ,j-1），上（i -1,j），左上（i -1,j-1）三个地位中获取最小的值再加上1。如下图，首先对比字符串HYP中第1个汉字"五"和字符串REF中第1个汉字"五"，发现两个汉字相等，所以对比[j]的左、上、左上三个地位的值，取出最小值0存入levenST[1][1]
也就是说当前地位的levenST[1,j]只与相邻的后面三个地位有关，而三个有色方块代表的物理意义如下：
左上表示交换错误 S 右上表示插入错误 I 左下表示删除错误 D
不断迭代下去，直到矩阵中一切的值都被计算出来之后，整个levenST矩阵右下角的为的值就是你要的编辑间隔了，图中编辑间隔为3。
此外，我们还想知道 I、D、S 到底各占多少，对齐的文本到底是什么样子的，这是我们要从右下角（6，6）回溯。对于右下角的“3”，它的前三个值最小为3，阐明没有发生错误。接上去（5，5）地位，前三个值为4、3、2，最小值为2，选择上方的方格，并记录一次插入错误，再如（2，3），前三个值为1、1、2，最小值为1，阐明发生了错误，这时按照 substitution > insert > delete 的优先级，选择左上方的方格。以此类推，直到遍历到左上角为止。如下图所示，我们就得到了一切的错误类型。
当然，优先级不同，回溯方法也不一样，假如优先级为：insert > delete > substitution，则结果如下：
下面看一个特殊状况，即句子扫尾有插入或者删除错误。
这时假如我们回溯整个矩阵发现，hyp先结束了，而ref还没有结束，为了得到一切的操作，我们必需要遍历的左上角才行，所以，强行从遍历结束的地位移动到左上角。那么，假如是hyp先结束，则一切移动都是删除错误（D），假如是ref先结束，那么一切错误都是插入错误（I）。
Python完成
WER(word error rate) 常常作为语音辨认义务的功能评测目的，WER的计算公式，如下：
如何经过计算编辑间隔，获取到WER计算的分子与分母呢？我们可以从较为简单的状况停止分析。
当两个字符串都为空串，那么编辑间隔为0； 当其中一个字符串为空串时，那么编辑间隔为另一个非空字符串的长度； 当两个字符串均为非空时(长度分别为 i 和 j )，取以下三种状况最小值即可： 1、长度分别为 i-1 和 j 的字符串的编辑间隔已知，那么加1即可； 2、长度分别为 i 和 j-1 的字符串的编辑间隔已知，那么加1即可； 3、长度分别为 i-1 和 j-1 的字符串的编辑间隔已知，此时思索两种状况，若第i个字符和第j个字符不同，那么加1即可；假如不同，那么不需求加1。
例如，求长度为ref和hyp的字符串的编辑间隔，首先定义函数——edit(i, j)，它表示第一个长度为i的字符串与第二个长度为j的字符串之间的编辑间隔。动态规划表达式可以写为：
if i == 0 且 j == 0，edit(i, j) = 0 if （i == 0 且 j > 0 ）或者 （i > 0 且j == 0），edit(i, j) = i + j if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + d(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，d(i, j) = 1；否则，d(i, j) = 0。
实古代码
Python 实古代码篇幅较大，此处不贴了，需求的可私聊。
输入结果数据结构
{ # 标注文本 "ref": "五六七八九十", # 预测文本 "hyp": "五七捌九玖十", "result_detail": { # 一切对的字列表 "C": [ { "ref_value": "五", # ref的值 "hyp_value": "五", # hyp的值 "ref_index": 0, # 该值在ref的索引地位 "hyp_index": 0, # 该值在hyp的索引地位 "ref_syllable": "wu", # ref中该值的音节 "hyp_syllable": "wu", # hyp中该值的音节 "ref_tones": "3", # ref中该值的音调 "hyp_tones": "3" # hyp中该值的音调 },{……} ], # 一切编辑的字列表 "S": [{……}, ], # 一切删除的字列表 "D": [{……}, ], # 所欲插入的字列表 "I": [{……}, ] }, # 字句的目的 "result_indicator": { # 字错率wer目的 "wer": 0.500, # 句错率ser目的 "ser": 1 }, # 编辑间隔计算出的各项值 "result_count": { # 全部的数量 N = S + I + D + C "N": 6, # 正确的的数量 "C": 4, # 错误的的数量 W = S + I + D "W": 3, # 插入的数量 "I": 1, # 删除的数量 "D": 1, # 编辑的数量 "S": 1 }, # 将 ref 与 hpy 建立相对索引对齐后的字典，方便展现输入 "relative_index_value": { # 索引 1 "1": { "ref_value": "五", # ref的值 "ref_index": 0, # 该值在ref的索引地位 "hyp_value": "五", # hyp的值 "hyp_index": 0, # 该值在hyp的索引地位 "syllable_type": "C", # 音节比对结果，C=正确 S=错误 "hyp_syllable": "wu", # hyp中该值的音节 "ref_syllable": "wu", # ref中该值的音节 "tones_type": "C", # 音调比对结果，C=正确 S=错误 "hyp_tones": "3", # hyp中该值的音调 "ref_tones": "3", # ref中该值的音调 "type": "C" # 字符比对结果，C=正确 S=编辑 I=插入 D=删除 }, # 索引二 "2": {{……},} }}实践输入JSON如下：
{ "ref": "五六七八九十", "hyp": "五七捌九玖十", "result_detail": { "C": [ { "ref_value": "五", "hyp_value": "五", "ref_index": 0, "hyp_index": 0, "ref_syllable": "wu", "hyp_syllable": "wu", "ref_tones": "3", "hyp_tones": "3" }, { "ref_value": "七", "hyp_value": "七", "ref_index": 2, "hyp_index": 1, "ref_syllable": "qi", "hyp_syllable": "qi", "ref_tones": "1", "hyp_tones": "1" }, { "ref_value": "九", "hyp_value": "九", "ref_index": 4, "hyp_index": 3, "ref_syllable": "jiu", "hyp_syllable": "jiu", "ref_tones": "3", "hyp_tones": "3" }, { "ref_value": "十", "hyp_value": "十", "ref_index": 5, "hyp_index": 5, "ref_syllable": "shi", "hyp_syllable": "shi", "ref_tones": "2", "hyp_tones": "2" } ], "S": [ { "ref_value": "八", "hyp_value": "捌", "ref_index": 3, "hyp_index": 2, "ref_syllable": "ba", "hyp_syllable": "ba", "syllable_type": "C", "ref_tones": "1", "hyp_tones": "1", "tones_type": "C" } ], "D": [ { "ref_value": "六", "hyp_value": null, "ref_index": 1, "hyp_index": 1, "ref_syllable": "liu", "hyp_syllable": null, "ref_tones": "4", "hyp_tones": null } ], "I": [ { "ref_value": null, "hyp_value": "玖", "ref_index": 5, "hyp_index": 4, "ref_syllable": null, "hyp_syllable": "jiu", "ref_tones": null, "hyp_tones": "3" } ] }, "result_indicator": { "wer": "0.500", "ser": 1 }, "result_count": { "N": 6, "C": 4, "W": 3, "I": 1, "D": 1, "S": 1 }, "relative_index_value": { "1": { "ref_value": "五", "ref_index": 0, "hyp_value": "五", "hyp_index": 0, "syllable_type": "C", "hyp_syllable": "wu", "ref_syllable": "wu", "tones_type": "C", "hyp_tones": "3", "ref_tones": "3", "type": "C" }, "2": { "ref_value": "六", "ref_index": 1, "hyp_value": null, "hyp_index": null, "syllable_type": "S", "hyp_syllable": null, "ref_syllable": "liu", "tones_type": "S", "hyp_tones": null, "ref_tones": "4", "type": "D" }, "3": { "ref_value": "七", "ref_index": 2, "hyp_value": "七", "hyp_index": 1, "syllable_type": "C", "hyp_syllable": "qi", "ref_syllable": "qi", "tones_type": "C", "hyp_tones": "1", "ref_tones": "1", "type": "C" }, "4": { "ref_value": "八", "ref_index": 3, "hyp_value": "捌", "hyp_index": 2, "syllable_type": "C", "hyp_syllable": "ba", "ref_syllable": "ba", "tones_type": "C", "hyp_tones": "1", "ref_tones": "1", "type": "S" }, "5": { "ref_value": "九", "ref_index": 4, "hyp_value": "九", "hyp_index": 3, "syllable_type": "C", "hyp_syllable": "jiu", "ref_syllable": "jiu", "tones_type": "C", "hyp_tones": "3", "ref_tones": "3", "type": "C" }, "6": { "ref_value": null, "ref_index": null, "hyp_value": "玖", "hyp_index": 4, "syllable_type": "S", "hyp_syllable": "jiu", "ref_syllable": null, "tones_type": "S", "hyp_tones": "3", "ref_tones": null, "type": "I" }, "7": { "ref_value": "十", "ref_index": 5, "hyp_value": "十", "hyp_index": 5, "syllable_type": "C", "hyp_syllable": "shi", "ref_syllable": "shi", "tones_type": "C", "hyp_tones": "2", "ref_tones": "2", "type": "C" } }}
|
