第四章 無損數據壓縮

第4章無損數據壓縮

4.1仙農-范諾與霍夫曼編碼4.2算術編碼4.3RLE編碼4.4詞典編碼第4章無損數據壓縮數據壓縮可分成兩種類型，一種叫做無損壓縮，另一種叫做有損壓縮。

無損壓縮是指使用壓縮后的數據進行重構(或者叫做還原，解壓縮)，重構后的數據與原來的數據完全相同

有損壓縮是指使用壓縮后的數據進行重構，重構后的數據與原來的數據有所不同本章主要介紹目前用得最多和技術最成熟的無損壓縮編碼技術。

第4章無損數據壓縮在數據壓縮技術中,編碼技術可分成三種類型:

熵編碼：不考慮數據源的無損數據壓縮技術,它把數據都看作“符號”，其核心思想是按照符號出現的概率大小給符號分配長度合適的代碼。概率大的代碼長度長，概率小的代碼長度短。

源編碼：編碼時考慮數據信號源的特性和信號的內容。通常為有損編碼技術?；旌暇幋a：組合源編碼和熵編碼的數據有損壓縮技術。2.1數據冗余一、冗余的概念數據能被壓縮的依據是數據本身存在冗余。冗余有：人為冗余視聽冗余數據冗余2.1數據冗余二、決策量在有限數目的互斥事件集合中，決策量是事件數的對數值，即

H0=log(n)對數的底數決定決策量的單位，sh(2)、Nat(e)、Hart(10)。2.1數據冗余三、信息量信息量是具有確定概率事件的信息的定量度量，定義為：

I(x)=log2(1/p(x))=-log2p(x)對一個等概率事件的集合，每個事件的信息量等于該集合的決策量。四、熵按照仙農(Shannon)的理論，信源S的熵定義為

其中pi是符號si在S中出現的概率；log(1/pi)表示包含在si中的信息量，H(s)為事件的信息量的平均值，也稱為事件的平均信息量。2.1數據冗余五、數據冗余量數據的冗余量(R)定義為決策量(H0)超過熵的量，即為：

R=H0-H(S)2.1數據冗余4.1仙農-范諾與霍夫曼編碼

[例4.1]有一幅40個像素組成的灰度圖像，灰度共有5級，分別用符號A、B、C、D和E表示,各符號在圖像中出現的數目見下表符 號

ABCDE出現的次數

157765如果用3個比特表示5個等級的灰度值，也就是每個像素用3比特表示，編碼這幅圖像總共需要120比特。

一、仙農-范諾編碼4.1仙農-范諾與霍夫曼編碼按照仙農理論，這幅圖像的熵為

H(S)=(15/40)

log2(40/15)+(7/40)

log2(40/7)+

+(5/40)

log2(40/5)=2.196

即每個符號用2.196比特表示，40個像素需用87.84比特。

4.1仙農-范諾與霍夫曼編碼仙農-范諾(Shannon-Fano)算法采用從上到下的方法進行編碼。首先按照符號出現的頻度或概率排序，例如A，B，C，D和E。然后使用遞歸方法分成兩個部分，每一部分具有近似相同的次數，如圖所示。按照這種方法進行編碼得到的總比特數為91，實際的壓縮比約為1.3:1。A:2位X15B:2位X7C:2位X7D:3位X6E:3位X54.1仙農-范諾與霍夫曼編碼二、霍夫曼編碼

霍夫曼(Huffman)則采用從下到上的編碼方法，仍以剛才的例子說明它的編碼步驟：

①初始化，根據符號概率的大小按由大到小順序對符號進行排序4.1仙農-范諾與霍夫曼編碼②把概率最小的兩個符號組成一個節(jié)點，如P1。

③重復步驟2，得到節(jié)點P2、P3和P4，形成一棵“樹”。④從根節(jié)點P4開始到相應于每個符號的“樹葉”，從上到下標上“0”(上枝)或者“1”(下枝)

。⑤從根節(jié)點P4開始順著樹枝到每個葉子分別寫出每個符號的代碼。

P1P2P3P40101100101001011101114.1仙農-范諾與霍夫曼編碼

⑥按照仙農理論，這幅圖像的熵為

H(S)=(15/39)

log2(39/15)+(7/39)

log2(39/7)+

+(5/39)

log2(39/5)=2.1859

壓縮比1.37:1

Huffman編碼需要各種代碼意義的“詞典”，即碼簿，那么就可以根據碼簿一個碼一個碼地依次進行譯碼。4.1仙農-范諾與霍夫曼編碼編碼原理——對出現頻率高的信源編碼長度短，而對出現頻率低的信源編碼長度長。其編碼步驟如下：

[1]信號源的數據按照出現概率遞減的順序排列

[2]合并兩個最小出現概率，作為新數據出現概率

[3]重復進行[1][2]，直至概率相加為1為止

[4]合并運算時，概率大者取0，概率小者取1(或相反）

[5]記錄概率為1處到各信號源的0、1序列，則得到相應的Huffman編碼。4.1仙農-范諾與霍夫曼編碼

編碼特點

[1]編碼長度可變，壓縮與解壓縮較慢

[2]硬件實現困難

[3]編碼效率取決于信號源的數據出現概率

[4]霍夫曼碼沒有錯誤保護功能，在譯碼時，如果碼串中沒有錯誤，那么就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，哪怕僅僅是1位出現錯誤，不但這個碼本身譯錯，更糟糕的是一錯一大串，全亂了套，這種現象稱為錯誤傳播(errorpropagation)4.2算術編碼

算術編碼把一個信源集合表示為實數線上的0到1之間的一個區(qū)間。這個集合中的每個元素都要用來縮短這個區(qū)間。信源集合的元素越多，所得到的區(qū)間就越小，當區(qū)間變小時，就需要一些更多的數位來表示這個區(qū)間，這就是區(qū)間作為代碼的原理。算術編碼首先假設一個信源的概率模型，然后用這些概率來縮小表示信源集的區(qū)間。消息的編碼輸出可以是最后一個間隔中的任意數。

4.2算術編碼[例4.2]假設信源符號為{00,01,10,11}，這些符號的概率分別為{0.1,0.4,0.2,0.3}，根據這些概率可把間隔[0,1)分成4個子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1)，其中表示半開放間隔，即包含不包含。上面的信息可綜合在表中。符號00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)4.2算術編碼現對輸入的二進制消息序列10001100101101進行編碼。新子區(qū)間的起始位置＝ 前子區(qū)間的起始位置＋ 當前符號的區(qū)間左端×前子區(qū)間長度新子區(qū)間的長度＝ 前子區(qū)間的長度×

當前符號的概率（等價于范圍長度）算術編碼過程舉例

4.2算術編碼4.2算術編碼步驟間隔譯碼符號譯碼判決1[0.5,0.7)100.51439在間隔[0.5,0.7)2[0.5,0.52)000.51439在上一間隔的第1個1/10

3[0.514,0.52)110.51439在上一間隔的第7個1/104[0.514,0.5146)000.51439在上一間隔的第1個1/10

5[0.5143,0.51442)100.51439在上一間隔的第5個1/106[0.514384,0.51442)110.51439在上一間隔的第7個1/107[0.5143876,0.5144402)010.51439在上一間隔的第2個1/104.2算術編碼編碼過程：考慮一個有M個符號的字符表集ai=(1,2,…,M)，假設概率p(ai)=pi，而。輸入符號用xn

=ai表示，第n個子間隔的范圍用表示。其中l(wèi)0=0，d0=1和p0=0，ln表示間隔左邊界的值,rn表示間隔右邊界的值，dn=rn-ln表示間隔長度。編碼步驟如下：4.2算術編碼步驟1：首先在1和0之間給每個符號分配一個初始子間隔，子間隔的長度等于它的概率，初始子間隔的范圍用I1=[l1,r1)=[,)表示。令d1=r1-l1，L=l1和R=r1

。步驟2：L和R的二進制表達式分別表示為： 和

其中uk和vk等于“1”或者“0”。4.2算術編碼比較u1和v1：①如果u1≠v1，不發(fā)送任何數據，轉到步驟3；②如果u1=v1

，就發(fā)送二進制符號u1。比較u2和v2：①如果u2≠v2

，不發(fā)送任何數據，轉到步驟3；②如果u2=v2

，就發(fā)送二進制符號u2?！@種比較一直進行到兩個符號不相同為止，然后進入步驟3，

4.2算術編碼步驟3：n加1，讀下一個符號。假設第n個輸入符號為xn=ai，按照以前的步驟把這個間隔分成如下所示的子間隔：

令dn=rn-ln，L=ln和R=rn

，然后轉到步驟2。4.2算術編碼發(fā)送1算術編碼概念

發(fā)送0發(fā)送011例：對序列a2,a1,a3編碼過程：4.2算術編碼接受的數字間隔譯碼輸出1[0.5,1)-0[0.5,0.75)0[0.5,0.625)1[0.5625,0.625)-1[0.59375,0.609375)………a2a1a3譯碼過程4.2算術編碼在算術編碼中需要注意的幾個問題：

①由于實際的計算機的精度不可能無限長，運算中出現溢出是一個明顯的問題，但多數機器都有16位、32位或者64位的精度，因此這個問題可使用比例縮放方法解決。

②算術編碼器對整個消息只產生一個碼字，這個碼字是在間隔[0,1)中的一個實數，因此譯碼器在接受到表示這個實數的所有位之前不能進行譯碼。

③算術編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導致整個消息譯錯。4.2算術編碼算術編碼可以是靜態(tài)的或者自適應的。在靜態(tài)算術編碼中，信源符號的概率是固定的。在自適應算術編碼中，信源符號的概率根據編碼時符號出現的頻繁程度動態(tài)地進行修改，在編碼期間估算信源符號概率的過程叫做建模。

現實中有許多這樣的圖像，在一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續(xù)的像素都具有相同的顏色值。在這種情況下就不需要存儲每一個像素的顏色值，而僅僅存儲一個像素的顏色值，以及具有相同顏色的像素數目就可以，或者存儲一個像素的顏色值，以及具有相同顏色值的行數。這種壓縮編碼稱為行程編碼(runlengthencoding，RLE)，具有相同顏色并且是連續(xù)的像素數目稱為行程長度。

4.3RLE編碼

例如對下面一行圖像數據：用RLE編碼方法得到的代碼為：80315084180。代碼中用黑體表示的數字是行程長度，黑體字后面的數字代表像素的顏色值。

4.3RLE編碼4.3RLE編碼

RLE是一種無損壓縮技術。尤其適用于計算機生成的圖像，對減少圖像文件的存儲空間非常有效。然而，RLE對顏色豐富的自然圖像就顯得力不從心。4.4詞典編碼

一、詞典編碼的思想

詞典編碼(dictionaryencoding)的根據是數據本身包含有重復代碼這個特性。它可分為兩類：

4.4詞典編碼第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數據中出現過，然后用已經出現過的字符串替代重復的部分，它的輸出僅僅是指向早期出現過的字符串的“指針”?！霸~典”是指用以前處理過的數據來表示編碼過程中遇到的重復部分。如LZ77和LZSS算法。

4.4詞典編碼第二類算法的想法是企圖從輸入的數據中創(chuàng)建一個“短語詞典(dictionaryofthephrases)”，短語可以是任意字符的組合。編碼數據過程中當遇到已經在詞典中出現的“短語”時，編碼器就輸出這個詞典中的短語的“索引號”，而不是短語本身。如LZW壓縮編碼。

4.4詞典編碼二、LZ77算法

算法中用到的幾個術語：

(1)輸入數據流(inputstream)：要被壓縮的字符序列。

(2)字符(character)：輸入數據流中的基本單元。

(3)編碼位置(codingposition)：輸入數據流中當前要編碼的字符位置，指前向緩沖存儲器中的開始字符。

(4)前向緩沖存儲器(Lookaheadbuffer)：存放從編碼位置到輸入數據流結束的字符序列的存儲器。

4.4詞典編碼(5)窗口(window)：指包含W個字符的窗口，字符是從編碼位置開始向后數也就是最后處理的字符數。

(6)指針(pointer)：指向窗口中的匹配串且含長度的指針。

4.4詞典編碼LZ77編碼算法的核心是查找從前向緩沖存儲器開始的最長的匹配串。編碼算法的具體執(zhí)行步驟如下：(1)把編碼位置設置到輸入數據流的開始位置。(2)查找窗口中最長的匹配串。(3)以“(Pointer,Length)Characters”的格式輸出，其中Pointer是指向窗口中匹配串的指針，Length表示匹配字符的長度，Characters是前向緩沖存儲器中的不匹配的第1個字符。(4)如果前向緩沖存儲器不是空的，則把編碼位置和窗口向前移(Length+1)個字符，然后返回到步驟2。4.4詞典編碼

位置123456789字符AABCBBABC步驟位置匹配串字符輸出11--A(0,0)A22AB(1,1)B34--C(0,0)C45BB(2,1)B57ABC(5,2)C4.4詞典編碼三、LZSS算法

LZSS算法的思想是如果匹配串的長度比指針本身的長度長就輸出指針，否則就輸出真實字符。由于輸出的壓縮數據流中包含有指針和字符本身，為了區(qū)分它們就需要有額外的標志位，即ID位。4.4詞典編碼LZSS編碼算法的具體執(zhí)行步驟如下：(1)把編碼位置置于輸入數據流的開始位置。(2)在前向緩沖存儲器中查找與窗口中最長的匹配串

①Pointer

：=匹配串指針。

②Length：=匹配串長度。(3)判斷匹配串長度Length是否大于等于最小匹配串長度(Length

MIN_LENGTH)，

如果“是”：輸出指針，然后把編碼位置向前移動Length個字符。

如果“否”：輸出前向緩沖存儲器中的第1個字符，然后把編碼位置向前移動一個字符。(4)如果前向緩沖存儲器不是空的，就返回到步驟2。4.4詞典編碼步驟位置匹配串輸出11--A22AA33--B44BB55--C66BB(3,2)78AAB(7,3)811CC位置123456789字符AABBCBBAABC10114.4詞典編碼四、LZ78算法

(1)字符流(Charstream)：要被編碼的數據序列。

(2)字符(Character)：字符流中的基本數據單元。

(3)前綴(Prefix)：在一個字符之前的字符序列。(4)綴?符串(String)：前綴＋字符。(5)碼字(Codeword)：碼字流中的基本數據單元，代表詞典中的一串字符。(6)碼字流(Codestream)：碼字和字符組成的序列，是編碼器的輸出。4.4詞典編碼(7)詞典(Dictionary)：綴-符串表。按照詞典中的索引號對每條綴?符串(String)指定一個碼字(Codeword)。

(8)當前前綴(Currentprefix)：在編碼算法中使用，指當前正在處理的前綴，用符號P表示。

(9)當前字符(Currentcharacter)：在編碼算法中使用，指當前前綴之后的字符，用符號C表示。(10)當前碼字(Currentcodeword)：在譯碼算法中使用，指當前處理的碼字，用W表示當前碼字，String.W表示當前碼字的綴?符串。4.4詞典編碼1、編碼算法

LZ78的編碼思想是不斷地從字符流中提取新的綴?符串(String)，通俗地理解為新“詞條”，然后用“代號”也就是碼字(Codeword)表示這個“詞條”。這樣一來，對字符流的編碼就變成了用碼字(Codeword)去替換字符流(Charstream)，生成碼字流(Codestream)，從而達到壓縮數據的目的。4.4詞典編碼步驟1：在開始時，詞典和當前前綴P都是空的。步驟2：當前字符C：=字符流中的下一個字符。步驟3：判斷P+C是否在詞典中：

(1)如果“是”：用C擴展P，讓P：=P+C；

(2)如果“否”：

①輸出與當前前綴P相對應的碼字和當前字符C；

②把字符串P+C添加到詞典中。

③令P：=空值。

(3)判斷字符流中是否還有字符需要編碼

①如果“是”：返回到步驟2。

②如果“否”：若當前前綴P不是空的，輸出相應于當前前綴P的碼字，然后結束編碼。

2、譯碼算法

具體算法如下：步驟1：在開始時詞典是空的。步驟2：當前碼字W：=碼字流中的下一個碼字。步驟3：當前字符C：=緊隨碼字之后的字符。步驟4：把當前碼字的綴?符串(string.W)輸出到字符流(Charstream)，然后輸出字符C。步驟5：把string.W+C添加到詞典中。步驟6：判斷碼字流中是否還有碼字要譯

(1)如果“是”，就返回到步驟2。

(2)如果“否”，則結束。4.4詞典編碼4.4詞典編碼位置123456789字符ABBCBCABA步驟位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)4.4詞典編碼五、LZW算法

在LZW算法中使用的術語與LZ78使用的相同，僅增加了一個術語—前綴根(Root)，它是由單個字符串組成的綴?符串(String)。在編碼原理上，LZW與LZ78相比有如下差別：①開始時詞典不能是空的，它必須包含可能在字符流出現中的所有單個字符，即前綴根(Root)。②每個編碼步驟開始時都使用一字符前綴(one-characterprefix)，因此在詞典中搜索的第1個綴?符串有兩個字符。

4.4詞典編碼1、編碼算法碼字(Codeword)前綴(Prefix)1

……193A194B……255

……1305abcdefxyF01234……詞典

4.4詞典編碼LZW編碼算法步驟步驟1：開始時的詞典包含所有可能的根(Root)，而當前前綴P為字符流中的第一個字符；

步驟2：當前字符(C)：=字符流中的下一個字符；

步驟3：判斷綴?符串P+C是否在詞典中

(1)如果“是”：P：=P+C //(用C擴展P)；

(2)如果“否”

①把代表當前前綴P的碼字輸出到碼字流;

②把綴?符串P+C添加到詞典;

③令P：=C//(現在的P僅包含一個字符C);

4.4詞典編碼步驟4：判斷字符流中是否還有字符要編碼

(1)如果“是”，就返回到步驟2；

(2)如果“否”

①把代表當前前綴P的碼字輸出到碼字流;

②結束。

4.4詞典編碼2、譯碼算法

LZW譯碼算法中還用到另外兩個術語：①當前碼字(Currentcodeword)：指當前正在處理的碼字，用cW表示，用string.cW表示當前綴?符串；②先前碼字(Previouscode