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

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

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

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

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

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

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

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

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

原理

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

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

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

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

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

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

類型

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

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

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

Lempel-Ziv（LZ）壓縮方法是最流行的無損存儲算法之一。DEFLATE是LZ的一個變體，它針對解壓速度與壓縮率進(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ù)串替換。對于大多數(shù)的LZ方法來說，這個表格是從最初的輸入數(shù)據(jù)動態(tài)生成的。這個表格經(jīng)常采用霍夫曼編碼維護(hù)（例如，SHRI、LZX）。目前一個性能良好基于LZ的編碼機(jī)制是LZX，它用于微軟公司的CAB格式。流Lempel-Ziv（LZ）壓縮方法是最流行的11算法編碼

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