是否有一種更有效的方法來處理這種差異函數？

Question

我有一個C＃函數，它可以逐行比較兩個字符串oldString和newString。每個比較僅在引號內考慮大小寫。例如，這兩條線都是平等的：

If Foo Then: Debug.Print "Hello World!" 
If foo Then: Debug.print "Hello World!" 

而這兩個不相等：

If Foo Then: Debug.Print "Hello World!" 
If Foo Then: Debug.Print "hello world!" 

該函數返回newString構建一個新的文件，但只要有不變線，從oldString線被用來代替。因此，如果這是oldString：

If Foo Then 
    Debug.Print "Hello World!" 
End If 
Debug.Print "This line will be deleted soon." 

這是newString：

If foo Then 
    Debug.print "Hello World!" 
    Debug.print "This is a new line." 
End If 

然後函數返回此：

If Foo Then 
    Debug.Print "Hello World!" 
    Debug.print "This is a new line." 
End If 

目前我正在使用基於動態規劃這個代碼處理最長的公共子串問題，並進行一些簡單的優化：

public static string FixCase(string oldString, string newString) { 
    if (string.Equals(oldString, newString, StringComparison.InvariantCulture)) { 
     return newString; 
    } 

    var oldLines = oldString.Split(new[] { "\r\n" }, StringSplitOptions.None).ToList(); 
    var newLines = newString.Split(new[] { "\r\n" }, StringSplitOptions.None).ToList(); 

    var headEqualLines = new List<string>(); 
    var minLineCount = oldLines.Count < newLines.Count ? oldLines.Count : newLines.Count; 
    for (var i = 0; i < minLineCount; i++) { 
     if (VbaLineEqual(oldLines[i], newLines[i])) { 
      headEqualLines.Add(oldLines[i]); 
     } else { 
      break; 
     } 
    } 
    oldLines.RemoveRange(0, headEqualLines.Count); 
    newLines.RemoveRange(0, headEqualLines.Count); 
    minLineCount -= headEqualLines.Count; 
    var tailEqualLines = new List<string>(); 
    if (oldLines.Count > 0 && newLines.Count > 0) { 
     for (var i = 1; i <= minLineCount; i++) { 
      if (VbaLineEqual(oldLines[oldLines.Count - i], newLines[newLines.Count - i])) { 
       tailEqualLines.Add(oldLines[oldLines.Count - i]); 
      } else { 
       break; 
      } 
     } 
     tailEqualLines.Reverse(); 
     oldLines.RemoveRange(oldLines.Count - tailEqualLines.Count - 1, tailEqualLines.Count); 
     newLines.RemoveRange(newLines.Count - tailEqualLines.Count - 1, tailEqualLines.Count); 
    } 

    var lengths = new int[oldLines.Count + 1, newLines.Count + 1]; 
    for (var i = 0; i < oldLines.Count; i++) { 
     for (var j = 0; j < newLines.Count; j++) { 
      if (VbaLineEqual(oldLines[i], newLines[j])) 
       lengths[i + 1, j + 1] = lengths[i, j] + 1; 
      else 
       lengths[i + 1, j + 1] = lengths[i + 1, j] > lengths[i, j + 1] ? lengths[i + 1, j] : lengths[i, j + 1]; 
     } 
    } 
    var result = new List<string>(); 
    var x = oldLines.Count; 
    var y = newLines.Count; 
    while (x != 0 && y != 0) { 
     if (lengths[x, y] == lengths[x - 1, y]) { 
      x--; 
     } else if (lengths[x, y] == lengths[x, y - 1]) { 
      result.Add(newLines[y - 1]); 
      y--; 
     } else { 
      result.Add(oldLines[x - 1]); 
      x--; 
      y--; 
     } 
    } 
    while (y != 0) { 
     result.Add(newLines[y - 1]); 
     y--; 
    } 
    result.Reverse(); 
    return string.Join("\r\n", headEqualLines.Concat(result).Concat(tailEqualLines)); 
} 

static bool VbaLineEqual(string oldLine, string newLine) { 
    if (string.Equals(oldLine, newLine, StringComparison.InvariantCulture)) 
     return true; 
    if (!string.Equals(oldLine, newLine, StringComparison.InvariantCultureIgnoreCase)) 
     return false; 
    var quoting = false; 
    for (var i = 0; i < oldLine.Length; i++) { 
     if (quoting && oldLine[i] != newLine[i]) 
      return false; 
     if (oldLine[i] == '"') 
      quoting = !quoting; 
    } 
    return true; 
} 

但是，當我使用5,000行左右的行對一對字符串執行此操作並在開始和結束附近進行更改時，性能和內存使用率都相當可怕，可能是由於分配了一個5,000×5,000的數組。

是否有任何預構建的庫可以處理這種比較，或者我可以使用更高效的算法？請注意，我想根據zlib許可證授權我的代碼，所以GNU diffutils並不好。

Answer 1

Google Diff Match and Patch library可以爲你解決這個問題。