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

計(jì)算字符串相似性的辦法很多，甚至最笨的辦法可以挨個(gè)匹配，這里要講的是使用萊文史特距離來(lái)計(jì)算字符串相似性。
萊文史特距離概念:假設(shè)函數(shù)名是LD

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

例如：
A=”abcd”, B=”abc”, 那么 LD(A,B)=1，只需在B字符串中插入一個(gè)字符那么就完全等于A
 A=”abcd”, B=”abcd”, 那么 LD(A,B)= ，因?yàn)檫@兩個(gè)貨完全相同
 A=”abcd”, B=”abdc”, 那么 LD(A,B)= 1，因?yàn)橹恍璋袯中”dc”互換位置就等于A了。
A=”fwegwegweg@#2″, B=”ddd*&&%^&”, 那么 LD(A,B)= ????，這個(gè)叔真不知道了，要用程序算了。
萊文史特距離計(jì)算出來(lái)的值越大代表步驟越多，說(shuō)明兩個(gè)字符串的相似程度越低。

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

算法注釋:
1、假設(shè)字符串str1的長(zhǎng)度為 n，str2 的長(zhǎng)度為 m。
   如果 n = 0，則返回 m并退出；(這是句廢話)
2、如果 m=0，則返回 n 并退出。(這依然是句廢話)
3、如果上述都不是則要開(kāi)始進(jìn)行計(jì)算，

構(gòu)建一個(gè)數(shù)組 d[0..m, 0..n]。
將第0行初始化為 0..n，第0列初始化為0..m。
依次檢查 str1 的每個(gè)字母(i=1..n)。
依次檢查 str2 的每個(gè)字母(j=1..m)。
如果 str1[i]=str2[j]，則 sign=0；(sign僅僅是個(gè)標(biāo)記，沒(méi)有任何意思，為了記錄相等還是不相等)
如果 str1[i]!=str12[j]，則 sign=1。
將 d[i,j] 設(shè)置為以下三個(gè)值中的最小值：
緊鄰當(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]既為最終的值

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

public class LDMaker//搞成一個(gè)類看起來(lái)專業(yè)，
 //實(shí)際上就是脫褲子放屁，這里使用來(lái)文史特距離算法
 //用于計(jì)算字符串之間的相似性
  {
    char[] str1;
    char[] str2;
    public LDMaker(string s1, string s2)
    {
  //替換掉 所有 數(shù)字 為固定數(shù)字 數(shù)字干擾 太嚴(yán)重
  //這里因人而異，在中文文章的匹配中，數(shù)字是干擾很?chē)?yán)重
  //的，所以我在某些應(yīng)用中把數(shù)字替換掉了。
  //原因是有的文章之間實(shí)際上相似性很高，但是故意在里面加一些數(shù)字
  //干擾該函數(shù)的執(zhí)行，讓機(jī)器看出來(lái)兩篇文章很不同。一般不需要做如下
  // 步驟
  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()//這是萊文史特距離的算法實(shí)現(xiàn)
{
  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);
      //修改一個(gè)字符
       d[i,j] = Math.Min(d[i,j], d[i - 1,j] + 1);
      // 插入一個(gè)字符串 
      d[i,j] = Math.Min(d[i,j], d[i,j - 1] + 1); 
      //刪除一個(gè)字符 
      } 
    } 
    return d[m, n];
    } catch(//出錯(cuò)返回一個(gè)很大值
    { 
      return 10000;
    }
   } 
}

希望本文所述對(duì)大家的C#程序設(shè)計(jì)有所幫助。

最新評(píng)論