用C#实现字符串相似度算法

小渣渣

最近需要处理一个问题，就是比较用户输入的字符串和系统取到的字符串，如果误差不是很大的，系统就认为符合要求的，最好可以设置阈值。
在搞验证码识别的时候需要比较字符代码的相似度用到“编辑距离算法”，关于原理和C#实现做个记录。

据百度百科介绍：

编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

　　例如将kitten一字转成sitting：

　　sitten （k→s）

　　sittin （e→i）

　　sitting （→g）

　　俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。因此也叫Levenshtein Distance。

例如

如果str1="ivan"，str2="ivan"，那么经过计算后等于 0。没有经过转换。相似度=1-0/Math.Max(str1.length,str2.length)=1
如果str1="ivan1"，str2="ivan2"，那么经过计算后等于1。str1的"1"转换"2"，转换了一个字符，所以距离是1，相似度=1-1/Math.Max(str1.length,str2.length)=0.8

应用

• DNA分析
• 拼字检查
• 语音辨识
• 抄袭侦测
  

算法用C#实现:

登录可见。

测试代码：

登录可见。

从测试结果得出，空格或者标点符号、字符串位置不同都会影响相似度的结果，所以，在进行字符串相识度比较的时候，建议去掉字符串中的所有空格和特殊符号再调用算法。

参考资料：http://www.cnblogs.com/ECJTUACM-873284962/p/7661375.html

在GitHub上面，也有一个关于c#字符串相似度比较的类库

FuzzyString是一个开发用于我日常工作的库，用于协调不同电网模型之间的命名约定。我已经剥离了电力系统特定的代码，并将可以有效地用作字符串扩展的内容放在一起，以确定两个字符串之间的近似相等性。此处使用的所有算法都已从在线资源中提取，转换为C＃，并编译到此库中。我发现了几个其他类似的开源实现，但没有用于.NET / C＃。将* .dll添加到项目中将允许您访问此扩展以及ApproximatelyEquals（）扩展名下的各个扩展。

地址：https://github.com/kdjones/fuzzystring

nuget安装：

登录可见。

该项目中包含的算法：

• 汉明距离
• Jaccard距离
• Jaro距离
• Jaro-Winkler距离
• Levenshtein距离
• 最长公共
• 子序列最长公共子串
• 重叠系数
• Ratcliff-Obershelp相似性
• Sorensen-Dice距离
• Tanimoto系数
  

使用：

登录可见。

结果：



（完）

QWERTYU

涨知识来了

domer

是不是回复了才能看到代码