字串的編輯距離實例詳解

　　動態規劃的演算法題往往都是各大公司筆試題的常客。在不少演算法類的微信公眾號中，關於「動態規劃」的文章屢見不鮮，都在試圖用最淺顯易懂的文字來描述講解動態規劃，甚至有的用漫畫來解釋，認真讀每一篇公眾號推送的文章其實都能讀懂，都能對動態規劃有個大概了解。

　　什麼是動態規劃？通俗地理解來說，一個問題的解決辦法一看就知道（窮舉），但不能一個一個數啊，你得找到最優的解決辦法，換句話說題目中就會出現類似“最多”、“最少”，“一共有多少種”等提法，這些題理論上都能使用動態規劃的思想來求解。 動態規劃與分治方法類似，都是透過組合子問題的解來求解原問題，但它對每個子問題只求解一次，將其保存在表格中，無需重新計算，通常用於求解最最佳化問題——《演算法導論》#。

　　編輯距離（Edit Distance），本文指的是Levenshtein距離，也就是字串S1透過插入、修改、刪除三種運算最少能轉換成字串S2#的次數。例如：S1 = abc，S2 = abf，編輯距離d = 1#（只需將c修改為f）。在本文中將利用動態規劃的演算法思想對字串的編輯距離求解。

　　定義：S1、S2表示兩個字串，S1(i)表示S 1的第一個字元，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         }          
         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 f12     |x|x|x|x|        
   |0|1|2|3|13     a |x|x|x|x|  =>  a |1|1|2|3|  => 编辑距离d = [4][4] = 314     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 f31           |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] = i38     '''39       
      d e f40           |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] = j48     '''49         
       上面两个操作后，求解矩阵变为50              d e f51           |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 162             
        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 delete68     
        return tmp if tmp < edit else edit69 70 s1 = "abc"71 s2 = "def"72 distance = levenshtein(s1, s2)73 print(distance)

 

##

以上是字串的編輯距離實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！