比較字符串與公差

Question

我正在尋找一種方法來比較一個字符串與一個字符串數組。做一個精確的搜索當然很容易，但我希望我的程序能夠容忍拼寫錯誤，缺少字符串的部分等等。

是否有某種框架可以執行此類搜索？我記住，搜索算法會返回幾個結果順序的匹配百分比或類似的東西。

Answer 1

您可以使用Levenshtein Distance algorithm。

「兩個字符串之間的Levenshtein距離被定義爲將一個字符串轉換爲另一個字符串所需的最小編輯次數，允許的編輯操作是插入，刪除或替換單個字符。 - Wikipedia.com

這一個是從dotnetperls.com：

using System; 

/// <summary> 
/// Contains approximate string matching 
/// </summary> 
static class LevenshteinDistance 
{ 
    /// <summary> 
    /// Compute the distance between two strings. 
    /// </summary> 
    public static int Compute(string s, string t) 
    { 
     int n = s.Length; 
     int m = t.Length; 
     int[,] d = new int[n + 1, m + 1]; 

     // Step 1 
     if (n == 0) 
     { 
      return m; 
     } 

     if (m == 0) 
     { 
      return n; 
     } 

     // Step 2 
     for (int i = 0; i <= n; d[i, 0] = i++) 
     { 
     } 

     for (int j = 0; j <= m; d[0, j] = j++) 
     { 
     } 

     // Step 3 
     for (int i = 1; i <= n; i++) 
     { 
      //Step 4 
      for (int j = 1; j <= m; j++) 
      { 
       // Step 5 
       int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; 

       // Step 6 
       d[i, j] = Math.Min(
        Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), 
        d[i - 1, j - 1] + cost); 
      } 
     } 
     // Step 7 
     return d[n, m]; 
    } 
} 

class Program 
{ 
    static void Main() 
    { 
     Console.WriteLine(LevenshteinDistance.Compute("aunt", "ant")); 
     Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha")); 
     Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax")); 
    } 
} 

你實際上可能更喜歡使用Damerau-Levenshtein distance algorithm，這也允許調換角色，這是在數據錄入人類共同的錯誤。你會發現它的C＃實現here。

Answer 2

以下是計算字符串間的Levenshtein Distance的兩種方法。

兩個字符串之間的Levenshtein距離被定義爲一個串轉換成另一個必要的修改的最小數目，與可允許的編輯操作是插入，缺失，或單個字符的替換。

一旦你得到了結果，你需要定義你想用什麼值作爲匹配的閾值。對一堆樣本數據運行該函數，以瞭解它是如何工作的，以幫助確定您的特定閾值。

/// <summary> 
    /// Calculates the Levenshtein distance between two strings--the number of changes that need to be made for the first string to become the second. 
    /// </summary> 
    /// <param name="first">The first string, used as a source.</param> 
    /// <param name="second">The second string, used as a target.</param> 
    /// <returns>The number of changes that need to be made to convert the first string to the second.</returns> 
    /// <remarks> 
    /// From http://www.merriampark.com/ldcsharp.htm 
    /// </remarks> 
    public static int LevenshteinDistance(string first, string second) 
    { 
     if (first == null) 
     { 
      throw new ArgumentNullException("first"); 
     } 
     if (second == null) 
     { 
      throw new ArgumentNullException("second"); 
     } 

     int n = first.Length; 
     int m = second.Length; 
     var d = new int[n + 1, m + 1]; // matrix 

     if (n == 0) return m; 
     if (m == 0) return n; 

     for (int i = 0; i <= n; d[i, 0] = i++) 
     { 
     } 

     for (int j = 0; j <= m; d[0, j] = j++) 
     { 
     } 

     for (int i = 1; i <= n; i++) 
     { 

      for (int j = 1; j <= m; j++) 
      { 
       int cost = (second.Substring(j - 1, 1) == first.Substring(i - 1, 1) ? 0 : 1); // cost 
       d[i, j] = Math.Min(
        Math.Min(
         d[i - 1, j] + 1, 
         d[i, j - 1] + 1), 
        d[i - 1, j - 1] + cost); 
      } 
     } 

     return d[n, m]; 
    } 

Answer 3

.NET框架中沒有任何東西可以幫助您開箱即用。

最常見的拼寫錯誤是那些字母是單詞體面表示的單詞，但不是正確的單詞拼寫。

例如，可能會認爲單詞sword和sord（是的，這是一個詞）具有相同的語音根源（發音時它們聽起來相同）。

這就是說，有很多算法可以用來將單詞（甚至是拼寫錯誤的）翻譯成語音變體。第一個是Soundex。實施相當簡單，並且有相當數量的.NET implementations of this algorithm。這很簡單，但它給你真正的價值，你可以相互比較。

另一個是Metaphone。儘管我找不到Metaphone的本地.NET實現，但所提供的鏈接還有許多可以轉換的其他實現的鏈接。最容易轉換的可能是Java implementation of the Metaphone algorithm。

應該指出的是，Metaphone算法已經過修訂。有Double Metaphone（其中有.NET implementation）和Metaphone 3。 Metaphone 3是一個商業應用程序，但在針對常用英語單詞數據庫運行時，雙精度鈴音算法的準確率爲98％，而Double Metaphone算法的準確率爲89％。根據您的需要，您可能需要查找（在Double Metaphone的情況下）或購買（在Metaphone 3的情況下）算法的源代碼，並通過P/Invoke層轉換或訪問它（有C++實現盛產）。

Metaphone和Soundex的區別在於Soundex產生固定長度的數字鍵，而Metaphone產生不同長度的鍵，所以結果會不同。最後，兩者都會爲你做同樣的比較，你只需根據你的要求和資源（以及拼寫錯誤的不容忍水平，當然），找出最適合你需求的最適合你的需求。

Answer 4

你可以在開源CommonLibrary.NET project中找到soundex和levenshtein距離算法的實現。

Answer 5

您的另一種選擇是使用Soundex或Metaphone進行語音比較。我剛剛完成了一篇介紹這兩種算法的C＃代碼的文章。你可以在http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex查看它。

Answer 6

這裏是LevenshteinDistance方法的一個實現，它使用更少的內存，同時產生相同的結果。這是在「帶有兩個矩陣行的迭代」標題下的wikipedia article中發現的僞代碼的C＃改編。

public static int LevenshteinDistance(string source, string target) 
{ 
    // degenerate cases 
    if (source == target) return 0; 
    if (source.Length == 0) return target.Length; 
    if (target.Length == 0) return source.Length; 

    // create two work vectors of integer distances 
    int[] v0 = new int[target.Length + 1]; 
    int[] v1 = new int[target.Length + 1]; 

    // initialize v0 (the previous row of distances) 
    // this row is A[0][i]: edit distance for an empty s 
    // the distance is just the number of characters to delete from t 
    for (int i = 0; i < v0.Length; i++) 
     v0[i] = i; 

    for (int i = 0; i < source.Length; i++) 
    { 
     // calculate v1 (current row distances) from the previous row v0 

     // first element of v1 is A[i+1][0] 
     // edit distance is delete (i+1) chars from s to match empty t 
     v1[0] = i + 1; 

     // use formula to fill in the rest of the row 
     for (int j = 0; j < target.Length; j++) 
     { 
      var cost = (source[i] == target[j]) ? 0 : 1; 
      v1[j + 1] = Math.Min(v1[j] + 1, Math.Min(v0[j + 1] + 1, v0[j] + cost)); 
     } 

     // copy v1 (current row) to v0 (previous row) for next iteration 
     for (int j = 0; j < v0.Length; j++) 
      v0[j] = v1[j]; 
    } 

    return v1[target.Length]; 
} 

這是一個可以給你百分比相似性的函數。

/// <summary> 
/// Calculate percentage similarity of two strings 
/// <param name="source">Source String to Compare with</param> 
/// <param name="target">Targeted String to Compare</param> 
/// <returns>Return Similarity between two strings from 0 to 1.0</returns> 
/// </summary> 
public static double CalculateSimilarity(string source, string target) 
{ 
    if ((source == null) || (target == null)) return 0.0; 
    if ((source.Length == 0) || (target.Length == 0)) return 0.0; 
    if (source == target) return 1.0; 

    int stepsToSame = LevenshteinDistance(source, target); 
    return (1.0 - ((double)stepsToSame/(double)Math.Max(source.Length, target.Length))); 
}