字符串相似度(编辑距离)

发表于 | 分类于 |

问题

许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：
1.修改一个字符（如把“a”替换为“b”）。
2.增加一个字符（如把“abdd”变为“aebdd”）。
3.删除一个字符（如把“travelling”变为“traveling”）。
比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g“的方式来达到目的。上面的两种方案，都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，给定任意两个字符串，写出一个算法来计算出它们的距离

分析

目前正在实习这家公司的笔试题，当时拿到题，就感觉似曾相识。回学校后，翻了翻之前的学习资料，在牛客网的算法面试题中找到了原型。它的确是一道经典的dp，其处理问题的方式，也是dp的常用套路。

编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。

假设当前有两个字符串，它们分别是str1和str2。dp[i][j]的含义：str2("0->i")通过操作变成str1("0->j")的编辑距离

考虑以下三种情况
str2("0->i")与str1("0->j-1")相同，在末尾增加一个str1[j]字符，故此时dp[i][j] = dp[i][j-1] + 1；
str2("0->i-1")与str1("0->j")相同，在末尾删除一个str2[i]字符，故此时dp[i][j] = dp[i-1][j] + 1；
str2("0->i-1")与str1("0->j-1")相同，根据str2[i]与str1[j]的相等情况，分别考虑。str2[i]等于str1[j]时，无需任何操作，故此时dp[i][j] = dp[i-1][j-1];str2[i]不等于str1[j]时，替换str2[i]字符为str1[j]字符，故此时dp[i][j] = dp[i-1][j-1] + 1；

根据上面的讨论，我们可以看到dp[i][j]的值依赖它左上角的3个dp值。在程序的开始阶段，我们应首先计算得到最不需要依赖的dp值，也就是整个dp二维数组中的第一行与第一列。

int minValue(int a, int b, int c)
{
    int t = a <= b ? a:b;
    return t <= c ? t:c;
}

int calculateStringDistance(string strA, string strB)
{
    int lenA = (int)strA.length();
    int lenB = (int)strB.length();

    //二维数组的内存分配，dp为一个数组指针
    int **dp = new int*[lenA];
    for (int i = 0; i < lenA; i++)
    {
        dp[i] = new int[lenB];
    }

    //初始化不需要依赖的dp值
    for(int i = 0; i < lenA; i++) dp[i][0] = i;
    for(int j = 0; j < lenB; j++) dp[0][j] = j;
    dp[0][0] = 0;

    //根据dp依赖的三种情况，从(1,1)位置处开始计算dp值
    for(int i = 1; i < lenA; i++)
    {
        for(int j = 1; j < lenB; j++)
        {
            if(strB[j-1] == strA[i-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = minValue(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1;
        }
    }

    int ret =  dp[lenA-1][lenB-1];

    //释放内存空间,先释放dp[i]的内存，再释放dp
    for(int i = 0; i < lenA; i++)
        delete [] dp[i];
    delete []dp;

    return ret;
}

int main()
{
    string A = "abcdefg";
    string B = "abcdef";
    cout <<calculateStringDistance(A, B) << endl;
}

编辑距离的应用

小规模的字符串近似搜索，类似于搜索引擎中输入关键字，出现类似的结果列表，具体实现细节，有兴趣可以移步字符串近似搜索，进行更多的了解。