無失真壓縮經典演算法

@前言

總結經典的檔案壓縮演算法原理,主要包括:哈夫曼壓縮演算法及其延伸,LZ77演算法及其演變演算法,LZ78演算法及其演變演算法,幾何編碼演算法Arithmetic Coding。

內容部分摘錄翻譯自港大‘多媒體技術’碩士課程


1.進行檔案壓縮的必要性

像圖片、聲音、視訊這些型別的多媒體資料要比文字資料佔用多得多的記憶體空間,尤其是視訊檔案,檔案傳輸時佔用頻寬大,儲存又佔用大量的硬碟空間。

舉個例子:一個1080p解析度格式下90分鐘的無壓縮視訊要多大?

1幀大小 = 1920 x 1080 x 3 = 6220800 bytes (1920×1080是每一幀的畫素數,3指的是每個畫素紅綠藍三個通道各佔一個位元組0~256)

每秒大小 = 6220800 x 25 = 155.52MB!(假設幀率為每秒25幀,很小了!)

每分鐘大小 = 155.52MB x 60 = 9.3312GB!

90分鐘:大約839.81GB

儲存高清視訊的藍光光碟容量不過只有大約50GB,所以視訊如果不壓縮根本沒法儲存,更不用說互相傳送了。

2.簡單黑白影象的壓縮

假設黑白影象的資料如下圖,黑色畫素用1編碼,白色影象用0編碼:

這裡寫圖片描述

黑白影象的尺寸為16×8 = 128,因此需要128bits來表示它。

如果我們從0開始算起,只儲存一些列0和1的個數,那麼上面的影象資訊可以表示為:

21 6 9 1 5 2 8 1 3 2 1 1 8 1 2 2 2 1 8 6 21

其中最大的數字是21,所以可以統一使用5bits(2^5=32)來表示每一個數字,那麼現在的儲存空間變為5×21=105bits,節省了23bits。

3.字串行程編碼

和上面黑白影象壓縮一樣的道理,這裡壓縮一段字串:RRRRRGGGBBBBBRRRRGB

壓縮的結果為:5R3G5B4R1G1B

這種方法叫做行程編碼run-ength encoding(RLE),應用於像BMP,TIFF格式的影象檔案中。

但這種壓縮編碼方式很有侷限性,我們無法繼續用相同的方法進一步壓縮壓縮後的資料,比如上面的壓縮結果無法繼續用這種方法壓縮,這種壓縮基於資料的重複性。

4.資訊的可壓縮性-資訊量和資訊熵

資訊量

資料的壓縮水平和資料的資訊量有關,資訊量越大自然資料量越大越難以壓縮。資料的資訊量如何來衡量呢?

例子:假設有一個64位的字串,64個數字,其中63個0,另一個是1,1可能出現在任意位置,也就是在某個位置的概率為1/64。現在從左往右讀取知道找到1。(注意下表是找到1之前的概率,當找到1之後,之後的符號確定不可能再出現1了,因此P(bi=1)變為0,P(bi=0)變為1)

對於在位置i的符號bi,bi為0或者為1的概率分佈如下:
這裡寫圖片描述

事實上,一個符號的概率越大,那麼它包含的資訊就越小,也就是資訊量和符號出現的概率成反比,資訊量的定義為:

h(x)=log21p(x)

h(x)=log_2\frac{1}{p(x)}

計算對應的符號資訊量表:
這裡寫圖片描述

資訊量計算:如果1位於第4個位置:000100…0,則總的資訊量為:

Sum = 0.0227 0.023 0.0235 5.9307 = 6

通用公式:

∑n=1ih(bn)=(∑m=66−i64log2mm−1 log211/(65−1))=log2((∏m=66−i64mm−1)(65−i))=6

\sum_{n=1}^ih(b_n)=(\sum_{m=66-i}^{64}log_2\frac{m}{m-1} log_2\frac{1}{1/(65-1)}) = log_2((\prod_{m=66-i}^{64}\frac{m}{m-1}) (65-i)) = 6

每個字元資訊量的和表示了整個字串的資訊量,這裡至少需要6位來表示這個字串,要儲存的是公式中的索引(0~63)。

資訊熵

資料的壓縮實際是用更短的資料來表示反覆出現的資料實現壓縮,因此資料重複率越高或者可預測性越強可壓縮性就越高,不同資料可壓縮的程度不一樣,資訊熵是用來衡量資料可壓縮的程度的一個引數,計算資訊最短的長度的期望,關於資訊熵:http://www.ruanyifeng.com/blog/2014/09/information-entropy.html

上面能精確計算資訊量是因為我們知道了字串的具體結構,對於未知的資訊我們只能根據概率計算其資訊量的期望,計算公式為:

H(X)=∑iP(xi)h(xi)

H(X) = \sum_{i}P(x_i)h(x_i)

最差的情況是當所有符號的概率都相同,概率均勻分佈,此時資訊熵為最大值,因為對於一個子串,根本無法預測下一個符號。

5.對編碼演算法的要求

  1. 通過編碼後的編碼必須可以準確解碼,編碼必須確定地對應一種原碼;
  2. 編碼演算法得到的編碼要容易解碼,可以很容易的找到資訊的末尾,可以線上解碼,可以直接對編碼進行解碼而不用知道完整的編碼資訊;
  3. 編碼必須是壓縮的,否則失去了編碼的意義;

6.哈夫曼編碼

哈夫曼編碼是David A. Huffman於1952年發明的一種滿足上面對編碼演算法要求的一種編碼演算法。

舉一個例子:知道一段字串全部由a,b,c,d,e五個字母組成,已知了每個字母出現的頻率:

a(0.25),b(0.25),c(0.2),d(0.15),e(0.15)

【如果不考慮編碼演算法,使用定長的編碼來區別五個字母,不利用頻率這些資訊,那麼五個字母每個字母需要用3bits表示(2^2=4,2^3=8).】

哈夫曼演算法是利用頻率資訊構造一棵二叉樹,頻率高的離根節點近(編碼長度短),頻率低的離根節點遠(編碼長度長),手動構造方法是先將字母按照頻率從小到大排序,然後不斷選擇當前還沒有父節點的節點中權值最小的兩個,構造新的父節點,父節點的值為這兩個節點值的和,直到構造成一棵二叉樹,上面的例子構造的Y一棵哈弗曼樹如下(由於構造過程中葉子節點的值以及新節點的值可能會相同,所以哈弗曼樹的結構不唯一):

這裡寫圖片描述

對構造的哈弗曼二叉樹進行編碼,左邊為0,右邊為1,就得到一個編碼的哈弗曼樹,從而對字串進行編碼。

哈夫曼演算法C 實現,使用線性陣列儲存節點的方式實現,輸入上面每個字母的權值可以得到哈弗曼樹結構:

#include <iostream>
using namespace std;
#define n 5         // 字元個數(葉子個數)
#define m 2*(n)-1   // 總節點數:1 2 4 8 ... n
typedef struct{
double weight;   // 節點權重
int lchild;      // 左子樹
int rchild;      // 右子樹
int parent;      // 父節點
}HTNODE;
typedef HTNODE HuffmanT[m];  // 一棵線性結構儲存的哈弗曼樹
/**
* 哈弗曼樹初始化
*/
void InitHT(HuffmanT T)
{
for(int i=0; i<m; i  )
{
T[i].lchild=-1;
T[i].rchild=-1;
T[i].parent=-1;
}
// 依次輸入每個節點的權重
for(int i=0; i<n; i  )
std::cin>>T[i].weight;
}
/**
* 找出還沒有父節點的節點中權值最小的兩個,p1和p2是要選出的權值最小的兩個節點的下標,n1是新父節點的下標
*/
void SelectMin(HuffmanT T, int n1, int &p1, int &p2)
{
int i, j;
// 先任意找兩個沒有父節點的節點
for(i=0; i<n1; i  )
if(T[i].parent==-1)
{
p1=i;
break;
}
for(j=i 1; j<n1;j  )
if(T[j].parent==-1)
{
p2=j;
break;
}
// 搜尋替換成權值最小的節點
for(i=0; i<n1; i  )
if((T[p1].weight>T[i].weight) && (T[i].parent==-1) && (p2!=i))
p1=i;
for(i=0; i<n1; i  )
if((T[p2].weight>T[i].weight) && (T[i].parent==-1) && (p1!=i))
p2=i;
}
/**
* 構造哈弗曼樹
*/
void CreatHT(HuffmanT T)
{
int i, p1, p2;
InitHT(T);
// 非葉子節點
for(i=n; i<m; i  )
{
// 找出還沒有父節點的節點中權值最小的兩個
SelectMin(T, i, p1, p2);
T[p1].parent=T[p2].parent=i;
T[i].lchild=p1;
T[i].rchild=p2;
T[i].weight=T[p1].weight T[p2].weight;
}
}
/**
* 列印哈弗曼樹
*/
void printHT(HuffmanT T)
{
for(int i=0; i<m; i  )
{
std::cout<<T[i].weight<<'\t'<<T[i].parent<<'\t'<<T[i].rchild<<'\t'<<T[i].lchild<<std::endl;
}
}
/**
* 前臺測試
*/
int main(){
HuffmanT T;
CreatHT(T);
printHT(T);
return 0;
}

縮減的哈夫曼演算法

哈夫曼編碼的縮減實質是對編碼字元分組繼續進行子分組內編碼。先將所有字元按照出現的概率排序,將概率相近的字元作為一個整體參與上一級的編碼,這樣上一級的編碼數量大大減少,分組內繼續進行內部哈夫曼編碼,同時在上一級中本組的編碼作為組內編碼的一個固定的字首。

這裡寫圖片描述

Shift Coding

和縮減的思想類似,將字元按照頻率8個一組分塊,每到下一塊在前面加111進行區分後繼續進行3bit的編碼。

這裡寫圖片描述

7.Lempel-Ziv壓縮演算法

LZ演算法及其衍生變形演算法是壓縮演算法的一個系列。LZ77和LZ78演算法分別在1977年和1978年被創造出來。雖然他們名字差不多,但是演算法方法完全不同。這一系列演算法主要適用於字母數量有限的資訊,比如文字、原始碼等。流行的GIF和PNG格式的影象,使用顏色數量有限的顏色空間,其壓縮就採用了兩種演算法的靈活變形應用。

LZ77:

推薦閱讀文章:

LZ77壓縮演算法編碼原理詳解(結合圖片和簡單程式碼)

LZ77演算法原理及實現

LZ77演算法的思想是在編碼解碼過程中,使用之前剛結束編解碼的部分資料的位置索引來代替當前要編解碼的資料,壓縮的實現靠的是之前編解碼結束的部分資料和當前資料的重複性。

演算法中幾個重要的物件概念:

LAB(look-ahead-buffer):將要編碼的固定長度的資料緩衝;

SB(search-buffer):剛過去的固定長度的資料緩衝,搜尋緩衝區,也就是臨時的資料字典,要從這裡面搜尋重複資料獲得壓縮索引;

Cursor:一個指標,指的是SB和LAB緩衝之間的邊界處

Token(p,l,c)編碼的結果:

  • p: 第一個數字指的是SB中開始匹配的位置,注意是從Cursor往前倒著數,從1開始數
  • l: 第二個數字指的是匹配成功的字元個數;
  • c: 第三個指的是LAB中匹配結束的下一個字元;

注意:在匹配時是搜尋字典中最長的匹配,且當前的LAB區域如果繼續匹配也繼續搜尋(比如匹配到SB的最後一個字元後下一個到LAB的第一個字元仍然匹配則繼續,直到不匹配或匹配數達到了LAB的長度限制則停止。如果在SB中一個都不匹配則不繼續搜尋,排除LAB第一個字元自身無盡迴圈匹配的情況)。

示例:

字串“aacaacabcabaaac”的一個LZ77編碼示例,其中緩衝長度分別為:LAB=4,SB=6

這裡寫圖片描述

LZ77的變形

LZR:就是SB搜尋緩衝的長度不固定了,演算法輸出的token位長度也是可變的。

LZH:演算法的輸出結果又進行了哈夫曼編壓縮。

DEFLATE:當前最流行的基於LZ77的壓縮演算法,是很多通用的Unix壓縮專案‘gzip’的一部分。

LZ78:

演算法是將編碼過程中之前編碼過的所有字元作為了一個索引字典,之前的每一次編碼是一個字典元素,之後的編碼如果包含之前字典的元素則用該元素的索引代替實現壓縮(注意是從之前的字典元素中找那個匹配最長的字典元素),同時記錄不匹配的那個字元。可以想到,不斷更新的字典中最長的字典元素很可能會越來越長且每次長一個字元。

示例:對字串“abacbabaccbabbaca“進行LZ78編碼。
這裡寫圖片描述

LZ78的變形演算法

上面說到LZ78的最長的字典元素只會越來越長不受限制,那麼就要使用變長的bit空間來儲存字典索引,當前字典的需要儲存索引的空間大小為$log2 (i)$ bits, $i$為目前字典中最長字典元素的長度。

LZC

演算法給字典元素的長度設定一個最大值,如果匹配的結果超出最大值時就選擇上一個相對較短的匹配的字典元素,防止字典元素變得太長。如果編碼壓縮率受限制變得太小,就清空之前的字典,比如重新開始壓縮演算法。

LZW

和LZ78不同的是,演算法開始不是空的字典,一開始就把可能的所有單一字元作為最開始的字典,另外不是和LZ78那樣記錄字典索引和不匹配字元,而是隻記錄匹配的字典索引(不可能出現不匹配的情況,至少匹配一個字元了)。

示例:對字串“abacbabaccbabbaca”進行LZW編碼:
這裡寫圖片描述

算術編碼

算數編碼是考慮到解決哈夫曼編碼的一個限制:對於資訊的編碼,要對每一個字元都要使用一個幾個二進位制的bit數區別表示,收到整體的影響,平均每個字元可能都要用不少的bit數空間來表示。
算術編碼是將編碼的訊息表示成實數0和1之間的一個間隔,訊息越長,編碼表示它的間隔就越小,形成結合越來越緊密的編碼,同時需要表示的二進位制位數就越多,導致算數編碼的最大問題就是計算機的精度問題,精度有限,正常情況下無法進行大量資料的編碼,事實上只能編碼很短的資料。後來有了其他的先進方法才使算術編碼得到應用,具體參考算數編碼文章連結。

推薦閱讀:算術編碼