2

我有一个基于最长递增子序列的算法，当每个集合中的对象都是唯一的时，它可以很好地解决相关的业务问题，但是当两个集合中存在许多非唯一对象时往往会给出奇怪的结果。

当存在非唯一对象时，使用 Patience Diff 算法（也基于最长递增子序列）的方法似乎可以提供我想要的结果。但是，在我弄清楚 Patience Diff 是否合适之前，如果合适的话，为了将其应用于我的问题，我需要更好地理解算法。

我了解步骤 1 到 3 中会发生什么，但我不清楚步骤 4 中会发生什么。在 1 到 3 之后，现在仍然存在无法匹配的唯一行块和非唯一行。那么接下来会发生什么——假设与文档剩余的第一行/最后一行不匹配，肯定它还没有终止（因为没有更多的唯一行）？或者它是否将一个文档中的每个非唯一块与另一个文档中的每个非唯一块进行比较，并以某种方式选择最佳匹配？

http://bramcohen.livejournal.com/73318.html

  1. 如果它们相同，则匹配两者的第一行，然后匹配第二、第三等，直到一对不匹配。
  2. 如果它们相同，则匹配两者的最后一行，然后匹配倒数第二行，倒数第二行等，直到一对不匹配。
  3. 找到两边恰好出现一次的所有行，然后在这些行上做最长的公共子序列，将它们匹配起来。
  4. 在匹配行之间的每个部分执行步骤 1-2
4

1 回答 1

2

一旦你用完了独特的线条，你需要回退到不同的对齐算法。Git 在那时使用标准的 diff 算法（Eugene Myers 的 O(ND) 算法）。

例如，如果这两个文件是：

a 12121 e 1212 b ee c x d
a 21212 e 2121 b ye c d

首先，耐心算法对齐两个文件中唯一且存在的任何行：

a b c d
a b c d

然后递归地对齐这些行之间的每个子范围，首先再次执行耐心算法，然后如果耐心算法不匹配任何内容，则执行 LCS 算法。

1212 e 121    |  ee  |    x
2121 e 2      |  ye  |

在第一个子范围中，e现在两者都是唯一的，因此第二个耐心差异传递将对齐它，将其分成两个新的子范围。新的第一个子范围（12121 与 21212）没有任何唯一行，因此它将与 LCS 算法对齐。第二个新子范围（1212 与 2121）是通过 LCS 算法的第二次通过完成的。

上面的第二组（ee vs ye）没有任何独特的线条，因此它们也将使用 LCS 算法对齐。

最后的分组（x vs nothing）只是输出 x 作为删除，而不做耐心或 LCS 算法。

于 2012-04-19T15:50:05.610 回答