背景

最近项目里面有业务需求需要计算文本相似度,这方面的算法挺多的,lcs就是其中的一个,lcs,就是求两个文本串的最长公共子序列问题,自己写了写,总结一下解决问题的整个过程。

最简单的解法:枚举

几乎所有最优化问题,都可以通过暴力枚举来解决,lcs也不例外,因为lcs问题父结构和子结构的求解方法相同,所以,我们可以通过递归来枚举。
但是有一个问题需要注意,我们枚举,实际上就是枚举出问题解决过程中所有可能出现的状态,这个状态,有可能是一个值,也有可能是一组值,如果一个值的话,这种情况一般比较好解决,但是如果是一组值的话,我们就需要想办法来保存这个状态。
要有状态的概念才行,不然可能枚举的话无从下手。lcs这个问题状态就是两个文本串相同的字符。每一组两个文本串相同的字符,就是一种状态,我们需要枚举所有的这种状态,来找到最长公共子串。

下面是我用枚举的方法写出来的程序,如下:

string MaxStr;

struct ChildStruct{
    int index_one;
    int index_two;
    string cs;
    ChildStruct(int one, int two, string c) : 
        index_one(one), index_two(two), cs(c){}
};

// 非DP解法:枚举所有状态
void search(const string& text_one, int index_one,
            const string& text_two, int index_two,
            string cur_str){
    queue<ChildStruct> q;

    for (int i = index_one; i < text_one.length(); ++i){
        for (int j = index_two; j < text_two.length(); ++j){
            if (text_one[i] == text_two[j]){
                ChildStruct cs(i, j, cur_str + text_one[i]);
                q.push(cs);
                break;
            }
        }
    }

    if (q.empty() && cur_str.length() > MaxStr.length()){
        MaxStr = cur_str;
    }

    while (!q.empty()){
        ChildStruct cur_cs = q.front();
        q.pop();
        search(text_one, cur_cs.index_one + 1,
               text_two, cur_cs.index_two + 1,
               cur_cs.cs);
    }
}

简单解释一下上面的程序,我们在search的嵌套for里面把text_one里面所有字符和text_two里所有字符相同的找出来,然后,每一个相同的都是一种状态,然后,我们再基于这种状态去枚举之后的所有状态。

用枚举解虽然简单,但是问题也很大,时间复杂度爆表,一旦两个文本串长度大一些,基本上就不实用了。所以,我们需要更高的算法来解决这个问题。

优化枚举:剪枝

我们上面的枚举算法,虽然最终能得出答案,但是这个解决问题的时间是一年还是两年,还是可能电脑报废了都计算不出答案也是可能的,所以,我们需要优化算法,来降低时间复杂度

优化枚举最容易想到的就是剪枝,将一些明显能看出不可能出现正确结果的分支剪掉,这样可以节省一大部分时间。

看我们上面的程序,如果text_one里面有很多相同的字符,那么这些相同的字符,我们拿第一个计算就好了,其余的就不用再浪费时间了,这里可以进行剪枝。
还有一个地方,如果已经计算好的公共子串和剩余还没有计算的子串长度加起来还不如现在已知的最好的公共子串长度的话,那么也没有必要浪费时间去计算了,只不过这个分支相比于上面的分支的话,有点鸡肋。

但是仅仅靠上面的两个剪枝,程序速度没有质的提升,文本串过大后,依然看不到跑完的希望,所以,我们需要继续来优化算法。

动态规划 -> 记忆搜索

我们这个时候,分析一下上面的程序到底是哪里浪费时间了,其实我们不用分析,稍微一想就能想到,这是一个明显的最优子结构、子问题重叠问题,父结构和子结构的求解思路一样,而且有大部分子问题是重叠的,时间浪费就浪费在重叠子问题的计算上。

如果我们能够解决这些重叠子问题计算时间的浪费,那么就能够把时间复杂度降到最低。

那么问题来了,怎样解决重叠子问题呢,这个最拿手的,肯定就是dp算法了。

dp解的话,又分为记忆搜索和递推两种,一般记忆搜索比递推要更容易理解,我们就先用记忆搜索写一下。

如果大家对最优子结构、重叠子问题,以及动态规划算法不熟的话,可以看我前面总结的动态规划问题的博客。

程序如下:

struct ChildStruct{
    int index_one;
    int index_two;
    string cs;
    ChildStruct(int one, int two, string s): index_one(one), index_two(two), cs(s){}

    bool operator<(const ChildStruct &rhs) const {
        if (index_one < rhs.index_one) return true;
        if (rhs.index_one < index_one) return false;
        if (index_two < rhs.index_two) return true;
        if (rhs.index_two < index_two) return false;
        return false;
    }
};

map<ChildStruct, string> mem_flag;
set<char> done;

string dp(const string& text_one, const int& index_one,
          const string& text_two, const int& index_two,
          const string& cur_str){
    queue<ChildStruct> q;
    done.clear();

    for (int i = index_one; i < text_one.length(); ++i){
        // 剪枝: 一层中相同的字符只需要用第一个字母来解即可
        if (done.count(text_one[i]) > 0) continue;
        for (int j = index_two; j < text_two.length(); ++j){
            if (text_one[i] == text_two[j]){
                string str; 
                str += text_one[i];
                q.push(ChildStruct(i, j, str));
                done.insert(text_one[i]);
                break;
            }
        }
    }

    string max_child;
    while (!q.empty()){
        ChildStruct cur_cs = q.front();
        q.pop();
        if (mem_flag.find(cur_cs) == mem_flag.end()){
            // 记忆最优子结构的解,解决重叠子问题浪费的时间
            mem_flag[cur_cs] = dp(text_one, cur_cs.index_one + 1, 
                                  text_two, cur_cs.index_two + 1,
                                  cur_cs.cs);
        }
        if (mem_flag[cur_cs].length() > max_child.length()){
            max_child = mem_flag[cur_cs];
        }
    }

    return cur_str + max_child;
}

如上,就是记忆搜索算法的解决方案,因为lcs问题满足最优子结构性质,所以,每一个子结构的求解,出来的都是他的最优解,这样,我们就能够对这个子结构的最优解做一个记录,当再次遇到相同子结构求解的时候,我们就直接从之前的记录中取出,这样就能节省重叠子问题计算的时间浪费。

到这里,我们已经基本解决了问题,但是,算法实现的对不对不能自己说,需要评测一下,我们找一个oj系统的题目来做一下.

我找了一个HDU的模板题做了一下,题目地址
结果悲剧了,没有ac,超时了,仔细一看,这个题目要求的是计算出长度即可,不需要记录公共子串的结果,好吧,我们优化一下。
不仅如此,我们记录状态的话,可以用一个预先分配好内容的二维数组来记录,而不是结构体,这样就能更好的优化。

优化以后的程序如下:

int mem_flag[500][500];

// 自顶向下:记忆搜索
int dp(const string& text_one, const int& index_one, const string& text_two, const int& index_two){
    set<char> done;
    int max_child = 0;

    for (int i = index_one; i < text_one.length(); ++i){
        // 剪枝:当前层所有相同的字符,用第一个来求解就可以
        if (done.count(text_one[i]) > 0) continue;
        for (int j = index_two; j < text_two.length(); ++j){
            // 如果字符相同,就进入这个相同的状态
            if (text_one[i] == text_two[j]){
                if (mem_flag[i][j] == 0)
                    // 基于本次相同的状态,去求解之后所有状态的情况
                    // 因为满足最优子结构的性质,所以求解出来的就是子结构的最优解
                    // 因为父结构和子结构的求解方式一样,所以可以递归解决
                    // 记录每个已经求结果的最优子结构,给后面重叠子问题的求解节省时间
                    mem_flag[i][j] = dp(text_one, i + 1, text_two, j + 1);
                //在本次所有的最优子结构的答案中,找到一个最长公共子串
                if (mem_flag[i][j] > max_child)
                    max_child = mem_flag[i][j];
                done.insert(text_one[i]);
                break;
            }
        }
    }
    return max_child + 1;
}

如上是我优化过后的程序,是不是一下变瘦了好多,๑乛◡乛๑(希望我也能一下变瘦好多)

我把优化后的程序又放在HDU上跑了一次,杯具继续,还是超市,纳尼(“▔㉨▔)汗,妈的,怎么回事。。。。

看来要逼我放大招了。。。
继续向下看↓

动态规划 -> 递推解法

我们前面已经说过,dp的问题,可以分为两种方案,一种是自顶向下递归记忆搜索解决,一种是自低向上递推解决,递归嘛,要涉及到一层一层的函数栈,速度肯定不如递推来的实在,于是乎,我们就写一下递推的解决方案试试吧。

程序如下:

// 自低向上:递推
int dp(const string& text_one, const string& text_two){
    for (int i = text_one.length() - 1; i >= 0; --i){
        for (int j = text_two.length() - 1; j >= 0; --j){
            if (text_one[i] == text_two[j]) 
                // 如果当前字符相同,这个时候,需要计算以text_one[i]和text_two[j]为首的公共子串的结果
                mem_flag[i][j] = mem_flag[i+1][j+1] + 1;
            else 
                // 如果当前字符不同,需要把之前所有比较情况下最好的结果向前推进
                // 用 i,j+1 和 i+1,j ,可以把所有 i+1,j+1 i+1,j i,j+1 三种情况的结果都递推过来
                mem_flag[i][j] = max(mem_flag[i][j+1], mem_flag[i+1][j]);
        }
    }
    return mem_flag[0][0];
}

以上,就是递推的解法,递推的话,我们需要计算好边界问题,这个不如记忆搜索好写,但是速度更快一些。

我又拿着递推的程序去HDU上跑了跑,嗯,这次果然过了。。。

总结

以上,就是我在解决lcs问题时的整个过程,比较有意思,后面有时间的话,会继续来优化~


原创文章,转载请注明地址: 文章地址