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

資料壓縮概念

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

資料壓縮包括有失真壓縮和無失真壓縮。

首先介紹資料壓縮的基本原理以及傳統的壓縮演算法，然後實際應用中的壓縮技術，包括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就不再尋找空位置，而是把需要編碼的內容當成新字元輸出。這樣就大大減少了尋找最長匹配串的時間開銷。

由於計算機是使用二進位制，那找到一個有兩種不同狀態的介質就可以儲存一個位元(資料位)的資料。可以簡單理解為燈泡的開閉狀態，開表示1，關閉表示0。我們一般買電腦的時候會留意處理器的頻率是多少赫茲，這個赫茲在這裡也就意味著，重新整理小燈泡狀態的速度是怎樣的，當然是越快越好。 具體技術上的實現是有一個稱為動態隨機存取儲存器(Dram)的東西實現。

我們都知道，任何資料在計算機上都只是一串01，所以我們所熟知的十進位制會被轉換為二進位制，37(10)=100101(2)。

簡單說下進位制之間的轉換，以二進位制轉十進位制為例，分別計算各數字位上2需要相乘的數量再各自相加，若當前位存在1則計算，2^5 + 0 + 0 + 2^2 + 0 + 1 = 37。另外，還有補碼和浮點數為了解決負數和小數的問題。

這裡的字元應該簡單理解為abcd這樣的英文字元。最終儲存的當然還是01，因此這裡需要使用ASCii對應規則，其實就是一個對映，考慮到計算機只認01，那我們只需要規定一個字元對應一個AScii值，而一個ASCii又對應一串二進位制數字。比如，a在AScii碼錶中對應的值是97(10)，那麼只需要a => 97(10) => 0110 0001(2)，這樣就把這個字元存入了電腦中。

英文倒好，全部單詞都是由26個字母組合而成，但中文漢字卻不一樣，每個漢字都是獨立的個體，在儲存上無法複用。因此有了GB2312(國標)，其中共有6736個漢字，因為這麼多的漢字已經大大的超過了一個位元組的容量。一個位元組的容量即2^8，一個位元組由八個二進位制位構成，前面說到AScii碼錶，只要一個位元組就可以儲存所有的字元，但中文卻需要兩個位元組，即16位。因此在一樣的容量限制下，相較於漢字電腦能容納下更多的英文字元。