最长公共子序列问题 动态规划

Longest common sequences(LCS)

abdcd 和 rtdaibicpd的最长公共子序列就是abcd

这个问题如何求解?首先考虑暴力求解的方法,以一个串的第i个字符为基准,在另一个串中找到第一个相同的元素,然后将串截短,递归查找两个串的相同元素,然后直到i遍历完成。

abdcd rtdaibicpd。变成 bdcd ibicpd 中找LCS

递归总是不太友好的,容易联想到这种问题存在最优子结构的性质。 因此可以考虑用动态规划的思想来解决问题。

定义\(dp[i][j]\)表示第一串从第0到第i个字符构成的串可第二个字符从第0个到第j个字符构成的串的LCS长度。

考虑好dp数组边界条件就可以了,解是dp[n][m]。求解顺序是从小到大,时间复杂度在O(nm)量级上。

一种用python的简单实现:

def LCS(a, b):
    n, m = len(a), len(b)
    dp = {}
    for i in range(n + 1):
        dp[i, 0] = 0
    for j in range(n + 1):
        dp[0, j] = 0
    for i in range(1, n + 1):
        for j in range(m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i, j] = dp[i - 1, j - 1] + 1
            else:
                dp[i, j] = max(dp[i -1, j], dp[i, j - 1])
    return dp[n, m]

在自然语言处理中的文本摘要任务中的一个评价指标ROUGH-L中,就用这个算法的应用,也可以在rouge这个python第三方库中rough-l算法的实现方法中看到动态规划方法实现的LCS算法的身影,见下图。

发表评论

电子邮件地址不会被公开。 必填项已用*标注