最近编辑距离问题

1. 问题描述

设A和B是两个字符串。要用最少的字符操作将字符串A转换成字符串B。这里所说的字符操作包括：（1）删除一个字符；（2）插入一个字符；（3）将一个字符改为另一个字符。

将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为 $d(A,B)$ 。设计一个有效算法，对任意给定的2个字符串A和B，计算他们的编辑距离 $d(A,B)$ 。

数据输入: 有文件input.txt提供数据。文件的第一行是字符串A，文件的第二行是字符串B。
结果输出: 将编辑距离 $d(A,B)$ 输出到文件的第一行。

1.1. 问题分析

从字符串A转换成字符串B，势必要更改B中含有而A中不含有的字符的个数，同理，就是在字符串A和字符串B中找到最长的公共子序列，这是可以保持不变的部分。找到公共的最长子序列，再将字符串A和字符串B长度的最大值 $max(A.length(),B.length())$ 减去公共最长子序列的长度，就是最近的编辑距离。那么问题就转换为书中的典型例题公共最长子序列问题。

1.2. 动态规划分析

设序列 $X = \{x_1,x_2, \cdots ,x_m \}$ 和 $Y= \{y_1,y_2, \cdots ,y_n \}$ 的最长公共子序列为 $Z=\{z_1,z_2,\cdots ,z_k\}$ ，则可能发生的情况有：

若 $x_m = y_n$ ,则 $z_k=x_m=y_n$ ，且 $Z_{k-1}$ 是 $X_{m-1}$ 和 $Y_{n-1}$ 的最长公共子序列。
若 $x_m \ne y_n$ 且 $z_k \ne x_m$ ,则 $Z$ 是 $X_{m-1}$ 和 $Y_n$ 的最长公共子序列。
若 $x_m \ne y_n$ 且 $z_k \ne y_n$ ,则 $Z$ 是 $X_{m}$ 和 $Y_{n-1}$ 的最长公共子序列。

两个序列的最长公共子序列包含了这两个蓄力的前缀的最长公共子序列。因此，最长子序列问题具有最优子结构性质

2. 算法设计

问题具有最优子结构性质，则可以利用动态规划算法来设计问题的解答，计算最长公共子序列，这里只需要计算长度即可，不必缓存公共子序列。根据上面的最优子结构可以建立递归关系，用 $maxLength[i][j]$ 记录序列 $X_i$ 和 $Y_j$ 的最长公共子序列的长度。其中 $X_i = \{x_1,x_2,\cdots, x_i\}; Y_j = \{y_1,y_2,\cdots,y_j\}$ 。当问题规模降到很小时，即 $i==0$ 或者 $j==0$ 时，问题自然得解，空序列是 $X_i$ 和 $Y_j$ 的最长公共子序列，长度为 $0$ 。下面其他的情况可由递推式得到

$maxLength[i][j] = \begin{cases} 0 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad i=0,j=0\\ maxLength[i-1][j-1] +1 \qquad \qquad \qquad \qquad \qquad \quad i,j>0;x_i =y_j\\ max\{maxLength[i][j-1],maxLength[i-1][j]\} \qquad i,j>0;x_i \ne y_j \end{cases}$
实现上述递归式可以写出下面的递归算法。recordProblem[i][j]用于记录 $X_i$ $Y_j$ 符合下面哪种情况，

$x[i] == x[j]$
$x[i] >= x[j]$
$x[i] < x[j]$

void EditDistance::LCSLength(size_t *** recordProblem, size_t  *** maxLength) {
    int row, line;

    for(row = 1; row <= m_ALength; row ++)
        (*maxLength)[row][0] = 0;
    for(line = 1; line <= m_BLength; line++)
        (*maxLength)[0][line] = 0;

    for(row = 1; row <= m_ALength; row++ )
        for(line = 1; line <= m_BLength; line++)
        {
            if(m_A[row] == m_B[line])
            {
                (*maxLength)[row][line] = (*maxLength)[row-1][line-1]  + 1;
                (*recordProblem)[row][line] = 1;
            }
            else if((*maxLength)[row - 1][line] > (*maxLength)[row][line - 1])
            {
                (*maxLength)[row][line] = (*maxLength)[row - 1 ][line];
                (*recordProblem)[row][line] = 2;
            }
            else
            {
                (*maxLength)[row][line] = (*maxLength)[row][line - 1];
                (*recordProblem)[row][line] = 3;
            }
        }
}

主函数中调用时需要把字符串A和字符串B长度的最大值 $max(A.length(),B.length())$ 减去公共最长子序列的长度

    test.LCSLength(record,max);
    std::cout << (*max)[test.getALength()][test.getBLength()]<<std::endl;
    size_t maxLength = (*max)[test.getALength()][test.getBLength()];
    if(test.getALength()  > test.getBLength())
        std::cout<<test.getALength() - maxLength <<std::endl;
    else
        std::cout<<test.getBLength() - maxLength <<std::endl;

2.1. 时间复杂度分析

上面的循环有两层，外层要循环m_ALength多次，而内层要循环m_BLength次，所以时间复杂度为 $O(mn)$ ,其中m，n分别两个序列的长度。

2.2. 结果验证

屏幕快照 2019-04-26 下午3.16.49.png