常用的無損數(shù)據(jù)壓縮方法.ppt

《常用的無損數(shù)據(jù)壓縮方法.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、6.3常用的無損數(shù)據(jù)壓縮方法6.3.1Huffman編碼6.3.2算術(shù)編碼6.3.3行程RLE編碼6.3.4詞典編碼2021/8/316.3.1Huffman編碼基本原理依據(jù)信源字符出現(xiàn)的概率大小來構(gòu)造代碼，對出現(xiàn)概率較大的信源字符，給予較短碼長，而對于出現(xiàn)概率較小的信源字符，給予較長的碼長，最后使得編碼的平均碼字最短。2021/8/326.3.1Huffman編碼具體的編碼步驟將信源出現(xiàn)的概率由大到小排序。將兩處最小概率組合相加，形成新概率。將新概率與未編碼的字符一起重新排序。重復(fù)步驟2、3，直到出現(xiàn)的概率和為1。分

2、配代碼代碼分配從最后一步開始反向進行，對最后兩個概率一個賦予0代碼，一個賦予1代碼。記錄下從樹的根到每個信源符號終節(jié)點的0和1序列。至于哪個為“1”哪個為“0”則無關(guān)緊要，最后的結(jié)果僅僅是分配的代碼不同，而代碼的平均長度是相同的。2021/8/336.3.1Huffman編碼Huffman編碼中求平均碼長的方法：概率×碼長2021/8/346.3.1Huffman編碼Huffman編碼練習(xí)一:設(shè)輸入圖像的灰度級{a1,a2,a3,a4,a5,a6}出現(xiàn)的概率分別是0.4、0.2、0.12、0.15、0.1、0.03。試

3、進行哈夫曼編碼，并計算平均碼字長度。2021/8/35Huffman編碼練習(xí)一答案最終編碼結(jié)果為：a1=1,a2=011,a3=001,a4=010,a5=0001,a6=000010100102021/8/36Huffman編碼練習(xí)一答案據(jù)公式　　　　　　　　圖像信源熵為：H(X)=-(0.4×log20.4+0.2×log20.2+0.12×log20.12+0.15×log20.15+0.1×log20.1+0.03×log20.03)=2.25bit根據(jù)哈夫曼編碼結(jié)果，平均碼字長度：Lc=0.4×1+0.2×3

4、+0.15×3+0.12×3+0.1×4+0.03×4=2.33編碼效率、壓縮比和冗余度分別為：96.6%、1.2、3.4%r=1-η=3.4%2021/8/376.3.1Huffman編碼Huffman編碼注意事項哈夫曼編碼沒有錯誤保護功能，在譯碼時，如果碼串中沒有錯誤，那么就能一個接一個的正確譯出代碼。但如果碼串中有錯誤，哪怕僅是1位出現(xiàn)錯誤，不但這個碼本身譯錯，后面的譯碼可能全錯，這種現(xiàn)象稱為錯誤傳播（ErrorPropagation）。哈夫曼編碼是可變長度碼，很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這

5、就需要在存儲代碼之前加以考慮。2021/8/386.3.2算術(shù)編碼算術(shù)編碼（arithmeticcodingAC）是利用0和1之間的間隔來表示信源編碼的一種方法，其編碼值是間隔的上、下限包含的相同二進制。編碼過程中的間隔決定了符號壓縮后的輸出。算術(shù)編碼用到兩個基本的參數(shù)符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在0到1之間。2021/8/396.3.2算術(shù)編碼編碼過程:設(shè)信源符號為{A,B,C,D}，其概率分別為{0.1,0.4,0.2,0.3}，按概率可

6、把間隔[0,1]分成4個子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1]，其中[x,y)表示半開放間隔，即包含x不包含y，如下表所示。符號ABCD概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]2021/8/3106.3.2算術(shù)編碼如果消息序列的輸入為：CADACDB，其編碼過程如下：首先輸入的符號是C，找到它的編碼范圍是[0.5,0.7)；由于消息中第2個符號A的編碼范圍是[0,0.1)，因此它的間隔就取[0.5,0.7)的第一個1

7、/10作為新間隔[0.5,0.52)；編碼第3個符號D時取新間隔為[0.514,0.52)；編碼第4個符號A時，取新間隔為[0.514,0.5146)，…。2021/8/3116.3.2算術(shù)編碼符號ABCD概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]2021/8/3126.3.2算術(shù)編碼消息的編碼輸出可以是最后一個間隔中的任意數(shù)，整個編碼過程如下圖所示。最后在[0.5143876,0.514402)中選擇一個數(shù)作為編碼輸出值：0.51439。解碼時，解碼器由編

8、碼輸出值：0.51439，可馬上解得一個字符為C，然后依次得到唯一解A,D,A,C,D,B。2021/8/3136.3.2算術(shù)編碼步驟譯碼間隔譯碼10.51439在間隔[0.5,0.7)1020.51439在間隔[0.5,0.7)的第1個1/100030.51439在間隔[0.5,0.52)的第7個1/101140.51439在間