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

问题

许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程度。我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
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;
}

编辑距离的应用

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