Csharp/C#教程：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#写的一款莱文史特距离的实现。

publicclassLDMaker//搞成一个类看起来专业， //实际上就是脱裤子放屁，这里使用来文史特距离算法 //用于计算字符串之间的相似性 { char[]str1; char[]str2; publicLDMaker(strings1,strings2) { //替换掉所有数字为固定数字数字干扰太严重 //这里因人而异，在中文文章的匹配中，数字是干扰很严重 //的，所以我在某些应用中把数字替换掉了。 //原因是有的文章之间实际上相似性很高，但是故意在里面加一些数字 //干扰该函数的执行，让机器看出来两篇文章很不同。一般不需要做如下 //步骤 s1=System.Text.RegularExpressions.Regex.Replace(s1,@"(d+)","1"); s2=System.Text.RegularExpressions.Regex.Replace(s2,@"(d+)","1"); str1=s1.ToCharArray(); str2=s2.ToCharArray(); } publicintGetLD()//这是莱文史特距离的算法实现 { try { intm=str1.Length; intn=str2.Length; int[,]d=newint[m+1,n+1]; for(inti=0;i<=m;i++) d[i,0]=i; for(inti=0;i<=n;i++) d[0,i]=i; for(inti=1;i<=m;i++) { for(intj=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); //删除一个字符 } } returnd[m,n]; }catch(//出错返回一个很大值 { return10000; } } }

希望本文所述对大家的C#程序设计有所帮助。

您可能感兴趣的文章:C#正则检测字符串是否字母数字混编的方法C#获取汉字字符串拼音首字母的方法C#判断字符串是否存在字母及字符串中字符的替换实例c#中判断字符串是不是数字或字母的方法C#实现实体类与字符串互相转换的方法C#实现简易的加密、解密字符串工具类实例C#实现的字符串相似度对比类C#从控制台读取字符串的方法C#统计字符串中数字个数的方法C#找出字符串中第一个字母并大写的方法

C++中vector可以作为map的键值实例代码

C++简单实现的全排列算法示例

上述就是C#学习教程：C#计算字符串相似性的方法分享的全部内容，如果对大家有所用处且需要了解更多关于C#学习教程，希望大家多多关注—计算机技术网(www.ctvol.com)!