动态规划法（十一）编辑距离

傷城~ 2022-04-02 15:52 280阅读 0赞

### 编辑距离问题 ###

什么是两个字符串的编辑距离（edit distance）？给定字符串s1和s2，以及在s1上的如下操作：

*  插入（Insert）一个字符
 *  移除（Remove）一个字符
 *  替换（Replace）一个字符

试问最小需要多少次这样的操作才能使得s1转换为s2？  
  比如，单词“cat”和“hat”，这样的操作最少需要一次，只需要把“cat”中的“c”替换为“h”即可。单词“recall”和“call”，这样的操作最少需要两次，只需要把“recall”中的“r”和“e”去掉即可。单词“Sunday”和“Saturday”，这样的操作最少需要3次，在“Sunday”的“S”和“u”中插入“a”和“t”，再把“n”替换成“r”即可。  
  那么，是否存在一种高效的算法，能够快速、准确地计算出两个字符串的编辑距离呢？

### 动态规划算法 ###

我们使用动态规划算法（Dynamic Programming）来计算出两个字符串的编辑距离。  
  我们从两个字符串s1和s2的最末端向前遍历来考虑。假设s1的长度为m，s2的长度为n，算法如下：

1.  如果两个字符串的最后一个字符一样，那么，我们就可以递归地计算长度为m-1和n-1的两个字符串的情形；
2.  如果两个字符串的最后一个字符不一样，那么，进入以下三种情形：
    
     *  插入： 递归地计算长度为m和n-1的两个字符串的情形，这是因为在s1中的末端插入了一个s2的最后一个字符，这样s1和s2的末端字符一样，就是1中情形；
     *  删除： 递归地计算长度为m-1和n的两个字符串的情形，这是在s1中的末端删除了一个字符；
     *  替换： 递归地计算长度为m-1和n-1的两个字符串的情形，这是因为把s1中末端字符替换成了s2的最后一个字符，这样s1和s2的末端字符一样，就是1中情形；

这样，我们就有了子结构问题。对于动态规划算法，我们还需要一个初始化的过程，然后中间维护一张二维表即可。初始化的过程如下: 如果m为0，则至少需要操作n次，即在s1中逐个添加s2的字符，一共是n次；如果n为0，则至少需要操作m次，即把s1的字符逐个删除即可，一共是m次。

### Python实现 ###

利用DP算法解决两个字符串的编辑距离的Python代码如下：

# -*- coding: utf-8 -*-
    # using Dynamic Programming to solve edit distance problem
    
    
    # s1, s2 are two strings
    def editDistDP(s1, s2):
    
       m, n = len(s1), len(s2)
       # Create a table to store results of subproblems
       dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
    
       # using DP in bottom-up manner
       for i in range(m + 1):
           for j in range(n + 1):
    
               # If first string is empty, only option is to
               # isnert all characters of second string, thus the
               # min opration is j
               if i == 0:
                   dp[i][j] = j
    
               # If second string is empty, only option is to
               # remove all characters of second string, thus the
               # min opration is i
               elif j == 0:
                   dp[i][j] = i
    
               # If last characters are same, ignore last character
               # and recursive for remaining string
               elif s1[i-1] == s2[j-1]:
                   dp[i][j] = dp[i-1][j-1]
    
               # If last character are different, consider all
               # possibilities and find minimum of inserting, removing, replacing
               else:
                   dp[i][j] = 1 + min(dp[i][j-1],  # Insert
                                      dp[i-1][j],  # Remove
                                      dp[i-1][j-1])  # Replace
    
       return dp[m][n]
    
    
    # Driver program
    s1 = "sunday"
    s2 = "saturday"
    edit_distance = editDistDP(s1, s2)
    print("The Edit Distance of '%s' and '%s' is %d."%(s1, s2, edit_distance))

输出结果如下：

The Edit Distance of 'sunday' and 'saturday' is 3.

### Java实现 ###

利用DP算法解决两个字符串的编辑距离的Java代码如下：

package DP_example;
    
    
    // 计算两个字符串的编辑距离(Edit Distance)
    public class Edit_Distance { 
    
       // 主函数
       public static void main(String[] args) { 
           String str1 = "cat";//"Sunday";
           String str2 = "hat";//"Saturday";
           int edit_dist = edit_distance(str1, str2);
           System.out.println(String.format("The edit distance of '%s' and '%s' is %d.",
                   str1, str2, edit_dist));
       }
    
       /* 函数edit_distanc: 计算两个字符串的编辑距离(Edit Distance) 传入参数: 两个字符串str1和str2 返回: 编辑距离 */
       public static int edit_distance(String str1, String str2){ 
    
           // 字符串的长度
           int m = str1.length();
           int n = str2.length();
    
           // 初始化表格，用于维护子问题的解
           int[][] dp = new int[m+1][n+1];
           for(int i=0; i <= m; i++)
               for(int j=0; j <= n; j++)
                   dp[i][j] = 0;
    
           // using DP in bottom-up manner
           for(int i=0; i <= m; i++){ 
               for(int j=0; j <= n; j++) { 
                   /* If first string is empty, only option is to * isnert all characters of second string, thus the * min opration is j */
                   if(i == 0) {  dp[i][j] = j;}
    
                   /* If second string is empty, only option is to * remove all characters of second string, thus the * min opration is i */
                   else if(j == 0){ dp[i][j] = i;}
    
                   /* If last characters are same, ignore last character * and recursive for remaining string */
                   else if(str1.charAt(i-1) == str2.charAt(j-1)){ 
                       dp[i][j] = dp[i-1][j-1];
                   }
    
                   /*If last character are different, consider all *possibilities and find minimum of inserting, removing, replacing */
                   else{ 
                       /* * dp[i][j-1]: Insert * dp[i-1][j]: Remove * dp[i-1][j-1]: Replace */
                       dp[i][j] = 1 + min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]);
                   }
               }
           }
    
           return dp[m][n];
       }
    
       public static int min(int i, int j){ 
           return (i <= j) ? i : j;
       }
    
    }

输出结果如下：

The edit distance of 'cat' and 'hat' is 1.

### 其它实现方式 ###

以上，我们用Python和Java以及动态规划算法自己实现了编辑距离的计算。当然，我们也可以调用第三方模块的方法，比如NTLK中的edit\_distance()函数，示例代码如下：

# 利用NLTK中的edit_distance计算两个字符串的Edit Distance
    
    from nltk.metrics import edit_distance
    
    s1 = "recall"
    s2 = "call"
    t = edit_distance(s1, s2)
    print("The Edit Distance of '%s' and '%s' is %d." % (s1, s2, t))

输出结果如下：

The Edit Distance of 'recall' and 'call' is 2.

### 总结 ###

在本文中，我们对于两个字符串的编辑距离的计算，只采用了插入、删除、替换这三种操作，在实际中，可能还会有更多的操作，比如旋转等。当然，这并不是重点，重点是我们需要了解解决这类问题的算法，即动态规划算法。在后续的文章中，笔者会介绍编辑距离在文本处理中的应用。  
  本次分享到此结束，欢迎大家交流~~

注意：本人现已开通微信公众号： Python爬虫与算法（微信号为：easy\_web\_scrape）， 欢迎大家关注哦~~

发表评论取消回复

表情：

评论列表（有 0 条评论，280人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode 编辑距离动态规划

> 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。 > 你可以对一个单词进行如下三种操作： > 插入一个字符

「爱情、让人受尽委屈。」/ 2023年08月17日 15:43/ 0 赞/ 216 阅读

相关经典动态规划：编辑距离

点击关注上方“五分钟学算法”，设为“置顶或星标”，第一时间送达干货。 ![format_png][] 转自面向大象编程本期例题：LeetCode 72. Edit

爱被打了一巴掌/ 2023年02月11日 04:56/ 0 赞/ 19 阅读

相关 LeetCode72. 编辑距离【动态规划】

难度：困难题目描述： > 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。 > > 你可以对一个单词进行

Love The Way You Lie/ 2023年01月22日 09:53/ 0 赞/ 30 阅读

相关 ACM 动态规划编辑距离

很久没有更博了..刚开学忙得飞起0..0 最近刷题发现自己有意逃避算法题，很生气啊自己居然潜意识逃避了... 所以今天很认真的写个动态规划！虽然这是最简单的动态规划..

野性酷女/ 2022年07月12日 09:52/ 0 赞/ 314 阅读

相关详解编辑距离问题(动态规划)

问题描述: 对于序列S和T, 它们之间的距离定义为: 对二者其一进行几次以下操作: 1, 删除一个字符; 2, 插入一个字符; 3, 改变一个字符. 每进行一次操作, 计

朴灿烈づ我的快乐病毒、/ 2022年04月23日 22:56/ 0 赞/ 384 阅读

相关动态规划-用编辑距离解释

动态规划-用编辑距离解释文章目录动态规划-用编辑距离解释前言状态转移递归实现迭代实现

分手后的思念是犯贱/ 2022年04月23日 05:38/ 0 赞/ 321 阅读

相关动态规划之编辑距离问题*

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4

「爱情、让人受尽委屈。」/ 2022年04月22日 02:08/ 0 赞/ 292 阅读

相关动态规划法（十一）编辑距离

编辑距离问题什么是两个字符串的编辑距离（edit distance）？给定字符串s1和s2，以及在s1上的如下操作：插入（Insert）一个字符移

傷城~/ 2022年04月02日 15:52/ 0 赞/ 281 阅读

相关【leetcode】编辑距离（动态规划）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

旧城等待，/ 2022年02月27日 04:16/ 0 赞/ 301 阅读

相关【动态规划】编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符删除一

缺乏、安全感/ 2021年10月03日 02:38/ 0 赞/ 443 阅读