文字列の編集距離例の詳細説明

動的計画法アルゴリズムの問​​題は、大手企業の筆記試験でもよく出題されます。多くのアルゴリズム WeChat 公開アカウントでは、「動的プログラミング」に関する記事がよくありますが、それらはすべて、動的プログラミングを説明するために最もわかりやすい言葉を使用しようとしています。実際、すべての公開記事を注意深く読んでください。アカウントによってプッシュされた記事を読んで理解することができ、誰もが動的プログラミングについて一般的な理解を得ることができます。

動的計画法とは何ですか？平たく言えば、問題の解決策は一目でわかりますが（網羅的なリスト）、それを一つずつ数えることはできません。つまり、最適な解決策を見つけなければなりません。 「少なくとも」「全部で何種類あるか」などの定式化を行うと、これらの問題は動的計画法という考え方を使うことで理論的に解くことができます。 動的プログラミングは分割統治法に似ていますが、部分問題の解を組み合わせて元の問題を解決しますが、各部分問題を一度だけ解決し、再計算せずにテーブルに保存するのが一般的です。最適化問題を解くための——「アルゴリズム入門」。

距離の編集 (Edit Distance) は、この記事では Levenshtein 距離 を指します。つまり、文字列 S1 は、挿入という 3 つの操作を通じて少なくとも S2 の文字列に変換できます。 、変更、削除の回数。例: S1 = abc、S2 = abf、編集距離d = 1 (cをfに変更するだけです)。この記事では、動的計画法のアルゴリズムの考え方を使用して、文字列の編集距離を解決します。 定義：S1とS2

は2つの文字列

を表し、S1(i)はS1の最初の文字を表し、d[i, j]はSを表します番目1のiのプレフィックスからS2のj番目のプレフィックスまで (例: :S1 = ”abc”,S2 = ”def”,S1をS2の編集距離はd[3, 3])です。

1. S

   1 = “abc”、S2 = “dec” の場合、それらの編集距離は d[3, 3] = 2 となり、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], if S1 = ”abc ", S2 という状況も存在します。 =「デフォルト」。 S1をS2に変換するプロセスは"modify"ですが、"insert"、を通じて削除することもできます。 「」 」 はS1をS2に変換します。

1)文字列S1の最後に文字「f」を挿入 S1[i] = S2[j]の場合、S1のときの編集距離はS2に変換されますはd[4, 3] = d[3, 2]です。したがって、d[i, j]=d[i, j - 1] + 1を取得します。 (+1はS1に”f”を加えたからです) ２）この時点で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"の動的計画法の解法過程を表で表現すると良いでしょう。 。

赤い四角形が必要な最終編集距離であり、解決プロセス全体がこのテーブル —— 2 次元配列を埋めることであることがわかります。以下は、それぞれ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 中国語 Web サイトの他の関連記事を参照してください。