最近编辑距离问题

2019-04-26  本文已影响0人  彳亍cium

最近编辑距离问题

1. 问题描述

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

  将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。设计一个有效算法,对任意给定的2个字符串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\},则可能发生的情况有:

  1. x_m = y_n,则z_k=x_m=y_n,且Z_{k-1}X_{m-1}Y_{n-1}的最长公共子序列。
  2. x_m \ne y_nz_k \ne x_m,则ZX_{m-1}Y_n的最长公共子序列。
  3. x_m \ne y_nz_k \ne y_n,则ZX_{m}Y_{n-1}的最长公共子序列。
两个序列的最长公共子序列包含了这两个蓄力的前缀的最长公共子序列。因此,最长子序列问题具有最优子结构性质

2. 算法设计

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

  1. x[i] == x[j]
  2. x[i] >= x[j]
  3. 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
上一篇 下一篇

猜你喜欢

热点阅读