比较string与宽容

我正在寻找一种方法来比较一个string与一个string数组。 做一个精确的search当然很容易，但是我希望我的程序能够容忍拼写错误，缺lessstring的部分等等。

有什么样的框架可以执行这样的search？ 我有一些记住，searchalgorithm会返回匹配的百分比或类似这样的几个结果顺序。

Answer 1

你可以使用Levenshtein距离algorithm 。

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

这个来自dotnetperls.com ：

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")); } } 

实际上，您可能更喜欢使用Damerau-Levenshtein距离algorithm ，该algorithm也允许字符转置，这是数据input中常见的人为错误。 你会在这里find它的C＃实现。

Answer 2

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

最常见的拼写错误是那些字母是一个体面的语音代表的单词，而不是正确的拼写。

例如，可以认为， sword和sord （是的，这是一个词）具有相同的语音根源（当你发音时，它们听起来是一样的）。

这就是说，有很多algorithm可以用来将单词（甚至是拼写错误的单词）翻译成语音变体。

首先是Soundex 。 这个algorithm相当简单，并且有相当数量的.NETalgorithm实现 。 这很简单，但它给你真正的价值，你可以相互比较。

另一个是Metaphone 。 虽然我找不到Metaphone的本地.NET实现，但所提供的链接还包含可以转换的其他许多实现的链接。 最容易转换的可能是Metaphonealgorithm的Java实现 。

应该指出的是，Metaphonealgorithm已经过修改。 有双重Metaphone （有一个.NET实现 ）和Metaphone 3 。 Metaphone 3是一个商业应用程序，但准确率为98％，而对于常用英语单词数据库运行时，Double Metaphonealgorithm的准确率为89％。 根据您的需要，您可能希望查找（在双倍audio的情况下）或购买（在Metaphone 3的情况下）该algorithm的源，并通过P / Invoke层转换或访问它（有C ++实现盛产）。

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

Answer 3

这里有两个方法可以计算string之间的Levenshtein距离 。

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

一旦你有了结果，你需要定义你想要使用什么值作为比赛的门槛。 对一堆样本数据运行该函数，以了解它是如何工作的，以帮助确定您的特定阈值。

  /// <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]; } 

Answer 4

你的另一种select是比较语音使用Soundex或Metaphone。 我刚刚完成了一篇介绍这两种algorithm的C＃代码的文章。 您可以在http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex查看它。;

Answer 5

您可以在开源的CommonLibrary.NET项目中findsoundex和levenshtein距离algorithm的实现。

Answer 6

这里是LevenshteinDistance方法的实现，它使用更less的内存，同时产生相同的结果。 这是在这个维基百科文章的“迭代与两个matrix行”标题下find的伪代码的C＃改编。

 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))); }