信息論與編碼之?dāng)?shù)據(jù)壓縮課件

信息論與數(shù)據(jù)壓縮班級(jí)姓名信息論與數(shù)據(jù)壓縮班級(jí)姓名1數(shù)據(jù)壓縮的含義與簡(jiǎn)介01理論與應(yīng)用03類型與流行算法04算法編碼05內(nèi)容大綱概要與原理02數(shù)據(jù)壓縮的含義與簡(jiǎn)介01理論與應(yīng)用03類型與流行算法04算法2信息論在數(shù)據(jù)壓縮技術(shù)中的應(yīng)用

數(shù)據(jù)壓縮作為信息論研究中的一項(xiàng)內(nèi)容，主要是有關(guān)數(shù)據(jù)壓縮比和各種編碼方法的研究，即按某種方法對(duì)源數(shù)據(jù)流進(jìn)行編碼，使得經(jīng)過(guò)編碼的數(shù)據(jù)流比原數(shù)據(jù)流占有較少的空間。

數(shù)據(jù)壓縮的主要目的是力求用最少的數(shù)據(jù)表示信源所發(fā)出的信號(hào)，使信號(hào)占用的存儲(chǔ)空間盡可能小，以達(dá)到提高信息傳輸速度的目的。數(shù)據(jù)壓縮在近代信息處理問(wèn)題中有大量的應(yīng)用，無(wú)論在數(shù)據(jù)存儲(chǔ)或傳送中，通過(guò)數(shù)據(jù)壓縮不僅可以大大節(jié)省資源利用的成本，而且把一些原來(lái)無(wú)實(shí)用意義的技術(shù)，如多媒體技術(shù)中的一些問(wèn)題，達(dá)到具有實(shí)用意義的標(biāo)準(zhǔn)。

數(shù)據(jù)壓縮技術(shù)的不斷完善是依靠在信息論這門(mén)學(xué)科的成長(zhǎng)上的，信息能否被壓縮以及能在多大程度上被壓縮與信息的不確定性有直接的關(guān)系，人工智能技術(shù)將會(huì)對(duì)數(shù)據(jù)壓縮的未來(lái)產(chǎn)生重大影響。信息論在數(shù)據(jù)壓縮技術(shù)中的應(yīng)用數(shù)據(jù)壓縮作為信息論3數(shù)據(jù)壓縮的含義與簡(jiǎn)介含義：數(shù)據(jù)壓縮是指在不丟失有用信息的前提下，縮減數(shù)據(jù)量以減少存儲(chǔ)空間，提高其傳輸、存儲(chǔ)和處理效率，或按照一定的算法對(duì)數(shù)據(jù)進(jìn)行重新組織，減少數(shù)據(jù)的冗余和存儲(chǔ)的空間的一種技術(shù)方法。

簡(jiǎn)介：在計(jì)算機(jī)科學(xué)和信息論中，數(shù)據(jù)壓縮或者源編碼是按照特定的編碼機(jī)制用比未經(jīng)編碼少的數(shù)據(jù)位元（或者其它信息相關(guān)的單位）表示信息的過(guò)程。例如，如果我們將“compression”編碼為“comp”那么這篇文章可以用較少的數(shù)據(jù)位表示。一種流行的壓縮實(shí)例是許多計(jì)算機(jī)都在使用的ZIP文件格式，它不僅僅提供了壓縮的功能，而且還作為歸檔工具（Archiver）使用，能夠?qū)⒃S多文件存儲(chǔ)到同一個(gè)文件中。數(shù)據(jù)壓縮的含義與簡(jiǎn)介含義：4

數(shù)據(jù)壓縮概要

對(duì)于任何形式的通信來(lái)說(shuō)，只有當(dāng)信息的發(fā)送方和接受方都能夠理解編碼機(jī)制的時(shí)候壓縮數(shù)據(jù)通信才能夠工作。例如，只有當(dāng)接受方知道這篇文章需要用英語(yǔ)字符解釋的時(shí)候這篇文章才有意義。同樣，只有當(dāng)接受方知道編碼方法的時(shí)候他才能夠理解壓縮數(shù)據(jù)。一些壓縮算法利用了這個(gè)特性，在壓縮過(guò)程中對(duì)數(shù)據(jù)進(jìn)行加密，例如利用密碼加密，以保證只有得到授權(quán)的一方才能正確地得到數(shù)據(jù)。數(shù)據(jù)壓縮能夠?qū)崿F(xiàn)是因?yàn)槎鄶?shù)現(xiàn)實(shí)世界的數(shù)據(jù)都有統(tǒng)計(jì)冗余。例如，字母“e”在英語(yǔ)中比字母“z”更加常用，字母“q”后面是“z”的可能性非常小。無(wú)損壓縮算法通常利用了統(tǒng)計(jì)冗余，這樣就能更加簡(jiǎn)練地、但仍然是完整地表示發(fā)送方的數(shù)據(jù)。

如果允許一定程度的保真度損失，那么還可以實(shí)現(xiàn)進(jìn)一步的壓縮。例如，人們看圖畫(huà)或者電視畫(huà)面的時(shí)候可能并不會(huì)注意到一些細(xì)節(jié)并不完善。同樣，兩個(gè)音頻錄音采樣序列可能聽(tīng)起來(lái)一樣，但實(shí)際上并不完全一樣。有損壓縮算法在帶來(lái)微小差別的情況下使用較少的位數(shù)表示圖像、視頻或者音頻。數(shù)據(jù)壓縮概要對(duì)于任5

原理

壓縮原理其實(shí)很簡(jiǎn)單，就是找出那些重復(fù)出現(xiàn)的字符串，然后用更短的符號(hào)代替，從而達(dá)到縮短字符串的目的。比如，有一篇文章大量使用"中華人民共和國(guó)"這個(gè)詞語(yǔ)，我們用"中國(guó)"代替，就縮短了5個(gè)字符，如果用"華"代替，就縮短了6個(gè)字符。事實(shí)上，只要保證對(duì)應(yīng)關(guān)系，可以用任意字符代替那些重復(fù)出現(xiàn)的字符串。

本質(zhì)上，所謂"壓縮"就是找出文件內(nèi)容的概率分布，將那些出現(xiàn)概率高的部分代替成更短的形式。所以，內(nèi)容越是重復(fù)的文件，就可以壓縮地越小。比如，"ABABABABABABAB"可以壓縮成"7AB"。相應(yīng)地，如果內(nèi)容毫無(wú)重復(fù)，就很難壓縮。極端情況就是，遇到那些均勻分布的隨機(jī)字符串，往往連一個(gè)字符都?jí)嚎s不了。比如，任意排列的10個(gè)阿拉伯?dāng)?shù)字（5271839406），就是無(wú)法壓縮的；再比如，無(wú)理數(shù)（比如π）也很難壓縮。

壓縮就是一個(gè)消除冗余的過(guò)程，相當(dāng)于用一種更精簡(jiǎn)的形式，表達(dá)相同的內(nèi)容?？梢韵胂?，壓縮過(guò)一次以后，文件中的重復(fù)字符串將大幅減少。好的壓縮算法，可以將冗余降到最低，以至于再也沒(méi)有辦法進(jìn)一步壓縮。原理壓縮原理其實(shí)6理論與應(yīng)用

壓縮的理論基礎(chǔ)是信息論（它與算法信息論密切相關(guān)）以及率失真理論，這個(gè)領(lǐng)域的研究工作主要是由ClaudeShannon奠定的，他在二十世紀(jì)四十年代末期及五十年代早期發(fā)表了這方面的基礎(chǔ)性的論文。Doyle和Carlson在2000年寫(xiě)道數(shù)據(jù)壓縮“有所有的工程領(lǐng)域最簡(jiǎn)單、最優(yōu)美的設(shè)計(jì)理論之一”。密碼學(xué)與編碼理論也是密切相關(guān)的學(xué)科，數(shù)據(jù)壓縮的思想與統(tǒng)計(jì)推斷也有很深的淵源。理論與應(yīng)用壓縮的理論基礎(chǔ)是信息論（它與算法信息7

應(yīng)用：一種非常簡(jiǎn)單的壓縮方法是行程長(zhǎng)度編碼，這種方法使用數(shù)據(jù)及數(shù)據(jù)長(zhǎng)度這樣簡(jiǎn)單的編碼代替同樣的連續(xù)數(shù)據(jù)，這是無(wú)損數(shù)據(jù)壓縮的一個(gè)實(shí)例。這種方法經(jīng)常用于辦公計(jì)算機(jī)以更好地利用磁盤(pán)空間、或者更好地利用計(jì)算機(jī)網(wǎng)絡(luò)中的帶寬。對(duì)于電子表格、文本、可執(zhí)行文件等這樣的符號(hào)數(shù)據(jù)來(lái)說(shuō)，無(wú)損是一個(gè)非常關(guān)鍵的要求，因?yàn)槌艘恍┯邢薜那闆r，大多數(shù)情況下即使是一個(gè)數(shù)據(jù)位的變化都是無(wú)法接受的。對(duì)于視頻和音頻數(shù)據(jù)，只要不損失數(shù)據(jù)的重要部分一定程度的質(zhì)量下降是可以接受的。通過(guò)利用人類感知系統(tǒng)的局限，能夠大幅度得節(jié)約存儲(chǔ)空間并且得到的結(jié)果質(zhì)量與原始數(shù)據(jù)質(zhì)量相比并沒(méi)有明顯的差別。這些有損數(shù)據(jù)壓縮方法通常需要在壓縮速度、壓縮數(shù)據(jù)大小以及質(zhì)量損失這三者之間進(jìn)行折衷。應(yīng)用：一種非常簡(jiǎn)單的壓縮方法是行程長(zhǎng)度編碼，8

有損圖像壓縮用于數(shù)碼相機(jī)中，大幅度地提高了存儲(chǔ)能力，同時(shí)圖像質(zhì)量幾乎沒(méi)有降低。用于DVD的有損MPEG-2編解碼視頻壓縮也實(shí)現(xiàn)了類似的功能。在有損音頻壓縮中，心理聲學(xué)的方法用來(lái)去除信號(hào)中聽(tīng)不見(jiàn)或者很難聽(tīng)見(jiàn)的成分。人類語(yǔ)音的壓縮經(jīng)常使用更加專業(yè)的技術(shù)，因此人們有時(shí)也將“語(yǔ)音壓縮”或者“語(yǔ)音編碼”作為一個(gè)獨(dú)立的研究領(lǐng)域與“音頻壓縮”區(qū)分開(kāi)來(lái)。不同的音頻和語(yǔ)音壓縮標(biāo)準(zhǔn)都屬于音頻編解碼范疇。例如語(yǔ)音壓縮用于因特網(wǎng)電話，而音頻壓縮被用于CD翻錄并且使用MP3播放器解碼。有損圖像壓縮用于數(shù)碼相機(jī)中，大幅度地提高了存儲(chǔ)9

類型

數(shù)據(jù)壓縮可分成兩種類型，一種叫做無(wú)損壓縮，另一種叫做有損壓縮。

無(wú)損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)完全相同；無(wú)損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。一個(gè)很常見(jiàn)的例子是磁盤(pán)文件的壓縮。根據(jù)目前的技術(shù)水平，無(wú)損壓縮算法一般可以把普通文件的數(shù)據(jù)壓縮到原來(lái)的1/2～1/4。一些常用的無(wú)損壓縮算法有霍夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)壓縮算法。

有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。有損壓縮適用于重構(gòu)信號(hào)不一定非要和原始信號(hào)完全相同的場(chǎng)合。例如，圖像和聲音的壓縮就可以采用有損壓縮，因?yàn)槠渲邪臄?shù)據(jù)往往多于我們的視覺(jué)系統(tǒng)和聽(tīng)覺(jué)系統(tǒng)所能接收的信息，丟掉一些數(shù)據(jù)而不至于對(duì)聲音或者圖像所表達(dá)的意思產(chǎn)生誤解，但可大大提高壓縮比類型數(shù)據(jù)壓縮可分成兩種類型，一種叫做無(wú)損壓10流行算法

Lempel-Ziv（LZ）壓縮方法是最流行的無(wú)損存儲(chǔ)算法之一。DEFLATE是LZ的一個(gè)變體，它針對(duì)解壓速度與壓縮率進(jìn)行了優(yōu)化，雖然它的壓縮速度可能非常緩慢，PKZIP、gzip以及PNG都在使用DEFLATE。LZW（Lempel-Ziv-Welch）是Unisys的專利，直到2003年6月專利到期限，這種方法用于GIF圖像。另外值得一提的是LZR(LZ-Renau)方法，它是Zip方法的基礎(chǔ)。LZ方法使用基于表格的壓縮模型，其中表格中的條目用重復(fù)的數(shù)據(jù)串替換。對(duì)于大多數(shù)的LZ方法來(lái)說(shuō)，這個(gè)表格是從最初的輸入數(shù)據(jù)動(dòng)態(tài)生成的。這個(gè)表格經(jīng)常采用霍夫曼編碼維護(hù)（例如，SHRI、LZX）。目前一個(gè)性能良好基于LZ的編碼機(jī)制是LZX，它用于微軟公司的CAB格式。流Lempel-Ziv（LZ）壓縮方法是最流行的11算法編碼

算術(shù)編碼由JormaRissanen發(fā)明，并且由Witten、Neal以及Cleary將它轉(zhuǎn)變成一個(gè)實(shí)用的方法。這種方法能夠?qū)崿F(xiàn)比眾人皆知的哈夫曼算法更好的壓縮，并且它本身非常適合于自適應(yīng)數(shù)據(jù)壓縮，自適應(yīng)數(shù)據(jù)壓縮的預(yù)測(cè)與上下文密切相關(guān)。算術(shù)編碼已經(jīng)用于二值圖像壓縮標(biāo)準(zhǔn)JBIG、文檔壓縮標(biāo)準(zhǔn)DejaVu。文本輸入系統(tǒng)Dasher是一個(gè)逆算術(shù)編碼器。算術(shù)編碼是近十多年來(lái)發(fā)展迅速的一種無(wú)失真信源編碼,它與最佳的哈夫曼碼相比,理論性能稍加遜色