using System; namespace Apewer.Internals { /// Levenshtein 距离:两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。 internal class Levenshtein { #region 结果 private double _Rate; private int _Times; private int _Distance; private TimeSpan _Duration; /// 相似度,取值范围 0 ~ 1。若不同,则趋近于 0;若完全相同,则为 1。 public double Rate { get { return _Rate; } } /// 对比次数。 public int Times { get { return _Times; } } /// 距离。 public int Distance { get { return _Distance; } } /// 时长。 public TimeSpan Duration { get { return _Duration; } } #endregion #region 计算 /// 字符串 1。 private char[] _ArrChar1; /// 字符串 2。 private char[] _ArrChar2; /// 开始时间。 private DateTime _BeginTime; /// 结束时间。 private DateTime _EndTime; /// 算法矩阵。 private int[,] _Matrix; /// 矩阵列数。 private int _Column; /// 矩阵行数。 private int _Row; private Levenshtein() { InitVariable(); } /// 初始化变量。 private void InitVariable() { _Rate = 0; _Times = 0; _Distance = 0; _Duration = new TimeSpan(0); } /// 初始化算法基本信息。 private void InitVariable(string arg1, string arg2) { InitVariable(); _ArrChar1 = arg1.ToCharArray(); _ArrChar2 = arg2.ToCharArray(); _Row = _ArrChar1.Length + 1; _Column = _ArrChar2.Length + 1; _Matrix = new int[_Row, _Column]; } /// 初始化矩阵的第一行和第一列。 private void InitMatrix() { for (int i = 0; i < _Column; i++) _Matrix[0, i] = i; for (int i = 0; i < _Row; i++) _Matrix[i, 0] = i; } /// 取三个数中的最小值。 private int Minimum(int argFirst, int argSecond, int argThird) { int intMin = argFirst; if (argSecond < intMin) intMin = argSecond; if (argThird < intMin) intMin = argThird; return intMin; } /// 计算相似度。 private void Compute() { // 开始时间。 _BeginTime = DateTime.Now; // 初始化矩阵的第一行和第一列。 this.InitMatrix(); int intCost = 0; for (int i = 1; i < _Row; i++) { for (int j = 1; j < _Column; j++) { if (_ArrChar1[i - 1] == _ArrChar2[j - 1]) { intCost = 0; } else { intCost = 1; } // 关键步骤,计算当前位置值为左边 + 1、上面 + 1、左上角 + intCost 中的最小值。 // 循环遍历到最后 _Matrix[_Row - 1, _Column - 1] 即为两个字符串的距离。 _Matrix[i, j] = this.Minimum(_Matrix[i - 1, j] + 1, _Matrix[i, j - 1] + 1, _Matrix[i - 1, j - 1] + intCost); _Times++; } } // 结束时间。 _EndTime = DateTime.Now; // 相似率,移动次数小于最长的字符串长度的 20% 算同一题。 int intLength = _Row > _Column ? _Row : _Column; _Rate = 1 - (double)_Matrix[_Row - 1, _Column - 1] / intLength; _Duration = _EndTime - _BeginTime; _Distance = _Matrix[_Row - 1, _Column - 1]; } #endregion #region 方法 /// 计算两个字符串的相似度。 public static Levenshtein Compute(string arg1, string arg2) { var vString1 = string.IsNullOrEmpty(arg1) ? "" : arg1; var vString2 = string.IsNullOrEmpty(arg2) ? "" : arg2; var vInstance = new Levenshtein(); vInstance.InitVariable(vString1, vString2); vInstance.Compute(); return vInstance; } #endregion } }