潮湧浪平

數據壓縮是指在不丟失有用信息的前提下，縮減數據量以減少存儲空間，提高其傳輸、存儲和處理效率，或按照一定的算法對數據進行重新組織，減少數據的冗餘和存儲的空間的一種技術方法。

數據壓縮包括有損壓縮和無損壓縮。

在說壓縮機制前，先了解一下保存在文件中的字節形式。文件大小之所以用KB、MB表示，就是因為文件以字節為單位保存。

舉個例子，一個文件內，有100個A，4個E，這時要壓縮的話，把A賦予較小的摩爾斯編碼，如1，而E可以給較長的編碼以便較短的編碼分配給其餘較多的字符，如E對應110101101一共9位，這樣，加上字符間隔，一共是1×100＋9×4＋2×104=344位，344位（如果不夠8的整數倍，加上結束符然後補足8的倍數即可）。

原文件是8×104=832位，344÷832≈41%，顯然達到了很好的壓縮效率。

莫非8125

數據壓縮概念

數據壓縮是指在不丟失信息的前提下，縮減數據量以減少存儲空間，提高其傳輸、存儲和處理效率的一種技術，或者指按照一定的算法對數據進行重新組織，減少數據的冗餘和存儲的空間。

數據壓縮包括有損壓縮和無損壓縮。

首先介紹數據壓縮的基本原理以及傳統的壓縮算法，然後實際應用中的壓縮技術，包括Oracle壓縮技術、Google壓縮技術以及Hadoop壓縮技術。

主要內容

• 數據壓縮原理
• 傳統壓縮算法（包括LZ77算法和霍夫曼算法）
• Oracle壓縮技術
• Google壓縮技術
• Hadoop壓縮技術

1 數據壓縮原理

隨著科技的發展，人類社會也在發生著翻天覆地的變化，尤其是計算機的出現，更是將人類帶入了前所未有的信息時代。從電報電話，到廣播電視，再到手機和各種移動終端，人們的生活越來越方便，但同時也帶來了一個不容忽視的問題——信息爆炸！如何管理這些海量數據，如何從中找到有用的信息，這些問題都是人類從未遇到過的。其中最基本的一個問題是：如何把這些信息存儲起來？如果這個問題解決不了，其他的問題更是無從入手了。數據壓縮的理論基礎是信息論和率失真理論，克勞德•香農在20世紀40年代末期及50年代早期發表了這方面的基礎性論文。密碼學與編碼理論也是與數據壓縮密切相關的學科，數據壓縮的思想與統計推斷也有很深的淵源。以此為基礎，人們對於數據壓縮技術的研究已經有很長時間。圖7-1給出了一個例子。

圖7-1中上部的文本如果交給人來看，得出的結論恐怕只能是有很多A。但如果交給計算機來處理就可以得到更多的信息，也就是能準確地求出A的個數。更重要的是，圖7-1中下面的內容表達的含義和上面的一樣，但是卻用了更少的存儲空間。

1.1 數據壓縮的定義

數據壓縮是指在不丟失信息的前提下，縮減數據量以減少存儲空間，提高其傳輸、存儲和處理效率的一種技術，或者指按照一定的算法對數據進行重新組織，減少數據的冗餘和存儲的空間。

數據壓縮其實就是一個數據編碼的過程，可以理解為用不同的語言表達同樣的含義，只不過有些語言很簡練，而有些卻很繁瑣。我們的目的就是通過數據編碼用最簡潔的方式表達數據包含的信息，更確切地說是用最少的空間存儲最多的信息。

數據編碼是一個從源文件到編碼文件的映射過程。源文件的內容有多種形式（文本、圖像、聲音），但它們在計算機中都是以二進制的形式存儲的，只不過具體的二進制表示方法不同。瞭解這一點才能更好地學習數據壓縮原理，如表7-1所示的例子。表7-1 信息的二進制表示

從字面上看，ab和12的長度一樣，但正因為它們的數據類型不同，在計算機中存儲佔用的空間也不同。從計算機的角度考慮問題，能更好地理解壓縮的原理和巧妙之處。

1.2 數據為什麼可以壓縮

數據可以被壓縮，是因為數據中往往存在著大量的冗餘信息。如英語中就有26個字母，由此構成單詞、短語等語義單位，然後再加上一些標點符號構成文章。一篇英語文章中會有大量重複的字母、單詞或短語，如果能找到一種壓縮算法將一篇英語文章壓縮成26個字母和一些位置信息的組合，那麼應該就能達到最大程度的壓縮。我們姑且不談是否存在這樣的算法，只要理解減少信息冗餘是壓縮的本質。

在實際應用中，多媒體信息的壓縮是最常見的。事實上，多媒體信息存在許多數據冗餘。例如，一幅圖像中的建築背景、藍天和綠地，其中許多像素是相同的，如果逐點存儲，就會浪費許多空間，稱為空間冗餘。又如，在電視和動畫裡相鄰的運動圖像序列中，只有運動物體有少許變化，僅存儲差異部分即可，稱為時間冗餘。此外還有結構冗餘、視覺冗餘等，這就為數據壓縮提供了條件。

1.3 數據壓縮分類

數據壓縮的方式有很多，一般來說可以分為無損壓縮和有損壓縮。

無損壓縮是指使用壓縮後的數據進行解壓縮，得到的數據與原來的數據完全相同；無損壓縮用於要求重構的信號與原始信號完全一致的場合。一個很常見的例子是磁盤文件的壓縮。根據目前的技術水平，無損壓縮算法一般可以把普通文件的數據壓縮到原來的1/2～1/4。一些常用的無損壓縮算法有霍夫曼（Huffman）算法和LZW（Lenpel-Ziv & Welch）壓縮算法。

有損壓縮是指使用壓縮後的數據進行解壓縮，得到的數據與原來的數據有所不同，但不影響人對原始資料表達的信息的理解。有損壓縮適用於重構信號不一定非要和原始信號完全相同的場合。例如，圖像和聲音的壓縮就可以採用有損壓縮，因為其中包含的一些數據往往超過我們的視覺系統和聽覺系統所能接收的範圍，丟掉一些也不至於使人對聲音或者圖像所表達的意思產生誤解，但可大大提高壓縮比。

2 傳統壓縮技術

常見的無損壓縮算法有行程長度（run-length）編碼、字典編碼（LZ系列編碼）、霍夫曼編碼、算術編碼等；常見的有損壓縮算法有離散餘弦變換、分形壓縮、小波壓縮、線性預測編碼等。在這裡我們僅介紹無損壓縮中的兩種經典算法：霍夫曼編碼和LZ77編碼。

2.1 霍夫曼編碼

根據ASCII碼的規定，我們用8比特代表一個字符，但是如果提前知道了文件中各個字符出現的頻率，就可以對這些字符重新編碼。對於出現頻率高的字符用較少的比特表示；對於頻率較低的字符用較多的比特表示。由於使用頻率高的字符為字符集的子集，從總體上來說，還是減少了總共需要的比特數，達到了壓縮的目的，這正是霍夫曼編碼的思想。

使用霍夫曼編碼進行壓縮，首先要掃描整個文件，統計每個字符的頻率，然後根據頻率建立霍夫曼樹，由霍夫曼樹得到每個字符的編碼。由於頻率高的字符在霍夫曼樹中離根更近，它們的霍夫曼編碼長度更短；相反，頻率低的字符的編碼更長。最後，用霍夫曼編碼替換原文件中的字符。

建立霍夫曼樹的步驟如下。

（1）將所有的字符看成僅有一個節點的樹，節點的值是字符出現的頻率。

（2）從所有樹中找出值最小的兩棵樹，併為它們建立一個父節點，從而構成一棵新的樹，父節點的值為兩棵子樹的根節點值的和。

（3）重複步驟（2），直到得到最後一棵樹，這就是我們需要的霍夫曼樹。

有了霍夫曼樹就該考慮如何得到霍夫曼編碼。霍夫曼樹是一顆二叉樹，所有的葉子節點就是需要編碼的字符。我們在霍夫曼樹中所有父節點到左子樹的路徑上標0，到右子樹的路徑上標1。對於每個葉子節點，從根節點到它的路徑就是一個0和1構成的序列，這就是葉子節點字符的霍夫曼編碼。

顯然，對於出現次數多的字符，得到的霍夫曼編碼較短，出現次數少的字符，編碼較長，因此霍夫曼編碼是一種變長編碼。對於變長編碼，在解碼的時候會遇到如下問題：比如a的編碼是000，b的編碼是0001，c的編碼是1，那麼當遇到0001時，無法區分是ac還是b。出現這個問題的原因在於a的編碼是b的編碼的前綴。但霍夫曼編碼不會存在這個問題，因為霍夫曼樹中從根節點到一個葉子節點的路徑不可能是到另一個葉子節點路徑的前綴，所以一個霍夫曼編碼不可能是另一個霍夫曼編碼的前綴。我們稱霍夫曼編碼是一種前綴編碼。

2.2 LZ77算法

LZ77算法是一種詞典編碼，它用的詞典就是前面經過編碼的信息序列。編碼器利用一個滑動窗口查詢輸入的文本信息，如圖7-2所示。

圖7-2 滑動窗口

滑動窗口包括兩部分：查詢緩衝區和預見緩衝區。查詢緩衝區包含了最近剛經過編碼的序列，預見緩衝區包含接下來需要編碼的序列。在圖7-2中的查詢緩衝區包含了8個字符，預見緩衝區包含了7個字符。實際應用時，緩衝區的大小要比這個大得多，在這裡只是為了方便說明而設置小一點。

為了對預見緩衝區中的序列進行編碼，編碼器在查詢緩衝區中從後往前移動一個匹配指針，直到這個指針指向與預見緩衝區中第一個字符匹配的字符為止。從預見緩衝區到匹配指針之間的距離稱為偏移量，記作offset。接下來，編碼器會繼續檢查匹配指針後面的連續字符是否與預見緩衝區中的連續字符相匹配。查詢緩衝區和預見緩衝區中最長的匹配字符串長度稱作匹配長度，記作length。編碼器要查找最長的匹配字符串，當編碼器找到這個最長匹配串時，會用一個三元組對它進行編碼。三元組中的o代表offset，l代表length，c代表預見緩衝區中最長匹配串後的第一個不匹配字符。例如，在圖7-2中查詢指針指向了最長匹配串的開頭，offset等於7，匹配長度為4，預見緩衝區中的第一個不匹配字符為r。設置第三個元素c的原因是為了便於處理查詢緩衝區和預見緩衝區中沒有匹配字符串的情形。這種情況下，三元組中的offset和length都被設置為0，c被設置為不匹配字符本身。

如果設查詢緩衝區的大小為S，窗口（包括查詢緩衝區和預見緩衝區）的大小為W，源文件中的字符集大小為A，那麼用定長的三元組進行編碼需要的比特數是[log2S]+[log2W]+[log2A]，其中[]表示上取整。注意，第二項是[log2W]而不是[log2S]，因為匹配長度可能會超出查詢緩衝區，這種情況將在下面例子中說明。在下面的例子中，我們將會考慮如下編碼中可能遇到的三種情形。

（1）沒有匹配字符。

（2）有一個匹配字符。

（3）匹配字符串超出了查詢緩衝區的範圍。

例如編碼序列如下：... cabracadabrarrarrad ...假設窗口的大小為13，那麼預見緩衝區的大小為6，當前狀態如圖7-3所示。

圖7-3 窗口緩衝區的內容

預見緩衝區中包含了dabrar。我們在查詢緩衝區中查找d的匹配字符，但是沒有找到，所以輸出<0, 0, C(d)>。前兩個元素表示沒有匹配字符，第三個元素C(d)代表第一個d的編碼。

下面，我們繼續編碼的過程。因為前面對一個字符d進行了編碼，所以把窗口向後移動一個字符。現在緩衝區中的情況如圖7-4所示。

圖7-4 窗口向後移動一個字符

預見緩衝區中包含字符串abrarr。從當前位置往前在查找緩衝區中查找匹配字符，在偏移位置為2的地方找到了一個匹配的a。這個匹配字符串的長度為1。再往前查找，我們又在偏移位置為4的地方找到另一個匹配的a，這個匹配字符串的長度仍然是1。繼續向前查找，我們在偏移位置為7的地方找到了第三個匹配的a，但這次匹配字符串的長度為4（見圖7-5），我們找到了匹配最長的字符串。於是，我們用三元組<7, 4, C(r)>代替字符串abra，並且將窗口向後移動5個字符。

圖7-5 尋找最長匹配字符串

現在的窗口中包含如圖7-6所示的內容。

圖7-6 匹配字符可以跨過查找緩衝區

預見緩衝區中包含字符串rarrad，向前尋找匹配字符串。第一個匹配字符串的偏移位置是1，長度為1；第二個匹配字符串偏移位置是3，它的長度貌似是3，但實際上我們可以越過查找緩衝區，將重複字符串擴展到預見緩衝區，這一點前面已經提到了。所以這裡重複字符串的長度為5，而不是3。

這麼做是可行的，通過下面解碼的過程可以得到證實。假設已經解壓完成的字符串為cabraca，並且我們掃描到了三元組<0, 0, C(d)>，<7, 4, C(r)>，<3, 5, C(d)>。第一個三元組很好解碼，它沒有和已經解壓的字符串重複的字符串，並且下一個字符為d。現在得到的字符串為cabracad。第二個三元組的第一個元素說明了重複字符串的偏移位置為7，於是把指針向前移動7個字符，第二個元素說明重複長度為4。於是連續輸出後面的4個字符。具體解碼過程如圖7-7所示。

圖7-7 LZ77解碼過程

最後，讓我們看看第三個三元組<3, 5, C(d)>是怎樣解碼的。根據第一個元素我們把指針向前移動3個字符，然後開始重複輸出。前三個重複的字符是rar，複製指針繼續向後移動，如圖7-8所示，輸出剛複製過的第一個字符r，同樣再輸出第一個複製過的字符a。這樣一來，雖然在開始時只是複製了3個字符，但是最終我們解碼出了5個字符。注意，匹配字符串必須起始於查找緩衝區，但是可以延伸到預見緩衝區。事實上，如果預見緩衝區中的最後一個字符是r而不是d，即後面跟著一連串重複的rar，那麼整個rar重複序列可以用一個三元組進行編碼壓縮。

圖7-8 LZ77解碼過程

正如我們看到的，LZ77模式是一個非常簡單的自適應模式，它不要求知道源文件的任何信息，並且幾乎也不需要基於源文件的字符集。

3 Oracle混合列壓縮

數據存儲在傳統技術中往往是以“行”的形式，即同一行中的各列數據都是順序地存放在單個的數據塊中。由於不同列數據的類型可能不同，這些不同類型的數據存儲在一起，就使得壓縮後節省的空間並不是很大。為了獲得更高的壓縮率，Oracle採用列存儲的形式來存儲數據，並且採用了混合列壓縮（HCC，Hybrid Columnar Compression）技術。

HCC以塊（block）的形式來組織數據，它實際上同時利用了行存儲和列存儲的方法來存儲數據。這種混合策略不但達到了很好的列壓縮效果，而且還避免了單純列存儲時性能不足的缺點。一個稱作壓縮單元（compression unit）的邏輯結構被用來存儲列壓縮後的行數據。數據一旦被定位，一個行集合中的列值會被分組到一起，然後將其進行壓縮。當完成這樣的壓縮後，數據會被存儲到壓縮單元中。圖7-9是對壓縮單元概念的說明。

圖7-9 壓縮單元結構

列壓縮之所以能夠取得很高的壓縮率，是因為同一列的數據類型和值往往都很接近，重複的內容也就較多，為壓縮提供了更大的空間。Oracle在實際應用中採用了bzip2壓縮方法，bzip2本身是對Burrows–Wheeler算法的實現，這裡不做過多介紹，有興趣讀者可以查看相應資料。

HCC對於倉庫壓縮和存檔壓縮都是有效的技術，下面來看看它們是如何應用的。

3.1 倉庫壓縮

倉庫壓縮在典型情況下可以提供10∶1（10x）的壓縮率，節省的存儲空間大約是行業平均水平的5倍。

倉庫壓縮提供兩個層次的壓縮：低級（LOW）和高級（HIGH）。高級倉庫壓縮通常提供10x的壓縮比，而低級倉庫壓縮提供6x的壓縮比。這兩種壓縮技術都在實際應用中進行了優化，通過減少硬盤存儲塊來提高檢索查詢性能。為了最大程度節省存儲空間和提高查詢效率，默認情況下是進行高級壓縮。節省的存儲空間多了，但是數據加載的次數卻會略微增加。因此，對於那些對數據加載次數有限制的查詢來說，低級壓縮是更好的選擇。

3.2 存檔壓縮

所謂存檔數據，就是一些歷史數據。由於數據量不斷增加，很多IT管理人員都需要花費很多的精力和財力來管理存檔數據。一些機構開發出一種信息生命週期管理（ILM，Information Lifecycle Management）的策略來幫助他們存儲數據。典型的ILM策略包括將數據移動到更為廉價的存儲設備上，比如便宜的硬盤，但更常用的是磁帶。HCC的存檔壓縮技術可以減少存儲開銷，用更少的磁帶來存儲這些歷史數據。

存檔壓縮通過一系列優化，壓縮比可以到達15∶1（15x）。跟倉庫壓縮不同的是，存檔壓縮單純是為了節省存儲空間。運用了存檔壓縮後，通常都會降低系統的系能，這是採用達到最大壓縮比的算法的結果。因此這種壓縮方法一般用於那些不常用的歷史數據。Oracle在切分和二次切分中支持各種類型的表壓縮。因此，一種OLTP應用程序可以在一個分區中採用存檔壓縮來存儲歷史數據，而那些還在使用的數據可以位於使用Oracle OLTP表壓縮技術（Table Compression）的分區中。OLTP表壓縮技術是一種高級壓縮方法，用來壓縮那些操作頻繁的數據庫。OLTP表壓縮技術通常能達到2x到4x的壓縮比，為OLTP數據庫大大節省了存儲空間。

4 Google數據壓縮技術

作為Google三大技術之一的Bigtable，是Google內部開發的一個用來處理大數據量的系統。Bigtable內部存儲數據的文件是Google SSTable格式的。SSTable是一個持久化的、排序的、不可更改的Map結構，而Map是一個key-value映射的數據結構，key和value的值都是任意的Byte串。從內部看，SSTable是一系列的數據塊（通常每個塊的大小是64 KB，這個大小是可以配置的）。客戶程序可以控制一個局部性群組的SSTable是否需要壓縮，以什麼格式來壓縮。很多客戶程序使用了“兩遍”的、可定製的壓縮方式。

第一遍採用Bentley-McIlroy方式，這種方式在一個很大的掃描窗口裡對常見的長字符串進行壓縮；第二遍是採用快速壓縮算法，即在一個16 KB的小掃描窗口中尋找重複數據。兩個壓縮的算法都很快，在現在的機器上，壓縮的速率達到100～200 MB/s，解壓的速率達到400～1000 MB/s。

在這裡我們重點介紹第一遍壓縮中的Bentley-McIlroy算法。

4.1 尋找長的重複串

數據壓縮技術通常都會應用滑動窗口機制，窗口的典型長度是幾 KB。但滑動窗口機制存在一個致命的缺點，那就是它不能壓縮相距較遠的重複字符串。有很多算法可以用來尋找文本文件中的長重複串。其中包括McCreight的後綴樹、Manber和Myers的後綴數組。Bentley和McIlroy應用Karp和Rabin的指紋方法。

Karp和Rabin最初是在輔助字符串查找中提出的指紋方法：一個長為n的字符串是否包含一個長為m的查詢模式？Karp和Rabin將m個字符的模式定義為以一個大素數為模的多項式，產生的指紋結果可以作為32比特的字來存儲。他們的算法順次掃描輸入的字符串，並且針對n-m+1個長度為m的子串與同一個指紋進行比對。如果指紋沒有匹配成功，那麼我們確定輸入的字符串中不包含匹配的模式；如果指紋比對成功，那就要進一步確定子串是否真的包含匹配的模式。

Karp和Rabin證明了指紋算法幾點有用的性質。首先，指紋可以被很快地求出來：一個指紋可以在O(m)的時間內初始化，並且通過O(1)的時間滑動一個位置來更新指紋。其次，指紋幾乎不會產生錯誤的匹配：不相等的字符串幾乎不可能含有同樣的指紋。兩個不相等的字符串含有同樣32比特指紋的概率大約是2-32。另外，可以通過隨機地選擇大素數來產生隨機算法搜索文本。

Bentley-McIlroy壓縮算法利用了上面提出的塊大小參數b。b的典型大小介於20到1000之間。理想情況下，我們希望忽略那些長度小於b的重複串，而壓縮那些長度大於b的長重複串。Bentley-McIlroy算法要求長度至少為2b-1的字符串才會被壓縮，介於b到2b-1之間的字符串有可能被壓縮，小於b的字符串肯定不會被壓縮。

Bentley和McIlroy提出的基本數據結構存儲了每個大小為b字節的不重疊塊的指紋。也就是說，依次存儲了字節1到b，字節b+1到2b，……的指紋。在一個長度為n的文件中，大約會存儲n/b個指紋。Bentley和McIlroy將它們存儲在一個哈希表中，同時存儲了代表指紋在原文件中位置的整數。當掃描輸入文件時，算法會利用哈希表查找指紋並且確定重複串的位置。

4.2 壓縮算法

因為Bentley-McIlroy算法僅僅表示長重複串，所以不必使用無效的表示。用序列“”來表示重複串，其中“開始位置”代表初始的位置，“長度”代表重複串的長度。比如，美國憲法的開頭如下：

The Constitution of the United States PREAMBLE We, the peopleof the United States, in order to form a more perfect Union, ...

壓縮後的形式如下：

The Constitution of the United States PREAMBLE We, the people<16,21>, in order to form a more perfect Union, ...

對於字符“

算法中的checkformatch函數在哈希表中尋找fp，當找到的時候對其進行編碼。

當匹配成功的時候該怎樣處理呢？假設b=100，並且當前長度為b的塊和第56個塊（也就是第5600個字節到第5699個字節）匹配成功。我們可以用序列<5600, 100>來表示當前塊。這種算法不會處理長度小於b的字符串。如果一個塊的大小至少是2b-1，那麼至少存在一個長度為b的子串能夠落在一個塊內並且被查找出來。

事實上，Bentley-McIlroy採用了一個稍微聰明點的辦法。在查找到一個塊與一個指紋匹配成功以後，可以確保它不會是一個錯誤的匹配（這是指紋的性質之一）。然後Bentley-McIlroy會用貪婪算法儘量向前地查找匹配（但是不能超過b-1的長度，否則會找到前一個長度為b的塊），緊接著再儘可能向後查找匹配。如果有若干個塊和當前的指紋匹配，算法就選擇對其中最長的串進行編碼。表7-2所示的這些例子說明了b=1時算法的執行情況。

表7-2 b=1時的Bentley-McIlroy壓縮算法

從上面的實驗結果的最後一行可以看到，算法可以針對a不斷進行重複匹配，實現對最長匹配字符串的壓縮。

5 Hadoop壓縮技術

Hadoop中的存儲文件（HFile）在被寫入（刷新過程或者緊縮過程）時會以塊（block）為單位進行壓縮，在它們被讀取時需要進行解壓縮，也就需要花費一定的時間。既然這個過程增加了程序運行的時間，那為什麼還要進行壓縮呢？有下面幾個原因。

• 壓縮能夠減少從HDFS中讀出和寫入的字節數。
• 壓縮能有效地提高網絡帶寬和磁盤空間的利用率。
• 壓縮能減少讀操作時所需的數據量。

為了減少壓縮時間，需要選擇一種實時壓縮方法。Hadoop只裝載了Gzip壓縮技術，它是比較慢的。為了使效率和優勢最大化，必須允許LZO運行在Hadoop上。

5.1 LZO簡介

LZO是一個數據壓縮庫，適用於對數據進行實時的壓縮和解壓縮。根據用戶不同的參數設置，LZO可以實現快速壓縮，或者實現高比例壓縮。但無論採用哪種壓縮形式，在解壓時速度都是非常快的，這也正是LZO的優勢所在。LZO開始是用ANSI C編寫的，源代碼和壓縮數據的格式都可輕易跨平臺。LZO應用一系列算法，這些算法具有以下特點。

• 解壓縮很簡單而且相當快。
• 解壓不需要額外的內存空間。
• 壓縮速度很快。
• 壓縮時僅需要64 KB的內存空間。
• 允許在壓縮部分以損失壓縮速度為代價提高壓縮率，解壓速度不會降低。
• 包括生成預先壓縮數據的壓縮級別，這樣可以得到相當有競爭力的壓縮比。
• 另外還有一個只需要8 KB內存的壓縮級別。
• 算法是線程安全的。
• 算法是無損的。

LZO是一種塊壓縮算法，塊大小在壓縮和解壓縮時必須是一樣的。LZO將一塊數據壓縮成與滑動字典匹配的部分以及沒有匹配的部分。LZO很注重長的匹配字符串，因為可以在處理高冗餘數據以及無法壓縮的數據時獲得更好的效果。在處理不能壓縮的數據時，LZO最多隻會讓每1024字節數據增加64字節的內容（壓縮後會多一些壓縮數據，如滑動字典信息等）。

LZO實際上包含很多算法，在最大程度上保證了對這些算法的兼容性。儘管LZO的壓縮庫中包含了很多可用的壓縮算法，在應用的時候只會加載一種壓縮算法。這些算法包括LZ01、LZ01A、LZO1B、LZ01F、LZ01X、LZ01Y、LZ01Z等。經過試驗，證明LZ01B適用於大的數據塊或者存在大量冗餘的數據，LZ01F適用於小的數據塊或者二進制數據，LZ01X對於所有場景都常常是最好的選擇。LZ01Y和LZ01Z幾乎同LZ01X是一樣的，只不過針對某些文件它們能獲得更高的壓縮比。

那麼如何選擇具體使用哪種算法呢？正如上面所說，LZ01X通常都是最好的選擇，一般來說有以下幾種情境。

• 當想要更快的壓縮速度時選擇LZ01X-1。
• 當產生與預壓縮數據時使用LZ01X-999。
• 如果只有很少的內存可用時，那就選擇LZ01X-1(11)或者LZ01X-1(12)。

這些算法在解壓時有什麼區別？我們還用LZ01X來做代表，因為它是標準的解壓器，相當快，所以儘可能選擇它。它包含以下幾種解碼器（decompressor）。

• lzo1x_decompress：這種解碼器需要合法的壓縮數據，如果壓縮數據損壞，那麼解壓過程可能使你的程序崩潰，因為它並不會做預先的檢查。
• lzo1x_decompress_safe：這種“安全”解壓器速度有些慢，但是它能夠檢測出所有壓縮數據的錯誤，並且返回錯誤代碼，它永遠不會崩潰。
• lzo1x_decompress_asm和lzo1x_decompress_asm_safe：類似上面兩個解碼器，只不過它們是用匯編語言編寫的。
• lzo1x_decompress_asm_fast：跟lzo1x_decompress_asm相比更快。由於速度快，它會在解壓後的數據塊後面增加3字節的數據（因為數據以4字節進行傳輸，這樣表示解壓數據塊的結束）。從一個內存塊向另一個內存塊解壓時可以使用這種解碼器，只不過需要提供額外3字節的輸出空間。但如果直接往視頻內存中解壓時別使用這種解碼器，因為額外的3字節數據會影響視頻顯示。

5.2 LZO原理

LZO雖然包含了很多小的算法，但是基本原理都與LZSS壓縮算法類似，所以首先介紹一下LZSS的原理。LZSS算法在壓縮數據時，會設定標識位來說明後續編碼的情況，如圖7-10所示。在這裡，LZSS利用8 bit的標誌位說明其後面緊鄰4個位置的情況，每兩位為一組，F(01)h=F(00 00 00 01)2，F(00)2表示新字符，F(01)2表示重複字符，F(11)2表示控制字符。需要強調的是，LZSS限制重複字符串的長度不能太小（這裡要求不能小於2），所以第二個位置的A被當成新字符看待。這樣前三個字符都是新字符，它們對應的標識位都為F(00)2。從第四個位置開始出現重複字符串，所以相應的標識位為F(01)2。((03)h, (06)h)中第一個元素表示重複字符串的位置偏移量，第二個元素表示重複長度，因為與第一個AAB重複，而且第一個A距離當前位置為3，且重複的長度為6，所以這裡的就用((03)h, (06)h)表示後續的AABAAB了。

圖7-10 LZSS壓縮算法示例

LZSS存在一個缺點，就是當用來壓縮的內容重複率低時，它仍然需要用標誌位F(00)h表示，這就會增加很多不必要的空間開銷。另外，由於LZSS在尋找重複串時是找最長的匹配串，所以時間開銷也比較大。針對這兩個缺點，LZO進行了改進，因此它的效率更高。還是上面的例子，採用LZO壓縮，如圖7-11所示。

圖7-11 LZO壓縮算法示例

LZO不會採取標誌位，而是直接計算新字符出現的次數，如上面例子中新字符的長度為3，所以就用(03)h表示。在解壓的時候讀到(03)h就知道後面三個字符為新字符直接輸出，到第四個字符是重複串，向前偏移3個位置，輸出長度為6的重複串。

在尋找匹配串時，LZO不是尋找最長的重複串，而是通過兩次哈希操作，在記憶體（LZO編碼過程中需要用記憶體記錄編碼信息）中尋找位置。如果兩次哈希都產生衝突，那麼LZO就不再尋找空位置，而是把需要編碼的內容當成新字符輸出。這樣就大大減少了尋找最長匹配串的時間開銷。

張強Beijing

壓縮是基於一定的壓縮算法，比如無損壓縮等。計算機要存的內容分為指令和數據兩塊。一般在內存的一開始指定地址中存放的是啟動指令，所謂的boot。指令中會包含數據存放地址。

關鍵字: 電腦 壓縮 科技