資料壓縮/資料差異化
資料壓縮可以被視為資料差異化的一個特例。[1] 就像資料壓縮涉及通常在兩臺不同機器上執行的兩個過程——“資料壓縮器”和“資料擴充套件器”——資料差異化涉及通常在兩臺不同機器上執行的兩個過程——分別為“差異化程式”和“補丁程式”。
一些用於資料差異化的演算法和程式與“小視窗壓縮”（又稱傳統資料壓縮）中使用的演算法非常相似——例如“大視窗壓縮”（又稱“資料摺疊”[2]）——而另一些則非常不同——例如“資料重複資料刪除”[3][4]和rsync演算法。
一些用於大型檔案傳統資料壓縮的演算法類似於資料差異化演算法——例如在霍夫曼：儲存頻率表中描述的儲存許多霍夫曼頻率表的某些技術。
為資料差異化開發的一些演算法和程式包括
- diff（“w:增量壓縮”）
- rsync
- rdiff
- lzip
- rzip
- IZO（資訊壓縮最佳化器）[2]
- xdelta[5]
- bsdiff 4和bspatch[6]
- bsdiff 6和Percival的通用增量壓縮器[6][7]
對於其他形式的壓縮，更多資訊通常會帶來更好的壓縮效果。但是，Factor、Sheinwald和Yassour在2001年的實驗似乎表明，當使用類似LZ77的壓縮排行資料差異化時，嘗試使用大量類似於目標檔案的共享檔案通常會比使用該集合中的單個參考檔案產生更差的壓縮效果。[8]
在壓縮非常大的檔案時，字典的預載入內容通常不會有太大區別，因此許多系統從空字典開始。
但是，在兩種情況下，預載入字典可以生成明顯更小的檔案
- 壓縮大量短字串時，或
- 進行資料差異化時——壓縮某個與接收方已有的某個檔案幾乎相同的大檔案。
一些資料壓縮演算法的實現已經支援預載入字典。
- 流行的zlib壓縮庫支援deflateSetDictionary()和inflateSetDictionary()函式來預載入字典。[9]
一種可能的資料差異化方法涉及調整某些壓縮演算法以“預載入”其內部資料結構（其“視窗”或“字典”）來自我們已經擁有的檔案的資料，以允許壓縮演算法使用這些資料來（希望）在下一個檔案上獲得更好的壓縮效果。[10][11]
例如，IPSW演算法（Shapira和Storer的原地滑動視窗）將類似LZ77的解壓縮器的源滑動視窗初始化為某個共享檔案S，[8]允許目標檔案T的公共子字串從S中複製出來，以及（像其他類似LZ77的壓縮器一樣）允許重複的子字串從目標檔案T先前解壓縮的部分複製，或者如果所有其他方法都失敗，則從壓縮檔案中的文字值複製。
有時，此類“預載入”實現使用未修改的“小視窗壓縮”演算法，如美國專利RE41152 2010中所述。許多早期的壓縮演算法使用“靜態字典”（Huffword、PalmDoc等）預載入字典。LZW演算法比非常類似的LZ78演算法提供更好的壓縮效果。關於LZW的一種思考方式是，想象一下256個文字位元組值不是一個單獨的“特殊情況”，而是實際上預載入到字典中；而LZ78演算法實際上是從空字典開始，因此壓縮效果較差。
對於許多壓縮演算法，此類預載入受“視窗”或“歷史限制”的限制——當視窗或限制為，例如，32 kByte時，無論嘗試預載入什麼或多少資料，只有最後32 kByte才會產生任何影響。
這導致一些從事資料差異化工作的人使用比其他壓縮研究人員大得多的視窗或歷史限制。
LZ77風格的解壓縮器有一個固定大小的“視窗”，用於儲存最近解壓縮的文字，“複製引用”只能引用該視窗內的文字。
從理論上講，許多壓縮演算法沒有固有的“歷史限制”——例如LZ78風格的演算法和自適應霍夫曼演算法。但是，在實踐中，大多數壓縮演算法的實現都會定期重置其字典並從頭開始。因此，它們具有字典重置之間最大文字長度的塊大小。
對於許多早期的壓縮演算法，提高效能的一種簡單方法是增加視窗大小。（即，對於LZ77演算法，從字面上增加“視窗”緩衝區，或者對於LZ78風格的演算法，簡單地減少字典重置頻率）。這些早期的壓縮演算法通常是在記憶體遠小於現代機器的機器上開發的，因此“視窗大小”、“重置頻率”和“內部字典大小”都受到此限制。（這些早期機器的執行速度也遠低於現代機器，並且許多演算法——例如LZRW系列演算法——受到這些速度限制的嚴重約束；目前尚不清楚這對字典大小有何影響）。
為簡單起見，我們將考慮將視窗大小加倍對各種演算法的影響。原始的“小視窗”演算法具有一定的固定視窗大小W，而加寬的“大視窗”演算法具有一定的固定視窗大小2*W，可以將其視為“近視窗”，其中包含與小視窗演算法相同的所有內容，以及“遠視窗”，其中包含小視窗演算法無法訪問的內容，但也許大視窗演算法可以利用這些內容來獲得更好的壓縮效果。
唉，增加視窗大小會帶來收益遞減。實際上，幾乎總存在某種資料相關的“最佳”視窗大小。將視窗大小增加到最佳值以上會導致更差的壓縮效果（壓縮檔案更大）。
視窗大小大於最佳大小會產生負面影響的原因有4個
1. 一些LZ77風格的演算法使用固定長度的線性偏移。將視窗大小加倍必然會使每個複製項的長度增加1位。對於典型的16位複製項，除非壓縮器可以在遠視窗中找到比近視窗中任何字串都長的匹配字串，否則這會使壓縮檔案長度增加17/16倍（壓縮效果更差）。
2. 其他LZ77風格的演算法使用可變長度的偏移。通常，更遠的偏移量更長。將視窗大小加倍通常會使“極其接近”的複製項的長度保持不變，將近視窗外邊界附近的一些複製項的大小增加1位，並需要更大的複製項才能引用遠視窗中的內容。因此，與類別（1）相比，增加視窗大小對類別（2）幾乎沒有懲罰。但是，收益並不那麼好。在許多情況下，即使遠視窗中存在一個非常好的長匹配，其長度超過近視窗中的任何匹配，它也不會使壓縮檔案變小——引用該遠處匹配字串所需的較長複製項可能與可以從近視窗中的兩個位置重新組合相同字串的兩個較短複製項的長度相同甚至更長。
3. 正如Jeff J. Kato等人所指出的那樣，[12] 當嘗試壓縮具有略微不同特徵的資料，或嘗試壓縮特徵從一部分到另一部分發生變化（“發展”）的檔案時，視窗/字典中存在一種檔案的資料甚至可能適得其反。通常最好重置字典並從頭開始。
但是，有時這些“大視窗”壓縮器具有很大的優勢——特別是當我們目前嘗試壓縮的檔案不僅僅是相同型別的檔案，而是與某個早期檔案完全相同。當檔案*大部分*相同並且只有少量編輯時，一些大視窗技術也能很好地工作。
一些壓縮軟體的預設視窗大小或塊大小為
- gzip：32 kByte滑動視窗
- bzip2：900 kB的塊
- DEFLATE（如用於“.zip”、“.jar”、“.png”等）：32 kByte 滑動視窗
- GIF 標準提到了兩種 LZW 編碼器
- 一些 GIF 編碼器實現會在字典每次填滿時重置字典——
即，壓縮器在每 (最大字典大小 - 硬編碼條目數) = 2048 - (256 + 2) 個壓縮符號後傳送“清除程式碼”來重置字典。
）。GIF LZW 編碼器在字典填滿後變得不適應，同時它正在“等待”下一個清除程式碼。
- lzip
- lrzip 和 SuperREP 具有“無限”視窗（不受可用 RAM 的限制）
- rzip 具有 900 MB 的視窗（比 bzip2 大 1000 倍） http://en.wikipedia.org/wiki/Rzip
- 資訊壓縮最佳化器 (IZO) 也具有不受可用 RAM 限制的視窗 https://www.usenix.org/conference/lisa-08/izo-applications-large-window-compression-virtual-machine-management
- xdelta
http://en.wikipedia.org/wiki/xdelta
- ↑ w:資料差異化
- ↑ a b http://static.usenix.org/event/lisa08/tech/full_papers/smith/smith_html/
- ↑ Dutch T. Meyer 和 William J. Bolosky。 "實用重複資料刪除研究"。
- ↑ 維基百科：重複資料刪除
- ↑ http://code.google.com/p/xdelta/
- ↑ a b “透過使用字尾排序（特別是 Larsson 和 Sadakane 的 qsufsort）並利用可執行檔案如何更改，bsdiff 通常生成的二進位制補丁比 Xdelta 生成的補丁小 50-80%，比 .RTPatch 生成的補丁小 15%……一個更復雜的演算法，通常提供大約 20% 更小的補丁，在我的博士論文中進行了描述。”——Colin Percival。 "二進位制差異/補丁實用程式"
- ↑ Colin Percival。 "匹配與不匹配及相關應用"。論文。2006 年。
- ↑ a b Dana Shapira 和 James A. Storer。 "就地差分檔案壓縮"。2005 年。
- ↑ http://www.gzip.org/zlib/manual.html#deflateSetDictionary http://www.gzip.org/zlib/manual.html#inflateSetDictionary
- ↑ "壓縮演算法能否在檔案集上“學習”並更好地壓縮它們？"
- ↑ comp.compression：“在解壓縮時保證可用的一組資料檔案”
- ↑ Jeff J. Kato、David W. Ruska、David J. Van Maren。美國專利 4847619 "基於效能的資料壓縮字典重置"。1987 年。
- ↑ Attila Tarpai。 "GIF 中的延遲清除程式碼"。2010 年。
- ↑ "GIF89a 規範封面：LZW 壓縮中的延遲清除程式碼"
- ↑ GIF 檔案格式：可移植性警告 2：延遲清除程式碼問題
