1

所以我一直在为 Perl 和 Python 做一些练习题（在两者之间进行选择），我遇到了一个问题，我需要像 Github 一样制作自己的差异算法。我已经知道最长公共子序列问题是解决方案的重要组成部分。我使用LCS 的维基百科页面作为参考，但我仍然无法找出差异部分。

我也意识到 CPAN 上已经有像 Algorithm:Diff 这样的模块，但这主要是为了练习，那些感觉像是在作弊。

我想出了算法的python/伪代码版本，但我打算用多维数组来做，而Perl似乎没有。

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

基本上我能想到的伪代码（几乎类似于 python，但应该用于 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))

我还没有实现它，但我认为这基本上就是我可以计算两个字符串的 LCS 长度的方法？

输出明智，它应该针对“人类”和“黑猩猩”（LCS = HMAN）返回 4

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

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

4

1 回答 1

0

您可以在 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-perl.blogspot.de 上的博客文章 Loopify Recursions），即不是递归的（大多数示例代码使用递归，在 Perl 中不能很好地扩展）。因此，如果您想从代码中学习，请查看 subs LCS() 和 _lcs()。

如果你想要差异，即编辑脚本，你可以从 LCS 数组重建它。

lcs2align() 方法几乎做到了这一点。

use Data::Dumper;
use LCS;
print Dumper(
  LCS->lcs2align(
    [qw(a   b)],
    [qw(a b b)],
    LCS->LCS([qw(a b)],[qw(a b b)])
  )
);
# prints
$VAR1 = [
          [
            'a',
            'a'
          ],
          [
            '',
            'b'
          ],
          [
            'b',
            'b'
          ]
];

sdiff() 格式的差异（参见 Algorithm::Diff）现在看起来像：

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

如何从对齐中获取编辑脚本应该是微不足道的，并留作练习。

如果你想要更快的实现，你可以使用 LCS::Tiny，或者最快的纯 Perl 实现 LCS::BV，或者最快的更大规模的 Algorithm::Diff::XS（参见我的博客文章 Tuning Algorithm::Diff at wollmers-perl .blogspot.de)

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

于 2015-06-18T08:32:26.973 回答