【文章內(nèi)容簡介】 22=∈[，1） 第三個符號為d；去掉累積概率Pd： =0放大至[0，1)(Pd1)：0 24=0∈[0,) 第四個符號為a。算術(shù)編碼從性能上看具有許多優(yōu)點，特別是由于所需的參數(shù)很少，不象哈夫曼那樣需要一個很大的碼表，常設(shè)計成自適應(yīng)算術(shù)編碼來針對一些信源概率未知或非平穩(wěn)情況。但是在實際實現(xiàn)時還有一些問題，如計算復(fù)雜性，計算的精度以及存儲量等，隨著這些問題的解決，算術(shù)編碼正在進(jìn)入實用階段，但要擴(kuò)大應(yīng)用范圍或進(jìn)一步提高性能，降低造價，還需進(jìn)一步改進(jìn)。這就是我們下有章要介紹到的算術(shù)編碼的改進(jìn)。第3章 哈夫曼碼和算術(shù)碼的改進(jìn)優(yōu)化上一章所講到的各種編碼算法中,實用性較強(qiáng)的一般是算術(shù)碼和哈夫曼碼,但是在實際實現(xiàn)時也還是存在一些問題,如計算復(fù)雜性,計算的精度以及存儲量等,因而,這兩種編碼方法還有待我們進(jìn)一步去改進(jìn)和優(yōu)化。1. 基本概念（1）圖像熵設(shè)圖像灰度級序列a 1, a2，…a n出現(xiàn)的概率集合為P 1,p2，…，p n，定義圖像熵H為 （311）（2）平均碼字長度設(shè)有n個圖像灰度級(k =1, 2，…,n), (k = 1, 2，…，n)為第k個圖像灰度級的編碼長度其相應(yīng)出現(xiàn)的概率為(k= 1, 2，…,n)，則該n個圖像灰度級序列的編碼長度為 （312）（3）平均偏離方差設(shè)圖像灰度級序列(k =1, 2，…,n), 其相應(yīng)出現(xiàn)的概率為,(k= 1, 2，…,n),(k = 1, 2，…，n)為第k個圖像灰度級的編碼長度, 該組灰度級序列的平均碼長為R, 定義該組灰度級序列的平均偏離方差為 （313） 先按出現(xiàn)的概率大小排隊，把2個最小的概率相加，再重新排隊，“0”和“1”賦以相加的2個概率，讀出時由該符號開始一直到最后的1，將路線上遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號的Huffman編碼。例1設(shè)有7個圖像灰度級序列，按出現(xiàn)概率的大小順序進(jìn)行排序(見表311)，其編碼見圖（31）表31 7個圖象灰度的出現(xiàn)概率灰度等級概率灰度等級概率a1 a5 a2 a6 a3 a7 a4 圖31 表（31）的編碼表1編碼的平均碼長R= 2+ 2+ 3+0. 173 +4+4+4= bit.相應(yīng)的圖像熵為H=－(++++++)=++++++=性質(zhì)1 在Huffman編碼中，平均碼字長度等于其內(nèi)部結(jié)點值的和。由性質(zhì)1易得性質(zhì)2。性質(zhì)2 同一組灰度級序列的多種的平均碼長相等。3．Huffman編碼的不唯一性因為Huffman編碼的步驟是任取的，因此編碼不唯一。 例2．設(shè)有8個圖像灰度級序列，按出現(xiàn)概率的大小進(jìn)行排序(見表312)。對于該組圖像灰度級序列，下面給出3種不同的H uffman編碼，由于其圖像熵只與圖像灰度級序列出現(xiàn)的概率有關(guān)，因此這3種編碼的圖像熵皆為H=－(+++++++)=+++++++=編碼方案1見圖（32）。表32 8個圖像灰度級的出現(xiàn)概率灰度等級概率灰度等級概率a1 a5 a2 a6 a3 a7 a4 a8 圖32 表2的編碼1 編碼方案1的平均碼長R = 1+3+3+ 3+5+ 53= bit.依次類推，編碼方案2的平碼長R= 1+ 3+ 3+ 4+ 4+ 4+ 5 2= 2. 38 hit。4．對Huffman編碼的討論由以上計算可知，表2的編碼方案的圖像熵和平均碼長均相同，現(xiàn)計算它們的平均偏離方差。編碼1：D=（）2+()22+()2+()2+()23=編碼2: D=（）2+()22+()2+()2+()22=由計算結(jié)果可知，選擇不同的編碼方案，所得到的平均偏離方差不同。當(dāng)圖像灰度級出現(xiàn)的概率集合固定時，平均偏離方差卞要取決于由Huffman的構(gòu)造過程中葉結(jié)點到根結(jié)點的路徑長度，從而得出定理1。定理1在H uffm an編碼過程中，當(dāng)出現(xiàn)2個以上最小概率的結(jié)點時，若選擇樹中葉結(jié)點概率為最小者與葉結(jié)點概率為最大者進(jìn)行合并，則得到相應(yīng)編碼的平均偏離方差為最小。5．Huffman編碼算法的優(yōu)化 1) 先將各信源符號出現(xiàn)的概率由大到小排列；2) 按定理中的方法將最小的2個概率相加，形成1個新的概率集合，再按1)方法重排，如此反復(fù)進(jìn)行直到只有2個概率為止； 3) 分配碼字。哈夫曼(huffman)樹，又稱最優(yōu)樹，是帶權(quán)路徑長度最小的二叉樹。樹的帶權(quán)路徑長度是樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記，其中n為葉子結(jié)點數(shù)目，為第i個葉子結(jié)點的權(quán)值，為第i個葉子結(jié)點的路徑長度。根據(jù)這個定義，求取哈夫曼樹的帶權(quán)路徑長度(WPL) 必須獲取各個葉子結(jié)點的權(quán)值和所處路徑長度。通過對哈夫曼算法的研究，提出一種求取哈夫曼樹WPL的改進(jìn)方法。 求WPL的改進(jìn)方法由于以下條件成立:(1) 葉子結(jié)點i的帶權(quán)路徑長度 ，即w1連續(xù)相加次。(2) 構(gòu)造哈夫曼樹過程中，選取權(quán)值最小的結(jié)點作為左右子樹構(gòu)造一棵新的二叉樹，且新置的二叉樹的根結(jié)點權(quán)伯為其左右子樹上根結(jié)點的權(quán)值之和。 新置結(jié)點的產(chǎn)生，葉子結(jié)點的權(quán)值被累計相加到這結(jié)點的權(quán)值中，等價于葉子結(jié)點的權(quán)值被相乘了相應(yīng)次數(shù)。所以得到改進(jìn)求取WPL的方法為：相加所有新置結(jié)點的權(quán)值即為該哈夫曼樹的WPL。例如3:v,e,r,y,g,o,a,d在某個文件中出現(xiàn)的次數(shù)分別為5,29,7,8,，對這8個結(jié)點構(gòu)造哈夫曼樹，得到結(jié)果如圖（33）所示，生成哈夫曼樹的狀態(tài)圖如圖（34）所示。傳統(tǒng)求解WPL的方法為：根據(jù)圖（33）求葉子結(jié)點的路徑長度 WPL=（3+5+7+8）4+（11+14）3+（23+29）2 =234+253+522 =92+75+104 =271改進(jìn)后的求解WPL方法為:將圖（34）中編號為9到15的權(quán)信相加 WPL=8+15+29+42+58+100=271 兩種方法求取結(jié)果完全一致，但改進(jìn)后的方法省略求葉子結(jié)點路徑長度，從而節(jié)省時間，同時，第一種方法只需要簡的一的相加運(yùn)算，減少了乘法運(yùn)算，有效提高了求取哈夫曼樹WPL的效率和正確性。編號權(quán)值 1 5 2 29 3 7 4 8 5 14 6 23 7 3 8 11 9 8 10 15 11 19 12 29 13 42 14 58 15 100 圖33 哈夫曼樹 圖34 生成哈夫曼樹后狀態(tài)6．結(jié)束語 改進(jìn)后的求WPL方法更加簡單，快速，極大地減少了出錯機(jī)率。哈夫曼算法有效地實現(xiàn)了數(shù)據(jù)壓縮，但在很多壓縮工具中常與其他壓縮算法合用來更大空間地提高壓縮比例。哈夫曼算法除在數(shù)據(jù)壓縮方而被廣泛應(yīng)用外。在許多實際場合中也常被使用。1．算術(shù)編碼的性質(zhì)分析 首先抄錄Rissanen和Langdon的部分結(jié)果，包括算術(shù)編碼迭代關(guān)系的表示、解碼規(guī)則以及可解碼性的充分條件，之后討論算術(shù)編碼的分析性質(zhì)。輸入符號串λ字母表記為S = (0,1, ,d－1)，s后跟符號k(k∈S)構(gòu)成符號串sk，空串記為又，算術(shù)編碼的迭代關(guān)系表示為: (321) 其中，B(sk)稱為augend， (322) A (si)稱為addends，不失一般性，取。 解碼規(guī)則 s可以寫為s= s39。ks，如果滿足： 可解碼性的充分條件 如果對任何s都有 (323)可解碼性的充分條件是容易滿足的，通常取 (324) 即可，其中是符號i的概率。我們有下面定理.定理1(算術(shù)編碼的區(qū)間套性質(zhì)) 對任何s和k, ，有下式成立： (328)并且， （329） 定理2 (算術(shù)編碼的區(qū)間套性質(zhì))} 構(gòu)成一閉區(qū)間套，即隨的增加單調(diào)下降 （3211） 并且，當(dāng)趨于無窮時，的長度趨于0。定理3 (算術(shù)編碼的收斂性) 當(dāng)增加時，C(s)單調(diào)上升并有界，C39。(s)單調(diào)下降并有界，C(s)和C39。 (s)收斂到共同的極限 （3212）記~S，稱為字符集S張成的字符串空間。 對于使用有限精度計算的實際應(yīng)用來說，不能直接對數(shù)C(s)和A(s)進(jìn)行迭代計算，因而不同于式(311)(312)，算術(shù)編碼的計算格式為 （3213） （3214） 其中，C,A是兩個有限位數(shù)的寄存器，不失一般性，仍將其記為p(k),0 p(k)1,P(k)是累積概率。 （3215）我們定義操作符，稱作直接和將作用于輸出的二進(jìn)制小數(shù)C(s)，得到輸出比特數(shù)的計數(shù)，記為。對二進(jìn)制小數(shù)x,x不含進(jìn)位時，記為i,其中xi是0或1，記號︱x︱做類似的理解。定義 (C(s)+i) ,并且 （3216）x有一個進(jìn)位時，進(jìn)位不記入︱x︱，記為i , 定義： (C(s)+i), 并且 （3217）當(dāng)然，進(jìn)位為0時，式（3117）蘊(yùn)涵式（3116）。推廣至一般的x，x =……x小數(shù)點左邊的位數(shù)不計入︱x︱，有2(C(s)+i) , 并且 （3218）3．位陷阱技術(shù)(陷阱位和trap_n)陷阱位是輸出碼流中最近的一個值為。的比特，SetTra p為真表示陷阱位存在，trap_n表示輸出碼流中位于陷阱位之后的比特數(shù)，這些比特的值必全是1，當(dāng)然trap_n可以為零。使用SetTrap和trap_n后，Cs)不一定是對s的完整的編碼輸出，s的完整的編碼輸出是虛擬的，記為Ctotal(s)，有 　　　　　　　　 （3219）① 進(jìn)位陷阱技術(shù) 進(jìn)位陷阱技術(shù)包括三部分內(nèi)容:進(jìn)位陷阱的初始化、C的進(jìn)位處理、C的移位處理。 初始化：置布爾型變量SetTra p為假，整型變量trap_n清零.進(jìn)位處理：1）2) 如果trap_n0，則 (小數(shù)點后有((trap_n一1)個0,trap_n清零，退出進(jìn)位處理。3) 如果trap_n =0，則置SetTrap為假，退出進(jìn)位處理。移位處理：1) 如果C≥ a，則置OutBit=1,并且C=C－a 否則，置OutBit=0 。2) 如果SetTra p真，并且OutBit=1，則trap_n=trap_n+1，退出移位處理.3) 如果SetTra p真，并且OutBit=0，則C(s)=C(s)…1(0后面有trap_n個1), 則trap_n清零，退出移位處理.4) 如果SetT ra p假，并且OutBit=1，則C(s)=C(s)0. 1退出移位處理。5) 如果SetTra p假，并且OutBit=，則置SetTra p為真，退出移位處理。②正確性證明進(jìn)位陷阱技術(shù)的正確性要求包括兩個內(nèi)容，一是要能正確地將C的進(jìn)位加到C(s)上，二是要能正確地將C的移位加到C(s)上。 SetTrap為真時若出現(xiàn)進(jìn)位，則進(jìn)位陷阱技術(shù)實現(xiàn)了C(s) = C(s)0. 100…0, 1后面有(trap_n－1)個0，則無法留下陷阱位，故將SetTrap置為假。這是進(jìn)位的正確結(jié)果。因而有下列定理。 定理1 當(dāng)SetTrap為真時，進(jìn)位陷阱技術(shù)總可以正確地進(jìn)位。 定理2 當(dāng)有進(jìn)位時，SetTra p必為真。 證明. 陷阱位是最近的一個值為0的比特，只在兩種情況下SetTra p為假，一是從未輸出過0，二是tra p_ n為零時，陷阱位接受一個進(jìn)位后，被置為假。 在第一種情況下，C(s)的各位全是1，即取為最大值C(s) = 0. 11…1，若出現(xiàn)進(jìn)位，會使C(s)≥, 算術(shù)編碼的區(qū)間套性質(zhì)知，這是不可能的。 下面證明，若出現(xiàn)第二種情況，則直到獲得下一個陷阱位之前，不會出現(xiàn)進(jìn)位。設(shè)串s的編碼完成時，SetTra p為真，trap_n為零，有