6

我正在编写一个差异文本工具来比较两个相似的源代码文件。

周围有很多这样的“差异”工具，但我的应该会有所改进：

如果它发现一组行在两边不匹配（即在两个文件中），它不仅应突出显示这些行，还应突出这些行中的各个更改（我在这里称之为行间比较）。

我的一些可行的解决方案的一个例子：

替代文本 http://files.tempel.org/tmp/diff_example.png

它目前所做的是采用一组不匹配的行并再次通过差异算法运行它们的单个字符，从而产生粉红色突出显示。

但是，包含“原始 2”的第二组不匹配需要更多工作：这里，添加了前两行右侧（“添加的行 a/b”），而第三行是左侧的更改版本。我希望我的软件能够检测到可能的更改和可能的新行之间的差异。

在看这个简单的例子时，我可以很容易地检测到这种情况：

使用 Levenshtein 之类的算法，我可以发现在 3 到 5 组中的所有右行中，第 5 行与左行 3 匹配得最好，因此我可以推断出添加了右侧的第 3 行和第 4 行，并执行 inter - 左行 3 和右行 5 的行比较。

到目前为止，一切都很好。但是我仍然坚持如何将其变成为此目的的更通用的算法。

在更复杂的情况下，一组不同的线条可能会在两侧添加线条，中间有一些紧密匹配的线条。这变得相当复杂：

我不仅必须将左侧的第一行与右侧的最佳行匹配，反之亦然，以此类推。基本上，我必须将左边的每一行与右边的每一行相匹配。在最坏的情况下，这可能会产生甚至交叉，因此不再容易清楚哪些行是新插入的，哪些行是刚刚更改的（注意：我不想处理这样一个块中可能移动的行，除非这实际上会简化算法）。

当然，这永远不会是完美的，但我正在努力让它变得比现在更好。任何不太理论但相当实用的建议（我不太了解抽象算法）都会受到赞赏。

更新

我必须承认我什至不明白 LCS 算法是如何工作的。我只是简单地给它输入两个字符串数组，然后输出一个不匹配的序列列表。我基本上使用这里的代码：http: //www.incava.org/projects/java/java-diff

查看代码，我发现一个函数 equal() 负责告诉算法两行是否匹配。根据 Pavel 的建议，我想知道这是否是我进行更改的地方。但是怎么做？这个函数只返回一个布尔值——而不是一个可以识别匹配质量的相对值。而且我不能简单地使用一个固定的 Levenshtein 配给来决定一条类似的线是否仍然被认为是相等的——我需要一些能够自我采用的东西来适应整个有问题的线。

所以，我基本上要说的是，我仍然不明白我将在哪里应用与不（完全）匹配的线条的相对相似性相关的模糊值。

4

3 回答 3

3

Levenshtein 距离基于将一个字符串转换为另一个字符串的“编辑脚本”的概念。它与用于通过插入间隙字符对齐 DNA 序列的Needleman-Wunsch 算法非常密切相关，在该算法中，我们使用动态编程搜索在 O( nm ) 时间内最大化得分的对齐方式。字符之间的完全匹配会增加分数，而不匹配或插入的空白字符会降低分数。AACTTGCCA和的对齐示例AATGCGAT：

AACTTGCCA-
AA-T-GCGAT
(6 matches, 1 mismatch, 3 gap characters, 3 gap regions)

我们可以认为顶部字符串是“开始”序列，我们正在将其转换为底部的“最终”序列。-底部包含空格字符的每一列是一个删除，顶部包含一个空格字符的每一列-是一个插入，而具有不同（非间隙）字符的每一列是一个替换。上述比对中有2个缺失，1个插入和1个替换，所以Levenshtein距离为4。

这是相同字符串的另一种对齐方式，具有相同的 Levenshtein 距离：

AACTTGCCA-
AA--TGCGAT
(6 matches, 1 mismatch, 3 gap characters, 2 gap regions)

但请注意，尽管间隙数量相同，但间隙区域却少了一个。由于生物过程比多个单独的间隙更可能产生较大的间隙，因此生物学家更喜欢这种对齐方式——您的程序的用户也会如此。这是通过惩罚我们计算的分数中的间隙区域数量来实现的。一个 O( nm ) 算法来完成这个长度为n和m的字符串由 Gotoh 在 1982 年在一篇名为“一种用于匹配生物序列的改进算法”的论文中给出。不幸的是，我找不到任何指向论文免费全文的链接——但是你可以通过谷歌搜索“序列对齐”和“仿射间隙惩罚”找到许多有用的教程。

一般来说，匹配、不匹配、间隙和间隙区域权重的不同选择会给出不同的对齐方式，但是对于间隙区域的任何负分数都会更喜欢上面的底部对齐方式而不是顶部对齐方式。

这一切与你的问题有什么关系？ 如果您在具有适当间隙惩罚的单个字符上使用 Gotoh 算法（通过一些经验测试得出），您应该会发现与您给出的示例一样，看起来很糟糕的对齐数量显着减少。

效率考虑

理想情况下，您可以只对字符执行此操作而完全忽略行，因为仿射惩罚将尽可能地将更改聚集成跨越多行的块。但由于运行时间较长，可能更现实的是先通过行然后对字符重新运行算法，使用所有不相同的行作为输入。在这种方案下，任何相同行的共享块都可以通过将其压缩为具有膨胀匹配权重的单个“字符”来处理，这有助于确保不会出现“交叉”。

于 2010-02-10T10:53:46.523 回答
0

With an algo such as Levenshtein, I could find that of all right lines in the set of 3 to 5, line 5 matches left line 3 best, thus I could deduct that lines 3 and 4 on the right were added, and perform the inter-line comparison on left line 3 and right line 5.

After you have determined it, use the same algorithm to determine what lines in these two chinks match each other. But you need to make slight modificaiton. When you used the algorithm to match equal lines, the lines could either match or not match, so that added either 0 or 1 to the cell of the table you used.

When comparing strings in one chunk some of them are "more equal" than others (ack. to Orwell). So they can add a real number from 0 to 1 to the cell when considering what sequence matches best so far.

To compute this metrics (from 0 to 1), you can apply to each pair of strings you encounter... right, the same algorithm again (actually, you already did this when you were doing the first pass of Levenstein algorithm). This will compute the length of LCS, whose ratio to the average length of two strings would be the the metric value.

Or, you can borrow the algorithm from one of diff tools. For instance, vimdiff can highlight the matches you require.

于 2010-02-09T21:05:30.427 回答
0

这是其他人刚刚让我意识到的一种可能的解决方案：

我原来的做法是这样的：

  1. 将文本分成单独的行，并使用 LCS 算法来确定哪里有不匹配的行块。
  2. 使用一些智能算法（这个问题是关于）来确定这些行中的哪一个密切匹配，即告诉这些行在修订之间进行了修改。
  3. 再次使用 LCS 逐行比较那些紧密匹配的行，同时将不匹配的行标记为全新的。

虽然这可以在比较源代码修订时更好地直观显示更改，但我现在发现更简单的方法通常就足够了。它是这样工作的：

  1. 和上面一样。
  2. 获取不匹配行的右侧和左侧块，连接这些行，并将它们标记化（变成特定于语言的标记/单词，或者只是变成单个字符）
  3. 将 LCS 算法应用于两个令牌数组。

也许那些回答我最初问题的人认为我一直都知道这样做，但我非常关注每行比较，以至于我没有想到通过连接它们来将 LCS 应用于一组行，而不是逐行处理它们。

因此，虽然这种方法不会像我最初的意图那样提供详细的更改信息，但它仍然比我昨天写这个问题时开始的结果有所改善。

我将把这个问题留待一段时间——也许其他人，阅读了所有这些，仍然可以提供一个完整的答案（Pavel 和 random_hacker 提供了一些建议，但它还不是一个完整的解决方案——无论如何，谢谢你的有用评论）。

于 2010-02-10T12:23:23.687 回答