幾種壓縮算法原理介紹（轉(zhuǎn)）

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

1.1. 原理

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

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

1.2. 實(shí)現(xiàn)

RLE 可以使用很多不同的方法。基本壓縮庫(kù)中詳細(xì)實(shí)現(xiàn)的方式是非常有效的一個(gè)。一個(gè)特殊的標(biāo)記字節(jié)用來(lái)指示重復(fù)節(jié)的開(kāi)始，而不是對(duì)于重復(fù)非重復(fù)節(jié)都 coding run 。

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

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

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

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

2.   哈夫曼

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

哈夫曼算法在改變?nèi)魏畏?hào)二進(jìn)制編碼引起少量密集表現(xiàn)方面是最佳的。然而，它并不處理符號(hào)的順序和重復(fù)或序號(hào)的序列。

2.1. 原理

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

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

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

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

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

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

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

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

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

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

2.2. 實(shí)現(xiàn)

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

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

1．  慢位流實(shí)現(xiàn)

2．  相當(dāng)慢的解碼（比編碼慢）

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

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

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

2．  編碼相當(dāng)容易理解

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

3.   Rice

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

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

3.1. 原理

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

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

3.2. 實(shí)現(xiàn)

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

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

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

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

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

3．  最壞的情況，輸出。

4.   Lempel-Ziv (LZ77)

Lempel-Ziv 壓縮模式有許多不同的變量。基本壓縮庫(kù)有清晰的 LZ77 算法的實(shí)現(xiàn)（ Lempel-Ziv ， 1977 ），執(zhí)行的很好，源代碼也非常容易理解。

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

4.1. 原理

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

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

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

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

1．  唯一的標(biāo)記

2．  偏移數(shù)量

3．  字符串長(zhǎng)度

由編碼的模式?jīng)Q定引用是一個(gè)固定的或變動(dòng)的長(zhǎng)度。后面的情況經(jīng)常是首選，因?yàn)樗试S編碼器用引用的大小來(lái)交換字符串的大小（例如，如果字符串相當(dāng)長(zhǎng)，增加引用的長(zhǎng)度可能是值得的）。

4.2. 實(shí)現(xiàn)

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

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

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

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

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

posted on 2011-04-06 08:48 coreBugZJ 閱讀(359) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): Algorithm