C#计算字符串相似性的方法

这篇文章主要介绍了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#写的一款莱文史特距离的实现。

1. public class LDMaker//搞成一个类看起来专业， 
2. //实际上就是脱裤子放屁，这里使用来文史特距离算法 
3. //用于计算字符串之间的相似性 
4. { 
5. char[] str1; 
6. char[] str2; 
7. public LDMaker(string s1, string s2) 
8. { 
9. //替换掉 所有 数字 为固定数字 数字干扰 太严重 
10. //这里因人而异，在中文文章的匹配中，数字是干扰很严重 
11. //的，所以我在某些应用中把数字替换掉了。 
12. //原因是有的文章之间实际上相似性很高，但是故意在里面加一些数字 
13. //干扰该函数的执行，让机器看出来两篇文章很不同。一般不需要做如下 
14. // 步骤 
15. s1=System.Text.RegularExpressions.Regex.Replace(s1,@"(/d+)","1"); 
16. s2 = System.Text.RegularExpressions.Regex.Replace(s2, @"(/d+)", "1"); 
17. str1 = s1.ToCharArray(); 
18. str2 = s2.ToCharArray(); 
19. } 
20. public int GetLD()//这是莱文史特距离的算法实现 
21. { 
22. try 
23. { 
24. int m=str1.Length; 
25. int n=str2.Length; 
26. int[,] d = new int[m+1, n+1]; 
27. for (int i = 0; i <= m ; i++) 
28. d[i, 0] = i; 
29. for (int i = 0; i <= n ; i++) 
30. d[0, i] = i; 
31. for (int i = 1; i <= m; i++) 
32. { 
33. for (int j = 1; j <= n; j++) 
34. { 
35. d[i,j] = d[i - 1,j - 1] + (str1[i - 1] == str2[j - 1] ? 0 : 1); 
36. //修改一个字符 
37. d[i,j] = Math.Min(d[i,j], d[i - 1,j] + 1); 
38. // 插入一个字符串  
39. d[i,j] = Math.Min(d[i,j], d[i,j - 1] + 1);  
40. //删除一个字符  
41. }  
42. }  
43. return d[m, n]; 
44. } catch(//出错返回一个很大值 
45. {  
46. return 10000; 
47. } 
48. }  
49. } 

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