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#程序设计有所帮助。

赞 (0)

相关推荐

  • C#从控制台读取字符串的方法

    本文实例讲述了C#从控制台读取字符串的方法.分享给大家供大家参考.具体实现方法如下: using System; class ReadLine { public static void Main() { Console.Write("Please enter your favorite animal: "); string animal = Console.ReadLine(); Console.WriteLine("Good choice: " + animal)

  • C#实现实体类与字符串互相转换的方法

    本文实例讲述了C#实现实体类与字符串互相转换的方法.分享给大家供大家参考.具体实现方法如下: using System; using System.Collections.Generic; using System.Text; namespace PackDLL.Data.ConvertData { /// <summary> /// 实体类.字符串互相转换 /// </summary> public class PackReflectionEntity<T> { //

  • C#找出字符串中第一个字母并大写的方法

    本文实例讲述了C#找出字符串中第一个字母并大写的方法.分享给大家供大家参考,具体如下: class Program { static void Main(string[] args) { String aa = "%.,46,2xb1bfs.,,"; int pos = isLetter(aa); aa = aa.Substring(pos, 1); Console.WriteLine(aa.ToUpper()); Console.Read(); } public static int

  • C#实现简易的加密、解密字符串工具类实例

    C#实现简易的加密、解密字符串工具类实例

    本文实例讲述了C#实现简易的加密.解密字符串工具类.分享给大家供大家参考.具体如下: 这里的类CypherHelper是一个用于加密.解密字符串的工具类~~~,适合于方便地加密.解密长度较短的密码等字符串(C#里面已经有了库System.Security.Cryptography,对于比较长的字符串或流来说是一个更好的选择) 类CypherHelper代码: class CypherHelper { /// <summary> /// 加密字符串 /// </summary> //

  • c#中判断字符串是不是数字或字母的方法

    一.判断字母 复制代码 代码如下: string str = Console.ReadLine();if (char.isLetter(str)){}else if (char.IsDigit(str)){} if(ch>='a'&&ch<='z') 小写字母if(ch>='A'&&ch<='Z') 大写字母数字也一样.判断汉字一般是输入 >255 因为汉字是大字符集二.判断输入的是不是数字 复制代码 代码如下: try{int n = 0;n

  • C#判断字符串是否存在字母及字符串中字符的替换实例

    本文实例讲述了C#判断字符串是否存在字母及字符串中字符的替换的方法.分享给大家供大家参考.具体实现方法如下: 首先要添加对命名空间"using System.Text.RegularExpressions;"的引用 下面以一个字符串为例: 复制代码 代码如下: string ss = "aaZ31 dd2f3"; string sss = ss.Replace(" ", "");//将字符串ss中的空格去掉 string ss

  • C#统计字符串中数字个数的方法

    本文实例讲述了C#统计字符串中数字个数的方法.分享给大家供大家参考.具体实现方法如下: // DigitCounter.cs // 编译时使用:/target:library using System; // 声明与 Factorial.cs 中的命名空间相同的命名空间.这样仅允许将 // 类型添加到同一个命名空间中. namespace Functions { public class DigitCount { // NumberOfDigits 静态方法计算 // 传递的字符串中数字字符的数

  • C#正则检测字符串是否字母数字混编的方法

    本文实例讲述了C#正则检测字符串是否字母数字混编的方法.分享给大家供大家参考.具体如下: using System.Text; using System.Text.RegularExpressions; public static class StringExtensions { public static bool IsAlphanumeric(this string source) { Regex pattern = new Regex("[^0-9a-zA-Z]"); retur

  • C#实现的字符串相似度对比类

    本类适用于比较2个字符的相似度,代码如下: using System; using System.Collections.Generic; using System.Text; public class StringCompute { #region 私有变量 /// <summary> /// 字符串1 /// </summary> private char[] _ArrChar1; /// <summary> /// 字符串2 /// </summary>

  • C#获取汉字字符串拼音首字母的方法

    本文实例讲述了C#获取汉字字符串拼音首字母的方法.分享给大家供大家参考.具体如下: 这个C#类经常能够用到,将提取汉字的拼音首字母,方便用户查询 using System.Text; namespace DotNet.Utilities { public class PinYin { public string GetFirstLetter(string hz) { string ls_second_eng = "CJWGNSPGCGNESYPBTYYZDXYKYGTDJNNJQMBSGZSCY

随机推荐