基于动态规划的计算两个字符串的编辑距离

字符串编辑距离： 是一种字符串之间相似度计算的方法。给定两个字符串S、T，将S转换成T所需要的删除，插入，替换操作的数量就叫做S到T的编辑路径。而最短的编辑路径就叫做字符串S和T的编辑距离。

eg：S=“eeba” T=”abac” 我们可以按照这样的步骤转变：(1) 将S中的第一个e变成a;(2) 删除S中的第二个e;(3)在S中最后添加一个c; 那么S到T的编辑路径就等于3。当然，这种变换并不是唯一的，但如果3是所有变换中最小值的话。那么我们就可以说S和T的编辑距离等于3了。

动态规划(dynamic programming)是一种解决复杂问题最优解的策略。它的基本思路就是：将一个复杂的最优解问题分解成一系列较为简单的最优解问题，再将较为简单的的最优解问题进一步分解，直到可以一眼看出最优解为止。

动态规划算法是解决复杂问题最优解的重要算法。其算法的难度并不在于算法本身的递归难以实现，而主要是编程者对问题本身的认识是否符合动态规划的思想。现在我们就来看看动态规划是如何解决编辑距离的。

动态规划解决编辑距离
还是这个例子：S=“eeba” T=”abac” 。我们发现当S只有一个字符e、T只有一个字符a的时候，我们马上就能得到S和T的编辑距离edit(0,0)=1(将e替换成a)。那么如果S中有1个字符e、T中有两个字符ab的时候，我们是不是可以这样分解：edit(0,1)=edit(0,0)+1(将e替换成a后，在添加一个b)。如果S中有两个字符ee，T中有两个字符ab的时候，我们是不是可以分解成：edit(1,1)=min(edit(0,1)+1, edit(1,0)+1, edit(0,0)+f(1,1)). 这样我们可以得到这样一些动态规划公式：
如果i=0且j=0 edit(0, 0)=1
如果i=0且j>0 edit(0, j )=edit(0, j-1)+1
如果i>0且j=0 edit( i, 0 )=edit(i-1, 0)+1
如果i>0且j>0 edit(i, j)=min(edit(i-1, j)+1, edit(i,j-1)+1, edit(i-1,j-1)+f(i , j) )

小注：edit(i,j)表示S中[0…. i]的子串 si 到T中[0….j]的子串t1的编辑距离。f(i,j)表示S中第i个字符s(i)转换到T中第j个字符s(j)所需要的操作次数，如果s(i)==s(j)，则不需要任何操作f(i, j)=0； 否则，需要替换操作，f(i, j)=1 。

编辑距离的实际应用
baidu、google等知名全文搜索系统。当我们输入一个错误的query=”Jave” 的时候，返回中有大量包含正确的拼写 “Java”的网页。

编辑距离在自然语言文本处理领域(NLP)中是计算字符串相似度的重要方法。一般而言，对于中文语句的相似度处理，我们很多时候都是将词作为一个基本操作单位，而不是字(字符)。