我需要计算2个字符串之间的相似度。那我到底是什么意思?让我用一个例子来解释:
hospital
haspita
现在,我的目标是确定需要修改多少个字符才能得到真实的单词。在此示例中,我需要修改2个字母。那么百分比是多少?我总是用真实的字眼来形容。因此它变为2/8 = 25%,因此这两个给定的字符串DSM为75%。
如何将性能作为主要考虑因素来实现?
您要查找的内容称为 编辑距离 或 Levenshtein距离 。维基百科文章解释了它是如何计算的,并且在底部有一段不错的伪代码,可帮助您非常轻松地用C#编写此算法。
这是第一个链接在下面的站点的实现:
private static int CalcLevenshteinDistance(string a, string b) { if (String.IsNullOrEmpty(a) && String.IsNullOrEmpty(b)) { return 0; } if (String.IsNullOrEmpty(a)) { return b.Length; } if (String.IsNullOrEmpty(b)) { return a.Length; } int lengthA = a.Length; int lengthB = b.Length; var distances = new int[lengthA + 1, lengthB + 1]; for (int i = 0; i <= lengthA; distances[i, 0] = i++); for (int j = 0; j <= lengthB; distances[0, j] = j++); for (int i = 1; i <= lengthA; i++) for (int j = 1; j <= lengthB; j++) { int cost = b[j - 1] == a[i - 1] ? 0 : 1; distances[i, j] = Math.Min ( Math.Min(distances[i - 1, j] + 1, distances[i, j - 1] + 1), distances[i - 1, j - 1] + cost ); } return distances[lengthA, lengthB]; }