RLE
RLE
又叫
Run Length Encoding
，是一個(gè)針對(duì)無損壓縮的非常簡(jiǎn)單的算法。它用重復(fù)字節(jié)和重復(fù)的次數(shù)來簡(jiǎn)單描述來代替重復(fù)的字節(jié)。盡管簡(jiǎn)單并且對(duì)于通常的壓縮非常低效，但它有的時(shí)候卻非常有用（例如，
JPEG
就使用它）。
1.1.
原理
圖
2.1
顯示了一個(gè)如何使用
RLE
算法來對(duì)一個(gè)數(shù)據(jù)流編碼的例子，其中出現(xiàn)六次的符號(hào)‘
93
’已經(jīng)用
3
個(gè)字節(jié)來代替：一個(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é)用來指示重復(fù)節(jié)的開始，而不是對(duì)于重復(fù)非重復(fù)節(jié)都
coding run
。
因此非重復(fù)節(jié)可以有任意長(zhǎng)度而不被控制字節(jié)打斷，除非指定的標(biāo)記字節(jié)出現(xiàn)在非重復(fù)節(jié)（頂多以兩個(gè)字節(jié)來編碼）的稀有情況下。為了最優(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é)來編碼
256
個(gè)字節(jié)）而言非常少見的有損壓縮率的方法。
在這種模式下，最壞的壓縮結(jié)果是：
輸出大小
=257/256*
輸入大小
+1
2.??
哈夫曼
哈夫曼編碼是無損壓縮當(dāng)中最好的方法。它使用預(yù)先二進(jìn)制描述來替換每個(gè)符號(hào)，長(zhǎng)度由特殊符號(hào)出現(xiàn)的頻率決定。常見的符號(hào)需要很少的位來表示，而不常見的符號(hào)需要很多為來表示。
哈夫曼算法在改變?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)使用很少的位，不常見的符號(hào)使用較多的位。
簡(jiǎn)短的說，這個(gè)問題的解決方案是為了查找每個(gè)符號(hào)的通用程度，我們建立一個(gè)未壓縮數(shù)據(jù)的柱狀圖；通過遞歸拆分這個(gè)柱狀圖為兩部分來創(chuàng)建一個(gè)二叉樹，每個(gè)遞歸的一半應(yīng)該和另一半具有同樣的權(quán)（權(quán)是
∑
N
K
=1
符號(hào)數(shù)
k
, N
是分之中符號(hào)的數(shù)量，符號(hào)數(shù)
k
是符號(hào)
k
出現(xiàn)的次數(shù)
）
這棵樹有兩個(gè)目的：
1．
?
編碼器使用這棵樹來找到每個(gè)符號(hào)最優(yōu)的表示方法
2．
?
解碼器使用這棵樹唯一的標(biāo)識(shí)在壓縮流中每個(gè)編碼的開始和結(jié)束，其通過在讀壓縮數(shù)據(jù)位的時(shí)候自頂向底的遍歷樹，選擇基于數(shù)據(jù)流中的每個(gè)獨(dú)立位的分支，一旦一個(gè)到達(dá)葉子節(jié)點(diǎn)，解碼器知道一個(gè)完整的編碼已經(jīng)讀出來了。
我們來看一個(gè)例子會(huì)讓我們更清楚。圖
2.2
顯示了一個(gè)
10
個(gè)字節(jié)的未壓縮的數(shù)據(jù)。
根據(jù)符號(hào)頻率，哈夫曼編碼器生成哈夫曼樹（圖
2.4
）和相應(yīng)的編碼表示（圖
2.3
）。
?
你可以看到，常見的符號(hào)接近根，因此只要少數(shù)位來表示。于是最終的壓縮數(shù)據(jù)流如圖
2.5
所示。
壓縮后的數(shù)據(jù)流是
24
位（三個(gè)字節(jié)），原來是
80
位（
10
個(gè)字節(jié)）。當(dāng)然，我應(yīng)該存儲(chǔ)哈夫曼樹，這樣解碼器就能夠解碼出對(duì)應(yīng)的壓縮流了，這就使得該例子中的真正數(shù)據(jù)流比輸入的流數(shù)據(jù)量大。這是相對(duì)較短的數(shù)據(jù)上的副作用。對(duì)于大數(shù)據(jù)量來說，上面的哈夫曼樹就不占太多比例了。
解碼的時(shí)候，從上到下遍歷樹，為壓縮的流選擇從左
/
右分支，每次碰到一個(gè)葉子節(jié)點(diǎn)的時(shí)候，就可以將對(duì)應(yīng)的字節(jié)寫到解壓輸出流中，然后再?gòu)母_始遍歷。
2.2.
實(shí)現(xiàn)
哈夫曼編碼器可以在基本壓縮庫(kù)中找到，其是非常直接的實(shí)現(xiàn)。
這個(gè)實(shí)現(xiàn)的基本缺陷是：
1．
?
慢位流實(shí)現(xiàn)
2．
?
相當(dāng)慢的解碼（比編碼慢）
3．
?
最大的樹深度是
32
（編碼器在任何超過
32
位大小的時(shí)候退出）。如果我不是搞錯(cuò)的話，這是不可能的，除非輸出的數(shù)據(jù)大于
2
32
字節(jié)。
另一方面，這個(gè)實(shí)現(xiàn)有幾個(gè)優(yōu)點(diǎn)：
1．
?
哈夫曼樹以一個(gè)緊密的形式每個(gè)符號(hào)要求
12
位（對(duì)于
8
位的符號(hào)）的方式存儲(chǔ)，這意味著最大的頭為
384
。
2．
?
編碼相當(dāng)容易理解
哈夫曼編碼在數(shù)據(jù)有噪音的情況（不是有規(guī)律的，例如
RLE
）下非常好，這中情況下大多數(shù)基于字典方式的編碼器都有問題。
3.??
Rice
對(duì)于由大
word
（例如：
16
或
32
位）組成的數(shù)據(jù)和教低的數(shù)據(jù)值，
Rice
編碼能夠獲得較好的壓縮比。音頻和高動(dòng)態(tài)變化的圖像都是這種類型的數(shù)據(jù)，它們被某種預(yù)言預(yù)處理過（例如
delta
相鄰的采樣）。
盡管哈夫曼編碼處理這種數(shù)據(jù)是最優(yōu)的，卻由于幾個(gè)原因而不適合處理這種數(shù)據(jù)（例如：
32
位大小要求
16GB
的柱狀圖緩沖區(qū)來進(jìn)行哈夫曼樹編碼）。因此一個(gè)比較動(dòng)態(tài)的方式更適合由大
word
組成的數(shù)據(jù)。
3.1.
原理
Rice
編碼背后的基本思想是盡可能的用較少的位來存儲(chǔ)多個(gè)字（正像使用哈夫曼編碼一樣）。實(shí)際上，有人可能想到
Rice
是靜態(tài)的哈夫曼編碼（例如，編碼不是由實(shí)際數(shù)據(jù)內(nèi)容的統(tǒng)計(jì)信息決定，而是由小的值比高的值常見的假定決定）。
編碼非常簡(jiǎn)單：將值
X
用
X
個(gè)‘
1
’位之后跟一個(gè)
0
位來表示。
3.2.
實(shí)現(xiàn)
在基本壓縮庫(kù)針對(duì)
Rice
做了許多優(yōu)化：
1．
?
每個(gè)字最沒有意義的位被存儲(chǔ)為
k
和最有意義的
N-k
位用
Rice
編碼。
K
作為先前流中少許采樣的位平均數(shù)。這是通常最好使用
Rice
編碼的方法，隱藏噪音且對(duì)于動(dòng)態(tài)變化的范圍并不導(dǎo)致非常長(zhǎng)的
Rice
編碼。
2．
?
如果
rice
編碼比固定的開端長(zhǎng)，
T
，一個(gè)可選的編碼：輸出
T
個(gè)‘
1
’位，緊跟（
log2(X-T)
）個(gè)‘
1
’和一個(gè)‘
0
’位，接著是
X-T
（最沒有意義的
(log2(X-T))-1
位）。這對(duì)于大值來說都是比較高效的代碼并且阻止可笑的長(zhǎng)
Rice
編碼（最壞的情況，對(duì)于一個(gè)
32
位
word
單個(gè)
Rice
編碼可能變成
2
32
位或
512MB
）。
如果開端是
4
，下面是結(jié)果編碼表：
|
X
|
bin
|
Rice
|
Thresholded
|
Rice
|
|
0
|
00000
|
0
|
0
|
?
|
|
1
|
00001
|
10
|
10
|
?
|
|
2
|
00010
|
110
|
110
|
?
|
|
3
|
00011
|
1110
|
1110
|
?
|
|
4
|
00100
|
11110
|
11110
|
?
|
|
5
|
00101
|
111110
|
111110
|
?
|
|
6
|
00110
|
1111110
|
11111100
|
+1
|
|
7
|
00111
|
11111110
|
11111101
|
?
|
|
8
|
01000
|
111111110
|
1111111000
|
+1
|
|
9
|
01001
|
1111111110
|
1111111001
|
?
|
|
10
|
01010
|
11111111110
|
1111111010
|
-1
|
|
11
|
01011
|
111111111110
|
1111111011
|
-2
|
|
12
|
01100
|
1111111111110
|
111111110000
|
?
|
|
13
|
01101
|
11111111111110
|
111111110001
|
-1
|
|
14
|
01110
|
111111111111110
|
111111110010
|
-2
|
|
15
|
01111
|
1111111111111110
|
111111110011
|
-3
|
|
16
|
10000
|
11111111111111110
|
111111110100
|
-4
|
|
17
|
10001
|
111111111111111110
|
111111110101
|
-5
|
|
18
|
10010
|
1111111111111111110
|
111111110110
|
-6
|
|
19
|
10011
|
11111111111111111110
|
111111110111
|
-7
|
|
20
|
10100
|
111111111111111111110
|
11111111100000
|
-5
|
就像你看到的一樣，在這個(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
編碼器能用來通用目標(biāo)的壓縮，特別對(duì)于文本執(zhí)行的很好。它也在
RLE
和哈夫曼編碼器（
RLE
，
LZ
，哈夫曼）中使用來大多數(shù)情況下獲得更多的壓縮。
4.1.
原理
在
LZ
壓縮算法的背后是使用
RLE
算法用先前出現(xiàn)的相同字節(jié)序列的引用來替代。
簡(jiǎn)單的講，
LZ
算法被認(rèn)為是字符串匹配的算法。例如：在一段文本中某字符串經(jīng)常出現(xiàn)，并且可以通過前面文本中出現(xiàn)的字符串指針來表示。當(dāng)然這個(gè)想法的前提是指針應(yīng)該比字符串本身要短。
例如，在上一段短語“字符串”經(jīng)常出現(xiàn)，可以將除第一個(gè)字符串之外的所有用第一個(gè)字符串引用來表示從而節(jié)省一些空間。
一個(gè)字符串引用通過下面的方式來表示：
1．
?
唯一的標(biāo)記
2．
?
偏移數(shù)量
3．
?
字符串長(zhǎng)度
由編碼的模式?jīng)Q定引用是一個(gè)固定的或變動(dòng)的長(zhǎng)度。后面的情況經(jīng)常是首選，因?yàn)樗试S編碼器用引用的大小來交換字符串的大小（例如，如果字符串相當(dāng)長(zhǎng)，增加引用的長(zhǎng)度可能是值得的）。
4.2.
實(shí)現(xiàn)
使用
LZ77
的一個(gè)問題是由于算法需要字符串匹配，對(duì)于每個(gè)輸入流的單個(gè)字節(jié)，每個(gè)流中此字節(jié)前面的哪個(gè)字節(jié)都必須被作為字符串的開始從而盡可能的進(jìn)行字符串匹配，這意味著算法非常慢。
另一個(gè)問題是為了最優(yōu)化壓縮而調(diào)整字符串引用的表示形式并不容易。例如，必須決定是否所有的引用和非壓縮字節(jié)應(yīng)該在壓縮流中的字節(jié)邊界發(fā)生。
基本壓縮庫(kù)使用一個(gè)清晰的實(shí)現(xiàn)來保證所有的符號(hào)和引用是字節(jié)對(duì)齊的，因此犧牲了壓縮比率，并且字符串匹配程序并不是最優(yōu)化的（沒有緩存、歷史緩沖區(qū)或提高速度的小技巧），這意味著程序非常慢。
另一方面，解壓縮程序非常簡(jiǎn)單。
一個(gè)提高
LZ77
速度的試驗(yàn)已經(jīng)進(jìn)行了，這個(gè)試驗(yàn)中使用數(shù)組索引來加速字符串匹配的過程。然而，它還是比通常的壓縮程序慢。