这篇文章是尝试给像作者一样的算法爱好者(业余的委婉说法)解释一下编辑距离求解方法的思考过程,其实也是为了强迫自己真正的吃透编辑距离求解的方法论,以期能达到举一反三的效果。根据以上受众定位,我首先还是引入一段对编辑距离的解释,然后再从递归到递推(动态规划)讲讲对这个问题求解本身的正向思考过程,而不是拿到一个解法来说明它的正确性。
编辑距离的定义是用增删改三种操作将一个字符串演变为一个目标字符串所需的操作次数。比如将horse转化为ros,可以是如下步骤:
1)删除h变成orse; 2)删除o变成rse; 3)增加o变成rose; 4)删除e变成ros
也可以是如下步骤:
1)改h为r变成rorse; 2)删r变成rose; 3)删e变成ros
显然第二种策略要优于第一种,但是这种演变策略的排列组合随着源串a和目的串b的长度增长会几何级数的增长。我们需要用程序来求解。
这是一个典型的考动态规划的编程题,很多文章都会给出一个递推公式,但是这个递推公式为何正确,得到这个公式的思考过程是啥,为什么这么思考?回答了这几个问题才算理解了编辑距离的精髓,而且才能有举一反三的可能性。看了很多解释的文章,感觉都是从结果来理解和解释递推过程反证过程的有效性,隔靴搔痒,没有讲到这个公式是怎么得来的,怎么一下子就能得出这么精妙的计算方法,感觉就像现在解释机器学习模型的原理那样,训练出来一个有效的神经网络结构,然后再试图解释每一层是在干嘛,然而并不是一开始设计的时候就知道会是这样。但编辑距离这个算法是完全由人想出来的,必然是有设计者的心路历程可循。下面讲下我对这个问题的理解思路。
最容易想到的方法是递归,递归函数以目标字符串和源字符串为输入参数,代码如下:
1 2 3 4 5 6 7 8 9 |
def lev(a, b): if len(a) == 0 or len(b) == 0: return max(len(a),len(b)) if a[0] == b[0]: return lev(a[1:],b[1:]) #首字符相等则跳过 ADD = lev(a,b[1:]) # add b[0]到a的开始, 问题转化为求a,b[1:]的编辑距离,因为头部相同的字符不增加编辑距离 DEL = lev(a[1:],b) # del a[0] REP = lev(a[1:],b[1:]) # set a[0] = b[0], 问题转为求a[1:],b[1:],原因同计算a的解释 return 1 + min(ADD,DEL,REP) |