显示Levenshtein距离的结果

Question

给定两个字符串（s1，s2），Levenshtein距离是将s1更改为s2所需的最小操作次数，反之亦然。

我想显示将s1更改为s2的结果。例如，更改星期日到星期六需要3次操作。我需要显示S ++ u +日。 “+”用于每个需要的操作。

Answer 1

这是一个JavaScript代码片段，它返回你想要的东西。如果您熟悉dynamic programming algorithm，您应该可以遵循此代码。返回字符串r和处理min/curMin的所有字符串操作/操作都是从原始版本更改的。

function edits(t, s) { 
    var r = ""; 
    if (s === t) { 
     return s; 
    } 
    var n = s.length, m = t.length; 
    if (n === 0 || m === 0) { 
     return "+".repeat(n + m); 
    } 
    var x, y, a, b, c, min = 0; 
    var p = new Array(n); 
    for (y = 0; y < n;) 
     p[y] = ++y; 
    for (x = 0; x < m; x++) { 
     var e = t.charCodeAt(x); 
     c = x; 
     b = x + 1; 
     var currMin = min; 
     min = n + 1; 
     for (y = 0; y < n; y++) { 
      a = p[y]; 
      if (a < c || b < c) { 
       b = (a > b ? b + 1 : a + 1); 
      } 
      else { 
       if (e !== s.charCodeAt(y)) { 
        b = c + 1; 
       } 
       else { 
        b = c; 
       } 
      } 
      if (b < min) { 
       min = b; 
      } 
      p[y] = b; 
      c = a; 
     } 
     if (min > currMin) { 
      r += "+"; 
     } 
     else { 
      r += t[x]; 
     } 
    } 
    return r; 
} 

EDIT：上面的实施，是速度和空间优化，从而可能难以阅读的版本。下面的实施是JS version from Wikipedia的修改版本，应该更易于遵循。

function getEditDistance(a, b) { 
    if(a.length === 0) return "+".repeat(b.length); 
    if(b.length === 0) return "+".repeat(a.length); 

    var matrix = []; 

    // increment along the first column of each row 
    var i; 
    for(i = 0; i <= b.length; i++){ 
     matrix[i] = [i]; 
    } 

    // increment each column in the first row 
    var j; 
    for(j = 0; j <= a.length; j++){ 
     matrix[0][j] = j; 
    } 

    var r = "", min = 0;; 

    // Fill in the rest of the matrix 
    for(i = 1; i <= b.length; i++){ 

     var currMin = min; 
     min = a.length + 1; 

     for(j = 1; j <= a.length; j++){ 

      if(b.charAt(i-1) == a.charAt(j-1)){ 
       matrix[i][j] = matrix[i-1][j-1]; 
      } else { 
       matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, // substitution 
        Math.min(matrix[i][j-1] + 1, // insertion 
         matrix[i-1][j] + 1)); // deletion 
      } 

      if (matrix[i][j] < min) { 
       min = matrix[i][j]; 
      } 
     } 

     if (min > currMin) { 
      r += "+"; 
     } 
     else { 
      r += b[i-1]; 
     } 
    } 
    return r; 
} 

EDIT2：增加该算法和例如输出

下面的解释是从输入字符串“小猫”和“坐”的的Levenshtein矩阵。我在原始算法中改变的是，我添加了一个检查，如果当前行的最小值大于前一行的最小值，并且如果是，则在当前行中存在编辑并因此添加“+”。如果不是，并且当前行的“编辑成本”与以前相同。然后不需要编辑，我们只是将当前字符添加到结果字符串中。可以按照通过在图像中的行的算法行（开始于行1和列1）

实例：

> getEditDistance("kitten", "sitting"); 
'+itt+n+' 
> getEditDistance("Sunday", "Saturday"); 
'S++u+day'