91网首页-91网页版-91网在线观看-91网站免费观看-91网站永久视频-91网站在线播放

這篇文章主要介紹了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#寫的一款萊文史特距離的實現。

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