# 比较string与宽容

“两个string之间的Levenshtein距离被定义为将一个string转换为另一个string所需的最小编辑次数，允许的编辑操作是插入，删除或replace单个字符。 – 维基百科

``using System; /// <summary> /// Contains approximate string matching /// </summary> static class LevenshteinDistance { /// <summary> /// Compute the distance between two strings. /// </summary> public static int Compute(string s, string t) { int n = s.Length; int m = t.Length; int[,] d = new int[n + 1, m + 1]; // Step 1 if (n == 0) { return m; } if (m == 0) { return n; } // Step 2 for (int i = 0; i <= n; d[i, 0] = i++) { } for (int j = 0; j <= m; d[0, j] = j++) { } // Step 3 for (int i = 1; i <= n; i++) { //Step 4 for (int j = 1; j <= m; j++) { // Step 5 int cost = (t[j - 1] == s[i - 1]) ? 0 : 1; // Step 6 d[i, j] = Math.Min( Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost); } } // Step 7 return d[n, m]; } } class Program { static void Main() { Console.WriteLine(LevenshteinDistance.Compute("aunt", "ant")); Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha")); Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax")); } }` `

.NET框架中没有任何东西可以帮助你实现这个开箱即用的function。

Metaphone和Soundex的区别在于Soundex产生固定长度的数字键，而Metaphone产生不同长度的键，所以结果将会不同。 最后，两者都会为你做同样的比较，你只需要根据你的要求和资源（当然还有拼写错误的不容忍等级），找出最适合你的需求。

` ` /// <summary> /// Calculates the Levenshtein distance between two strings--the number of changes that need to be made for the first string to become the second. /// </summary> /// <param name="first">The first string, used as a source.</param> /// <param name="second">The second string, used as a target.</param> /// <returns>The number of changes that need to be made to convert the first string to the second.</returns> /// <remarks> /// From http://www.merriampark.com/ldcsharp.htm /// </remarks> public static int LevenshteinDistance(string first, string second) { if (first == null) { throw new ArgumentNullException("first"); } if (second == null) { throw new ArgumentNullException("second"); } int n = first.Length; int m = second.Length; var d = new int[n + 1, m + 1]; // matrix if (n == 0) return m; if (m == 0) return n; for (int i = 0; i <= n; d[i, 0] = i++) { } for (int j = 0; j <= m; d[0, j] = j++) { } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int cost = (second.Substring(j - 1, 1) == first.Substring(i - 1, 1) ? 0 : 1); // cost d[i, j] = Math.Min( Math.Min( d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost); } } return d[n, m]; }` `

` `public static int LevenshteinDistance(string source, string target) { // degenerate cases if (source == target) return 0; if (source.Length == 0) return target.Length; if (target.Length == 0) return source.Length; // create two work vectors of integer distances int[] v0 = new int[target.Length + 1]; int[] v1 = new int[target.Length + 1]; // initialize v0 (the previous row of distances) // this row is A[0][i]: edit distance for an empty s // the distance is just the number of characters to delete from t for (int i = 0; i < v0.Length; i++) v0[i] = i; for (int i = 0; i < source.Length; i++) { // calculate v1 (current row distances) from the previous row v0 // first element of v1 is A[i+1][0] // edit distance is delete (i+1) chars from s to match empty t v1[0] = i + 1; // use formula to fill in the rest of the row for (int j = 0; j < target.Length; j++) { var cost = (source[i] == target[j]) ? 0 : 1; v1[j + 1] = Math.Min(v1[j] + 1, Math.Min(v0[j + 1] + 1, v0[j] + cost)); } // copy v1 (current row) to v0 (previous row) for next iteration for (int j = 0; j < v0.Length; j++) v0[j] = v1[j]; } return v1[target.Length]; }` `

` `/// <summary> /// Calculate percentage similarity of two strings /// <param name="source">Source String to Compare with</param> /// <param name="target">Targeted String to Compare</param> /// <returns>Return Similarity between two strings from 0 to 1.0</returns> /// </summary> public static double CalculateSimilarity(string source, string target) { if ((source == null) || (target == null)) return 0.0; if ((source.Length == 0) || (target.Length == 0)) return 0.0; if (source == target) return 1.0; int stepsToSame = LevenshteinDistance(source, target); return (1.0 - ((double)stepsToSame / (double)Math.Max(source.Length, target.Length))); }` `