介绍

编辑距离是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个（或哪几个）是比较可能的字。DNA 也可以视为用 A、C、G 和 T 组成的字符串，因此编辑距离也用在生物信息学中，判断二个 DNA 的类似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。

编辑距离有几种不同的定义，差异在可以对字符串进行的处理。

• 在莱文斯坦距离中，可以删除、加入、取代字符串中的任何一个字元，也是较常用的编辑距离定义，常常提到编辑距离时，指的就是莱文斯坦距离。
• 也存在其他编辑距离的定义方式，例如 Damerau-Levenshtein 距离是一种莱文斯坦距离的变种，但允许以单一操作交换相邻的两个字符（称为字符转置），如 AB→BA 的距离是 1（交换）而非 2（先删除再插入、或者两次替换）。
• LCS（最长公共子序列）距离只允许删除、加入字元。
• Jaro 距离只允许字符转置。
• 汉明距离只允许取代字元。

问题

给出两个字符串 str1 和 str2，以及以下可以对 str1 进行的操作。请找出将 "str1" 转换为 "str2" 所需的最少编辑（操作）次数。

• 插入
• 删除
• 替换

上述所有操作的成本都相同。

在这种情况下，有哪些子问题？从两个字符串的左边或右边开始，一个一个地处理所有字符。让我们从右边开始遍历，每一对被遍历的字符都有两种可能。

m: Length of str1 (first string)
n: Length of str2 (second string)

• 如果两个字符串的最后一个字符相同，则什么都不做。忽略最后一个字符，获得其余字符串的计数。所以我们对长度为 m-1 和 n-1 的字符串进行递归。

• 否则（如果最后一个字符不一样），我们考虑对'str1' 的所有操作，考虑对第一个字符串的最后一个字符的所有三个操作，递归计算所有三个操作的最小成本，取三个值中的最小值。

  • 插入。递归计算 m 和 n-1。
  • 删除。对 m-1 和 n 进行递归。
  • 替换。对 m-1 和 n-1 进行递归。

递归法

// Javascript program to find minimum numberoperations to convert str1 to str2
function min(x, y, z) {
  if (x <= y && x <= z) return x;
  if (y <= x && y <= z) return y;
  else return z;
}
 
function editDist(str1, str2, m, n) {
  // If first string is empty, the only option is to insert all characters of second string into first
  if (m == 0) return n;
  // If second string is empty, the only option is to remove all characters of first string
  if (n == 0) return m;

  // If last characters of two strings are same, nothing much to do. Ignore last
  // characters and get count for remaining strings.
  if (str1[m - 1] == str2[n - 1]) return editDist(str1, str2, m - 1, n - 1);

  // If last characters are not same, consider all three operations on last character of first
  // string, recursively compute minimum cost for all three operations and take minimum of three values.
  return 1 + min(editDist(str1, str2, m, n - 1), // Insert
    editDist(str1, str2, m - 1, n), // Remove
    editDist(str1, str2, m - 1, n - 1)); // Replace
}

上述解决方案的时间复杂性是指数级的。在最坏的情况下，我们最终可能要进行 O (3^m) 次操作。最坏的情况是，两个字符串中没有一个字符匹配。下面是最坏情况下的递归调用图。辅助空间是 O (1)，因为没有额外的空间被利用。

我们可以看到，许多子问题被反复解决，例如，eD (2, 2) 被调用三次。由于相同的子问题被再次调用，这个问题具有重叠子问题的特性。因此，编辑距离问题具有动态规划问题的两种属性。像其他典型的动态规划 (DP) 问题一样，可以通过构建一个存储子问题结果的临时数组来避免相同子问题的重新计算。

动态规划法

// A Dynamic Programming based Javascript program to find minimum number operations to convert str1 to str2
function min(x,y,z) {
  if (x <= y && x <= z) return x;
  if (y <= x && y <= z) return y;
  else return z;
}
 
function editDistDP(str1,str2,m,n) {
  // Create a table to store results of subproblems
  let dp = new Array(m + 1);
  for(let i=0;i<m+1;i++) {
    dp[i]=new Array(n+1);
    for(let j=0;j<n+1;j++) dp[i][j]=0;
  }

  // Fill d[][] in bottom up manner
  for (let i = 0; i <= m; i++) {
    for (let j = 0; j <= n; j++) {
      // If first string is empty, only option is to insert all characters of second string
      if (i == 0) dp[i][j] = j; // Min. operations = j

      // If second string is empty, only option is to remove all characters of second string
      else if (j == 0) dp[i][j] = i; // Min. operations = i

      // If last characters are same, ignore last char and recur for remaining string
      else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1];

      // If the last character is different, consider all possibilities and find the minimum
      else dp[i][j] = 1 + min(dp[i][j - 1], // Insert
                           dp[i - 1][j], // Remove
                           dp[i - 1][j - 1]); // Replace
    }
  }

  return dp[m][n];
}

或者：

/*
Wikipedia -> https://en.wikipedia.org/wiki/Edit_distance

Q. -> Given two strings `word1` and `word2`. You can perform these operations on any of the string to make both strings similar.
    - Insert
    - Remove
    - Replace
Find the minimum operation cost required to make both same. Each operation cost is 1.

Algorithm details ->
time complexity - O(n*m)
space complexity - O(n*m)
*/

const minimumEditDistance = (word1, word2) => {
  const n = word1.length
  const m = word2.length
  const dp = new Array(m + 1).fill(0).map(item => [])

  /*
    fill dp matrix with default values -
        - first row is filled considering no elements in word2.
        - first column filled considering no elements in word1.
    */
  for (let i = 0; i < n + 1; i++) dp[0][i] = i;
  for (let i = 0; i < m + 1; i++) dp[i][0] = i;

  /*indexing is 1 based for dp matrix as we defined some known values at first row and first column/*/
  for (let i = 1; i < m + 1; i++) {
    for (let j = 1; j < n + 1; j++) {
      const letter1 = word1[j - 1]
      const letter2 = word2[i - 1]

      if (letter1 === letter2) dp[i][j] = dp[i - 1][j - 1];
      else dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1;
    }
  }

  return dp[m][n]
}

• 时间复杂度：O (m x n)
• 辅助空间：O (m x n)

降低空间复杂度

在上面给出的方法中，我们需要 O (m x n) 空间。如果字符串的长度大于 2000，这就不合适了，因为它只能创建 2000×2000 的二维数组。为了填补 DP 数组中的一行，我们只需要一行，即上面的一行。例如，如果我们要在 DP 数组中填充 i = 10 行，我们只需要第 9 行的值。所以我们只需创建一个 2 x str1 长度的 DP 数组。这种方法减少了空间的复杂性。

// A Space efficient Dynamic Programming based Javascript program to find minimum number operations to convert str1 to str2
function EditDistDP(str1, str2) {
  let len1 = str1.length;
  let len2 = str2.length;

  // Create a DP array to memoize result of previous computations
  let DP = new Array(2);
  for(let i = 0; i < 2; i++) {
    DP[i] = new Array(len1+1);
    for(let j = 0; j < len1 + 1; j++) DP[i][j] = 0;
  }

  // Base condition when second String is empty then we remove all characters
  for (let i = 0; i <= len1; i++) DP[0][i] = i;

  // Start filling the DP, This loop run for every character in second String
  for (let i = 1; i <= len2; i++) {
      // This loop compares the char from second String with first String characters
      for (let j = 0; j <= len1; j++) {
          // if first String is empty then we have to perform add character operation to get second String
          if (j == 0) DP[i % 2][j] = i;
          // if character from both String is same then we do not perform any operation . here i % 2 is for bound the row number.
          else if (str1[j-1] == str2[i-1]) DP[i % 2][j] = DP[(i - 1) % 2][j - 1];
          // if character from both String is not same then we take the minimum from three specified operation
          else DP[i % 2][j] = 1 + Math.min(DP[(i - 1) % 2][j], Math.min(DP[i % 2][j - 1], DP[(i - 1) % 2][j - 1]));
      }
  }

  // after complete fill the DP array if the len2 is even then we end up in the 0th row else we end up
  // in the 1th row so we take len2 % 2 to get row
  return DP[len2 % 2][len1];
}

• 时间复杂度：O (m x n)
• 辅助空间：O (m)

带缓存的递归

这是递归的缓存版本，即自上而下的 DP。

function minDis(s1,s2,n,m,dp) {
  // If any String is empty, return the remaining characters of other String
  if(n == 0) return m;
  if(m == 0) return n;
               
  // To check if the recursive tree for given n & m has already been executed
  if(dp[n][m] != -1) return dp[n][m];
                  
  // If characters are equal, execute recursive function for n-1, m-1
  if(s1[n - 1] == s2[m - 1]) {         
    if(dp[n - 1][m - 1] == -1) return dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp);         
    else return dp[n][m] = dp[n - 1][m - 1]; 
  }
    
  // If characters are nt equal, we need to find the minimum cost out of all 3 operations.    
  else {         
    let m1, m2, m3; // temp variables 
    if(dp[n-1][m] != -1) m1 = dp[n - 1][m];             
    else m1 = minDis(s1, s2, n - 1, m, dp);    
              
    if(dp[n][m - 1] != -1) m2 = dp[n][m - 1];          
    else m2 = minDis(s1, s2, n, m - 1, dp);    
     
    if(dp[n - 1][m - 1] != -1) m3 = dp[n - 1][m - 1];    
    else m3 = minDis(s1, s2, n - 1, m - 1, dp);     
    
    return dp[n][m] = 1 + Math.min(m1, Math.min(m2, m3));      
  }
}

参考

• Edit distance - Wikiwand (opens new window)
• 编辑距离 - Wikiwand (opens new window)
• Edit Distance | DP-5 - GeeksforGeeks (opens new window)