本文實例講述了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#程序設計有所幫助。
新聞熱點
疑難解答
