1. 首頁
  2. 問答
  3. 文檔差異算法如何工作？

文檔差異算法如何工作？

2009-10-02 55 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

相關問題

 相關問題