编辑距离 动态规划 python,求最小编辑距离

　　1.编辑距离定义今天我们来研究一个有趣的算法问题，叫做字符串编辑距离。距离研究的问题和最长公共子序列的问题类似，都是比较两个字符串的相似度，只是采用的标准不同。

　　首先给出编辑距离的定义：设A和B是两个字符串，用最少的字符运算将字符串A转换成字符串B。这里提到的字符操作包括：

　　(1)删除一个字符(delete)；

　　(2)插入一个字符；

　　(3)将一个字符改为另一个字符(替换)。

　　将字符串A转换为字符串B所使用的字符操作数的最小数目称为字符串A到B的编辑距离，通常三次操作的代价是相同的，即每一次字符操作都会导致一次转换，这也符合我们通常的认知。但是，有时也可以对这三种运算应用不同的影响因子，使算法趋向于某种变换，这可以通过修改三种运算的代价来实现。

　　其实也可以包含更多的字符操作。比如在英文输入的过程中，经常会出现两个字符不小心互换的问题(trueture)，那么就可以增加一个新的操作——换位，也就是把相邻的两个字符互换。此时编辑距离升级为Damerau-Levenshteindistance，包括插入、删除、替换、替换四个操作。OCR应用程序中还有其他操作：将两个字符合并为一个字符或将一个字符拆分为两个字符。当然，字符操作也可以减少。例如，仅使用替换操作来查找两个长度相等的字符串的汉明距离。还有，在寻找最长公共子序列(LCS)的问题上，实际上等价于我们只使用插入和删除操作。虽然共同序列是在LCS发现的，但我们也可以发现它们之间的简化版编辑距离。

　　2.编辑距离属性编辑距离具有以下属性：

　　两个字符串的最小编辑距离至少是两个字符串的长度差；两个字符串之间的最大编辑距离最多为两个字符串中较长字符串的长度；当且仅当两个字符串相同时，两个字符串之间的编辑距离为零；如果两个字符串长度相等，则编辑距离的上限为汉明距离；编辑距离满足三角不等式，即d (a，c) d (a，b) d (b，c)；如果两个字符串有相同的前缀或后缀，删除相同的前缀或后缀对编辑距离没有影响，其他位置不能随意删除。

　　3.编辑距离的应用

　　距离编辑被广泛使用，最初的应用是拼写检查和近似字符串匹配。在生物医学领域，科学家把DNA看成由A、S、G、T组成的字符串，然后用编辑距离来判断不同DNA的相似性。至于近似字符串匹配，LCS也是一个不错的选择，它在不同的问题中都有自己的位置。

　　编辑距离的另一个很好的用途是在语音识别中，它被用作一个评估指标。语音测试集中的每一句话都有一个标准答案，然后用编辑距离来判断识别结果与标准答案的差异。不同的错误可以反映识别系统中存在的问题。如果识别结果中有很多插入错误，说明识别结果中有很多漏字。一个可能的原因是VAD做的不好；或者识别结果中有很多替换错误，很可能是训练过程中的语言模型不好。

　　再看另一个应用。在linux下，我们经常使用diff命令或vimdiff命令来逐行比较两个文件之间的差异。运行该命令后，将显示两个文件之间的差异。显示方式实际上是根据编辑距离来定义的：在哪个位置插入或删除多少行，或者替换哪些行。所以我们可以使用编辑距离来实现diff命令。

　　3.实现这个问题的算法，像LCS，也是用动态规划来解决的。定义了dij表示长度为I的字符串A变成长度为j的字符串B所需的编辑距离，需要注意的是，如果字符串A的最终长度为M，字符串B的最终长度为N，那么D矩阵就是(M ^ 1)*(N ^ 1)的矩阵，因为它可以表示长度为0的字符串之间的转换。它的递推公式满足：

　　我们来解释一下上面的公式。前两行是初始化，分别代表字符串B和A为空时对应的编辑距离计算。当字符串B为空时，我们只需要不断地删除字符来改变A为B，否则，我们需要不断地添加字符。初始化完矩阵D的第一行第一列后，我们就可以根据第三行的公式计算出矩阵的剩余元素了。第(I，j)个元素在计算时依赖于它的三个相邻位置(i-1，j-1)，(I，j-1)和(i-1，j)。公式的整体结构与LCS和DTW非常相似。唯一的难点是哪个位置对应删除操作，哪个位置对应插入操作。从公式中可以看出，( i-1，j)对应于删除操作，( I，j-1)对应于插入操作。可以理解，现在把字符串a(1，i-1)转换成b(1，J)需要Di-1和J步。在将a(1，I)转换为b(1，j)时，我们可以直接删除字符a(i)，问题就变成了a(1，i-1)转换为B(同理，现在需要di，j-1运算将字符串a(1，I)转换为b(1，j-1)，那么在将a(1，I)转换为b(1，j)时，我们可以将b(j)加到a(1，I)的末尾(此时，a(1，I)对应的代码实现如下

　　/* *计算a-b的编辑距离* dist[i][j]表示长度为I的字符串变成长度为J的字符串所需的编辑距离* operation[i][j]表示变换过程中的相应操作* 0:正确；1:字符替换；2:插入；3:Delete */int edit _ distance(char * a，char * b){ int len _ a=strlen(a)；int len _ b=strlen(b)；//b是空字符串。将A改为B需要不断删除A的字符for(int I=0；I=len _ a；I){ dist[I][0]=I；操作[I][0]=3；}//a是空字符串。将A改为B需要不断地添加B的字符for(int j=0；j=len _ b；j){ dist[0][j]=j；操作[0][j]=2；}运算[0][0]=0；for(int I=1；I=len _ a；I){ for(int j=1；j=len _ b；j ){int cost=(a[i-1]==b[j-1]？0 : 1);int deletion=dist[I-1][j]1；int insertion=dist[I][j-1]1；int替换=dist[i-1][j-1]成本；//如果不回溯，就用下面这句//dist [i] [j]=min(删除，min(插入，替换))；if(deletion insertion){ if(substitution insertion){ dist[I][j]=insertion；运算[I][j]=2；} else { dist[I][j]=substitution；操作[I][j]=成本；} } else { if(substitution deletion){ dist[I][j]=deletion；运算[I][j]=3；} else { dist[I][j]=substitution；操作[I][j]=成本；}}}}return dist[len_a][len_b]。}很多时候，我们不是简单的找剪辑距离，还有具体的操作步骤。这可以通过回溯上述代码计算的运算矩阵来实现。回溯代码如下：

　　void back trace(int operation[][MAX _ l EN 1]，char* a，char* b){int插入=0，删除=0，替换=0；int i，j；int len 1=strlen(a)；int len 2=strlen(b)；for (i=len1，j=len2I=0j=0；){ switch(operation[I][j]){ case 0://printf((% d，%d) right\n ，I，j)；printf(pos %d right\n ，I)；I-；j-；继续；case 1://printf((%d，% d)替换\n ，I，j)；printf( pos % d substitute(% c-% c)\ n ，I，a[i-1]，b[j-1])；I-；j-；替代；继续；案例2://printf((% d，%d) insert\n ，I，j)；printf(pos %d insert (%c)\n ，I，b[j-1])；j-；插入；继续；案例3://printf((% d，%d) delete\n ，I，j)；printf(pos %d delete (%c)\n ，I，a[I-1])；I-；删除；继续；}}printf(插入：%d，删除：%d，替换：%d\n ，插入，删除，替换)；}可以测试上面的代码，也可以根据上面的代码自行扩展，比如实现diff命令或者实现扩展编辑距离等。其实Damerau-Levenshteindistance的扩展在了解了基本的编辑距离之后也很简单，无非就是增加一个替换操作。递归公式如下：

　　作为一个经典的字符串动态编程话题，编辑距离有着非常重要的应用。希望你能熟练掌握。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。