編集距離NET実装

    /// <summary>
    /// Calculate Text Edit Distance Utility Class
    /// </summary>
    public static class TextEditDistanceUtility
    {
        /// <summary>
        /// get edit distance between two string
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns></returns>
        public static int GetEditDistance(string str1, string str2)
        {
            if (str1 == str2) return 0;
            else if (String.IsNullOrEmpty(str1) && String.IsNullOrEmpty(str2)) return 0;
            else if (String.IsNullOrEmpty(str1) && !String.IsNullOrEmpty(str2)) return str2.Length;
            else if (!String.IsNullOrEmpty(str1) && String.IsNullOrEmpty(str2)) return str1.Length;
            int[,] d = new int[str1.Length + 1, str2.Length + 1];
            d.Initialize();
            int cost = 0;
            for (int i = 0; i < d.GetLength(0); i++)
            {
                d[i, 0] = i;
            }
            for (int j = 0; j < d.GetLength(1); j++)
            {
                d[0, j] = j;
            }
            for (int i = 0; i < str1.Length; i++)
            {
                for (int j = 0; j < str2.Length; j++)
                {
                    if (str1[i] == str2[j]) cost = 0;
                    else cost = 1;
                    d[i + 1, j + 1] = Math.Min(Math.Min(d[i, j + 1] + 1, d[i + 1, j] + 1), Math.Min(d[i + 1, j] + 1, d[i, j] + cost));
                }
            }
            return d[str1.Length, str2.Length];
        }
    }

Edit Distanceは2つの文字列の間で何回の基礎操作を必要として相手の操作になることができることを比較して、1つの文字を増加して、1つの文字を削除して、1つの文字を修正して、すべて1回の操作とします
例えばabbとbbb、編集距離は1、abcはaa、編集距離は2
このアルゴリズムの多くの応用は2回の結果の差がどれだけ大きいかを比較することである.