编辑距离与字符错误率CER-Toy模板网

这篇具有很好参考价值的文章主要介绍了编辑距离与字符错误率CER。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

在语音识别场景中，字符错误率（Character Error Rate，CER）是衡量语音识别效果的一个重要指标。下文将介绍CER的原理，并且给出python实现的代码。

1 编辑距离

说到CER，不得不提的是编辑距离（Edit Distance），它是一个用来衡量两个序列的相似度指标。

假设有两个字符串（a和b），编辑距离是指把字符串a修改成b（或者把b改成a）需要的最少编辑次数。编辑的操作只能有三种：

插入（Insertion）
删除（Deletion）
替换（Substitution）

比如，把cat修改成cafe可以这样编辑：

cat --> caf（替换）
caf --> cafe（插入）

也可以这样编辑：

cat --> cate（插入）
cate --> cafe（替换）

1.1 原理

将两个字符串a和b的编辑距离表示为 $lev_{a,b}$ 。之所以用 $l e v$ ，是因为编辑距离的作者叫Levenshtein，所以编辑距离也叫Levenshtein Distance。

用 $lev_{a,b}(i,j)$ 表示字符串a的前i个字符与b的前j个字符间的编辑距离，比如， $lev_{cat,cafe}(2,3)$ 就表示ca与caf之间编辑距离。

Levenshtein Distance的思路就是，要计算字符串之间的距离，先计算子串间的距离，要计算子串间的距离，先计算子子串间的距离，如此分解下去。用数学语言表示，就是下面这个公式

$lev_{a,b}(i,j)=\begin{cases} max(i,j) & \text{ if } min(i,j)=0 \\ min\begin{cases} lev_{a,b}(i-1,j)+1 \\ lev_{a,b}(i,j-1)+1 \\ lev_{a,b}(i-1,j-1)+sign(a_i,b_j) \end{cases} & \text{ if } min(i,j)\neq0 \end{cases}$
其中，
$sign(a_i,b_j)=\begin{cases} 0 & \text { if } a_i = b_j \\ 1 & \text { if } a_i \neq b_j \end{cases}$

$m i n (i, j) = 0$ 说明有一个子串是空的，什么都没有，要修改成另外一个子串，光插入字符就行，所以需要的最少编辑次数就是 $m a x (i, j)$ 。比如 $lev_{cat,cafe}(2,0)=lev_{ca,空白}=2$ 。
$\neq 0$ 的时候， $lev_{a,b}(i,j)$ 等于以下三种情况的最小值：
- $lev_{a,b}(i-1,j)+1$
- $lev_{a,b}(i,j-1)+1$
- $lev_{a,b}(i-1,j-1)+sign(a_i,b_j)$
  
  以cat和cafe为例， $lev_{cat, cafe}$ 等于以下三种情况的最小值：
1. $lev_{ca, cafe}+1$ ，cat的子串ca与cafe求编辑距离再加1，加1是因为 $lev_{ca, cat}=1$ 。
2. $lev_{cat, caf}+1$ ，cafe的子串caf与cat求编辑距离再加1，加1是因为 $lev_{caf, cafe}=1$ 。
3. $lev_{ca, caf}+1$ ，cat和cafe各自的子串ca和caf求编辑距离再加1，加1是因为(ca)t替换成(caf)e需要一次操作。

根据上面的公式可知，当 $i = ∣ a ∣, j = ∣ b ∣$ 时， $lev_{a,b}=lev_{a,b}(i,j)$ ，其中 $∣ a ∣$ 和 $∣ b ∣$ 分别表示a和b的长度。

1.2 演算过程

编辑距离的计算过程可以用一个矩阵来记录。

以cat和cafe为例，建立一个矩阵，用来记录计算的中间结果：

		c	a	f	e
	0	1	2	3	4
c	1	$a_{1,1}$	$a_{1,2}$	$a_{1,3}$	$a_{1,4}$
a	2	$a_{2,1}$	$a_{2,2}$	$a_{2,3}$	$a_{2,4}$
t	3	$a_{3,1}$	$a_{3,2}$	$a_{3,3}$	$a_{3,4}$

第二行的01234表示从什么都没有到c、ca、caf、cafe分别需要的最少编辑次数；同样地，第二列的0123表示从什么都没有到c、ca、cat分别需要的最少编辑次数。

$a_{1,1}=min(a_{1,0}+1,a_{0,1}+1,a_{0,0})$

$a_{1,2}=min(a_{1,1}+1,a_{0,2}+1,a_{0,1}+1)$

$a_{2,1}=min(a_{1,1}+1,a_{2,0}+1,a_{1,0}+1)$

……

最终的矩阵如下：

		c	a	f	e
	0	1	2	3	4
c	1	0	1	2	3
a	2	1	0	1	2
t	3	2	1	1	2

可以找出规律， $每个格子的值 = m i n (上方格子的值 + 1 ，左方格子的值 + 1 ，左上方格子 + (0 或 1))$ ，0还是1取决于格子左边的字母是否等于格子上面的字母。

1.3 代码实现

找到编辑距离的计算规律后，代码实现就不难了。python代码如下：

def edit_distance(str1, str2):
    """计算两个字符串之间的编辑距离。
    Args:
        str1: 字符串1。
        str2: 字符串2。
    Returns:
        dist: 编辑距离。
    """
    matrix = [[i + j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)]
    for i in range(1, len(str1) + 1):
        for j in range(1, len(str2) + 1):
            if str1[i - 1] == str2[j - 1]:
                d = 0
            else:
                d = 1
            matrix[i][j] = min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + d)
    dist = matrix[len(str1)][len(str2)]
    return dist

2 字符错误率

弄清楚编辑距离的原理后，理解字符错误率（CER）就很简单了。假设我说了一句话a，被语音识别系统识别成b，那么 $cer=lev_{a,b}\div|a|$ ，就这么简单，所以代码也很简单：

def get_cer(src, trg):
    """把源字符串src修改成目标字符串trg的字符错误率。
    Args:
        src: 源字符串。
        trg: 目标字符串。
    Returns:
        cer: 字符错误率。
    """
    dist = edit_distance(src, trg)
    cer = dist / len(trg)
    return cer