• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C#如何使用编辑距离算法实现字符串相似度比较

OC/C/C++ 水墨上仙 2568次浏览

C#通过编辑距离算法实现字符串相似度比较编辑距离:通过插入、删除、替换一个字符(和交换相邻字符)的操作,使得字符串A和字符串B相同,而最少的操作次数就是编辑距离。如字符串abcd和aca的距离是2

public class LevenshteinDistance
    {
        private static LevenshteinDistance _instance=null;
        public static LevenshteinDistance Instance
        {
            get
            {
                if (_instance == null)
                {
                    return new LevenshteinDistance();
                }
                return _instance;
            }
        }
    
        /// <summary>
        /// 取最小的一位数
        /// </summary>
        /// <param name="first"></param>
        /// <param name="second"></param>
        /// <param name="third"></param>
        /// <returns></returns>
        public int LowerOfThree(int first, int second, int third)
        {
            int min = first;
            if (second < min)
                min = second;
            if (third < min)
                min = third;
            return min;
        }
        public int Levenshtein_Distance(string str1, string str2)
        {
            int[,] Matrix;
            int n=str1.Length;
            int m=str2.Length;
            int temp = 0;
            char ch1;
            char ch2;
            int i = 0;
            int j = 0;
            if (n ==0)
            {
                return m;
            }
            if (m == 0)
            {
                return n;
            }
            Matrix=new int[n+1,m+1];
            for (i = 0; i <= n; i++)
            {
                //初始化第一列
                Matrix[i,0] = i;
            }
            for (j = 0; j <= m; j++)
            {
                //初始化第一行
                Matrix[0, j] = j;
            }
            for (i = 1; i <= n; i++)
            {
                ch1 = str1[i-1];
                for (j = 1; j <= m; j++)
                {
                    ch2 = str2[j-1];
                    if (ch1.Equals(ch2))
                    {
                        temp = 0;
                    }
                    else
                    {
                        temp = 1;
                    }
                    Matrix[i,j] = LowerOfThree(Matrix[i - 1,j] + 1, Matrix[i,j - 1] + 1, Matrix[i - 1,j - 1] + temp);
                }
            }
            for (i = 0; i <= n; i++)
            {
                for (j = 0; j <= m; j++)
                {
                    Console.Write(" {0} ", Matrix[i, j]);
                }
                Console.WriteLine("");
            }
            return Matrix[n, m];
        }
        /// <summary>
        /// 计算字符串相似度
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns></returns>
        public decimal LevenshteinDistancePercent(string str1,string str2)
        {
            int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length;
            int val = Levenshtein_Distance(str1, str2);
            return 1 - (decimal)val / maxLenth;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            string str1 = "你好蒂蒂";
            string str2="你好蒂芬";
            Console.WriteLine("字符串1 {0}", str1);
            Console.WriteLine("字符串2 {0}", str2);
            Console.WriteLine("相似度 {0} %", LevenshteinDistance.Instance.LevenshteinDistancePercent(str1, str2)*100);
            Console.ReadLine();
        }
    }


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C#如何使用编辑距离算法实现字符串相似度比较
喜欢 (0)
加载中……