c# - LCS算法：如何从一个表中找出，找到了多少个最长的公共子序列？

Question

我在 C# 中实现了最长公共子序列问题。我需要检测两个字符串之间的所有常见最大子序列。

为此，我使用Needleman-Wunsch 算法创建了一个表，用于存储每个计算步骤的 LCS 序列。

是否有机会确定找到了多少个最大子序列（使用表格）？

根据这一点，我想选择一种方法来收集每个子序列。关键是，对于一个子序列递归是不需要的，所以它会提供更好的性能。它对我的任务至关重要。

这是一个代码片段，其中实现了项目的基本功能：

    private static int[][] GetMatrixLCS(string x, string y)
        {
            var lenX = x.Length;
            var lenY = y.Length;
            matrixLCS = new int[lenX + 1][];
            for (var i = 0; i < matrixLCS.Length; i++)
            {
                matrixLCS[i] = new int[lenY + 1];
            }
            for (int i = 0; i <= lenX; i++)
            {
                for (int j = 0; j <= lenY; j++)
                {
                    if (i == 0 || j == 0)
                        matrixLCS[i][j] = 0;
                    else
                    if (x[i - 1] == y[j - 1])
                        matrixLCS[i][j] = matrixLCS[i - 1][j - 1] + 1;
                    else
                        matrixLCS[i][j] = Math.Max(matrixLCS[i - 1][j], matrixLCS[i][j - 1]);
                }
            }
            return matrixLCS;
        }

    static HashSet<string> FindAllLcs(string X, string Y, int lenX, int lenY)
        {
            var set = new HashSet<string>();
            if (lenX == 0 || lenY == 0)
                return emptySet;
            if (X[lenX - 1] == Y[lenY - 1])
            {
                var tempResult = FindAllLcs(X, Y, lenX - 1, lenY - 1);
                foreach (var temp in tempResult)
                    set.Add(temp + X[lenX - 1]);
                return set;
            }
            if (matrixLCS[lenX - 1][lenY] >= matrixLCS[lenX][lenY - 1])
                set = FindAllLcs(X, Y, lenX - 1, lenY);
            if (matrixLCS[lenX][lenY - 1] >= matrixLCS[lenX - 1][lenY])
                set.UnionWith(FindAllLcs(X, Y, lenX, lenY - 1));
            return set;
        }

以及具有两种输入和预期输出的示例：

    public void SingleOutput()
    {
    var sequence = LCS.FindLCS("ABC", "AB");
    Assert.AreEqual(1, sequence.Length);
    Assert.AreEqual("AB", sequence[0]);
    }

    public void MultipleOutput() 
    { 
    var sequence = LCS.FindLCS("BCAB", "ABC"); 
    Assert.AreEqual(2, sequence.Length); 
    Assert.AreEqual("AB", sequence [0]);
    Assert.AreEqual("BC", sequence [1]);
    }

任何帮助将不胜感激。

标签： c#algorithmlcsneedleman-wunsch

Answer 1

最简单的方法是使用朴素的实现通过矩阵记录迭代期间的所有匹配。

如果其他算法提供有效的解决方案，我需要allLCS()进行测试，这必须是所有可能的 LCS 之一。

代码在github 上。

它在 Perl 中，但很容易理解。遍历矩阵并在单元格中添加匹配项。最后右下角的单元格包含 LCS 的长度。这就是天真的算法。现在在每次匹配时将坐标记录为哈希中的数组 [i,j]，匹配计数作为键。

# get all LCS of two arrays
# records the matches by rank
sub allLCS {
  my ($self,$X,$Y) = @_;

  my $m = scalar @$X;
  my $n = scalar @$Y;

  my $ranks = {}; # e.g. '4' => [[3,6],[4,5]]
  my $c = [];
  my ($i,$j);

  for (0..$m) {$c->[$_][0]=0;}
  for (0..$n) {$c->[0][$_]=0;}
  for ($i=1;$i<=$m;$i++) {
    for ($j=1;$j<=$n;$j++) {
      if ($X->[$i-1] eq $Y->[$j-1]) {
        $c->[$i][$j] = $c->[$i-1][$j-1]+1;
        push @{$ranks->{$c->[$i][$j]}},[$i-1,$j-1];
      }
      else {
        $c->[$i][$j] =
          ($c->[$i][$j-1] > $c->[$i-1][$j])
            ? $c->[$i][$j-1]
            : $c->[$i-1][$j];
      }
    }
  }
  my $max = scalar keys %$ranks;
  return $self->_all_lcs($ranks,1,$max);
} 

最后，这个记录匹配的集合通过以下方法连接_all_lcs()：

sub _all_lcs {
  my ($self,$ranks,$rank,$max) = @_;

  my $R = [[]];

  while ($rank <= $max) {
    my @temp;
    for my $path (@$R) {
      for my $hunk (@{$ranks->{$rank}}) {
        if (scalar @{$path} == 0) {
          push @temp,[$hunk];
        }
        elsif (($path->[-1][0] < $hunk->[0]) && ($path->[-1][1] < $hunk->[1])) {
          push @temp,[@$path,$hunk];
        }
      }
    }
    @$R = @temp;
    $rank++;
  }
  return $R;
}

代码受论文启发

罗纳德 I. 格林伯格。所有最长公共子序列的快速简单计算