• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

字符串相似度算法(编辑距离算法 Levenshtein Distance)原理及C#代码实现

OC/C/C++ 水墨上仙 1305次浏览

字符串相似度算法(编辑距离算法 Levenshtein Distance)原理及C#代码实现转自:http://www.deepleo.com/archives/220

编辑距离,又称Levenshtein距离(也叫做Edit&nbspDistance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。例如将kitten一字转成sitting:sitten&nbsp(k→s)sittin&nbsp(e→i)sitting&nbsp(→g)俄罗斯科学家Vladimir&nbspLevenshtein在1965年提出这个概念。因此也叫Levenshtein&nbspDistance。例如如果str1=”ivan”,str2=”ivan”,那么经过计算后等于&nbsp0。没有经过转换。相似度=1-0/Math.Max(str1.length,str2.length)如果str1=”ivan1″,str2=”ivan2″,那么经过计算后等于1。str1的”1″转换”2″,转换了一个字符,所以距离是1,相似度=1-1/Math.Max(str1.length,str2.length)应用DNA分析拼字检查语音辨识抄袭侦测算法过程str1或str2的长度为0返回另一个字符串的长度。&nbspif(str1.length==0)&nbspreturn&nbspstr2.length;&nbspif(str2.length==0)&nbspreturn&nbspstr1.length;初始化(n+1)*(m+1)的矩阵d,并让第一行和列的值从0开始增长。扫描两字符串(n*m级的),如果:str1[i]&nbsp==&nbspstr2[j],用temp记录它,为0。否则temp记为1。然后在矩阵d[i,j]赋于d[i-1,j]+1&nbsp、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。扫描完后,返回矩阵的最后一个值d[n][m]即是它们的距离。计算相似度公式:1-它们的距离/两个字符串长度的最大值。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DeepLeo.Library.String
{
public class LevenshteinSimilarity
{
public class LevenshteinDistance
{
/// <summary>
/// 取最小的一位数
/// </summary>
/// <param name="first"></param>
/// <param name="second"></param>
/// <param name="third"></param>
/// <returns></returns>
private int LowerOfThree(int first, int second, int third)
{
int min = Math.Min(first, second);
return Math.Min(min, third);
}
private int Levenshtein_Distance(string str1, string str2)
{
int[,] Matrix;
int n = str1.Length;
int m = str2.Length;
 
int temp = 0;
char ch1;
char ch2;
int i = 0;
int j = 0;
if (n == 0)
{
return m;
}
if (m == 0)
{
 
return n;
}
Matrix = new int[n + 1, m + 1];
 
for (i = 0; i <= n; i++)
{
//初始化第一列
Matrix[i, 0] = i;
}
 
for (j = 0; j <= m; j++)
{
//初始化第一行
Matrix[0, j] = j;
}
 
for (i = 1; i <= n; i++)
{
ch1 = str1[i - 1];
for (j = 1; j <= m; j++)
{
ch2 = str2[j - 1];
if (ch1.Equals(ch2))
{
temp = 0;
}
else
{
temp = 1;
}
Matrix[i, j] = LowerOfThree(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1, Matrix[i - 1, j - 1] + temp);
}
}
for (i = 0; i <= n; i++)
{
for (j = 0; j <= m; j++)
{
Console.Write(" {0} ", Matrix[i, j]);
}
Console.WriteLine("");
}
 
return Matrix[n, m];
}
/// <summary>
/// 计算字符串相似度
/// </summary>
/// <param name="str1"></param>
/// <param name="str2"></param>
/// <returns></returns>
public decimal LevenshteinDistancePercent(string str1, string str2)
{
//int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length;
int val = Levenshtein_Distance(str1, str2);return 1 - (decimal)val / Math.Max(str1.Length, str2.Length);
}
}
}
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明字符串相似度算法(编辑距离算法 Levenshtein Distance)原理及C#代码实现
喜欢 (0)
加载中……