[Irving]字符串相似度-字符编辑距离算法（c#实现）

编辑距离（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);