?? 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="http://www.contextfree.net/">返回斷章取義堂</a> <a href="http://www.contextfree.net/wangyg/">返回詠剛的家</a></p>
<p>【提示】我的網站上新增了一篇文章<a href="../../../b/tech_his/data_compression_history.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">算起來，數據壓縮的起源要比計算機的起源早得多，有興趣的讀者可以翻閱一下任何一本成語辭典，查查諸如“二桃三士”、“蕭規曹隨”之類的短語涵蓋了多少信息內容。<font
color="#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
年第一次發表了他的論文“最小冗余度代碼的構造方法”(A
Method 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 發表了論文“順序數據壓縮的一個通用算法”(A
Universal Alogrithem for Sequential Data Compression)。</font></p>
<p align="left"><font color="#000000">1978
年，他們發表了該論文的續篇“通過可變比率編碼的獨立序列的壓縮”(Compression
of 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 for
High-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
進行了改進，隨之誕生了一批我們今天還在大量使用的壓縮程序。Haruyasu
Yoshizaki(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 年，John
Warnock 和 Martin Newel 將其演變為 JAM 語言。1982 年，John
Warnock 和 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>
有問題嗎？有建議嗎？快給王笨笨寫信：wangyg@contextfree.net
</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 + -