?? chapter1.htm
字號:
<html><head><meta http-equiv="Content-Type"content="text/html; charset=gb_2312-80"><meta name="GENERATOR" content="Microsoft FrontPage Express 2.0"><title>笨笨數據壓縮教程</title></head><body bgcolor="#FFFFFF"><p align="right"><a href="../../../index.html">返回斷章取義堂</a> <a href="../../index.html">返回詠剛的家</a></p><p style="background-color:#AAEEFF;font-size:14px;color:#0000AA">《笨笨數據壓縮教程》是我在1998年因工作需要研究壓縮算法時寫的文章（算是一種工作筆記吧，其中難免有許多疏漏），1999年初隨著項目變遷，就把壓縮技術的研究暫時擱置了。從那以后，一是工作太忙，二是自己懶惰，總之是沒能把半部壓縮教程補全。非常對不住大家。——王詠剛，2003年3月</p><p><img src="benben.jpg"alt="笨笨數據壓縮教程(Benben's Data Compression Guide)"width="370" height="129"></p><h2>第一章 輕松一下：數據壓縮簡史</h2><div align="right"><address> <a href="content.htm">目錄</a> <a href="Chapter2.htm">第二章</a></address></div><p align="left">算起來，數據壓縮的起源要比計算機的起源早得多，有興趣的讀者可以翻閱一下任何一本成語辭典，查查諸如“二桃三士”、“蕭規曹隨”之類的短語涵蓋了多少信息內容。<fontcolor="#FF8040">:-)</font></p><p align="left"><font color="#000000">認真一點：數據壓縮技術在計算機技術的萌芽時期就已經被提上了議事日程，有關信息如何被高效存儲和傳遞的話題不斷被軍事科學家、數學家、電子學家討論來、討論去。終于，隨著信息論的產生和發展，數據壓縮也由熱門話題演變成了真正的技術。</font></p><p align="left"><font color="#000000"><strong>通用無損數據壓縮</strong></font></p><p align="left"><font color="#000000">科學家在研究中發現，大多數信息的表達都存在著一定的冗余度，通過采用一定的模型和編碼方法，可以降低這種冗余度。貝爾實驗室的Claude Shannon 和 MIT 的 R.M.Fano幾乎同時提出了最早的對符號進行有效編碼從而實現數據壓縮的Shannon-Fano 編碼方法。</font></p><p align="left"><font color="#000000">D.A.Huffman 于 1952年第一次發表了他的論文“最小冗余度代碼的構造方法”(AMethod for the Construction of Minimum Redundancy Codes)。從此，數據壓縮開始在商業程序中實現并被應用在許多技術領域。UNIX系統上一個不太為現代人熟知的壓縮程序 COMPACT就是 Huffman 0 階自適應編碼的具體實現。80年代初，Huffman 編碼又在 CP/M 和 DOS系統中實現，其代表程序叫 SQ。在數據壓縮領域，Huffman的這一論文事實上開創了數據壓縮技術一個值得回憶的時代，60年代、70 年代乃至 80 年代的早期，數據壓縮領域幾乎一直被Huffman 編碼及其分支所壟斷。如果不是后面將要提到的那兩個以色列人，也許我們今天還要在Huffman 編碼的 0 和 1 的組合中流連忘返。</font></p><p align="left"><font color="#000000">讓我們沿著 Huffman的軌跡再向后跳躍幾年，80 年代，數學家們不滿足于Huffman編碼中的某些致命弱點，他們從新的角度入手，遵循Huffman 編碼的主導思想，設計出另一種更為精確，更能接近信息論中“熵”極限的編碼方法——算術編碼。憑借算術編碼的精妙設計和卓越表現，人們終于可以向著數據壓縮的極限前進了。可以證明，算術編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號精確表達原始信息內容。當然，算術編碼同時也給程序員和計算機帶來了新的挑戰：要實現和運行算術編碼，需要更為艱苦的編程勞動和更加快速的計算機系統。也就是說，在同樣的計算機系統上，算術編碼雖然可以得到最好的壓縮效果，但卻要消耗也許幾十倍的計算時間。這就是為什么算術編碼不能在我們日常使用的壓縮工具中實現的主要原因。</font></p><p align="left"><font color="#000000">那么，能不能既在壓縮效果上超越Huffman，又不增加程序對系統資源和時間的需求呢？我們必須感謝下面將要介紹的兩個以色列人。</font></p><p align="left"><font color="#000000">直到 1977年，數據壓縮的研究工作主要集中于熵、字符和單詞頻率以及統計模型等方面，研究者們一直在絞盡腦汁為使用Huffman 編碼的程序找出更快、更好的改進方法。1977年以后，一切都改變了。</font></p><p align="left"><font color="#000000">1977 年，以色列人Jacob Ziv 和 Abraham Lempel 發表了論文“順序數據壓縮的一個通用算法”(AUniversal Alogrithem for Sequential Data Compression)。</font></p><p align="left"><font color="#000000">1978年，他們發表了該論文的續篇“通過可變比率編碼的獨立序列的壓縮”(Compressionof Individual Sequences via Variable-Rate Coding)。</font></p><p align="left"><font color="#000000">所有的一切都改變了，在這兩篇論文中提出的兩個壓縮技術被稱為LZ77 和 LZ78 (不知為什么，作者名字的首字母被倒置了)。簡單地說，這兩種壓縮方法的思路完全不同于從Shannon 到 Huffman 到算術壓縮的傳統思路，倒是和本章開頭所舉的成語辭典的例子頗為相似，因此，人們將基于這一思路的編碼方法稱作“字典”式編碼。字典式編碼不但在壓縮效果上大大超過了Huffman，而且，對于好的實現，其壓縮和解壓縮的速度也異常驚人。</font></p><p align="left"><font color="#000000">1984 年，Terry Welch發表了名為“高性能數據壓縮技術”(A Technique forHigh-Performance Data Compression)的論文，描述了他在Sperry Research Center(現在是 Unisys 的一部分)的研究成果。他實現了LZ78 算法的一個變種 —— LZW。LZW 繼承了 LZ77 和LZ78壓縮效果好、速度快的優點，而且在算法描述上更容易被人們接受（有的研究者認為是由于Welch 的論文比 Ziv 和 Lempel 的更容易理解），實現也比較簡單。不久，UNIX上出現了使用 LZW 算法的 Compress 程序，該程序性能優良，并有高水平的文檔，很快成為了UNIX 世界的壓縮程序標準。緊隨其后的是 MS-DOS環境下的 ARC 程序( System Enhancement Associates, 1985 )，還有象PKWare、PKARC 等仿制品。LZ78 和 LZW 一時間統治了UNIX 和 DOS 兩大平臺。</font></p><p align="left"><font color="#000000">80年代中期以后，人們對 LZ77進行了改進，隨之誕生了一批我們今天還在大量使用的壓縮程序。HaruyasuYoshizaki(Yoshi) 的 LHarc 和 Robert Jung 的 ARJ 是其中兩個著名的例子。LZ77得以和 LZ78、LZW一起壟斷當今的通用數據壓縮領域。</font></p><p align="left"><font color="#000000">目前，基于字典方式的壓縮已經有了一個被廣泛認可的標準，從古老的PKZip 到現在的 WinZip，特別是隨著 Internet上文件傳輸的流行，ZIP 格式成為了事實上的標準，沒有哪一種通用的文件壓縮、歸檔系統敢于不支持ZIP 格式。</font></p><p align="left"><font color="#000000"><strong>多媒體信息的壓縮</strong></font></p><p align="left"><font color="#000000">今天的程序員們和設計師們往往樂此不疲地為計算機更換更大的硬盤，增加更多的內存，其主要目的是為了存放和處理越來越多的聲音、圖像和視頻數據。對聲音、圖像、視頻等多媒體信息的壓縮有兩條思路，要么采用成熟的通用數據壓縮技術進行壓縮，要么根據媒體信息的特性設計新的壓縮方法。事實上，人們在兩條道路上都作了卓有成效的探索。</font></p><p align="left"><font color="#000000">還記得 GIF 格式嗎？GIF可以把原始圖形文件以非常小數據量存儲，可以在同一個文件中存儲多幅圖像從而實現動畫效果。知道GIF 中的圖像使用什么方法壓縮的嗎？LZW!原來如此啊。GIF 大概是使用通用壓縮技術壓縮圖像信息的最成功的例子，當然，GIF文件中除了經過 LZW壓縮的像素信息以外，還保存有圖像的各種屬性信息以及圖像所使用的調色板信息等。GIF精確地保留了原始圖像的每一個像素信息，是無損圖像壓縮的代表。</font></p><p align="left"><font color="#000000">根據媒體特性量身定制的壓縮方法中，行程編碼(RLE:Run-Length Encoding)是最為簡單、最容易被想到的一種。大多數計算機中產生的圖像(和現實世界的圖像例如照片不同)都具有著大面積重復的顏色塊，為什么非要用無數個完全相同的顏色值來表示某塊圖像呢？我們完全可以用一個顏色值加一個重復次數來表示這一塊圖像，冗余度由此減小了，這就是RLE 方法的基本思路。顯然，它不適于用來壓縮照片、聲音等很少連續重復信息的數據。RLE方法最有代表性的實現有 PCX 和 Targa 圖形格式。</font></p><p align="left"><font color="#000000">如果分別考察的話，只有黑白兩種顏色的二值圖像以及只有256 級灰度變化的圖像具有一些獨特的地方，可以被壓縮算法加以利用。我們知道，傳真圖像是一種典型的二值圖像。國際電報電話咨詢委員會(CCITT )為此建立了一系列的壓縮標準，專門用于壓縮傳遞二值圖像（可以是無損的或有損的）。對于灰度圖像，除了著名的JPEG 標準以外，后文將要介紹的一種叫 FELICS的算法可以實現效果非常好的無損壓縮。</font></p><p align="left"><font color="#000000">70 年代末 80年代初，人們逐漸意識到，對到多數灰度或是彩色圖像乃至聲音文件，沒有必要忠實地保留其所有信息，在允許一定的精度損失的情況下，可以實現更為有效的壓縮方法。到80 年代末，許多人已經在這一領域取得了不小的收獲，設計出了一批在壓縮效果上讓人驚訝不已的聲音和圖像壓縮算法。在此基礎上，國際標準化組織(ISO )和 CCITT聯合組成了兩個委員會。委員會的名字我們大概都已經非常熟悉了：靜態圖像聯合專家小組(JPEG )和動態圖像聯合專家小組( MPEG )。JPEG 的壓縮目標是靜止圖像（灰度的和彩色的），MPEG的目標則是聲音和視頻。但他們的基本思路是完全一樣的，即保留媒體信息中最有規律、最能體現信息主要特征的數據，而略去其他不重要的數據。他們都取得了令人贊嘆的成就。</font></p><p align="left"><font color="#000000">你剛看完 VCD嗎？那么你剛剛享用過他們為我們帶來的樂趣了。知道普通VCD 每一幀有多少彩色像素嗎？知道每秒鐘播放多少幀嗎？知道的話，算一算一部100 分鐘的電影不壓縮的話需要多少空間。每張光盤的容量是640M，那么，不壓縮的電影需要多少張光盤來存放呢？你該知道JPEG 或是 MPEG 的厲害了吧。</font></p><p align="left"><font color="#000000">最后，必須簡單地提到與圖像壓縮領域相關的電子出版印刷領域中的一種叫做PostScript 的東西。PostScript是作為電子印刷業的標準頁面描述語言被設計出來的，它起源于1976 年的 Evans & Sutherland計算機公司，當時的名字是 Design System。1978 年，JohnWarnock 和 Martin Newel 將其演變為 JAM 語言。1982 年，JohnWarnock 和 Chuck Geschke 創建了著名的 Adobe System 公司，并第三次設計和實現了這個語言，并將其稱為PostScript。</font></p><p align="left"><font color="#000000">PostScript的主要思路是存儲和傳輸預先定義的命令來“畫”出圖像，而不是存儲和傳輸圖像的每一個像素，這特別適用于在激光打印機上的輸出。采用類似“從(10,10)到(100, 100)畫一條紅色直線”或是“在（50，50）以40 為半徑畫一個藍色的圓”之類的命令存儲圖像顯然比直接存儲每個像素節省了不少地方。所以，從壓縮技術的角度來看，PostScript也可以算是壓縮方法的一種。根據類似的原理，Windows中的 WMF 格式、HP 的 HPGL 語言、AutoCAD 中使用的 DXF格式等等，都可以對某種特定的圖像進行有效的壓縮。</font></p><div align="center"><center><address> <a href="content.htm">目錄</a> <a href="Chapter2.htm">第二章</a></address></center></div><p align="left"><font color="#000000"></font> </p><div align="right"><address> <a href="mailto:wangyg@contextfree.net">有問題嗎？有建議嗎？快給王笨笨寫信</a></address></div><div align="right"><address> <strong>章節書簽：</strong><a href="default.htm">前言</a> <a href="content.htm">目錄</a> <a href="Chapter1.htm">1</a> <a href="Chapter2.htm">2</a> <a href="Chapter3.htm">3</a> <a href="Chapter4.htm">4</a> <a href="Chapter5.htm">5</a> <a href="Chapter6.htm">6</a> <a href="Chapter7.htm">7</a> <a href="Chapter8.htm">8</a> <a href="Chapter9.htm">9</a> <a href="Chapter10.htm">10</a> <a href="Chapter11.htm">11</a> <a href="Chapter12.htm">12</a> </address></div></body></html>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -