曖昧検索 (Fuzzy-matching) を N-gram 方式で行う

　N-gram 方式と呼ばれる方法で曖昧検索をする方法: http://www.ctrans.org/gobi/1162190725 に感銘を受けたので、早速C#用のクラスに書き起こしてみた。デフォルトでは Bigram で比較する。語順や読みを考慮しないならシンプルながら便利。

public class Ngram {
    /// <summary>
    /// Bigramで比較
    /// </summary>
    public static float Compare(string strA,string strB) {
        return Compare(2,strA,strB);
    }

    public static float Compare(int n,string strA,string strB) {
        // strAのN-gramリストを作成する
        List<string>  blist = new List<string>();
        for (int i=0;i<strA.Length-(n-1);i++) {
            string  ngitem = strA.Substring(i,n);
            if (!blist.Contains(ngitem)) { blist.Add(ngitem); }
        }
        blist.Sort();

        // strBのN-gramリストとの一致を見る
        int  found = 0;
        for (int i=0;i<strB.Length-(n-1);i++) {
            string  ngitem = strB.Substring(i,n);
            if (blist.Contains(ngitem)) { found++; }
        }

        // 重複箇所の割合を返す
        return (float)found / blist.Count;
    }
}

// -------------------------------------------------------

public class Program {
    static void Main(string[] args) {
        // 0.6666667
        Console.WriteLine(
            Ngram.Compare("武蔵は左手を柄に添え、右足を大きく踏み出した",
                          "小次郎は左手を柄に添えて、右足を踏み出した"));
    }
}