Ausführliche Erläuterung der Beispiele für den Bearbeitungsabstand von Zeichenfolgen

Fragen zu dynamischen Programmieralgorithmen sind häufig häufige Fragen in schriftlichen Prüfungen großer Unternehmen. In vielen öffentlichen WeChat-Konten werden Artikel zum Thema „dynamische Programmierung“ verwendet. Sie alle versuchen, die dynamische Programmierung mit den einfachsten und verständlichsten Worten zu beschreiben und zu erklären Tatsächlich können alle durch die Nummer geschobenen Artikel gelesen und verstanden werden, und jeder kann ein allgemeines Verständnis der dynamischen Programmierung erlangen.

Was ist dynamische Programmierung? Laienhaft ausgedrückt kann man die Lösung eines Problems auf einen Blick erkennen (erschöpfende Liste), aber man kann sie nicht einzeln aufzählen. Mit anderen Worten: Es wird Fragen wie „die“ geben „am meisten“ und „am meisten“ in der Frage „Mindestens“, „wie viele Arten gibt es insgesamt“ und anderen Formulierungen können diese Fragen theoretisch mit der Idee der dynamischen Programmierung gelöst werden. Dynamische Programmierung ähnelt der Divide-and-Conquer-Methode. Sie löst das ursprüngliche Problem durch die Kombination der Lösungen von Teilproblemen, löst jedoch jedes Teilproblem nur einmal und speichert es in einer Tabelle ohne Neuberechnung Wird normalerweise zur Lösung optimaler Probleme verwendet —— „Einführung in Algorithmen“ .

Distanz bearbeiten (Bearbeiten Distanz), bezieht sich in diesem Artikel auf die Distanz Levenshtein , bei der es sich um die Zeichenfolge S1Die Mindesthäufigkeit , die durch die drei Vorgänge Einfügen , Ändern und Löschen in eine Zeichenfolge S2 umgewandelt werden kann. Zum Beispiel: S1 = abc, S2 = abf, Abstand bearbeiten d = 1 ( Es muss nur c in f geändert werden. In diesem Artikel wird die Algorithmusidee der dynamischen Programmierung verwendet, um den Bearbeitungsabstand von Zeichenfolgen zu lösen.

Definition: S1, S2

stellt zwei Zeichenfolgen dar , S1(i) stellt S dar. Die erste Zeichen von 1, d[i, j] bedeutet S1s tes i Präfix zum jten Präfix von S2 (z. B. :S1 = "abc" ,S2 = "def",Lösen Sie den Bearbeitungsabstand von S1 bis S2 als d[3 , 3]).

1. Wenn

   S1 = „abc“, S2 = „dec“, dann ist ihr Bearbeitungsabstand d[3, 3] = 2, beachten Sie dass das letzte Zeichen der beiden Zeichenfolgen dasselbe ist, d. h. S1(3) = S2(3) erfordert keine Transformation, also S1 = “abc“, S2 = „dec“ <= > S1' = "ab", S2' = "de", das heißt, wenn S1[i] = S[j], , d [i, j] = d[i-1,j -1]. Holen Sie sich die Formel: d[i, j] = d[i - 1, j - 1] (S1[i] = S2[j])

2. Die obige Formel ergibt die Berechnungsformel , wenn S1[i] = S2[j] Offensichtlich gibt es eine andere Situation, in der S1[. i] ≠ S2[j], wenn S1 = „abc“, S2 = „def“. Der Prozess der Konvertierung von S1 in S2 kann "geändert", Sie können aber auch " bis "" einfügen, "löschen “ bewirkt, dass sich S1 in S2 verwandelt.

1) Fügen Sie das

Zeichen „f“S1 ein 🎜>, zu diesem Zeitpunkt S1 = “abcf“, S2 = „def“, zu diesem Zeitpunkt d. h. S1[i] = S2[j] Im Fall von beträgt der Bearbeitungsabstand von S1, umgewandelt in S2, d[4, 3] = d[ 3, 2]. Also erhalten wir d[i, j]=d[i, j - 1] + 1. (+1 liegt daran, dass S1 “f“ hinzugefügt hat)　2 )Einfügen das Zeichen

„c“ am Ende der Zeichenfolge S2, dann S1 = „abc“ , S2 = „defc“, dies ist der Fall von S1[i] = S[j], S1 in S2 ist d[3, 4] = d[2, 3] . Wir erhalten also d[i, j]=d[i - 1, j] + 1 Tatsächlich geschieht dies für S1 Löschen. (+1 liegt daran, dass S2 “c“ hinzugefügt hat)　3 ) Ändern S1

das letzte Zeichen der Zeichenfolge bis “f“, zu diesem Zeitpunkt S1 = "abf" , S2 = "def", zu diesem Zeitpunkt, S1[i] = S[j] Im Fall von beträgt der Bearbeitungsabstand der Transformation von S1 in S2 d[3, 3] = d[2, 2]. Wir erhalten also d[i, j] = d[i – 1, j - 1] + 1. (+1 liegt daran, dass S1 "c" geändert hat) Zusammenfassend erhalten wir die Rekursionsformel:

=>

Sie können genauso gut einen Tisch dazu verwenden Drücken Sie die dynamische Planung aus. Der Lösungsprozess von S1=“abc“, S2=“def“.

Es ist ersichtlich, dass das rote Quadrat der erforderliche endgültige Bearbeitungsabstand ist und der gesamte Lösungsprozess darin besteht, diese Tabelle auszufüllen — —Zweidimensionales Array. Im Folgenden finden Sie die dynamischen Programmierlösungen für den String-Bearbeitungsabstand in Java bzw. 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 }

Das obige ist der detaillierte Inhalt vonAusführliche Erläuterung der Beispiele für den Bearbeitungsabstand von Zeichenfolgen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!