本文共 2420 字，大约阅读时间需要 8 分钟。
前几天交接跟问新同事知道编辑距离吗，同事轻描淡写的就说知道啊，动态规划，给我讲了讲，我心想，卧槽，工大的本硕就是不一样。。。
今天有空赶紧恶补下，之前一直听说动态规划动态规划，也没静下心看，今天终于是仔细看了《算法图解》动态规划的问题，就是小偷偷东西最优解的。。。认真读下来发现这本书讲得还真是不错，把挺复杂的知识清晰简单的讲明白了。
看完了动态规划，又继续看莱文斯坦距离，之前项目测各家语音识别结果的时候用的这个算法，当时第一次感受到算法的不仅好玩，还实用。不过只知道这个算法就是通过对字符串的插入、删除、和替换，计算和另一个字符串的相似度，并不知道原理。
明白了动态规划又仔细看了看代码，终于是理解的差不多了。其实也不难，反正就是会者不难、难者不会。。。
ps：《算法图解》这本书一定得看完
最后贴下源代码，自己写了些注释
import numpydef wer2(r, h): ''' This function was originally written by Martin Thoma https://martin-thoma.com/word-error-rate-calculation/ Calculation of WER with Levenshtein distance. Works only for iterables up to 254 elements (uint8). O(nm) time ans space complexity. Parameters ---------- r : list h : list Returns ------- int Examples -------- >>> wer("who is there".split(), "is there".split()) 1 >>> wer("who is there".split(), "".split()) 3 >>> wer("".split(), "who is there".split()) 3 ''' # Initialization #生成一个全是0的二维数组 d = numpy.zeros((len(r)+1)*(len(h)+1), dtype=numpy.uint8) print(d) #此时的d形如：[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] #将二维数组变成n*n的格式 d = d.reshape((len(r)+1, len(h)+1)) print(d) #此时的的形如： """ [[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] """ #为数组两侧赋值 for i in range(len(r)+1): for j in range(len(h)+1): if i == 0: d[0][j] = j elif j == 0: d[i][0] = i print(d) #此时的d形如： """ [[0 1 2 3] [1 0 0 0] [2 0 0 0] [3 0 0 0] ] """ # Computation #计算编辑距离 for i in range(1, len(r)+1): for j in range(1, len(h)+1): if r[i-1] == h[j-1]: d[i][j] = d[i-1][j-1] else: #替换 substitution = d[i-1][j-1] + 1 #插入 insertion = d[i][j-1] + 1 #删除 deletion = d[i-1][j] + 1 print(substitution,insertion,deletion) d[i][j] = min(substitution, insertion, deletion) print(d) #最终的d形如： """ [[0 1 2 3] [1 1 2 3] [2 2 1 2] [3 3 2 2]] """ return d[len(r)][len(h)]if __name__ == '__main__': res=wer2(['c','b','c'],['a','b','d']) print(res) 打印结果：
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]] [[0 1 2 3] [1 0 0 0] [2 0 0 0] [3 0 0 0]] 1 2 2 2 2 3 3 3 4 2 3 2 3 2 4 3 4 3 3 4 2 2 3 3 [[0 1 2 3] [1 1 2 3] [2 2 1 2] [3 3 2 2]] 2
转载地址：http://zcxws.baihongyu.com/