RLE

RLE又叫Run Length Encoding，是一個(gè)針對無(wú)損壓縮的非常簡(jiǎn)單的算法。它用重復字節和重復的次數來(lái)簡(jiǎn)單描述來(lái)代替重復的字節。盡管簡(jiǎn)單并且對于通常的壓縮非常低效，但它有的時(shí)候卻非常有用（例如，JPEG就使用它）。

1.1. 原理

圖2.1顯示了一個(gè)如何使用RLE算法來(lái)對一個(gè)數據流編碼的例子，其中出現六次的符號‘93’已經(jīng)用3個(gè)字節來(lái)代替：一個(gè)標記字節（‘0’在本例中）重復的次數（‘6’）和符號本身（‘93’）。

RLE解碼器遇到符號‘0’的時(shí)候，它表明后面的兩個(gè)字節決定了需要輸出哪個(gè)符號以及輸出多少次。

1.2. 實(shí)現

RLE可以使用很多不同的方法?；緣嚎s庫中詳細實(shí)現的方式是非常有效的一個(gè)。一個(gè)特殊的標記字節用來(lái)指示重復節的開(kāi)始，而不是對于重復非重復節都coding run。

因此非重復節可以有任意長(cháng)度而不被控制字節打斷，除非指定的標記字節出現在非重復節（頂多以?xún)蓚€(gè)字節來(lái)編碼）的稀有情況下。為了最優(yōu)化效率，標記字節應該是輸入流中最少出現的符號（或許就不存在）。

重復runs能夠在32768字節的時(shí)候運轉。少于129字節的要求3個(gè)字節編碼（標記+次數+符號），而大雨128字節要求四個(gè)字節（標記+次數的高4位|0x80+次數的低4位）。這是通常所有采用的壓縮的做法，并且也是相比較三個(gè)字節固定編碼（允許使用3個(gè)字節來(lái)編碼256個(gè)字節）而言非常少見(jiàn)的有損壓縮率的方法。

在這種模式下，最壞的壓縮結果是：

輸出大小=257/256*輸入大小+1

2.   哈夫曼

哈夫曼編碼是無(wú)損壓縮當中最好的方法。它使用預先二進(jìn)制描述來(lái)替換每個(gè)符號，長(cháng)度由特殊符號出現的頻率決定。常見(jiàn)的符號需要很少的位來(lái)表示，而不常見(jiàn)的符號需要很多為來(lái)表示。

哈夫曼算法在改變任何符號二進(jìn)制編碼引起少量密集表現方面是最佳的。然而，它并不處理符號的順序和重復或序號的序列。

2.1. 原理

我不打算探究哈夫曼編碼的所有實(shí)際的細節，但基本的原理是為每個(gè)符號找到新的二進(jìn)制表示，從而通常符號使用很少的位，不常見(jiàn)的符號使用較多的位。

簡(jiǎn)短的說(shuō)，這個(gè)問(wèn)題的解決方案是為了查找每個(gè)符號的通用程度，我們建立一個(gè)未壓縮數據的柱狀圖；通過(guò)遞歸拆分這個(gè)柱狀圖為兩部分來(lái)創(chuàng )建一個(gè)二叉樹(shù)，每個(gè)遞歸的一半應該和另一半具有同樣的權（權是∑^N_K =₁符號數_k, N是分之中符號的數量，符號數_k是符號k出現的次數）

這棵樹(shù)有兩個(gè)目的：

1．  編碼器使用這棵樹(shù)來(lái)找到每個(gè)符號最優(yōu)的表示方法

2．  解碼器使用這棵樹(shù)唯一的標識在壓縮流中每個(gè)編碼的開(kāi)始和結束，其通過(guò)在讀壓縮數據位的時(shí)候自頂向底的遍歷樹(shù)，選擇基于數據流中的每個(gè)獨立位的分支，一旦一個(gè)到達葉子節點(diǎn)，解碼器知道一個(gè)完整的編碼已經(jīng)讀出來(lái)了。

我們來(lái)看一個(gè)例子會(huì )讓我們更清楚。圖2.2顯示了一個(gè)10個(gè)字節的未壓縮的數據。

根據符號頻率，哈夫曼編碼器生成哈夫曼樹(shù)（圖2.4）和相應的編碼表示（圖2.3）。

你可以看到，常見(jiàn)的符號接近根，因此只要少數位來(lái)表示。于是最終的壓縮數據流如圖2.5所示。

壓縮后的數據流是24位（三個(gè)字節），原來(lái)是80位（10個(gè)字節）。當然，我應該存儲哈夫曼樹(shù)，這樣解碼器就能夠解碼出對應的壓縮流了，這就使得該例子中的真正數據流比輸入的流數據量大。這是相對較短的數據上的副作用。對于大數據量來(lái)說(shuō)，上面的哈夫曼樹(shù)就不占太多比例了。

解碼的時(shí)候，從上到下遍歷樹(shù)，為壓縮的流選擇從左/右分支，每次碰到一個(gè)葉子節點(diǎn)的時(shí)候，就可以將對應的字節寫(xiě)到解壓輸出流中，然后再從根開(kāi)始遍歷。

2.2. 實(shí)現

哈夫曼編碼器可以在基本壓縮庫中找到，其是非常直接的實(shí)現。

這個(gè)實(shí)現的基本缺陷是：

1．  慢位流實(shí)現

2．  相當慢的解碼（比編碼慢）

3．  最大的樹(shù)深度是32（編碼器在任何超過(guò)32位大小的時(shí)候退出）。如果我不是搞錯的話(huà)，這是不可能的，除非輸出的數據大于2³²字節。

另一方面，這個(gè)實(shí)現有幾個(gè)優(yōu)點(diǎn)：

1．  哈夫曼樹(shù)以一個(gè)緊密的形式每個(gè)符號要求12位（對于8位的符號）的方式存儲，這意味著(zhù)最大的頭為384。

2．  編碼相當容易理解

哈夫曼編碼在數據有噪音的情況（不是有規律的，例如RLE）下非常好，這中情況下大多數基于字典方式的編碼器都有問(wèn)題。

3.   Rice

對于由大word（例如：16或32位）組成的數據和教低的數據值，Rice編碼能夠獲得較好的壓縮比。音頻和高動(dòng)態(tài)變化的圖像都是這種類(lèi)型的數據，它們被某種預言預處理過(guò)（例如delta相鄰的采樣）。

盡管哈夫曼編碼處理這種數據是最優(yōu)的，卻由于幾個(gè)原因而不適合處理這種數據（例如：32位大小要求16GB的柱狀圖緩沖區來(lái)進(jìn)行哈夫曼樹(shù)編碼）。因此一個(gè)比較動(dòng)態(tài)的方式更適合由大word組成的數據。

3.1. 原理

Rice編碼背后的基本思想是盡可能的用較少的位來(lái)存儲多個(gè)字（正像使用哈夫曼編碼一樣）。實(shí)際上，有人可能想到Rice是靜態(tài)的哈夫曼編碼（例如，編碼不是由實(shí)際數據內容的統計信息決定，而是由小的值比高的值常見(jiàn)的假定決定）。

編碼非常簡(jiǎn)單：將值X用X個(gè)‘1’位之后跟一個(gè)0位來(lái)表示。

3.2. 實(shí)現

在基本壓縮庫針對Rice做了許多優(yōu)化：

1．  每個(gè)字最沒(méi)有意義的位被存儲為k和最有意義的N-k位用Rice編碼。K作為先前流中少許采樣的位平均數。這是通常最好使用Rice編碼的方法，隱藏噪音且對于動(dòng)態(tài)變化的范圍并不導致非常長(cháng)的Rice編碼。

2．  如果rice編碼比固定的開(kāi)端長(cháng)，T，一個(gè)可選的編碼：輸出T個(gè)‘1’位，緊跟（log2(X-T)）個(gè)‘1’和一個(gè)‘0’位，接著(zhù)是X-T（最沒(méi)有意義的(log2(X-T))-1位）。這對于大值來(lái)說(shuō)都是比較高效的代碼并且阻止可笑的長(cháng)Rice編碼（最壞的情況，對于一個(gè)32位word單個(gè)Rice編碼可能變成2³²位或512MB）。

如果開(kāi)端是4，下面是結果編碼表：

就像你看到的一樣，在這個(gè)實(shí)現中使用threshold方法僅僅兩個(gè)編碼導致一個(gè)最壞的情況；剩下的編碼產(chǎn)生比標準Rice編碼還要短的編碼。

3．  最壞的情況，輸出。

4.   Lempel-Ziv (LZ77)

Lempel-Ziv壓縮模式有許多不同的變量?；緣嚎s庫有清晰的LZ77算法的實(shí)現（Lempel-Ziv，1977），執行的很好，源代碼也非常容易理解。

LZ編碼器能用來(lái)通用目標的壓縮，特別對于文本執行的很好。它也在RLE和哈夫曼編碼器（RLE，LZ，哈夫曼）中使用來(lái)大多數情況下獲得更多的壓縮。

4.1. 原理

在LZ壓縮算法的背后是使用RLE算法用先前出現的相同字節序列的引用來(lái)替代。

簡(jiǎn)單的講，LZ算法被認為是字符串匹配的算法。例如：在一段文本中某字符串經(jīng)常出現，并且可以通過(guò)前面文本中出現的字符串指針來(lái)表示。當然這個(gè)想法的前提是指針應該比字符串本身要短。

例如，在上一段短語(yǔ)“字符串”經(jīng)常出現，可以將除第一個(gè)字符串之外的所有用第一個(gè)字符串引用來(lái)表示從而節省一些空間。

一個(gè)字符串引用通過(guò)下面的方式來(lái)表示：

1．  唯一的標記

2．  偏移數量

3．  字符串長(cháng)度

由編碼的模式?jīng)Q定引用是一個(gè)固定的或變動(dòng)的長(cháng)度。后面的情況經(jīng)常是首選，因為它允許編碼器用引用的大小來(lái)交換字符串的大?。ɡ?，如果字符串相當長(cháng)，增加引用的長(cháng)度可能是值得的）。

4.2. 實(shí)現

使用LZ77的一個(gè)問(wèn)題是由于算法需要字符串匹配，對于每個(gè)輸入流的單個(gè)字節，每個(gè)流中此字節前面的哪個(gè)字節都必須被作為字符串的開(kāi)始從而盡可能的進(jìn)行字符串匹配，這意味著(zhù)算法非常慢。

另一個(gè)問(wèn)題是為了最優(yōu)化壓縮而調整字符串引用的表示形式并不容易。例如，必須決定是否所有的引用和非壓縮字節應該在壓縮流中的字節邊界發(fā)生。

基本壓縮庫使用一個(gè)清晰的實(shí)現來(lái)保證所有的符號和引用是字節對齊的，因此犧牲了壓縮比率，并且字符串匹配程序并不是最優(yōu)化的（沒(méi)有緩存、歷史緩沖區或提高速度的小技巧），這意味著(zhù)程序非常慢。

另一方面，解壓縮程序非常簡(jiǎn)單。

一個(gè)提高LZ77速度的試驗已經(jīng)進(jìn)行了，這個(gè)試驗中使用數組索引來(lái)加速字符串匹配的過(guò)程。然而，它還是比通常的壓縮程序慢。