C#计算字符串相似性的方法
作者:kevin0216 发布时间:2022-08-18 11:32:15
本文实例讲述了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#程序设计有所帮助。
猜你喜欢
- 本文实例为大家分享了java使用influxDB数据库的具体代码,供大家参考,具体内容如下1.pom.xml中导入jar包依赖<!--
- 前言之前写了一个博客是关于使用SpringBoot使用validation-api实现参数校验,当时使用的注解都是validation-ap
- java.util 包提供了 Date 类来封装当前的日期和时间。 Date 类提供两个构造函数来实例化 Date 对象。第一个构造函数使用
- 提到java里的注解,和我们平时的注释还是有很大的区别,主要是作为java特性来使用的,跟我们常见的类是同一个使用的层面。关于java注解的
- 在Android中,线程内部或者线程之间进行信息交互时经常会使用消息,这些基础的东西如果我们熟悉其内部的原理,将会使我们容易、更好地架构系统
- 目录实现效果实现方式实现步骤Blend绘制Path绘制Path绘制直线绘制曲线改变曲线形状移除Path上的线段移除Path上的点Path添加
- 1. mapper.xml设置resultTyperesultType="com.alibaba.fastjson.JSONObj
- 在前面一篇Java Comparable和Comparator对比详解中,对于java中的排序方法进行比较和具体剖析,主要是针对 Compa
- 无论哪种界面框架输入文本框都是非常重要的控件, 但是发现flutter中的输入框TextField介绍的虽然多,但是各个属性怎么组合满足需要
- 一、题目描述题目:同步锁出现的目的就是为了解决多线程安全问题。同步锁的几种方式synchronized1、同步代码块2、同步方法jdk1.5
- android中提供了4中动画: AlphaAnimation 透明度动画效果 ScaleAnimation 缩放动画效果 Translat
- 一.前言这一篇来看看 SpringIOC 里面的一个细节点 , 来简单看看 BeanDefinition 这个对象 , 以及有没有办法对其进
- mapper-locations的作用说明1、mapper-locationsmapper-locations是一个定义mapper接口位置
- java web返回中文乱码ajax返回中文乱码问题 在浏览器按F12查看数据包可以看到charset为 iso-8859-1,这是spri
- 确保这个修改是正确的(否则将会出现乱码)创建i18n文件夹(就是国际化的意思),然后在此文件加下创login.properties logi
- 目录前言Hello World1.可以在 Spring Initializr上面添加,也可以手动在 pom.xml中添加如下代码∶2. 编写
- 在讲述这个模式之前,我们先看一个案例:游戏回档游戏的某个场景,一游戏角色有生命力、攻击力、防御力等数据,在打Boss前和后会不一样,我们允许
- spring Boot源码编译1. git上下拉最新版的spring Boot下载:git clone git@github.com:spr
- switch结构(开关语句)的语法switch(表达式 ){--->类型为int、char case 常量1 :---&g
- MyBatis简介MyBatis 是支持普通 SQL 查询,存储过程和高级映射的优秀持久层框架。 MyBatis 消除了几乎所有的 JDBC