编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如将kitten一字转成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
原理不再追溯，大牛博客应有尽有 善用搜索引擎皆可查询，下面贴出C# 实现，通过.net 3.0 扩展方法 调用方便
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace System
{
public static class StringExt
{
/// <summary>
/// 获取最小数值
/// </summary>
private static int getMin(
int a,
int b,
int c)
{
var min =
Math.Min(a, b);
return Math.Min(min, c);
}
/// <summary>
/// 字符距离算法,获取字符编辑距离
/// </summary>
public static int Levenshtein_Distance(
this string str1,
string str2)
{
int[,] Matrix;
int n =
str1.Length;
int m =
str2.Length;
char c1, c2;
int temp =
0;
int i, 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++
)
{
c1 = str1[i -
1];
for (j =
1; j <= m; j++
)
{
c2 = str2[j -
1];
if (c1.Equals(c2))
{
temp =
0;
}
else
{
temp =
1;
}
Matrix[i, j] = getMin(Matrix[i -
1, j] +
1, Matrix[i, j -
1] +
1, Matrix[i -
1, j -
1] +
temp);
}
}
return Matrix[n, m];
}
/// <summary>
/// 获取字符相识度
/// </summary>
public static decimal GetSimilarity(
this string str1,
string str2)
{
var l =
str1.Levenshtein_Distance(str2);
return 1 - (
decimal)l /
Math.Max(str1.Length, str1.Length);
}
}
}
调用方法
//获取字符编辑距离
var l =
textBox1.Text.ToString().Levenshtein_Distance(textBox2.Text);
//获取字符相识度
decimal Similarity = textBox1.Text.GetSimilarity(textBox2.Text);
转载于:https://www.cnblogs.com/teamate/p/3859202.html
相关资源：字符串相似度算法
