骰子Sorensen不使用Intersect方法計算Bigrams

Question

我一直在編程一個對象來計算兩個字符串之間的DiceSorensen距離。操作的邏輯並不困難。您計算一個字符串中存在多少個兩個字母對，然後將其與第二個字符串進行比較，然後執行此公式： 2（x intersect y）/（| x |。| y |）

其中| x |和| y |是x & y中的doubleram元素的數量。參考可以在這裏找到進一步的清晰https://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient

所以我試過了查找如何在網上做代碼在各個景點，但我遇到過的每個方法使用兩個列表之間的'相交'方法，並且就我而言意識到這將無法正常工作，因爲如果你有一個字符串，其中的bigram已經存在，它將不會添加另一個字符串。例如，如果我有一個字符串 'aaaa' 我希望有3'aa'bigrams但Intersect方法只會產生一個，如果我在這個假設上不正確，請告訴我因爲我想知道爲什麼這麼多人使用相交法。我的假設是基於MSDN網站https://msdn.microsoft.com/en-us/library/bb460136(v=vs.90).aspx

所以這裏是我做了

public static double SorensenDiceDistance(this string source, string target) 
{ 
    // formula 2|X intersection Y| 
    //   -------------------- 
    //   |X|  +  |Y| 

    //create variables needed 
    List<string> bigrams_source = new List<string>(); 
    List<string> bigrams_target = new List<string>(); 

    int source_length; 
    int target_length; 
    double intersect_count = 0; 
    double result = 0; 

    Console.WriteLine("DEBUG: string length source is " + source.Length); 

    //base case 
    if (source.Length == 0 || target.Length == 0) 
    { 
     return 0; 
    } 

    //extract bigrams from string 1 
    bigrams_source = source.ListBiGrams(); 
    //extract bigrams from string 2 
    bigrams_target = target.ListBiGrams(); 

    source_length = bigrams_source.Count(); 
    target_length = bigrams_target.Count(); 
    Console.WriteLine("DEBUG: bigram counts are source: " + source_length + " . target length : " + target_length); 
    //now we have two sets of bigrams compare them in a non distinct loop 

    for (int i = 0; i < bigrams_source.Count(); i++) 
    { 
     for (int y = 0; y < bigrams_target.Count(); y++) 
     { 
      if (bigrams_source.ElementAt(i) == bigrams_target.ElementAt(y)) 
      { 
       intersect_count++; 
       //Console.WriteLine("intersect count is :" + intersect_count); 
      } 
     } 
    } 
    Console.WriteLine("intersect line value : " + intersect_count); 

    result = (2 * intersect_count)/(source_length + target_length); 

    if (result < 0) 
    { 
     result = Math.Abs(result); 
    } 

    return result; 
} 

在代碼的某個地方，你可以看到我調用一個方法叫做listBiGrams的代碼，這是它的外觀

public static List<string> ListBiGrams(this string source) 
{ 
    return ListNGrams(source, 2); 
} 

public static List<string> ListTriGrams(this string source) 
{ 
    return ListNGrams(source, 3); 
} 

public static List<string> ListNGrams(this string source, int n) 
{ 
    List<string> nGrams = new List<string>(); 

    if (n > source.Length) 
    { 
     return null; 
    } 
    else if (n == source.Length) 
    { 
     nGrams.Add(source); 
     return nGrams; 
    } 
    else 
    { 
     for (int i = 0; i < source.Length - n; i++) 
     { 
      nGrams.Add(source.Substring(i, n)); 
     } 

     return nGrams; 
    } 
} 

所以我的代碼步步的理解是 1）在字符串 2）傳遞0長度檢查 3）創建列表和雙字母組向上流入他們 4）獲取每個二元列表的長度 5）嵌套循環檢查源位置[i]針對目標字符串中的每個二元組，然後遞增i直到沒有更多的源列表檢查 6）執行上面提到的等式wikipedia 7）如果結果是否定的Math.Abs​​它返回一個肯定的結果（但是我知道結果應該在0和1之間已經這是什麼讓我知道我做錯了什麼）

源字符串我用的是源=「這不是正確的字符串」，目標字符串是，目標=「這是一個正確的字符串」

我得到的結果是-0.090909090908

我很確定（99％）我錯過的東西很小，就像某處錯誤計算的長度或計數錯誤。如果有人能指出我做錯了什麼，我會很感激。感謝您的時間！

Answer 1

這看起來像家庭作業，但這種字符串相似性度量對我來說是新的，所以我看了一下。

Algorith implementation in various languages

正如你可能會注意到的C＃版本使用HashSet並採取IntersectWith方法的優點。

一個集合是不包含重複的元素，其 元素沒有特定的順序。

這可以解決您的字符串'aaaa'難題。那裏只有一個bigram。

My naive implementation on Rextester

如果你喜歡LINQ的話，我會建議Enumerable.Distinct，Enumerable.Union和Enumerable.Intersect。這些應該很好地模仿HashSet的重複刪除功能。

也發現這個不錯的StringMetric framework寫在斯卡拉。