文档差异算法如何工作？

Question

我想实现word文档的不同,需要实现哪些算法？

Answer 1

嗯,一般来说,diff'通常通过最长的常见子序列问题来解决.另请参阅关于Diff的维基百科文章的" 算法"部分:

diff的操作基于解决最长的常见子序列问题.

在这个问题中,您有两个项目序列:

   a b c d f g h j q z

   a b c d e f g i j k r x y z

并且您希望以相同的顺序找到两个原始序列中存在的最长项目序列.也就是说,您希望找到一个新序列,可以通过删除某些项目从第一个序列中获取,而通过删除其他项目从第二个序列中获取.您还希望此序列尽可能长.在这种情况下它是

   a b c d f g j z

从最长的常见子序列来看,获得类似diff的输出只是一小步:

   e   h i   q   k r x y 
   +   - +   -   + + + +

也就是说,这一切都适用于基于文本的文档.由于Word文档实际上是二进制格式,并且包含大量格式化信息和数据,因此这将更加复杂.理想情况下,您可以考虑自动化Word本身,因为它具有在文档之间"区分"的能力,如下所述:

Microsoft Word提示:如何比较两个文档的差异

Answer 2

一个差异是本质上只是一个解决方案的最长公共子序列问题.

最优解决方案需要动态编程知识,因此需要解决相当复杂的问题.

但是,也可以通过构造后缀树来完成.这两种算法都在这里列出.

Answer 3

参见C#的O(ND)差分算法.

Answer 4

LCS 问题的最佳解决方案是O(ND) Myer 算法，这是我用来实现差异 Office 2007 文档的算法方法。算法论文链接