Dice Sorensen Intersectメソッドを使用しないBigram計算の距離誤差

Question

2つの文字列間のDiceSorensen Distanceを計算するオブジェクトをプログラミングしています。操作のロジックはあまり難しくありません。文字列内に2つの文字ペアがいくつあるかを計算し、2番目の文字列と比較してからこの式を実行します。 2（x | y |）

ここで、x |と| y | x & yのバイグラム要素の数です。もっと分かりやすくするためにここに参照することができますhttps://en.wikipedia.org/wiki/S%C3%B8rensen%E2%80%93Dice_coefficient

私はさまざまな場所でコードをオンラインで実行する方法を探しましたが、私が遭遇したすべての方法は2つのリストの間で '交差'方法を使用しています。これは動作しません。バイグラムが既に存在する文字列があれば、別の文字列を追加しません。たとえば、文字列がある場合 'aaaa' 3 'aa' bigramsがありますが、Intersectメソッドでは1つしか生成されません。この仮定で間違っていると、なぜ私は多くの人が使用されたのか不思議です交差メソッド私の仮定は、だからここhttps://msdn.microsoft.com/en-us/library/bb460136(v=vs.90).aspx

MSDNのWebサイトに基づいており、私がどこかは、私が法と呼ばlistBiGramsを呼び出して見ることができるコードで

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; 
} 

をしたコードであり、これはそれが

をどのように見えるかであります

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の間でなければなりません）。

ソース文字列私はsource = "これは正しい文字列ではありません"で、ターゲット文字列はtarget = "これは正しい文字列"です。

私が得た結果は-0.090909090908

でした

私が紛失していることは、誤って計算された長さのような小さいものか、カウントの誤カウントであることがわかります（99％）。誰かが私が間違っていることを指摘できたら、本当に感謝しています。あなたの時間をありがとう！

Answer 1

これは宿題のようですが、文字列のこの類似度のメトリックは私には新しく、見ました。

Algorith implementation in various languages

あなたはC＃バージョンがHashSetを使用し、IntersectWith方法を活用して気づくことがあります。

セットは、重複する要素を含まず、その要素が特定の順序になっていないコレクションです。

これはあなたの文字列 'aaaa'パズルを解決します。そこには1つのbigramだけ。

My naive implementation on Rextester

あなたはLINQのを好むならば、私はEnumerable.Distinct、Enumerable.UnionとEnumerable.Intersectをお勧めしたいです。これらは、HashSetの重複削除機能をよく模倣するはずです。

Scalaで書かれたこの素晴らしいStringMetric frameworkも見つかりました。