8.动态规划(1)——字符串的编辑距离

  动态规划的算法题往往都是各大公司笔试题的常客。在不少算法类的微信公众号中,关于“动态规划”的文章屡见不鲜,都在试图用最浅显易懂的文字来描述讲解动态规划,甚至有的用漫画来解释,认真读每一篇公众号推送的文章实际上都能读得懂,都能对动态规划有一个大概了解。

  什么是动态规划?通俗地理解来说,一个问题的解决办法一看就知道(穷举),但不能一个一个数啊,你得找到最优的解决办法,换句话说题目中就会出现类似“最多”、“最少”,“一共有多少种”等提法,这些题理论上都能使用动态规划的思想来求解。动态规划与分治方法类似,都是通过组合子问题的解来求解原问题,但它对每个子问题只求解一次,将其保存在表格中,无需重新计算,通常用于求解最优化问题——《算法导论》

  编辑距离(Edit Distance),在本文指的是Levenshtein距离,也就是字符串S1通过插入、修改、删除三种操作最少能变换成字符串S2的次数。例如:S1 = abc,S2 = abf,编辑距离d = 1(只需将c修改为f)。在本文中将利用动态规划的算法思想对字符串的编辑距离求解。

  定义:S1、S2表示两个字符串,S1(i)表示S1的第一个字符,d[i, j]表示S1的第i个前缀到S2的第j个前缀(例如:S1 = ”abc”,S2 = ”def”,求解S1到S2的编辑距离为d[3, 3])。

  1.   若S1 = ”abc”, S2 = ”dec”,此时它们的编辑距离为d[3, 3] = 2,观察两个字符串的最后一个字符是相同的,也就是说S1(3) = S2(3)不需要做任何变换,故S1 = ”abc”, S2 = ”dec” <= > S1’ = ”ab”, S2’ = ”de”,即当S1[i] = S[j]时,d[i, j] = d[i-1,j -1]。得到公式:d[i, j] = d[i - 1, j - 1] (S1[i] = S2[j])
  2.   上面一条得出了当S1[i] = S2[j]的计算公式,显然还有另一种情况就是S1[i] ≠ S2[j],若S1 = ”abc”, S2 = ”def”。S1变换到S2的过程可以“修改”,但还可以通过“插入”、“删除”使得S1变换为S2。

    1)在S1字符串末位插入字符“f”,此时S1 = ”abcf”,S2 = ”def”,此时即S1[i] = S2[j]的情况,S1变换为S2的编辑距离为d[4, 3] = d[3, 2]。所以得出d[i, j]=d[i, j - 1] + 1。(+1是因为S1新增了”f”)

    2)在S2字符串末位插入字符“c”,此时S1 = ”abc”,S2 = ”defc”,此时即S1[i] = S[j]的情况,S1变换为S2的编辑距离为d[3, 4] = d[2, 3]。所以得出d[i, j]=d[i - 1, j] + 1,实际上这是对S1做了删除。(+1是因为S2新增了”c”)

    3)将S1字符串末位字符修改为”f”,此时S1 = ”abf”,S2 = ”def”,此时即S1[i] = S[j]的情况,S1变换为S2的编辑距离为d[3, 3] = d[2, 2]。所以得出d[i, j] = d[i – 1, j - 1] + 1。(+1是因为S1修改了“c”)

  综上,得出递推公式:

=>

  不妨用表格表示出动态规划对S1=”abc”,S2=“def”的求解过程。

  可以看出红色方块即是最终所求的编辑距离,整个求解过程就是填满这个表——二维数组。下面是Java、Python分别对字符串编辑距离的动态规划求解。

Java

  1 package com.algorithm.dynamicprogramming;
  2 
  3 /**
  4  * 动态规划——字符串的编辑距离
  5  * s1 = "abc", s2 = "def"
  6  * 计算公式:
  7  *          | 0                                           i = 0, j = 0
  8  *          | j                                           i = 0, j > 0
  9  * d[i,j] = | i                                           i > 0, j = 0
 10  *          | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1])    s1(i) = s2(j)
 11  *          | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]+1)  s1(i) ≠ s2(j)
 12  * 定义二维数组[4][4]:
 13  *      d e f            d e f
 14  *   |x|x|x|x|        |0|1|2|3|
 15  * a |x|x|x|x|  =>  a |1|1|2|3|  => 编辑距离d = [3][3] = 3
 16  * b |x|x|x|x|      b |2|2|2|3|
 17  * c |x|x|x|x|      c |3|3|3|3|
 18  *
 19  * Created by yulinfeng on 6/29/17.
 20  */
 21 public class Levenshtein {
 22 
 23     public static void main(String[] args) {
 24         String s1 = "abc";
 25         String s2 = "def";
 26         int editDistance = levenshtein(s1, s2);
 27         System.out.println("s1=" + s1 + "与s2=" + s2 + "的编辑距离为:" + editDistance);
 28     }
 29 
 30     /**
 31      * 编辑距离求解
 32      * @param s1 字符串s1
 33      * @param s2 字符串s2
 34      * @return 编辑距离
 35      */
 36     private static int levenshtein(String s1, String s2) {
 37         int i = 0;  //s1字符串中的字符下标
 38         int j = 0;  //s2字符串中的字符下标
 39         char s1i = 0;   //s1字符串第i个字符
 40         char s2j = 0;   //s2字符串第j个字符
 41         int m = s1.length();    //s1字符串长度
 42         int n = s2.length();    //s2字符串长度
 43         if (m == 0) {   //s1字符串长度为0,此时的编辑距离就是s2字符串长度
 44             return n;
 45         }
 46         if (n == 0) {
 47             return m;   //s2字符串长度为0,此时的编辑距离就是s1字符串长度
 48         }
 49         int[][] solutionMatrix = new int[m + 1][n + 1];     //求解矩阵
 50         /**
 51          *      d e f
 52          *   |0|x|x|x|
 53          * a |1|x|x|x|
 54          * b |2|x|x|x|
 55          * c |3|x|x|x|
 56          */
 57         for (i = 0; i < m + 1; i++) {
 58             solutionMatrix[i][0] = i;
 59         }
 60         /**
 61          *      d e f
 62          *   |0|1|2|3|
 63          * a |x|x|x|x|
 64          * b |x|x|x|x|
 65          * c |x|x|x|x|
 66          */
 67         for (j = 0; j < n + 1; j++) {
 68             solutionMatrix[0][j] = j;
 69         }
 70         /**
 71          * 上面两个操作后,求解矩阵变为
 72          *      d e f
 73          *   |0|1|2|3|
 74          * a |1|x|x|x|
 75          * b |2|x|x|x|
 76          * c |3|x|x|x|
 77          * 接下来就是填充剩余表格
 78          */
 79         for (i = 1; i < m + 1; i++) {   //i = 1,j = 1, 2, 3,以行开始填充
 80             s1i = s1.charAt(i - 1);
 81             for (j = 1; j < n + 1; j++) {
 82                 s2j = s2.charAt(j - 1);
 83                 int flag = (s1i == s2j) ? 0 : 1;    //根据公式,如果s1[i] = s2[j],则d[i,j]=d[i-1,j-1],如果s1[i] ≠ s2[j],则其中一个公式为d[i,j]=d[i-1,j-1]+1
 84                 solutionMatrix[i][j] = min(solutionMatrix[i][j-1] + 1, solutionMatrix[i-1][j] + 1, solutionMatrix[i-1][j-1] + flag);
 85             }
 86         }
 87         return solutionMatrix[m][n];
 88     }
 89 
 90     /**
 91      * 根据公式求解编辑距离
 92      * @param insert s1插入操作
 93      * @param delete s1删除操作
 94      * @param edit s1修改操作
 95      * @return 编辑距离
 96      */
 97     private static int min(int insert, int delete, int edit) {
 98         int tmp = insert < delete ? insert : delete;
 99         return tmp < edit ? tmp : edit;
100     }
101 }

  Python3

 1 '''
 2     动态规划——字符串的编辑距离
 3     s1 = "abc", s2 = "def"
 4     计算公式:
 5              | 0                                           i = 0, j = 0
 6              | j                                           i = 0, j > 0
 7     d[i,j] = | i                                           i > 0, j = 0
 8              | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1])    s1(i) = s2(j)
 9              | min(d[i,j-1]+1, d[i-1,j]+1, d[i-1,j-1]+1)  s1(i) ≠ s2(j)
10     定义二维数组[4][4]:
11         d e f            d e f
12     |x|x|x|x|        |0|1|2|3|
13     a |x|x|x|x|  =>  a |1|1|2|3|  => 编辑距离d = [4][4] = 3
14     b |x|x|x|x|      b |2|2|2|3|
15     c |x|x|x|x|      c |3|3|3|3|
16 '''
17 def levenshtein(s1, s2):
18     i = 0   #s1字符串中的字符下标
19     j = 0   #s2字符串中的字符下标
20     s1i = ""    #s1字符串第i个字符
21     s2j = ""    #s2字符串第j个字符
22     m = len(s1) #s1字符串长度
23     n = len(s2) #s2字符串长度
24     if m == 0:
25         return n    #s1字符串长度为0,此时的编辑距离就是s2字符串长度
26     if n == 0:
27         return m    #s2字符串长度为0,此时的编辑距离就是s1字符串长度
28     solutionMatrix = [[0 for col in range(n + 1)] for row in range(m + 1)]  #长为m+1,宽为n+1的矩阵
29     '''
30              d e f
31           |0|x|x|x|
32         a |1|x|x|x|
33         b |2|x|x|x|
34         c |3|x|x|x|
35     '''
36     for i in range(m + 1):
37         solutionMatrix[i][0] = i
38     '''
39              d e f
40           |0|1|2|3|
41         a |x|x|x|x|
42         b |x|x|x|x|
43         c |x|x|x|x|
44         
45     '''
46     for j in range(n + 1):
47         solutionMatrix[0][j] = j
48     '''
49         上面两个操作后,求解矩阵变为
50              d e f
51           |0|1|2|3|
52         a |1|x|x|x|
53         b |2|x|x|x|
54         c |3|x|x|x|
55         接下来就是填充剩余表格
56     '''
57     for x in range(1, m + 1):
58         s1i = s1[x - 1]
59         for y in range(1, n + 1):
60             s2j = s2[y - 1]
61             flag = 0 if s1i == s2j  else 1
62             solutionMatrix[x][y] = min(solutionMatrix[x][y-1] + 1, solutionMatrix[x-1][y] + 1, solutionMatrix[x-1][y-1] + flag)
63 
64     return solutionMatrix[m][n]
65 
66 def min(insert, delete, edit):
67     tmp = insert if insert < delete else delete
68     return tmp if tmp < edit else edit
69 
70 s1 = "abc"
71 s2 = "def"
72 distance = levenshtein(s1, s2)
73 print(distance) 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏calmound

zoj 1315 Excuses, Excuses!

题意:简单题,读懂题目就很好写了,这里要说的是,题目并没有叙述每句话里的单词长度是多少,所以导致我的数组开小了,一直SF,后来把数组开大后就A了        ...

35850
来自专栏程序生活

Leetcode-Easy 657. Judge Route Circle

657. Judge Route Circle 描述: 题目很简单,就是判断路线能否组成一圈。向“右”走的步数一定要等于向“左”走的步数;向“下”走的步数一...

31040
来自专栏数据结构与算法

洛谷 P1313 计算系数

题目描述 给定一个多项式 ,请求出多项式展开后 项的系数。 输入输出格式 输入格式: 输入文件名为factor.in。 共一行,包含5 个整数,分别为 a...

32830
来自专栏王肖的UT

GLSL-内置函数

76730
来自专栏程序生活

Tensorflow教程(十三) tf.Variable() 和tf.get_variable()1 简介2 区别3 实例

25230
来自专栏desperate633

LintCode 奇偶分割数组题目分析代码

8610
来自专栏Bingo的深度学习杂货店

Q152 Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) wh...

44070
来自专栏机器学习从入门到成神

机器学习中数据处理与可视化的python、numpy等常用函数

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

13810
来自专栏前端黑板报

一个数字截取引发的精度问题(四)

这篇是精度问题的最后一篇,要是想看前面的,请看微信历史记录。 做前端的都感觉JS这语言巨坑无比,兼容性让你摸不到头脑,甚至还会让你脱发。一些初学者遇到: 0.1...

273100
来自专栏mathor

matlab—回归与内插(完结)

66440

扫码关注云+社区

领取腾讯云代金券