小编典典

如何计算给定2个字符串的距离相似性度量?

c#

我需要计算2个字符串之间的相似度。那我到底是什么意思?让我用一个例子来解释:

  • 真实的话: hospital
  • 错误词: haspita

现在,我的目标是确定需要修改多少个字符才能得到真实的单词。在此示例中,我需要修改2个字母。那么百分比是多少?我总是用真实的字眼来形容。因此它变为2/8 =
25%,因此这两个给定的字符串DSM为75%。

如何将性能作为主要考虑因素来实现?


阅读 208

收藏
2020-05-19

共1个答案

小编典典

您要查找的内容称为 编辑距离
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];
    }
2020-05-19