付　慧　黃心淵

文章編號：1672-5913(2009)06-0071-03

摘要：隨著數(shù)字媒體技術(shù)的不斷發(fā)展，數(shù)據(jù)壓縮技術(shù)在多媒體領(lǐng)域發(fā)揮著越來越重要的作用。針對目前很多數(shù)據(jù)壓縮的教材是針對計算機專業(yè)和信息專業(yè)所編著的，在數(shù)字媒體技術(shù)專業(yè)講授這門課程時需要進行適當調(diào)整和更新?，F(xiàn)將我所在學校的數(shù)字媒體專業(yè)講授數(shù)據(jù)壓縮這門課程的大綱、授課重點內(nèi)容和實驗設計介紹如下，希望能夠有助于該門課程的建設。

關(guān)鍵詞: 數(shù)據(jù)壓縮；課程大綱；實驗設計

中圖分類號：G642

文獻標識碼：B

1數(shù)據(jù)壓縮課程大綱

我們在設定大綱時考慮到要結(jié)合本科生強調(diào)基礎理論知識的特點選擇了小部分學時用于介紹數(shù)據(jù)壓縮的基礎理論，這部分要涉及信息論中的一些內(nèi)容。數(shù)據(jù)壓縮算法的介紹占據(jù)主要的學時，我們選擇從單純的數(shù)據(jù)領(lǐng)域和多媒體(以圖像為例)領(lǐng)域兩個方面來介紹壓縮算法。分別選取有代表意義的經(jīng)典的算法進行介紹，同時輔助以實驗進行鞏固和練習。最后的學時用于介紹國際上和我國的各種數(shù)據(jù)壓縮標準，以及數(shù)據(jù)壓縮方法在視音頻領(lǐng)域的應用。

我校數(shù)字媒體專業(yè)的數(shù)據(jù)壓縮課程目前作為選修課，40學時，講授20學時，實驗20學時。相對于別的專業(yè)的數(shù)據(jù)壓縮課程，學時數(shù)不多。但是在有限的學時內(nèi)我們要盡量將該講的知識傳授給學生，因此我們設計了上述范圍的內(nèi)容。對于學時更充分的學校來說，以上的每個部分都可以進行內(nèi)容擴展，便于進行更深入的講授?，F(xiàn)將課程大綱介紹如下：

第一部分：數(shù)據(jù)壓縮基礎理論

第一章數(shù)據(jù)壓縮概述(2學時)

1.1為什么需要數(shù)據(jù)壓縮

1.2早期的數(shù)據(jù)壓縮思想

1.3數(shù)據(jù)壓縮的原理及實現(xiàn)

1.4數(shù)據(jù)壓縮的發(fā)展歷史

第二章數(shù)據(jù)壓縮基本概念(2學時)

2.1熵與信息量

2.2模型和編碼

2.3多媒體信息的壓縮

2.4有損壓縮

2.5無損壓縮

第二部分：數(shù)據(jù)壓縮算法介紹

第三章統(tǒng)計壓縮方法(4學時)

3.1Shannon-Fano編碼方法

3.2Huffman編碼方法

3.3算術(shù)編碼方法

第四章字典壓縮方法(4學時)

4.1符號串的壓縮

4.2什么是字典壓縮方法

4.3LZ77算法

4.4LZ78算法

4.5LZW算法

第五章多媒體數(shù)據(jù)壓縮之圖像數(shù)據(jù)的壓縮(4學時)

5.1彩色數(shù)字圖像基礎

5.2圖像文件壓縮格式

5.3GIF壓縮編碼

5.4JPEG壓縮編碼

第三部分：國際和國內(nèi)的數(shù)據(jù)壓縮標準和數(shù)據(jù)壓縮在視音頻領(lǐng)域的應用

第六章視音頻數(shù)據(jù)壓縮及國際國內(nèi)壓縮標準(4學時)

6.1視音頻壓縮的必要性

6.2視頻壓縮的國際標準

6.3視頻壓縮技術(shù)

6.4音頻壓縮的國際標準

6.5音頻壓縮技術(shù)

6.6我國視音頻壓縮標準——AVS(Audio Video Coding Standard)介紹

2數(shù)據(jù)壓縮課程重點內(nèi)容介紹

在選擇教材時，我選擇了國外作者David Salomon所著的Data Compression第三版，該書較為全面地介紹了數(shù)據(jù)壓縮的知識，包括大量的數(shù)據(jù)壓縮算法和實例。該書中除了介紹上述的大綱中的部分內(nèi)容，還詳細介紹了數(shù)據(jù)壓縮中的小波方法，視頻壓縮方法以及數(shù)據(jù)壓縮中用到的實用算法。但是由于這本著作的介紹較為詳盡，而我們授課學時有限，因此有很多內(nèi)容只能放棄。但是我把這門書的電子版提供給學生們，指導他們在課下如果感興趣的話可以自行閱讀。

針對第一部分，我們的重點放在介紹數(shù)據(jù)壓縮基礎理論的基本概念上。包括信息量、熵、模型和編碼等概念。由于熵的概念較為抽象，因此我們首先需要介紹信息量的概念。將信息量解釋為“量化了的信息，是對數(shù)據(jù)中包含信息內(nèi)容的觀察，它等于在這條數(shù)據(jù)中令你吃驚的數(shù)目。”這樣就將抽象的概念具體化了。而熵的概念就是度量信息量的一種方法。熵定義為“一條數(shù)據(jù)中有多少信息進行編碼的度量”，即消息的熵越高則包含的信息量越多，也即消息中令人吃驚的信息數(shù)目越多。因為消息中信息量不完全等同于消息本身，因此可知消息數(shù)據(jù)中存在冗余，而這些數(shù)據(jù)中的冗余信息與數(shù)據(jù)所表達的信息量無關(guān)，可以去除，因此數(shù)據(jù)壓縮才進入信息領(lǐng)域。數(shù)據(jù)壓縮的實現(xiàn)由兩部分組成，即“數(shù)據(jù)壓縮=模型+編碼”。因此要設計一個數(shù)據(jù)壓縮算法都會涉及到這兩方面的內(nèi)容。清楚了這些基本概念后，就可以針對各個具體的數(shù)據(jù)壓縮算法進行介紹了。

針對第二部分，重點在于對壓縮算法的理解和實現(xiàn)。統(tǒng)計壓縮方法、字典壓縮方法和多媒體壓縮方法的原理和實現(xiàn)是這部分的重點內(nèi)容。介紹每個算法時都要包括以下幾個方面：

① 基本思想：介紹算法實現(xiàn)的基本思想，從總體上先了解算法。

② 數(shù)據(jù)結(jié)構(gòu)：算法的具體實現(xiàn)中會涉及到的一些固定的數(shù)據(jù)結(jié)構(gòu)的介紹。

③ 算法實例：以一個具體的實例來具體說明算法的實現(xiàn)。

④ 算法描述：以流程圖或步驟總結(jié)的形式表述算法的實現(xiàn)過程。

⑤ 算法實現(xiàn)：介紹算法在實現(xiàn)過程中的關(guān)鍵步驟和問題，同時以程序的形式來描述算法。

⑥ 算法中的問題：強調(diào)在算法實現(xiàn)中容易出錯的問題，找出算法中可以改進的地方和改進方法。

將上述每個方面都講清楚了，算法就會非常容易理解。同時還要可以對同類算法之間進行一些比較，以便于同學們記憶和區(qū)分不同的算法。在逐個介紹這些算法的過程中，介紹算法中問題主要目的是要啟發(fā)式的引導同學們思考如何改進這些已有的壓縮算法。

例如在講到字典壓縮的LZ77算法時，算法要求輸出的必須都是三元組(偏移量，長度，下一個字符)。對于沒有匹配上的字符仍然要輸出一個三元組(0,0,字符)，這樣本來一個字符所需的存儲空間就要用一個三元組來代替，這個字符壓縮后反而變長了，那么如何解決這個問題呢？這實際上是數(shù)據(jù)壓縮在實現(xiàn)中的編碼問題。匹配不上的字符如何改進其編碼，使其不出現(xiàn)上述問題。一種解決方法是：將匹配串和不能匹配的單個字符分別編碼、分別輸出，輸出匹配串時不同時輸出后續(xù)字符。這種輸出方式的優(yōu)點是輸出單個字符的時候比較節(jié)省空間。另外，因為不強求每次都外帶一個后續(xù)字符，可以適應一些較長匹配的情況。通過將這種改進算法的思想教授給學生，可以引導他們在學習壓縮算法時多注意思考，能夠舉一反三的對算法進行修改和設計。

針對第三部分，重點在于了解目前已有的視音頻國際國內(nèi)標準，同時概括了解一下當前的熱點視音頻技術(shù)。

介紹視音頻標準時重點介紹一下我國的AVS (Audio Video Coding Standard)標準。AVS是我國具備自主知識產(chǎn)權(quán)的第二代信源編碼標準。AVS標準是《信息技術(shù) 先進音視頻編碼》系列標準的簡稱，AVS標準包括系統(tǒng)、視頻、音頻、數(shù)字版權(quán)管理等四個主要技術(shù)標準和一致性測試等支撐標準。

AVS最直接的產(chǎn)業(yè)化成果是未來10年我國需要的3～5億顆解碼芯片，最直接效益是節(jié)省超過10億美元的專利費。在多媒體領(lǐng)域開創(chuàng)新的數(shù)據(jù)壓縮標準和方法無疑有著巨大的前景和效益。數(shù)字媒體專業(yè)的學生需要了解社會和技術(shù)發(fā)展對多媒體數(shù)據(jù)壓縮技術(shù)的巨大需求，可以以此作為將來工作的一個領(lǐng)域。

3數(shù)據(jù)壓縮課程的實驗設計

課程算法的介紹是從易到難，實驗的完成也是循序漸進的。每次實驗同學們能夠鞏固學習到的算法，同時還可以為下一個算法的設計打好基礎。針對我們講授的算法和實驗學時數(shù)，我們共設計了4個實驗，實驗軟件采用VC++或Java。

實驗一：建立統(tǒng)計壓縮方法理論模型

實驗內(nèi)容：采用C/C++/Java編寫程序，根據(jù)Shannon-Fano編碼及Huffman編碼方法的原理，實現(xiàn)建立Shannon-Fano樹或建立Huffman樹。并自定義簡單輸入數(shù)據(jù)，檢驗結(jié)果。

實驗要求：

模型分別采用：

① 靜態(tài)的概率表

② 對每個輸入流建立概率表

輸入：鍵盤輸入的任意字符流。

輸出：每個字符的編碼，整個串的壓縮編碼，計算壓縮比(輸出流的大小/輸入流的大小)。

實驗目的：通過逐步實現(xiàn)算法，深入理解利用統(tǒng)計的方法進行數(shù)據(jù)壓縮的原理。實驗要求采用兩種不同的模型方法，目的是使同學們體會選取的模型不同會對數(shù)據(jù)壓縮算法產(chǎn)生不同的影響。

實驗二：統(tǒng)計壓縮方法的具體實現(xiàn)

實驗內(nèi)容：在實驗一中完成的統(tǒng)計數(shù)據(jù)壓縮方法理論模型的基礎上實現(xiàn)對數(shù)據(jù)文件的壓縮和解壓縮。

實驗要求：

輸入：字符串文件

功能1：將文件中的字符串進行Shannon-Fano編碼或Huffman編碼。

輸出：字符的編碼結(jié)果，并將字符串的編碼結(jié)果寫成2進制文件保存。

功能2：將2進制文件讀入，進行解碼。

輸出：解碼后的結(jié)果。

實驗目的：

本實驗要求輸入和輸出均為實際應用中的數(shù)據(jù)文件，使得數(shù)據(jù)壓縮算法成為真正能用的工具。本實驗通過解決壓縮算法在實際應用出現(xiàn)的一系列問題真正實現(xiàn)數(shù)據(jù)壓縮算法從理論到實踐的轉(zhuǎn)換。

實驗三：字典壓縮方法實現(xiàn)壓縮和解壓縮

實驗內(nèi)容：

基于給定程序(略)，用C/C++ /Java編寫程序，根據(jù)LZ77或者LZ78字典壓縮算法的原理實現(xiàn)文件的壓縮及解壓縮，并對實驗結(jié)果進行分析。

實驗要求：

輸入：字符串文件

輸出：輸出壓縮/解壓縮文件。

實驗目的：

學習已有的一個實現(xiàn)LZW算法的具體的程序，根據(jù)LZW算法和LZ77、LZ78算法的差別自己設計實現(xiàn)LZ77/LZ78字典壓縮算法，完成對數(shù)據(jù)文件的壓縮和解壓縮。本實驗能夠鍛煉學生的讀程序的能力，同時啟發(fā)他們學習已有程序的設計思想，進行部分改造來實現(xiàn)自己的算法。

實驗四：圖像數(shù)據(jù)壓縮

實驗內(nèi)容：

基于給定程序(略)，用C/C++/Java編寫程序，根據(jù)LZW字典壓縮算法的原理將圖像文件壓縮成GIF格式，用現(xiàn)有軟件檢驗生成GIF圖像文件的正確性，并對實驗結(jié)果進行分析。

實驗要求：

1 輸入：給定的Bmp格式圖像。

2 輸出：壓縮成GIF格式圖像。

實驗目的：

學習在已有程序的基礎上添加一些內(nèi)容來實現(xiàn)新的功能。在掌握圖像GIF壓縮編碼原理的基礎上，在給定的LZW程序上添加針對圖像數(shù)據(jù)文件的一些功能，實現(xiàn)圖像GIF壓縮。

本實驗使學生了解圖像數(shù)據(jù)壓縮方法，深入理解基于字典的方法進行數(shù)據(jù)壓縮的原理。

4總結(jié)

以上是我對“數(shù)據(jù)壓縮”這門課程的一些心得和總結(jié)。主要從課程的大綱、授課重點內(nèi)容和實驗設計進行了介紹。通過四次授課顯示，同學們對這樣的課程內(nèi)容掌握的較好，同時學習到的數(shù)據(jù)壓縮的思想對他們思考問題的方式也有很大的啟發(fā)作用。同學們在課程實驗中極大地鍛煉了編程能力，同時也通過實驗對算法的原理有了深入的理解，對算法的很多細節(jié)問題能夠提出自己的改造方法，進行了創(chuàng)造性的設計工作。衷心希望以上總結(jié)的內(nèi)容能夠?qū)@門課程的建設有所幫助。

參考文獻：

[1] David Salomon. Data Compression. 3rd Edition,SPRINGER-VERLAG NEW YORK INC,2004.

[2] 笨笨數(shù)據(jù)壓縮教程[EB/OL]. http://www.contextfree.net/wangyg/a/tutorial/benben.html.

[3] 林福宗. 多媒體技術(shù)基礎(第二版)[M]. 北京:清華大學出版社,2002,9.

[4] David Salomon著,吳樂南等譯. 數(shù)據(jù)壓縮原理與應用(第二版)[M]. 北京:電子工業(yè)出版社,1999.