問題

有沒有人在C#中實現或知道二進位制補丁生成演算法?

基本上,比較兩個檔案(指定的舊檔案和新檔案),並生成一個補丁檔案,可用於升級舊檔案,使其與新檔案具有相同的內容。

實現必須比較快,並且使用大檔案.它應該顯示O(n)或O(logn)執行時間.

我自己的演算法往往很糟糕(快但產生大量補丁)或慢(生成小補丁但有O(n^ 2)執行時).

任何建議或實現指標都會很好.

具體來說,實現將用於為我們有一個主伺服器的各種大型資料檔案保持伺服器的同步.當主伺服器資料檔案發生變化時,我們也需要更新幾個非站點伺服器.

我製作的最天真的演算法只適用於可以儲存在記憶體中的檔案,如下所示:

  1. 從舊檔案中抓取前四個位元組,呼叫鍵
  2. 將這些位元組新增到字典中,其中鍵 – >位置,其位置是我抓住這4個位元組的位置,從0開始
  3. 跳過這四個位元組中的第一個,抓取另外4個位元組(3個重疊,1個),並以相同的方式新增到字典中
  4. 對舊檔案中的所有4位元組塊重複步驟1-3
  5. 從新檔案的開始,抓住4個位元組,並嘗試在字典中查詢它
  6. 如果找到,透過比較兩個檔案中的位元組,找到最長的匹配數
  7. 在舊檔案中編碼對該位置的引用,並跳過新檔案中匹配塊
  8. 如果沒有找到,從新檔案中編碼1位元組,並跳過它
  9. 為新檔案的其餘部分重複步驟5-8

這有點像壓縮,沒有視窗,所以它會使用很多記憶體.但是,它相當快,只要我嘗試使程式碼輸出最小,就會生成相當小的補丁.

一個更有記憶效率的演算法使用視窗,但會產生更大的補丁檔案。

上面的演算法有更多微妙之處,我在this post中跳過,但如果需要,我可以釋出更多細節.但是,我確實認為我需要一個完全不同的演算法,因此上面的演算法改進可能不足以讓我得到太多.


編輯#1:這是對上述演算法的更詳細描述.

首先,組合兩個檔案,以便有一個大檔案。記住兩個檔案之間的切點。

其次,這樣做會抓住4個位元組,並將它們的位置新增到字典步驟中的所有內容在整個檔案中。

第三,從新檔案開始的位置,執行迴圈,嘗試找到現有的4位元組組合,並找到最長的匹配.確保我們只考慮舊檔案中的位置,或者比我們目前更早的新檔案中的位置.這確保我們可以在補丁應用程式中重用舊檔案和新檔案中的材料.


編輯#2:上述演算法的原始碼

您可能會收到關於證書有一些問題的警告.我不知道如何解決這個問題,所以目前只是接受證書.

原始碼從我的其他庫中使用了很多其他型別,以便檔案不是所有需要的,但這是演算法實現.


@lomaxx,我試圖為subversion中使用的演算法找到一個很好的文件,稱為xdelta,但除非你已經知道演算法是如何工作的,我發現的文件無法告訴我我需要知道什麼.

或者也許我只是很密集...:)

我從你給出的網站上快速瞭解了演算法,不幸的是它不可用.來自二進位制diff檔案的評論說:

找到一組最優的差異需要相對於輸入大小的二次時間,因此它很快就無法使用。

我的需求不是最佳的,所以我正在尋找更實際的解決方案.

但是感謝回答,如果我需要他的實用程式,我會新增一個書籤.

編輯#1:注意,我將檢視他的程式碼,看看我是否可以找到一些想法,我稍後還會發送一封帶有問題的電子郵件,但我已經閱讀了他引用的書,雖然解決方案有助於找到最佳解決方案,但由於時間需求,它不切實際.

編輯#2:我肯定會捕獲python xdelta實現.

  最佳答案

對不起,我無法提供更多的幫助.我將確定地繼續檢視xdelta,因為我已經使用它多次在我們生成的600MB ISO檔案上生成質量衍射,用於分發我們的產品並且它執行得很好.

  相同標籤的其他問題

c#filepatch