幾種壓縮算法原理介紹（轉）

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

1.1. 原理

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

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

1.2. 實現(xiàn)

RLE 可以使用很多不同的方法。基本壓縮庫中詳細實現(xiàn)的方式是非常有效的一個。一個特殊的標記字節(jié)用來指示重復節(jié)的開始，而不是對于重復非重復節(jié)都 coding run 。

因此非重復節(jié)可以有任意長度而不被控制字節(jié)打斷，除非指定的標記字節(jié)出現(xiàn)在非重復節(jié)（頂多以兩個字節(jié)來編碼）的稀有情況下。為了最優(yōu)化效率，標記字節(jié)應該是輸入流中最少出現(xiàn)的符號（或許就不存在）。

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

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

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

2.   哈夫曼

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

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

2.1. 原理

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

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

這棵樹有兩個目的：

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

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

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

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

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

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

解碼的時候，從上到下遍歷樹，為壓縮的流選擇從左 / 右分支，每次碰到一個葉子節(jié)點的時候，就可以將對應的字節(jié)寫到解壓輸出流中，然后再從根開始遍歷。

2.2. 實現(xiàn)

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

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

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

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

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

另一方面，這個實現(xiàn)有幾個優(yōu)點：

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

2．  編碼相當容易理解

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

3.   Rice

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

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

3.1. 原理

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

編碼非常簡單：將值 X 用 X 個‘ 1 ’位之后跟一個 0 位來表示。

3.2. 實現(xiàn)

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

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

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

如果開端是 4 ，下面是結果編碼表：

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

3．  最壞的情況，輸出。

4.   Lempel-Ziv (LZ77)

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

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

4.1. 原理

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

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

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

一個字符串引用通過下面的方式來表示：

1．  唯一的標記

2．  偏移數(shù)量

3．  字符串長度

由編碼的模式決定引用是一個固定的或變動的長度。后面的情況經常是首選，因為它允許編碼器用引用的大小來交換字符串的大小（例如，如果字符串相當長，增加引用的長度可能是值得的）。

4.2. 實現(xiàn)

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

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

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

另一方面，解壓縮程序非常簡單。

一個提高 LZ77 速度的試驗已經進行了，這個試驗中使用數(shù)組索引來加速字符串匹配的過程。然而，它還是比通常的壓縮程序慢。

posted on 2011-04-06 08:48 coreBugZJ 閱讀(369) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm