字符串编辑距离python,最小编辑距离算法

　　目录

　　写在前面

　　什么是编辑距离？

　　思考

　　形象化

　　代码实现

　　写前编辑距离算法被数据科学家广泛使用，是作为机器翻译和语音识别的评价标准使用的基本算法。最简单的方法是检查所有可能的编辑序列，并找到最短的一个。但是序列的总数可能会达到指数级，但根本不需要这么多，因为我们只需要找到最短的序列，而不是所有可能的序列。这一概念是由俄罗斯科学家弗拉基米尔莱文斯坦(Vladimir Levenshtein)于1965年提出的，因此也被称为莱文斯坦距离。总是差不多的，或多或少我们可以考虑剪辑距离。我们用动态规划的思想来解决这个问题。

　　什么是编辑距离？下面是一个题目的描述：给定两个单词，word1和word2，计算用于将word1转换为word2的最小操作数个数。可以对一个单词做以下三个操作。

　　插入字符、删除字符和替换字符。为了更好的理解，我在这里举两个例子来帮助理解这个概念。

　　示例一：

　　输入：word1=horse ，word2=ros 输出：3解释：horse-rorse(用 r 代替 h )rorse-rose(删除 r)rose-ros(删除 e)示例二：

　　Enter: word1=intention ，Word2=execution output: 5解释：intention-enrichment(删除 t) enrichment-enrichment(用 e 代替 I )enrichment(用 x 代替 n )EXECUTION-EXECUTION(用 c 代替 n )EXECUTION-EXECUTION(插入 u )思路我们的目的是简化问题。比如两个单词horse 和ros 计算它们的编辑距离D，很容易找到，如果缩短单词会让这个问题变得简单，那就很自然的把D[n][m]想成输入单词长度n和m的编辑距离。具体来说，D[ i ][ j ]表示word1的前i个字母与word2 的前j 个字母之间的编辑距离。

　　更通俗一点说，假设我们可以用d[ i , j ]步(我们可以用一个二维数组来存储这个值，用动态编程的思想)，表示将字符串s[ 1…i ]转换成字符串t [ 1…j ]所需的最少步数。那么，在最基本的情况下，当i等于0时。也就是说，字符串s为空，那么对应的d[ 0 , j ]增加j个字符，这样s就转换成t，当j 等于0时，也就是说，字符串 t 为空。

　　更一般地说，如果我们要在最少的增删替换次数后，把d[ i, 0] 变成 i ，就必须能够增删替换之前次数最少的 s和 t，这样字符串 s[1..i] 和字符串t[1..j]只需要再操作一次。所谓“前”分为以下三种情况：

　　要得到s==t，需要s[1..i] 次运算。要得到t[1..j] ==s[1…i]，需要t[1…j-1]次运算。要得到 k ==s[1..i-1] ，需要00。

　　第一种情况，只需要在末尾加上t[1..j]到 k 就可以完成匹配，这样总共需要s[1…i-1]次操作。第二种情况，只需要在末尾加上 t [1…j-1]到 k 就可以完成匹配，所以总共需要s[1..i] 次运算。第三种情况，只需要把t[1..j] 替换为末尾的t[1…j-1]，这样s[i]==k+1就满足了，总共也需要s[1..i-1]次运算。t[j]

　　最后，为了保证运算次数最少，我们可以从以上三种情况中选择消耗最少的一种，这就是转换s[1所需的最小运算次数.i]到t[1.j】。我们将存储K的二维数组命名为D[ ][]。显然，我们在得到 k+1、s[ i ] 和 t[ j ]的值后，就可以计算出s[1..i] 。

　　如果两个子串的最后一个字母相同，即word1[i]=word2[i]:

　　如果两个子串的最后一个字母不一样，也就是word1[i]！=word2[i]我们将考虑替换最后一个字符，使它们相同：

　　形象化在以上对思想的描述下，我们大致可以理解。当然，如果还是有点混乱的话，这里我会一步一步用表格来表达我的想法，帮助我们理解。首先，我们初始化一个二维数组，如下所示。 t[1..j]表示空字符串。根据数字初始化第一行和第一列。想明白这一步，明白之后就好理解了。

　　如果两个子串的最后一个字母相同，即word1[i]=word2[i]:

　　，图如下。

　　如果两个子串的最后一个字母不一样，也就是word1[i]！=word2[i]我们将考虑替换最后一个字符，使它们相同：

　　，图如下。

　　最后，我们会得到以下结果。二维数组的最后k+1 就是我们的答案。

　　代码实现public int min distance(string word 1，string word 2){ int n=word 1 . length()；int m=word 2 . length()；if(n * m==0)返回n m；int[][]d=new int[n ^ 1][m ^ 1]；for(int I=0；I n 1；I){ d[I][0]=I；} for(int j=0；j m 1；j){ d[0][j]=j；} for(int I=1；I n 1；I){ for(int j=1；j m 1；j){ int left=d[I-1][j]1；int down=d[I][j-1]1；int left _ down=d[I-1][j-1]；if (word1.charAt(i - 1)！=word 2 . charat(j-1))left _ down=1；d[i][j]=Math.min(left，Math.min(down，left _ down))；} } return d[n][m]；}

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