Explication détaillée des exemples de distance d'édition de chaînes

Les questions sur les algorithmes de programmation dynamique sont souvent des questions fréquentes lors des examens écrits des grandes entreprises. Dans de nombreux comptes publics algorithmiques de WeChat, les articles sur la « programmation dynamique » sont courants. Ils essaient tous d'utiliser les mots les plus compréhensibles pour décrire et expliquer la programmation dynamique. En fait, tous utilisent des bandes dessinées pour l'expliquer. les articles poussés par le compte peuvent être lus et compris, et tout le monde peut avoir une compréhension générale de la programmation dynamique.

Qu'est-ce que la programmation dynamique ? En termes simples, la solution à un problème peut être connue d'un coup d'oeil (liste exhaustive), mais on ne peut pas les compter une à une. Il faut trouver la solution optimale. Autrement dit, il y aura des questions comme "le plus". et "le plus" dans la question Au moins", "Combien de types y a-t-il au total" et d'autres formulations, ces problèmes peuvent théoriquement être résolus en utilisant l'idée de programmation dynamique. La programmation dynamique est similaire à la méthode diviser pour régner. Elle résout le problème d'origine en combinant les solutions des sous-problèmes, mais elle ne résout chaque sous-problème qu'une seule fois et l'enregistre dans un tableau sans recalcul. généralement utilisé pour résoudre le problème optimal. —— "Introduction aux algorithmes" .

Modifier la distance (Modifier Distance), dans cet article fait référence à Levenshteindistance , qui est la chaîne S1Le nombre minimum de fois qui peut être converti en chaîne S2 grâce aux trois opérations d'insertion , de modification et de suppression. Par exemple : S1 = abc, S2 = abf, modifier la distance d = 1 ( il suffit de changer c en f). Dans cet article, l'idée de l'algorithme de programmation dynamique sera utilisée pour résoudre la distance d'édition des chaînes.

Définition : S1, S2 représente deux chaînes , S1(i) représente S La première le caractère de 1, d[i, j] signifie S1le ème i préfixe au jième préfixe de S2 (par exemple :S1 = "abc" ,S2 = "def",Résoudre la distance d'édition de S1 à S2 comme d[3 , 3]).

1. Si S1 = « abc », S2 = « dec », alors leur distance d'édition est d[3, 3] = 2 , observez que le dernier caractère des deux chaînes est le même, c'est-à-dire que S1(3) = S2(3) ne nécessite aucune transformation, donc S1 = ”abc”, S2 = “dec” <= > S1' = "ab", S2' = "de", c'est-à-dire lorsque S1[i] = S[j], , d [i, j] = d[i-1,j -1]. Obtenez la formule : d[i, j] = d[i - 1, j - 1] (S1[i] = S2[j])

2. Celle ci-dessus donne la formule de calcul lorsque S1[i] = S2[j] Il existe évidemment une autre situation où S1[. i] ≠ S2[j], si S1 = « abc », S2 = « def ». Le processus de conversion de S1 en S2 peut être «modifié», Mais vous pouvez également insérer " en passant par "", "supprimer ” fait S1 transformé en S2.

1) Insérez le caractère "f"S1 chaîne 🎜>, à ce moment S1 = ”abcf”, S2 = “def”, à ce moment soit S1[i] = S2[j] Dans le cas de , la distance d'édition de S1 transformée en S2 est d[4, 3] = d[3, 2]. On obtient donc d[i, j]=d[i, j - 1] + 1. (+1 est parce que S1 a ajouté ”f”)

　2 )Insérer le caractère

« c » à la fin de la chaîne S2, puis S1 = « abc » , S2 = ”defc”, c'est le cas de S1[i] = S[j], S1 en S2 est d[3, 4] = d[2, 3] . On obtient donc d[i, j]=d[i - 1, j] + 1 En fait, cela se fait à S1. Supprimer. (+1 est parce que S2 a ajouté ”c”)　3 ) Modifier

S1

le dernier caractère de la chaîne à ”f”, à cet instant S1 = "abf" , S2 = "def", à cet instant, S1[i] = S[j] Dans le cas de , la distance d'édition de transformation de S1 en S2 est d[3, 3] = d[2, 2]. On obtient donc d[i, j] = d[i – 1, j - 1] + 1. (+1 c'est parce que S1 modifié "c") En résumé, on obtient la formule de récursion :

=>

Autant utiliser une table pour exprimer la planification dynamique Le processus de solution de S1=”abc”, S2=”def”.

On peut voir que le carré rouge est la distance d'édition finale requise, et tout le processus de solution consiste à remplir ce tableau — —Tableau bidimensionnel. Voici les solutions de programmation dynamique pour la distance d'édition de chaînes en Java et Python respectivement.

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 }

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!