數倉無損壓縮算法:gzip算法

語言: CN / TW / HK
摘要:一種無損的壓縮數據格式,是一個在類Unix上的一種文件解壓縮軟件。

本文分享自華為雲社區《GaussDB(DWS) gzip算法簡介》,作者:hw0086。

【算法原理】

gzip是一種無損壓縮算法,其基礎為Deflate,Deflate是LZ77與哈弗曼編碼的一個組合體。它的基本原理是:對於要壓縮的文件,首先使用LZ77算法的一個變種進行壓縮,對得到的結果再使用哈夫曼編碼(根據情況,使用靜態哈弗曼編碼或動態哈夫曼編碼)的方法進行壓縮。Deflate最初作為LZW以及其他受專利保護的數據壓縮算法的替代版本而設計的,當時那些專利限制了compress以及其它一些流行的歸檔工具的應用。

【壓縮核心Deflate】

1.LZ77算法

LZ77的核心思路是如果一個串中有兩個重複的串中有兩個重複的串,那麼只需要知道後面的串與前面串重複的長度和後面串起始字符與前面串起始字符相對於起始位置的距離。

例如:ABCCDEFABCCDEGH 通過LZ77算法可壓縮為ABCCDEF(7,6)GH,其中7表示重複串起始字符A到前面串起始字符的距離,5表示重複部分的長度(ABCCDE)。

LZ77採用滑動窗口(sliding-window compression)來實現這個算法,掃描頭從串的頭部開始掃描,在掃描頭的前面有一個長度未N的滑動窗口。若發現掃描頭處的串和窗口裏的最長匹配串是相同的,則用(兩個串之間的距離, 串長度)來代替後一個重複的串,同時還需要添加一個表示是真實串還是替換後的串的字節在前面以方便解壓。實際過程中滑動窗口的大小固定,匹配的串也有最小長度的限制,以方便(標識+串之間距離+串長度)之和所佔用的字節是固定的。

2.哈夫曼編碼

哈夫曼編碼是數據結構課程中一種常見的算法。哈夫曼編碼使用變長編碼表對源符號進行編碼,變長編碼表通過一種評估來源符號出現概率的方法得到,出現概率較高的字母使用較短的編碼,反之出現概率低的使用較長的編碼,這樣使編碼之後的字符串的平均長度、期望值降低,從而達到無損壓縮數據的目的。通過構造Huffman Tree的方式給字符重新編碼,避免一個葉子的路徑是另一個葉子路徑的前綴,以保證出現頻率越高的字符佔用的字節越少。

例如:給英文單字“F O R G E T”進行哈弗曼編碼,將每個英文字母出現頻率由小排到大,如下圖。

每個字母與都代表一個終端節點(葉子節點),比較留個字母中每個字母出現的頻率,將最小的兩個字母相加合成一個新的節點。如下圖。組成哈弗曼樹。

將上圖給定的哈弗曼樹的所有左鏈接設為0.右鏈接設為1,從根節點到葉子節點一次記錄每個字母的編碼,所得每個字母的編碼表如下圖。

【文件格式】

  • 10字節的頭,包含幻數、版本號以及時間戳
  • 可選的擴展頭,如原文件名
  • 文件體,包括DEFLATE壓縮的數據
  • 8字節的尾註,包括CRC-32校驗和以及未壓縮的原始數據長度

通常gzip僅用來壓縮單個文件,再對多個文件的壓縮歸檔通常會將這些文件合併成一個tar文件,再使用gzip對tar文件進行壓縮,最後生成.tar.gz或者.tgz文件,即“tar壓縮包”或者“tarball”。

【應用】

  • -c,--stdout將解壓縮的內容輸出到標準輸出,原文件保持不變
  • -d,--decompress解壓縮
  • -f,--force強制覆蓋舊文件
  • -l,--list列出壓縮包內儲存的原始文件的信息(如,解壓後的名字、壓縮率等)
  • -n,--no-name壓縮時不保存原始文件的文件名和時間戳,解壓縮時不恢復原始文件的文件名和時間戳(此時,解出來的文件,其文件名為壓縮包的文件名)
  • -N,--name壓縮時保存原始文件的文件名和時間戳,解壓縮時恢復原始文件的文件名和時間戳
  • -q,--quiet抑制所有警告信息
  • -r,--recursive遞歸
  • -t,--test測試壓縮文件完整性
  • -v,--verbose宂餘模式(即顯示每一步的執行內容)
  • -1、-2、...、-9壓縮率依次增大,速度依次減慢,默認為-6

 

點擊關注,第一時間瞭解華為雲新鮮技術~