計算機數據是怎么壓縮存儲的？

數據壓縮概念

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

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

首先介紹數據壓縮的基本原理以及傳統的壓縮算法，然后實際應用中的壓縮技術，包括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, ...

對于字符“<”，會表示成“<<”的形式。算法中主要的循環在于通過更新信號變量和查找哈希表尋找匹配來處理每一個字符。每b個字符都會存儲一個指紋。如果用變量fp代表指紋，那么可以用如下偽碼表示此循環：

initialize fpfor (i = b; i< n; i++) if (i % b == 0) store(fp, i) updata fp to include a[i] and exclude a[i-b] checkformatch(fp, i)

算法中的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就不再尋找空位置，而是把需要編碼的內容當成新字符輸出。這樣就大大減少了尋找最長匹配串的時間開銷。