algorithm - 动态规划 : Longest Common Subsequence

Question

我将复习在寻找两个等长字符串的最长公共(public)子序列的上下文中讨论动态规划的笔记。有问题的算法输出长度(不是子字符串)。

所以我有两个字符串，比如说:

S = ABAZDC，T = BACBAD

最长公共(public)子序列是 ABAD(子串不必是相邻的字母)

算法如下，其中LCS[i, j]表示S[1..i]和T[1..j]的最长公共(public)子序列:

if S[i] != T[j] then
    LCS[i, j] = max(LCS[i - 1, j], LCS[i, j - 1])
else
    LCS[i, j] = 1 + LCS[i - 1, j - 1]

我的笔记声称您可以填写一个表格，其中每个字符串都沿着一个轴书写。像这样的东西:

B A C B A D

A 0 1 1 1 1 1

B 1 1 1 2 2 2

一个...

Z

D

C

两个问题:

1) 我们实际上是如何开始填写这张表的。算法是递归的，但似乎没有提供基本情况(否则我只会调用 LCS[5, 5])？笔记声称你可以用 i 和 j 做两个简单的循环，并在恒定时间内填写每个点......

2) 我们如何修改算法以使最长公共(public)子序列为相邻字母？我的想法是，一旦我发现 S 中的下一个字母与 T 中的下一个字母不匹配，我就必须将当前子序列的长度重置为 0。但这很棘手，因为我想跟踪最长的到目前为止(我看到的第一个子序列可能是最长的)。所以也许我会有一个额外的参数，longestThusFar，当我们最初调用我们的算法并在后续调用中更改时，它是 0。

有人可以让这个更严格一点吗？

谢谢!

Answer 1

首先，算法是递归的，但实现总是迭代的。换句话说，我们没有显式地从函数本身调用同一个函数(递归)。

我们使用已经填充的表条目来补偿递归。

比如说，你有两个长度为 M 的字符串。

然后定义一个表的维度(M+1)X(M+1)。

for(i = 0 to M)
{
  LCS[0][i]=0;
}
for(i = 1 to M)
{
  LCS[i][0]=0;
}

然后你得到一张像这样的 table

    B,A,C,B,A,D
  0,0,0,0,0,0,0
A 0
B 0
A 0
Z 0
D 0
C 0

0th col中的每个零表示如果不考虑字符串BACBAD的字符，则LCS的长度= 0。

第 0 行中的每个零表示如果不考虑字符串 ABAZDC 的字符，则 LCS 的长度 = 0。

其余条目使用您提到的规则填写。

for(i = 1 to M)
{
 for(j = 1 to M)
 {
  if S[i-1] != T[j-1] then
    LCS[i, j] = max(LCS[i - 1, j], LCS[i, j - 1])
  else
    LCS[i, j] = 1 + LCS[i - 1, j - 1]
 }
}

注意它是 S[i-1] != T[j-1] 而不是 S[i] != T[j] 因为当你填充LCS[i,j]，您总是比较S 的第 i-1 个字符和 T 的第 j-1 个字符。

LCS 的长度由LCS[M,M] 给出。

理解这一点的最好方法是亲自尝试。

在回答你的第二个问题时，你不需要对算法做太多修改。

解决方案在于用于检索 LCS 的表。

为了检索 LCS，我们创建了一个额外的 T 表，其中包含维度为 MXM 的字符。我们修改算法如下。

for(i = 1 to M)
{
 for(j = 1 to M)
 {
  if S[i-1] != T[j-1] then
  {
     LCS[i, j] = max(LCS[i - 1, j], LCS[i, j - 1])
     if(LCS[i - 1, j]>=LCS[i, j - 1])          
      T[i-1][j-1]='u'//meaning up
     else T[i-1][j-1]='l'//meaning left
  }
  else
  {
    LCS[i, j] = 1 + LCS[i - 1, j - 1]
    T[i-1][j-1]='d'//meaning diagonally up
  }
 }
}

现在，为了知道两者共有的最长子串(OF ADJACENT LETTERS)，沿对角线遍历 T。

长度 = 在对角线上找到的连续 d 的最大数量。

任意方阵NXN的对角线遍历由.

包含主对角线的下三角

j=N-1
while(j>=0)
{
 i=j;k=0;
 while(i <= N-1)
 {
  entry T[i][k];
  ++i;++k
 }
 --j;
}

上三角

j=1;
while(j<=N-1)
{
 i=j;k=0;
 while(i<=N-1)
 {
  entry T[k][i];
  ++k;++i;
 }
 --j;
}