這篇文章主要介紹了C#計算字符串相似性的方法,實(shí)例分析了C#計算字符串相似性的原理與算法實(shí)現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下

本文實(shí)例講述了C#計算字符串相似性的方法。分享給大家供大家參考。具體如下：

計算字符串相似性的辦法很多，甚至最笨的辦法可以挨個匹配，這里要講的是使用萊文史特距離來計算字符串相似性。

萊文史特距離概念:假設(shè)函數(shù)名是LD

用于計算兩個字符串之間的相似度。 譬如有兩個字符串A和B。假設(shè)以A為基準(zhǔn)，那么該算法就是計算把B通過(替換、刪除、加字符)等方法變成A需要多少步。

例如：

A=”abcd”, B=”abc”, 那么 LD(A,B)=1，只需在B字符串中插入一個字符那么就完全等于A

A=”abcd”, B=”abcd”, 那么 LD(A,B)= ，因?yàn)檫@兩個貨完全相同

A=”abcd”, B=”abdc”, 那么 LD(A,B)= 1，因?yàn)橹恍璋袯中”dc”互換位置就等于A了。

A=”fwegwegweg@#2″, B=”ddd*&&%^&”, 那么 LD(A,B)= ????，這個叔真不知道了，要用程序算了。

萊文史特距離計算出來的值越大代表步驟越多，說明兩個字符串的相似程度越低。

譬如大家要做個簡易的“文章抄襲”判定功能，那么用這個萊文史特距離完全可以實(shí)現(xiàn)個初步方法。

算法注釋:

1、假設(shè)字符串str1的長度為 n，str2 的長度為 m。

如果 n = 0，則返回 m并退出;(這是句廢話)

2、如果 m=0，則返回 n 并退出。(這依然是句廢話)

3、如果上述都不是則要開始進(jìn)行計算，

構(gòu)建一個數(shù)組 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僅僅是個標(biāo)記，沒有任何意思，為了記錄相等還是不相等)

如果 str1[i]!=str12[j]，則 sign=1。

將 d[i,j] 設(shè)置為以下三個值中的最小值：

緊鄰當(dāng)前格上方的格的值加一，即 d[i-1,j]+1

緊鄰當(dāng)前格左方的格的值加一，即 d[i,j-1]+1

當(dāng)前格左上方的格的值加sign，即 d[i-1,j-1]+sign

重復(fù)上述幾步直到循環(huán)結(jié)束。d[n,m]既為最終的值

接下來是用c#寫的一款萊文史特距離的實(shí)現(xiàn)。

1. public class LDMaker//搞成一個類看起來專業(yè)， 

2. //實(shí)際上就是脫褲子放屁，這里使用來文史特距離算法 

3. //用于計算字符串之間的相似性 

4. { 

5. char[] str1; 

6. char[] str2; 

7. public LDMaker(string s1, string s2) 

8. { 

9. //替換掉 所有 數(shù)字 為固定數(shù)字 數(shù)字干擾 太嚴(yán)重 

10. //這里因人而異，在中文文章的匹配中，數(shù)字是干擾很嚴(yán)重 

11. //的，所以我在某些應(yīng)用中把數(shù)字替換掉了。 

12. //原因是有的文章之間實(shí)際上相似性很高，但是故意在里面加一些數(shù)字 

13. //干擾該函數(shù)的執(zhí)行，讓機(jī)器看出來兩篇文章很不同。一般不需要做如下 

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()//這是萊文史特距離的算法實(shí)現(xiàn) 

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#程序設(shè)計有所幫助。