無(wú)損數(shù)據(jù)壓縮.ppt

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

1、第四章無(wú)損數(shù)據(jù)壓縮方式：無(wú)損有損無(wú)損，losslesscompression,redundancyreduction壓縮后的數(shù)據(jù)能夠完全恢復(fù)，如磁盤上的數(shù)據(jù)文件，壓縮后是原來(lái)的1/2—1/4算法有：Huffman,RLE,算術(shù)編碼，詞典編碼有損：lossy,不可逆壓縮。聲音、圖像中的變換編碼，例如，DPCM(圖3-14）由于存在量化器4.1Shannon的信息論與數(shù)據(jù)壓縮1.Astory：Europe，Albert,patentauditor主要申請(qǐng)：任意英文文件，壓縮到10個(gè)字母一個(gè)bit。Claude:破壞了信息論的數(shù)據(jù)壓縮理論極限。1

2、948年Shannon創(chuàng)立的信息論：數(shù)據(jù)壓縮理論極限。數(shù)據(jù)壓縮的技術(shù)途徑。壓縮原理：信源中信息分布不均勻；信源中信息含有冗余（相關(guān)性）2.信息熵entropy問(wèn)題：隨機(jī)變量的一個(gè)取值a，攜帶的信息量是多少？相關(guān)概念：消息：數(shù)據(jù)、電報(bào)、電話。信息：對(duì)信息加工，有特定價(jià)值一個(gè)信息帶有一定的信息量，大小不等例子一個(gè)消息：某試驗(yàn)成功試驗(yàn)人員預(yù)計(jì)成功的可能性99%：信息量很小試驗(yàn)人員預(yù)計(jì)成功的可能性1%：信息量很大3.信息量答案：在收到信息以前，處于某種不確定狀態(tài)中，收到信息之后，消除或部分消除了此不確定性。消除不確定性多少，就可以作為信息的度量。4

3、.Shannon用概率說(shuō)明這一概念事件出現(xiàn)的概率小，相當(dāng)于不確定性多，反之，則少。P為事件的概率，對(duì)應(yīng)的不確定性為h(p)=-logp5.信息熵（Entrop）表示每出現(xiàn)一個(gè)字符所給出的平均信息量。6.信息熵的理解：處于事件發(fā)生之前，根據(jù)先驗(yàn)概率Pj,就有不同的確定性存在，h(Pj)與H(x)都是不確定性度量。當(dāng)處于事件發(fā)生之時(shí)，是一種驚奇性的度量但出于事件發(fā)生之后，不確定性已被解除，則是獲得信息的度量可以認(rèn)為是事件隨機(jī)性的度量，因其僅僅對(duì)概率Pj取另個(gè)坐標(biāo)而已。7.H(x)就是對(duì)離散信源進(jìn)行無(wú)失真編碼時(shí)的碼長(zhǎng)極限。8.舉例信源取4個(gè)符號(hào)a

4、1,a2,a3,a4,概率1/2，1/4，1/8，1/8信源的熵H(x)=…=1.75bit/字符若用編碼(0,10,110,111),則平均碼長(zhǎng)=…=1.75考慮以下幾種變長(zhǎng)編碼：碼Ｂ唯一可譯例1：例4.1例2：8個(gè)字符具有等可能性例3：字符的分布已知：P=(0.9,0.02,0.02,0.02,0.01,0.01,0.01,0.01)H(p)=0.74bit/字符信源字母概率碼A碼B碼Ca1１／２０００a2１／４１１０１０a3１／８１１１１０１０１a4１／８１１１１１１１１１４.2算術(shù)編碼提出Rissanen1976年提出。在JPEG與

5、JBIG（Bi-levelimage)中都有算術(shù)編碼的內(nèi)容。2.思想把信源符號(hào)構(gòu)成的串S,唯一地映射到實(shí)數(shù)軸上（0，1）之間的一個(gè)實(shí)數(shù)。前提：知道信源每個(gè)符號(hào)的概率。3.舉例假設(shè)信源由四個(gè)符號(hào){a1,a2,a3,a4}組成，這些符號(hào)的概率分別是（0.1,0.4,0.2,0.3).a1,a2,a3,a4四個(gè)符號(hào)的二進(jìn)制編碼分別為00，01，10，11符號(hào)序列S=a3a1a4a1a3a4a2的二進(jìn)制序列為10001100101101編碼：把S映射到（0，1）之間的實(shí)數(shù)的過(guò)程,見(jiàn)圖4-3譯碼:見(jiàn)教案。4.3RLE編碼RLE原理：圖像（靜止圖像）的

6、相鄰像素相關(guān)性（灰度、彩色）。用二元組（行程，灰度或彩色值）表示。2.舉例圖4-53.不足：隨機(jī)的圖像，平均碼長(zhǎng)增加。4.4詞典編碼思想Huffman編碼：符號(hào)的概率已知，概率大的符號(hào)分配較短的碼字。而實(shí)際上不太現(xiàn)實(shí)。將長(zhǎng)度不同的符號(hào)串（短語(yǔ)）編碼成一個(gè)個(gè)新的單詞。每個(gè)符號(hào)串分配一個(gè)編碼。編碼等長(zhǎng)（如12位二進(jìn)制）。2.提出：以色列J.Ziv與A.Lempel,LZ77,LZ78,1984,T.A.Welch提出LZW,在Unix中應(yīng)用。詞典編碼舉例LZ78編碼思想：不斷從字符流中形成新的綴—符串，綴—符串作為新的詞條存入字典中，并給該詞條

7、分配一個(gè)碼字。對(duì)字符流的編碼就用“(綴的編碼,符)”表示，實(shí)現(xiàn)壓縮。舉例：表4-13,字符流為：ABBCBCABALZ78編碼舉例字符流詞典與碼字流（輸出）位置字符1A2B3B4C5B6C7A8B9A序號(hào)位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)問(wèn)題為什么不直接輸出詞條的序號(hào)？LZ78算法術(shù)語(yǔ)字符流字符碼字流碼字前綴綴—符串詞典：綴—符串、碼字構(gòu)成的對(duì)應(yīng)表編碼算法譯碼算法2.LZW與LZ78相比，有如下特點(diǎn)所有可能出現(xiàn)的字符都事先放在字典中。輸出的碼字流中僅由詞典中的碼字組成。編碼算

8、法例4.7譯碼算法p59