从最长公共子序列打印差异

Question

因此，我一直在为Perl和Python做一些实践问题（在2种方法之间进行选择），我遇到了一个问题，我需要像Github一样创建自己的diff算法。 我知道最长的公共子序列问题是解决方案的一个重要部分。我使用了wikipedia page for LCS作为参考，但是我仍然无法确定diff部分。在

我也意识到已经有类似CPAN的模块了算法：Diff，但这主要是为了练习，那些感觉像作弊的人。在

我找到了这个算法的python/pseudocode版本，但我计划用多维数组来实现，Perl似乎没有。在

现在我可以成功地获得Perl中最长的公共子序列长度了。在

基本上，我能想到的伪代码是这样的：

function lengthOfLCS(string1, string2){
    if length(string1) == 0 or length(string2) == 0:
         return 0
    else if string1[0] eq string2[0]: 
         return 1+ lengthOfLCS(stringA[1:], stringB[1:])
    return max(lengthOfLCS(string1, string2[1:], lengthOfLCS(string1[1:], string2))

我还没有实现它，但我想这基本上就是如何计算两个字符串的lc的长度的？在

输出方面，对“人类”和“黑猩猩”（LCS=HMAN）应该返回4

所以我要问的是，从现在开始，如何使用Perl打印diff？我知道应该返回一个List/Array，而不是只返回LCS的长度，这可以通过在LCS函数中返回多维列表，然后在单独的diff函数中处理它来实现。在

我对Perl有点陌生，所以如果有任何指针/提示，我将不胜感激。 谢谢。在

Answer 1

您可以在Perl中使用我的LCS的引用实现，它需要两个数组引用作为输入，并返回一个包含两个元素数组的数组，其中包含匹配元素的索引。在

use LCS;
my $lcs = LCS->LCS( [qw(a b)], [qw(a b b)] );
# $lcs now contains an arrayref of matching positions
# same as
$lcs = [
  [ 0, 0 ],
  [ 1, 2 ]
];

LCS使用传统的算法并迭代地读取LCS（请参阅我在wollmers的博客文章loopifyrecursions）-perl.blogspot.de)，即不是递归的（大多数示例代码使用递归，这在Perl中不能很好地伸缩）。因此，如果您想从代码中学习，可以研究subs LCS（）和\u LCS（）。在

如果需要diff，即编辑脚本，可以从LCS数组重建它。在

lcs2align（）方法几乎可以做到这一点。在

^{pr2}$

sdiff（）（see Algorithm::Diff）格式的diff现在看起来像：

[
  [ 'u', 'a', 'a'  ],
  [ '+', '',  'b'  ],
  [ 'u', 'b', 'b'  ],
]

如何从对齐中获取编辑脚本应该是很简单的，可以留作练习。在

如果您想要更快的实现，可以使用LCS:：Tiny，或者最快的纯Perl实现LCS:：BV，或者更大规模的最快算法：：Diff:：XS（请参阅我在wollmers的博客Tuning Algorithm:：Diff）-perl.blogspot.de)在

请记住，基于LCS的脚本不会自动编辑。LCS基于编辑操作，仅允许插入和删除（简单编辑距离）。SES算法通常最小化Levenshtein距离（插入、删除和不匹配）。在