C#计算字符串相似性的方法
本文实例讲述了C#计算字符串相似性的方法。分享给大家供大家参考。具体如下:
计算字符串相似性的办法很多,甚至最笨的办法可以挨个匹配,这里要讲的是使用莱文史特距离来计算字符串相似性。
莱文史特距离概念:假设函数名是LD
用于计算两个字符串之间的相似度。 譬如有两个字符串A和B。假设以A为基准,那么该算法就是计算把B通过(替换、删除、加字符)等方法变成A需要多少步。
例如:
A=”abcd”, B=”abc”, 那么 LD(A,B)=1,只需在B字符串中插入一个字符那么就完全等于A
A=”abcd”, B=”abcd”, 那么 LD(A,B)= ,因为这两个货完全相同
A=”abcd”, B=”abdc”, 那么 LD(A,B)= 1,因为只需把B中”dc”互换位置就等于A了。
A=”fwegwegweg@#2″, B=”ddd*&&%^&”, 那么 LD(A,B)= ????,这个叔真不知道了,要用程序算了。
莱文史特距离计算出来的值越大代表步骤越多,说明两个字符串的相似程度越低。
譬如大家要做个简易的“文章抄袭”判定功能,那么用这个莱文史特距离完全可以实现个初步方法。
算法注释:
1、假设字符串str1的长度为 n,str2 的长度为 m。
如果 n = 0,则返回 m并退出;(这是句废话)
2、如果 m=0,则返回 n 并退出。(这依然是句废话)
3、如果上述都不是则要开始进行计算,
构建一个数组 d[0..m, 0..n]。
将第0行初始化为 0..n,第0列初始化为0..m。
依次检查 str1 的每个字母(i=1..n)。
依次检查 str2 的每个字母(j=1..m)。
如果 str1[i]=str2[j],则 sign=0;(sign仅仅是个标记,没有任何意思,为了记录相等还是不相等)
如果 str1[i]!=str12[j],则 sign=1。
将 d[i,j] 设置为以下三个值中的最小值:
紧邻当前格上方的格的值加一,即 d[i-1,j]+1
紧邻当前格左方的格的值加一,即 d[i,j-1]+1
当前格左上方的格的值加sign,即 d[i-1,j-1]+sign
重复上述几步直到循环结束。d[n,m]既为最终的值
接下来是用c#写的一款莱文史特距离的实现。
public class LDMaker//搞成一个类看起来专业, //实际上就是脱裤子放屁,这里使用来文史特距离算法 //用于计算字符串之间的相似性 { char[] str1; char[] str2; public LDMaker(string s1, string s2) { //替换掉 所有 数字 为固定数字 数字干扰 太严重 //这里因人而异,在中文文章的匹配中,数字是干扰很严重 //的,所以我在某些应用中把数字替换掉了。 //原因是有的文章之间实际上相似性很高,但是故意在里面加一些数字 //干扰该函数的执行,让机器看出来两篇文章很不同。一般不需要做如下 // 步骤 s1=System.Text.RegularExpressions.Regex.Replace(s1,@"(\d+)","1"); s2 = System.Text.RegularExpressions.Regex.Replace(s2, @"(\d+)", "1"); str1 = s1.ToCharArray(); str2 = s2.ToCharArray(); } public int GetLD()//这是莱文史特距离的算法实现 { try { int m=str1.Length; int n=str2.Length; int[,] d = new int[m+1, n+1]; for (int i = 0; i <= m ; i++) d[i, 0] = i; for (int i = 0; i <= n ; i++) d[0, i] = i; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { d[i,j] = d[i - 1,j - 1] + (str1[i - 1] == str2[j - 1] ? 0 : 1); //修改一个字符 d[i,j] = Math.Min(d[i,j], d[i - 1,j] + 1); // 插入一个字符串 d[i,j] = Math.Min(d[i,j], d[i,j - 1] + 1); //删除一个字符 } } return d[m, n]; } catch(//出错返回一个很大值 { return 10000; } } }
希望本文所述对大家的C#程序设计有所帮助。
相关文章
- 我们在使用C#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章介绍了C#判断字符串是否数字或字母的实例,有需要的朋友可以参考一下...2020-06-25
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
- 这篇文章主要介绍了PostgreSQL判断字符串是否包含目标字符串的多种方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25