编辑距离（edit distance）
做语音识别算法工程师好几年，最近才弄清楚wer与插入错误，删除错误和替换错误的统计算法，真是惭愧。
编辑距离，又称Levenshtein Distance，是一位俄罗斯的科学家Vladimir Levenshtein 在1965年在1965年提出来的。编辑距离指的是在两个字符串S1和S2 之间，将S1转换为S2所需要的最少编辑操作次数。
有三种且仅有三种字符编辑操作：
[En]
There are three and only three character editing operations:
- 插入（Insertion）
- 删除（Deletion）
- 替换（Substitution）
编辑距离的算法公式：
我们将两个字符串 a,b 的编辑距离表示为
，其中和 分别对应字符串a,b的长度。两个字符串 a,b 的编辑距离即可用如下的数学语言表示：
是指字符串a的前个字符和字符串b的前个字符之间的编辑距离。这里的的上限是的长度。注意，字符串的第一个字符的index从 1 开始。
当
，表示字符串a或者b有一个是空字符串，所以，将a转化成b就需要次编辑。
当
, 表示a和b都不是空字符串，a和b的编辑距离等于三种情况下编辑距离的最小值。其中，
- 表示插入编辑，（个人理解：从末尾删除一个字符后的和的编辑距离只需做一次插入操作就和相等）
- 表示删除编辑，
- 且 表示替换编辑，
- 且 表示跳过不做编辑
算法举例：
a: “This great machine can recognize speech”
b: “This machine can wreck a nice beach”
- 首先列一个表格，表格的长度和宽度分别等于|a|+2和|b|+2,行列开头分别填充一个0.
0 this machine can wreck a nice beach 0 this great machine can recognize speech
- 计算当
0 this machine can wreck a nice beach 0 0 1 2 3 4 5 6 7 this 1 great 2 machine 3 can 4 recognize 5 speech 6
- 计算第一行：
0 this machine can wreck a nice beach 0 0 1 2 3 4 5 6 7 this 1 0 1 2 3 4 5 6 great 2 machine 3 can 4 recognize 5 speech 6
计算技巧：只需要计算单元格的上+1，左+1，左上+1（或+0）的值，再进行比较即可。比如计算（1，2）时，上面单元2+1=3，左面单元0+1=1，左上单元，由于this = machine，所以是1+0=1。三者取最小值是1
0 this machine 0 0 1 2 this 1 0 1
- 以此类推，填满整个表格，最右下角的值就是a和b的编辑距离5。
0 this machine can wreck a nice beach 0 0 1 2 3 4 5 6 7 this 1 0 1 2 3 4 5 6 great 2 1 1 2 3 4 5 6 machine 3 2 1 2 3 4 5 6 can 4 3 2 1 2 3 4 5 recognize 5 4 3 2 2 3 4 5 speech 6 5 4 3 3 3 4 5
如，红色路径，对应的回溯路径是c-d-c-c-s-s-i-i.
那么：ref :This great machine can recognize speech
hyp:This machine can wreck a nice beach
再比如绿色路径，对应的额回溯路径是：c-d-c-c-s-i-i-s
那么：ref :This great machine can recognize speech
hyp:This machine can wreck a nice beach
橙色和蓝色回溯路径，同样会导致ref和hyp对应方式不同。但是这些不同的回溯方式不影响最终的识别率wer的值。
上面的例子，不同的回溯路径恰好会使I-D-S相同，但是，有的时候，不用的回溯路径会导致不同的I-D-S。例如：
ref: x, y, z；
hyp: a,b,c,y
回溯路径1：
ref： x y z
hyp: a b c y
回溯路径2：
ref: x y z
hyp:a b c y
上面两种不同的对齐方式，编辑距离一样，wer也一样，但是I-D-S一个是2-1-1，另外一个是 1-0-3。可见，在语言识别wer统计过程中，不同的对其方式会产生不同的I-D-S统计结果。
Original: https://blog.csdn.net/yishujixiaoxiao/article/details/114373775
Author: HELLO BUGs
Title: 编辑距离与语音识别中WER的计算
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/515466/
转载文章受原作者版权保护。转载请注明原作者出处！