1. 首页
  2. 问答
  3. 文档差异算法如何工作？

文档差异算法如何工作？

2009-10-02 53 views

回答

3

LCS最优化的解决方案是O(ND) Myer 's algorithm，这里是一个算法的做法，我曾经实施过不同的Office 2007文档。 Link to algorithm paper

来源

2009-10-03 17:34:39 SunnyShah

+4

纸链接不起作用。 – 2013-08-05 03:53:44

+2

This正在为我工​​作：http://www.xmailserver.org/diff2.pdf – Zamicol 2017-02-21 18:01:54

15

差异基本上只是a solution到longest common sub-sequence problem。

最佳解决方案需要知识dynamic programming，所以这是一个相当复杂的问题来解决。

但是，它也可以通过构建后缀树来完成。这两种算法都被概述为here。

来源

2009-10-02 15:24:13

+1

通常当你假设你的文档是字符或字节流时。这里的问题是关于单词文件。在实现这样一个算法之前，你需要问自己一个问题是蓝色8pt Verdana中的“Hello World”，与红色10pt Arial等中的“Hello World”相同。 – quosoo 2009-10-02 15:28:36

+1

是的，很显然，基本算法需要额外的逻辑来解析差异，但算法的核心仍然是相同的。 – 2009-10-02 15:30:33

2

正如Ben S指出的那样，差分问题一般可以通过求解最长的公共子序列问题来解决。更具体地说，Hunt-McIlroy algorithm是应用于该问题的经典算法之一（例如，在Unix'diff实用程序的实现中）。

来源

2009-10-02 15:28:29

28

那么，一般来说，diff'ing通常是由Longest common subsequence problem解决。还看到Diff维基百科文章的“Algorithm"部分：

差异的操作是基于 解决最长公共子 问题

在这个问题上，你有一个项目两个 序列：

a b c d f g h j q z 

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

，你要查找的最长 序列物品存在于 机器人h原始序列以相同的 的顺序排列。也就是说，你想要找到一个新的 序列，它可以从 的第一个序列中删除一些 项目，并从第二个序列中删除其他项目的 。你也想 这个序列只要 是可能的。在这种情况下，它是

a b c d f g j z

从最长公共子 这只是一小步，得到 DIFF样输出：

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

那说，这一切都正常工作与基于文本的文档。由于Word文档实际上是一种二进制格式，并且包含大量格式化信息和数据，因此这将变得更为复杂。理想情况下，你可以看看自动运行Word本身，因为它有能力的文档之间“差异”，详见这里：

Microsoft Word Tip: How to compare two documents for differences

来源

2009-10-02 15:30:03 CraigTP

+0

实现差异算法有两个目的：只存储版本之间的差异，或显示版本之间的差异。这些是非常不同的（没有双关语意图）。 LCS通常仅用于显示差异，但为了实现最佳存储，需要更高级的算法。例如，如果您从文档的一个部分剪下大部分，并将其粘贴到另一部分中，则优秀的存储算法会检测到该部分，而不会将其存储为“嘿，这里出现了大量新数据”。 – 2009-10-02 15:32:52

+2

@Lasse - 同意。由于最初的提问者在谈论Word文档，因此我认为他们会更偏好差异化的“视觉”方面，而不是存储方面。然而，对于存储方面你是正确的，你会看到Delta Encoding/Compression（http://en.wikipedia.org/wiki/Delta_encoding）等。 – CraigTP 2009-10-02 16:37:41

相关问题

 相关问题