我需要计算两个字符串之间的相似性.那我到底是什么意思?让我举个例子来解释:
- 真实的世界:
hospital
- 错误的单词:
haspita
现在我的目标是确定需要修改多少个字符才能获得真正的单词.在本例中,我需要修改2个字母.那么百分比是多少呢?我总是取真实单词的长度.所以它变成2/8=25%,所以这2个给定的字符串DSM是75%.
在性能成为关键考虑因素的情况下,我如何实现这一目标?
我需要计算两个字符串之间的相似性.那我到底是什么意思?让我举个例子来解释:
hospital
haspita
现在我的目标是确定需要修改多少个字符才能获得真正的单词.在本例中,我需要修改2个字母.那么百分比是多少呢?我总是取真实单词的长度.所以它变成2/8=25%,所以这2个给定的字符串DSM是75%.
在性能成为关键考虑因素的情况下,我如何实现这一目标?
你要找的是edit distance或Levenshtein distance.维基百科的文章解释了它是如何计算的,底部有一段很好的伪代码,可以帮助你很容易地用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];
}