數(shù)據(jù)壓縮的起源要比計(jì)算機(jī)的起源早得多，數(shù)據(jù)壓縮技術(shù)在計(jì)算機(jī)技術(shù)的萌芽時(shí)期就已經(jīng)被提上了議事日程，軍事科學(xué)家、數(shù)學(xué)家、電子學(xué)家一直在研究有關(guān)信息如何被高效存儲(chǔ)和傳遞的問(wèn)題。隨著信息論的產(chǎn)生和發(fā)展，數(shù)據(jù)壓縮也由熱門(mén)話題演變成了真正的技術(shù)。
數(shù)據(jù)壓縮可分成兩種類(lèi)型，一種叫做無(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)
合。磁盤(pán)文件的壓縮就是一個(gè)很常見(jiàn)的例子。根據(jù)目前的技術(shù)水平，無(wú)損壓縮算法一般可以把普通文件的數(shù)據(jù)壓縮到原來(lái)的1/2～1/4。
有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)有所不同，但不會(huì)讓人對(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ù)大致可以按照以下的方法分類(lèi)：
?????????????????????????????????????????????????????????????????????????????????????? 壓縮技術(shù)
?????????????????????????????????????????????????????????????????????????????????????????????? |
?????????????????????????????????????????????????????????????????????????/------------------------------\
????????????????????????????????????????????????????????通用無(wú)損數(shù)據(jù)壓縮 ????????????多媒體數(shù)據(jù)壓縮(大多為有損壓縮)
??????????????????????????????????????????????????????????????????????
| ????????????????????????????????????????????????????????|
??????????????????????????????????????????????????????????/----------------\?
?????????????????/------------------------------------\
??????????????????????????????????????????????????基于統(tǒng)計(jì)????????? 基于字典???音頻壓縮???????? 圖像壓縮?????????????? 視頻壓縮
??????????????????????????????????????????????????
模型的壓 ????????模型的壓 ????????| ????????????????????????|
????????????????????????????????|
??????????????????????????????????????????????????縮技術(shù) ????????????縮技術(shù) ????????MP3等 ????/-------------------\????????????AVI
????????????????????????????????????????????????????????|
????????????????????????|???????????????????????????????二值 灰度 彩色
矢量?????? MPEG2等
????????????????????????????????????????????????????/------\ ????????/-------------\????????????????????圖像 圖像 圖像 圖像
????????????????????????????????????????????Huffman 算術(shù) LZ77 LZ78 LZW???????????????????? ?| ????????|???????? ?|????????\?
????????????????????????????????????????????編碼 ????編碼 ????\-------------/????????????????傳真機(jī) FELICS GIF ????????PostScript
????????????????????????????????????????????????|
????????????|???????????????????? | ????????????????????????標(biāo)準(zhǔn)
????JPEG等 JPEG等 Windows WMF等
???????????????????????????????????UNIX下 ????????? 接近無(wú)損???????PKZIP、LHarc、ARJ、
???????????????????????????????????的COMPACT? 壓縮極限????????UNIX下的COMPRESS
???????????????????????????????????程序等???????????? 的高級(jí)應(yīng)用????程序等
通用無(wú)損數(shù)據(jù)壓縮的歷史
科學(xué)家在研究中發(fā)現(xiàn)，大多數(shù)信息的表達(dá)都存在著一定的冗余度，通過(guò)采用一定的模型和編碼方法，可以
降低這種冗余度。貝爾實(shí)驗(yàn)室的 Claude Shannon 和 MIT 的 R.M.Fano 幾乎同時(shí)提出了最早的對(duì)符號(hào)進(jìn)行有
效編碼從而實(shí)現(xiàn)數(shù)據(jù)壓縮的 Shannon-Fano 編碼方法。
D.A.Huffman
于1952年第一次發(fā)表了他的論文“最小冗余代碼的構(gòu)造方法”(A Method for the Construction of Minimum
Redundancy Codes)。從此，數(shù)據(jù)壓縮開(kāi)始在商業(yè)程序中實(shí)現(xiàn)并被應(yīng)用在許多技術(shù)領(lǐng)域。UNIX 系統(tǒng)上一個(gè)壓縮程序 COMPACT
就是 Huffman 0 階自適應(yīng)編碼的具體實(shí)現(xiàn)。80 年代初，Huffman編碼又在CP/M 和DOS 系統(tǒng)中實(shí)現(xiàn)，其代表程序叫
SQ。在數(shù)據(jù)壓縮領(lǐng)域，Huffman 的這一論文事實(shí)上開(kāi)創(chuàng)了數(shù)據(jù)壓縮技術(shù)一個(gè)值得回憶的時(shí)代，60 年代、70 年代乃至 80
年代的早期，數(shù)據(jù)壓縮領(lǐng)域幾乎一直被 Huffman 編碼及其分支所壟斷。如果不是后面將要提到的那兩個(gè)以色列人，也許我們今天還要在
Huffman編碼的 0 和 1 的組合中流連忘返。
80年代，數(shù)學(xué)家們不滿足于 Huffman
編碼中的某些致命弱點(diǎn)，他們從新的角度入手，遵循 Huffman
編碼的主導(dǎo)思想，設(shè)計(jì)出另一種更為精確，更能接近信息論中“熵”極限的編碼方法——算術(shù)編碼。憑借算術(shù)編碼的精妙設(shè)計(jì)和卓越表現(xiàn)，人們終于可以向著數(shù)據(jù)壓
縮的極限前進(jìn)了。可以證明，算術(shù)編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號(hào)精確表達(dá)原始信息內(nèi)容。當(dāng)然，算術(shù)編碼同時(shí)也給程序員和計(jì)
算機(jī)帶來(lái)了新的挑戰(zhàn)：要實(shí)現(xiàn)和運(yùn)行算術(shù)編碼，需要更為艱苦的編程勞動(dòng)和更加快速的計(jì)算機(jī)系統(tǒng)。也就是，在同樣的計(jì)算機(jī)系統(tǒng)上，算術(shù)編碼雖然可以得到最好的
壓縮效果，但卻要消耗也許幾十倍的計(jì)算時(shí)。這就是為什么算術(shù)編碼不能在我們?nèi)粘Ｊ褂玫膲嚎s工具中實(shí)現(xiàn)的主要原因。
那么，能不能既在壓縮效
果上超越 Huffman，又不增加程序?qū)ο到y(tǒng)資源和時(shí)間的需求呢？我們必須感謝下面將要介紹的兩個(gè)以色列人。直到 1977
年，數(shù)據(jù)壓縮的研究工作主要集中于熵、字符和單詞頻率以及統(tǒng)計(jì)模型等方面，研究者們一直在絞盡腦汁為使用Huffman編碼的程序找出更快、更好的改進(jìn)方
法。1977 年以后，一切都改變了。
1977 年，以色列人 Jacob Ziv 和 Abraham Lempel
發(fā)表了論文“順序數(shù)據(jù)壓縮的一個(gè)通用算法”(A Universal Alogrithem for Sequential Data
Compression)。1978 年，他們發(fā)表了該論文的續(xù)篇“通過(guò)可變比率編碼的獨(dú)立序列的壓縮”(Compression of
Individual Sequences via Variable-Rate Coding)。在這兩篇論文中提出的壓縮技術(shù)分別被稱(chēng)為 LZ77
和 LZ78 (不知為什么，作者名字的首字母被倒置了)。簡(jiǎn)單地說(shuō)，這兩種壓縮方法的思路完全不同于從 Shannon 到 Huffman
到算術(shù)壓縮的傳統(tǒng)思路，人們將基于這一思路的編碼方法稱(chēng)作“字典”式編碼。字典式編碼不但在壓縮效果上大大超過(guò)了
Huffman，而且，對(duì)于好的實(shí)現(xiàn)，其壓縮和解壓縮的速度也異常驚人。
1984 年，Terry Welch
發(fā)表了名為“高性能數(shù)據(jù)壓縮技術(shù)”(A Technique for High-Performance Data
Compression)的論文，描述了他在 Sperry Research
Center(現(xiàn)在是Unisys的一部分)的研究成果。他實(shí)現(xiàn)了LZ78 算法的一個(gè)變種 —— LZW。LZW 繼承了 LZ77 和 LZ78
壓縮效果好、速度快的優(yōu)點(diǎn)，而且在算法描述上更容易被人們接受（有的研究者認(rèn)為是由于 Welch 的論文比 Ziv 和 Lempel
的更容易理解），實(shí)現(xiàn)也比較簡(jiǎn)單。不久，UNIX 上出現(xiàn)了使用 LZW 算法的 Compress
程序，該程序性能優(yōu)良，并有高水平的文檔，很快成為了 UNIX 世界的壓縮程序標(biāo)準(zhǔn)。緊隨其后的是 MS-DOS 環(huán)境下的ARC程序(
System Enhancement Associates, 1985 )，還有象 PKWare、PKARC
等仿制品。LZ78和LZW一時(shí)間統(tǒng)治了UNIX和DOS兩大平臺(tái)。
80 年代中期以后，人們對(duì) LZ77
進(jìn)行了改進(jìn)，隨之誕生了一批我們今天還在大量使用的壓縮程序。Haruyasu Yoshizaki(Yoshi)的LHarc和Robert
Jung的ARJ是其中兩個(gè)著名的例子。LZ77得以和LZ78、LZW一起壟斷當(dāng)今的通用數(shù)據(jù)壓縮領(lǐng)域。
目前，基于字典方式的壓縮已經(jīng)有了一個(gè)被廣泛認(rèn)可的標(biāo)準(zhǔn)，從古老的PKZip到現(xiàn)在的WinZip，特別是隨
著Internet上文件傳輸?shù)牧餍校琙IP 格式成為了事實(shí)上的標(biāo)準(zhǔn)，沒(méi)有哪一種通用的文件壓縮、歸檔系統(tǒng)不支
持 ZIP 格式。本章主要介紹目前用得最多和技術(shù)最成熟的無(wú)損壓縮編碼技術(shù)，包括包含霍夫曼(Huffman)編碼、算術(shù)編碼、RLE編碼和詞典編碼 。注意有一部分壓縮算法受到美國(guó)專(zhuān)利法的保護(hù)（例如 LZW 算法的某些部分和高階算術(shù)壓縮算法的某些細(xì)節(jié)等）。
4.1 仙農(nóng)-范諾與霍夫曼編碼
4.1.1 仙農(nóng)-范諾（Shannon-Fano）編碼
仙農(nóng)-范諾編碼算法需要用到下面兩個(gè)基本概念：
1. Entropy(熵)
(1) 熵是信息量的度量方法，表示一條信息中真正需要編碼的信息量。事件發(fā)生的可能性越小（數(shù)學(xué)上就
是概率越小），表示某一事件出現(xiàn)的消息越多。
(2) 某個(gè)事件的信息量用Ii=-log2 pi表示（有時(shí)稱(chēng)為surprise）， 其中pi為第i個(gè)事件的概率，0 pi 1對(duì)數(shù)以2為底時(shí)，熵的單位是"bits"。
2. 信源S的熵
按照仙農(nóng)(Shannon)的理論，信源S的熵定義為
其中pi是符號(hào)si在S中出現(xiàn)的概率；log2(1/ pi)表示包含在si中的信息量，也就是編碼si所需要的位數(shù)。
例如，一幅用256級(jí)灰度表示的圖像，如果每一個(gè)象素點(diǎn)灰度的概率均為pi=1/256，編碼每一個(gè)象素點(diǎn)就需
要8位。（最大熵分布）
最小熵分布： 除了一個(gè)符號(hào)外其余符號(hào)的概率全為0，H＝0bits.（定義0log20＝0）
例如，對(duì)下面這條只出現(xiàn)了 a b c 三個(gè)字符的字符串：aabbaccbaa，字符串長(zhǎng)度為 10，字符 a b c 分
別出現(xiàn)了 5 3 2 次，則 a b c 在信息中出現(xiàn)的概率分別為 0.5 0.3 0.2，他們的熵分別為：
Ea = -log2(0.5) = 1
Eb = -log2(0.3) = 1.737
Ec = -log2(0.2) = 2.322
整條信息的熵也即表達(dá)整個(gè)字符串需要的位數(shù)為：
Ea * 5 + Eb * 3 + Ec * 2 = 14.855 位
如果用計(jì)算機(jī)中常用的 ASCII 編碼，表示上面的字符串需要整整80位！信息為什么能被壓縮而不丟失原
有的信息內(nèi)容呢？簡(jiǎn)單地講，用較少的位數(shù)表示較頻繁出現(xiàn)的符號(hào)，這就是數(shù)據(jù)壓縮的基本準(zhǔn)則。（怎樣用 0
1 這樣的二進(jìn)制數(shù)碼表示零點(diǎn)幾個(gè)二進(jìn)制位呢？確實(shí)很困難，但不是沒(méi)有辦法。一旦找到了準(zhǔn)確表示零點(diǎn)幾個(gè)
二進(jìn)制位的方法，就接近無(wú)損壓縮的極限了。）
[例4.1] 有一幅40個(gè)象素組成的灰度圖像，灰度共有5級(jí)，分別用符號(hào)A、B、C、D和E表示，40個(gè)象素中出
現(xiàn)灰度A的象素?cái)?shù)有15個(gè)，出現(xiàn)灰度B的象素?cái)?shù)有7個(gè)，出現(xiàn)灰度C的象素?cái)?shù)有7個(gè)等等，如表4-01所示。
如果用3個(gè)位表示這5個(gè)等級(jí)的灰度值，也就是每個(gè)象素用3位表示(等長(zhǎng)編碼)，編碼這幅圖像總共需要120
位。
表4-01 符號(hào)在圖像中出現(xiàn)的數(shù)目
按照仙農(nóng)理論，這幅圖像的熵為 H(S)=(15/40)×log2(40/15) + (7/40)×log2(40/7) +… + (5/40)
×log2(40/5) = 2.196
這就是說(shuō)每個(gè)符號(hào)用2.196位表示，40個(gè)象素需用87.84位。
最早闡述和實(shí)現(xiàn)這種編碼的是Shannon(1948年)和Fano(1949年)，因此被稱(chēng)為仙農(nóng)-范諾(Shannon-Fano)算
法。這種方法采用從上到下的方法進(jìn)行編碼。
首先按照符號(hào)出現(xiàn)的頻度或概率排序，例如，A，B，C，D和E，如表4-02所示。
然后使用遞歸方法分成兩個(gè)部分，每一部分具有近似相同的次數(shù)，如圖4-01所示。
按照這種方法進(jìn)行編碼得到的總位數(shù)為91，實(shí)際的壓縮比約為1.3 : 1。
表4-02 Shannon-Fano算法舉例表
符 號(hào) A B C D E
出現(xiàn)的次數(shù) 15 7 7 6 5
符號(hào) 出現(xiàn)的次數(shù)(pi) log2(1/pi) 分配的代碼 需要的位數(shù)
A 15 (0.375) 1.4150 00 30
B 7 (0.175) 2.5145 01 14
C 7 (0.175) 2.5145 10 14
D 6 (0.150) 2.7369 110 18
E 5 (0.125) 3.0000 111 15
第 4 頁(yè)
4
圖4-01 仙農(nóng)-范諾算法編碼舉例
4.1.2 霍夫曼(Huffman)編碼
霍夫曼在1952年提出了另一種編碼方法，即從下到上的編碼方法。現(xiàn)以一個(gè)具體的例子說(shuō)明它的編碼步
驟：
(1) 初始化，根據(jù)符號(hào)概率的大小按由大到小順序?qū)Ψ?hào)進(jìn)行排序，如表4-03和圖4-02所示。
(2) 把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)，如圖4-02中的D和E組成節(jié)點(diǎn)P1。
(3) 重復(fù)步驟2，得到節(jié)點(diǎn)P2、P3和P4，形成一棵“樹(shù)”，其中的P4稱(chēng)為根節(jié)點(diǎn)。
(4) 從根節(jié)點(diǎn)P4開(kāi)始到相應(yīng)于每個(gè)符號(hào)的“樹(shù)葉”，從上到下標(biāo)上“0”(上枝)或者“1”(下枝)，至于哪
個(gè)為“1”哪個(gè)為“0”則無(wú)關(guān)緊要，最后的結(jié)果僅僅是分配的代碼不同，而代碼的平均長(zhǎng)度是相同的。
(5) 從根節(jié)點(diǎn)P4開(kāi)始順著樹(shù)枝到每個(gè)葉子分別寫(xiě)出每個(gè)符號(hào)的代碼，如表4-03所示。
(6) 按照仙農(nóng)理論，這幅圖像的熵為
H(S)=(15/39)×log2(39/15) + (7/39)×log2(39/7) + … + (5/39)×log2(39/5) = 2.1859
壓縮比1.37:1。
表4-03 霍夫曼編碼舉例
圖4-02 霍夫曼編碼方法
霍夫曼碼的碼長(zhǎng)雖然是可變的，但卻不需要另外附加同步代碼（前綴代碼）。例如，碼串中的第1位為0，
那末肯定是符號(hào)A，因?yàn)楸硎酒渌?hào)的代碼沒(méi)有一個(gè)是以0開(kāi)始的，因此下一位就表示下一個(gè)符號(hào)代碼的第1
符號(hào) 出現(xiàn)的次數(shù)(pi) log2(1/pi) 分配的代碼 需要的位數(shù)
A 15(0.3846) 1.38 0 15
B 7(0.1795) 2.48 100 21
C 6(0.1538) 2.70 101 18
D 6(0.1538) 2.70 110 18
E 5(0.1282) 2.96 111 15
第 5 頁(yè)
4
位。同樣，如果出現(xiàn)“110”，那么它就代表符號(hào)D。如果事先編寫(xiě)出一本解釋各種代碼意義的“詞典”，即碼
簿，那么就可以根據(jù)碼簿一個(gè)碼一個(gè)碼地依次進(jìn)行譯碼。
與仙農(nóng)-范諾編碼相同，這兩種方法都自含同步碼，在編碼之后的碼串中不需要另外添加標(biāo)記符號(hào)（即在
譯碼時(shí)分割符號(hào)的特殊代碼）。
采用霍夫曼編碼時(shí)有兩個(gè)問(wèn)題值得注意：
①霍夫曼碼沒(méi)有錯(cuò)誤保護(hù)功能，在譯碼時(shí)，如果碼串中沒(méi)有錯(cuò)誤，那么就能一個(gè)接一個(gè)地正確譯出代碼。
但如果碼串中有錯(cuò)誤，哪怕僅僅是1位出現(xiàn)錯(cuò)誤，不但這個(gè)碼本身譯錯(cuò)，更糟糕的是一錯(cuò)一大串，全亂了套，
這種現(xiàn)象稱(chēng)為錯(cuò)誤傳播(error propagation)。計(jì)算機(jī)對(duì)這種錯(cuò)誤也無(wú)能為力，說(shuō)不出錯(cuò)在哪里，更談不上去
糾正它。
②霍夫曼碼是可變長(zhǎng)度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲(chǔ)
代碼之前加以考慮。
盡管如此，霍夫曼碼還是得到廣泛應(yīng)用。 霍夫曼編碼方法的編碼效率比仙農(nóng)-范諾編碼效率高一些。
4.2 算術(shù)編碼
算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)(如JPEG，JBIG)中扮演了重要的角色。在算術(shù)編碼中，消息用0到1之間的實(shí)
數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，
也決定編碼過(guò)程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。編碼過(guò)程中的間隔決定了符號(hào)壓縮后的輸
出。算術(shù)編碼器的編碼過(guò)程可用下面的例子加以解釋。
[例4.2] 假設(shè)信源符號(hào)為{00, 01, 10, 11}，這些符號(hào)的概率分別為{ 0.1, 0.4, 0.2, 0.3 }，根據(jù)這些
概率可把間隔[0, 1)分成4個(gè)子間隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1)，其中[x,y)表示半開(kāi)放
間隔，即包含x不包含y。上面的信息可綜合在表4-04中。
表4-04 信源符號(hào)，概率和初始編碼間隔
如果二進(jìn)制消息序列的輸入為：10 00 11 00 10 11 01。編碼時(shí)首先輸入的符號(hào)是10，找到它的編碼范圍
是[0.5, 0.7)。消息中第二個(gè)符號(hào)00的編碼范圍是[0, 0.1)，因此就取[0.5, 0.7)的第一個(gè)十分之一作為新間
隔[0.5, 0.52)。依此類(lèi)推，編碼第3個(gè)符號(hào)11時(shí)取新間隔為[0.514, 0.52)，編碼第4個(gè)符號(hào)00時(shí)，取新間隔為
[0.514, 0.5146)，… 。消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)。整個(gè)編碼過(guò)程如圖4-03所示。
符號(hào) 00 01 10 11
概率 0.1 0.4 0.2 0.3
初始編碼間隔 [0, 0.1) [0.1, 0.5) [0.5, 0.7) [0.7, 1)
第 6 頁(yè)
4
圖4-03 算術(shù)編碼過(guò)程舉例
這個(gè)例子的編碼和譯碼的全過(guò)程分別表示在表4-05和表4-06中。
根據(jù)上面所舉的例子，可把計(jì)算過(guò)程總結(jié)如下。
考慮一個(gè)有M個(gè)符號(hào)i=(1,2,…,M)的字符表集，假設(shè)概率p( i)=pi，而
。輸入符號(hào)用xn表示，第n個(gè)子間隔的范圍用
表示。其中l(wèi)0=0，d0=1和p0=0，ln表示間隔左邊界的值,rn 表示間
隔右邊界的值，dn=rn-ln表示間隔長(zhǎng)度。編碼步驟如下：
步驟1：首先在1和0之間給每個(gè)符號(hào)分配一個(gè)初始子間隔，子間隔的長(zhǎng)度等于它的概率，初始子間隔的范
圍用I1=[l1，r1)=[ ， )表示。令d1=r1-l1，L=l1和R=r1。
步驟2：L和R的二進(jìn)制表達(dá)式分別表示為：
和
其中ui 和vi 等于“1”或者“0”。
①如果u1
≠v1 ，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3；
②如果u1=v1，就發(fā)送二進(jìn)制符號(hào)u1。
比較u2
和v2：如果u2≠v2 ，不發(fā)送任何數(shù)據(jù)，轉(zhuǎn)到步驟3；
如果u2=v2，就發(fā)送二進(jìn)制符號(hào)u2。
…
這種比較一直進(jìn)行到兩個(gè)符號(hào)不相同為止，然后進(jìn)入步驟3。
步驟3：n加1，讀下一個(gè)符號(hào)。假設(shè)第n個(gè)輸入符號(hào)為xn= i，按照以前的步驟把這個(gè)間隔分成如下所示的
子間隔：
第 7 頁(yè)
4
令L=ln，R=rn 和 dn=rn-ln，然后轉(zhuǎn)到步驟2。
表4-05 編碼過(guò)程
表4-06 譯碼過(guò)程
[例4.3] 假設(shè)有4個(gè)符號(hào)的信源，它們的概率如表4-07所示：
表4-07 符號(hào)概率
輸入序列為xn： 2， 1， 3，…。它的編碼過(guò)程如圖4-04所示，現(xiàn)說(shuō)明如下。
輸入第1個(gè)符號(hào)是x1= 2，可知i=2，定義初始間隔＝[0.5, 0.75)，由此可知
d1=0.25，左右邊界的二進(jìn)制數(shù)分別表示為：L＝0.5=0.1(B)，R＝0.7＝0.11… (B) 。按照步驟2，u1=v1，發(fā)
送1。因u2≠v2，因此轉(zhuǎn)到步驟3。
輸入第2個(gè)字符x2= 1，i=1，它的子間隔＝[0.5, 0.625)，由此可
得d2=0.125。左右邊界的二進(jìn)制數(shù)分別表示為：L＝0.5=0.100 … (B)，R＝0.101… (B)。按照步驟2，
u2=v2=0，發(fā)送0，而u3和v3不相同，因此在發(fā)送0之后就轉(zhuǎn)到步驟3。
輸入第3個(gè)字符，x3= 3，i=3，它的子間隔＝[0.59375, 0.609375)
，由此可得d3=0.015625。左右邊界的二進(jìn)制數(shù)分別表示為：L＝0.59375=0.10011 (B)，R＝
步驟 輸入符號(hào) 編碼間隔 編碼判決
1 10 [0.5, 0.7) 符號(hào)的間隔范圍[0.5, 0.7)
2 00 [0.5, 0.52) [0.5, 0.7)間隔的第一個(gè)1/10
3 11 [0.514, 0.52) [0.5, 0.52)間隔的最后三個(gè)1/10
4 00 [0.514, 0.5146) [0.514, 0.52)間隔的第一個(gè)1/10
5 10 [0.5143, 0.51442) [0.514, 0.5146)間隔的第五個(gè)1/10開(kāi)始，二個(gè)1/10
6 11 [0.514384, 0.51442 [0.5143, 0.51442)間隔的最后3個(gè)1/10
7 01 [0.5143836, 0.514402) [0.514384, 0.51442)間隔的4個(gè)1/10，從第1個(gè)1/10開(kāi)始
8 從[0.5143876, 0.514402)中選擇一個(gè)數(shù)作為輸出：0.5143876
步驟 間隔 譯碼符號(hào)譯碼判決
1 [0.5, 0.7) 10 0.51439在間隔 [0.5, 0.7)
2 [0.5, 0.52) 00 0.51439在間隔 [0.5, 0.7)的第1個(gè)1/10
3 [0.514, 0.52) 11 0.51439在間隔[0.5, 0.52)的第7個(gè)1/10
4 [0.514, 0.5146) 00 0.51439在間隔[0.514, 0.52)的第1個(gè)1/10
5 [0.5143, 0.51442) 10 0.51439在間隔[0.514, 0.5146)的第5個(gè)1/10
6 [0.514384, 0.51442) 11 0.51439在間隔[0.5143, 0.51442)的第7個(gè)1/10
7 [0.51439, 0.5143948) 01 0.51439在間隔[0.51439, 0.5143948)的第1個(gè)1/10
8 譯碼的消息：10 00 11 00 10 11 01
信源符號(hào)ai 1 2 3 4
概率pi p1=0.5 p2=0.25 p3=0.125 p4=0.125
初始編碼間隔 [0, 0.5) [0.5, 0.75) [0.75, 0.875) [0.875, 1)
第 8 頁(yè)
4
0.609375=0.100111 (B)。按照步驟2，u3=v3=0，u4=v4=1，u5=v5=1，但u6和v6不相同，因此在發(fā)送011之后轉(zhuǎn)到
步驟3。
…
發(fā)送的符號(hào)是：10011…。被編碼的最后的符號(hào)是結(jié)束符號(hào)。
圖4-04 算術(shù)編碼概念
就這個(gè)例子而言，算術(shù)編碼器接受的第1位是“1”，它的間隔范圍就限制在[0.5, 1)，但在這個(gè)范圍里有
3種可能的碼符2， 3和4，因此第1位沒(méi)有包含足夠的譯碼信息。在接受第2位之后就變成“10”，它落在
[0.5, 0.75)的間隔里，由于這兩位表示的符號(hào)都指向2開(kāi)始的間隔，因此就可斷定第一個(gè)符號(hào)是2。在接受
每位信息之后的譯碼情況如下表4-08所示。
表4-08 譯碼過(guò)程表
在上面的例子中，我們假定編碼器和譯碼器都知道消息的長(zhǎng)度，因此譯碼器的譯碼過(guò)程不會(huì)無(wú)限制地運(yùn)行
下去。實(shí)際上在譯碼器中需要添加一個(gè)專(zhuān)門(mén)的終止符，當(dāng)譯碼器看到終止符時(shí)就停止譯碼。
在算術(shù)編碼中需要注意的幾個(gè)問(wèn)題：
(1) 由于實(shí)際的計(jì)算機(jī)的精度不可能無(wú)限長(zhǎng)，運(yùn)算中出現(xiàn)溢出是一個(gè)明顯的問(wèn)題，但多數(shù)機(jī)器都有16位、
32位或者64位的精度，因此這個(gè)問(wèn)題可使用比例縮放方法解決。
(2) 算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔[0, 1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受
到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。
(3) 算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。
算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號(hào)的概率是固定的。在自適應(yīng)算術(shù)編碼
中，信源符號(hào)的概率根據(jù)編碼時(shí)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)地進(jìn)行修改，在編碼期間估算信源符號(hào)概率的過(guò)程叫
做建模。需要開(kāi)發(fā)動(dòng)態(tài)算術(shù)編碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切實(shí)際的。當(dāng)壓縮
消息時(shí)，我們不能期待一個(gè)算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過(guò)程中估算概率。因
此動(dòng)態(tài)建模就成為確定編碼器壓縮效率的關(guān)鍵。
接受的數(shù)字 間隔 譯碼輸出
1 [0.5, 1) -
0 [0.5, 0.75) 2
0 [0.5, 0.609375) 1
1 [0.5625, 0.609375) -
1 [0.59375, 0.609375) 3
… … …
第 9 頁(yè)
4
4.3 RLE編碼
在一幅圖像中經(jīng)常包含有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行
上有許多連續(xù)的像素都具有相同的顏色值。在這種情況下就不需要存儲(chǔ)每一個(gè)像素的顏色值，而僅僅存儲(chǔ)一個(gè)
像素的顏色值，以及具有相同顏色的像素?cái)?shù)目就可以，或者存儲(chǔ)一個(gè)像素的顏色值，以及具有相同顏色值的行
數(shù)。這種壓縮編碼稱(chēng)為行程編碼(run length encoding，RLE)，具有相同顏色并且是連續(xù)的像素?cái)?shù)目稱(chēng)為行程
長(zhǎng)度。
假定有一幅灰度圖像，第n行的像素值如圖4-05所示：
圖4-05 RLE編碼的概念
用RLE編碼方法得到的代碼為：80315084180。代碼中用黑體表示的數(shù)字是行程長(zhǎng)度，黑體字后面的數(shù)字代
表像素的顏色值。例如黑體字50代表有連續(xù)50個(gè)像素具有相同的顏色值，它的顏色值是8。
對(duì)比RLE編碼前后的代碼數(shù)可以發(fā)現(xiàn)，在編碼前要用73個(gè)代碼表示這一行的數(shù)據(jù)，而編碼后只要用11個(gè)代
碼表示代表原來(lái)的73個(gè)代碼，壓縮前后的數(shù)據(jù)量之比約為7:1，即壓縮比為7:1。這說(shuō)明RLE確實(shí)是一種壓縮技
術(shù)，而且這種編碼技術(shù)相當(dāng)直觀，也非常經(jīng)濟(jì)。
譯碼時(shí)按照與編碼時(shí)采用的相同規(guī)則進(jìn)行，還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。
RLE所能獲得的壓縮比有多大，這主要是取決于圖像本身的特點(diǎn)。如果圖像中具有相同顏色的圖像塊越
大，圖像塊數(shù)目越少，獲得的壓縮比就越高。反之，壓縮比就越小。
RLE壓縮編碼尤其適用于計(jì)算機(jī)生成的圖像，對(duì)減少圖像文件的存儲(chǔ)空間非常有效。然而，RLE對(duì)顏色豐富
的自然圖像就顯得力不從心，在同一行上具有相同顏色的連續(xù)像素往往很少，而連續(xù)幾行都具有相同顏色值的
連續(xù)行數(shù)就更少。如果仍然使用RLE編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來(lái)的圖像數(shù)據(jù)變得更
大。請(qǐng)注意，這并不是說(shuō)RLE編碼方法不適用于自然圖像的壓縮，相反，在自然圖像的壓縮中還真少不了RLE，
只不過(guò)是不能單純使用RLE一種編碼方法，需要和其他的壓縮編碼技術(shù)聯(lián)合應(yīng)用。
4.4 詞典編碼
有許多場(chǎng)合，開(kāi)始時(shí)不知道要編碼數(shù)據(jù)的統(tǒng)計(jì)特性，也不一定允許你事先知道它們的統(tǒng)計(jì)特性。因此，人
們提出了許許多多的數(shù)據(jù)壓縮方法，盡可能獲得最大的壓縮比。這些技術(shù)統(tǒng)稱(chēng)為通用編碼技術(shù)。詞典編碼
(Dictionary Encoding)技術(shù)就屬于這一類(lèi)。
4.4.1 詞典編碼的思想
詞典編碼(dictionary encoding)的根據(jù)是數(shù)據(jù)本身包含有重復(fù)代碼這個(gè)特性。例如文本文件和光柵圖像
就具有這種特性。詞典編碼法的種類(lèi)很多，歸納起來(lái)大致有兩類(lèi)。
第一類(lèi)詞典算法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過(guò)，然后輸出僅僅是指向早
期出現(xiàn)過(guò)的字符串的“指針”。這種編碼概念如圖4-06所示。
第 10 頁(yè)
4
圖4-06 第一類(lèi)詞典法編碼概念
這里所指的“詞典”是指用以前處理過(guò)的數(shù)據(jù)來(lái)表示編碼過(guò)程中遇到的重復(fù)部分。這類(lèi)編碼算法都是以
Abraham Lempel和Jakob Ziv在1977年開(kāi)發(fā)和發(fā)表的稱(chēng)為L(zhǎng)Z77算法為基礎(chǔ)的，例如1982年由Storer和Szymanski
改進(jìn)的稱(chēng)為L(zhǎng)ZSS算法 。
第二類(lèi)詞典算法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語(yǔ)詞典(dictionary of the phrases)”，這種短語(yǔ)
不一定是具有具體含義的短語(yǔ)，可以是任意字符的組合。編碼過(guò)程中遇到已經(jīng)在詞典中出現(xiàn)的“短語(yǔ)”時(shí)，編
碼器就輸出這個(gè)詞典中的短語(yǔ)的“索引號(hào)”，而不是短語(yǔ)本身。這個(gè)概念如圖4-07所示。
圖4-07 第二類(lèi)詞典法編碼概念
J.Ziv和A.Lempel在1978年首次發(fā)表了介紹這種編碼方法的文章。在他們的研究基礎(chǔ)上，Terry A.Weltch
在1984年發(fā)表了改進(jìn)這種編碼算法的文章，因此把這種編碼方法稱(chēng)為L(zhǎng)ZW(Lempel-Ziv Walch)壓縮編碼，在高
速硬盤(pán)控制器上 首先應(yīng)用了這種算法。
4.4.2 LZ77算法
為了更好地說(shuō)明LZ77算法的原理，首先介紹算法中用到的幾個(gè)術(shù)語(yǔ)：
(1) 輸入數(shù)據(jù)流(input stream)：要被壓縮的字符序列。
(2) 字符(character)：輸入數(shù)據(jù)流中的基本單元。
(3) 編碼位置(coding position)：輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，指前向緩沖存儲(chǔ)器中的開(kāi)始字
符。
(4) 前向緩沖存儲(chǔ)器(Lookahead buffer)：存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲(chǔ)器。
(5) 窗口(window)：指包含W個(gè)字符的窗口，字符是從編碼位置開(kāi)始向后數(shù)，也就是最后處理的W個(gè)字
符 。(滑動(dòng)窗口)
(6) 指針(pointer)：指向窗口中的匹配串的開(kāi)始位置且含長(zhǎng)度的指針。
LZ77編碼算法的核心是查找從前向緩沖存儲(chǔ)器開(kāi)始的與窗口中最長(zhǎng)的匹配串。編碼算法的具體執(zhí)行步驟如
下：
第 11 頁(yè)
4
(1) 把編碼位置設(shè)置到輸入數(shù)據(jù)流的開(kāi)始位置。
(2) 查找窗口中最長(zhǎng)的匹配串。
(3) 以“(Pointer, Length) Character”三元組的格式輸出，其中Pointer是指向窗口中匹配串的指針，
Length表示匹配字符的長(zhǎng)度，Characters是前向緩沖存儲(chǔ)器中的不匹配的第1個(gè)字符。沒(méi)有匹配的字符串時(shí)，
輸出“(0, 0) Character”
(4) 如果前向緩沖存儲(chǔ)器不是空的，則把編碼位置和窗口向前移(Length+1)個(gè)字符，然后返回到步驟2。
[例4.4] 待編碼的數(shù)據(jù)流如表4-09所示，編碼過(guò)程如表4-10所示。現(xiàn)作如下說(shuō)明：
(1) “步驟”欄表示編碼步驟。
(2) “位置”欄表示編碼位置，輸入數(shù)據(jù)流中的第1個(gè)字符為編碼位置1。
(3) “匹配串”欄表示窗口中找到的最長(zhǎng)的匹配串。
(4) “字符”欄表示匹配之后在前向緩沖存儲(chǔ)器中的第1個(gè)字符。
(5) “輸出”欄以“(Back_chars, Chars_length) Explicit_character”格式輸出。其中，
(Back_chars, Chars_length)是指向匹配串的指針，告訴譯碼器“在這個(gè)窗口中向后退Back_chars個(gè)字符然后
拷貝Chars_length個(gè)字符到輸出”，Explicit_character是真實(shí)字符。例如，表4-10中的輸出“(5,2) C”告
訴譯碼器回退5個(gè)字符，然后拷貝2個(gè)字符“AB”
表4-09待編碼的數(shù)據(jù)流
表4-10 編碼過(guò)程
4.4.3 LZSS算法
LZ77通過(guò)輸出真實(shí)字符解決了在窗口中出現(xiàn)沒(méi)有匹配串的問(wèn)題，但這個(gè)解決方案包含有冗余信息。冗余信
息表現(xiàn)在兩個(gè)方面，一是空指針，二是編碼器輸出的字符可能包含在下一個(gè)匹配串中的字符。
LZSS算法以比較有效的方法解決這個(gè)問(wèn)題，思想是如果匹配串的長(zhǎng)度比指針本身的長(zhǎng)度 （最小匹配串長(zhǎng)
度）長(zhǎng)就輸出指針，否則就輸出真實(shí)字符。由于輸出的壓縮數(shù)據(jù)流中包含有指針和字符本身，為了區(qū)分它們就
需要有額外的標(biāo)志位，即ID位。
LZSS編碼算法的具體執(zhí)行步驟如下：
(1) 把編碼位置置于輸入數(shù)據(jù)流的開(kāi)始位置。
(2) 在前向緩沖存儲(chǔ)器中查找與窗口中最長(zhǎng)的匹配串
① Pointer ：=匹配串指針。
② Length ：=匹配串長(zhǎng)度。
(3) 判斷匹配串長(zhǎng)度Length是否大于等于最小匹配串長(zhǎng)度(Length≥MIN_LENGTH)，
如果“是”：輸出指針，然后把編碼位置向前移動(dòng)Length個(gè)字符。
位置 1 2 3 4 5 6 7 8 9
字符 A A B C B B A B C
步驟 位置 匹配串 字符 輸出
1 1 -- A (0,0) A
2 2 A B (1,1) B
3 4 -- C (0,0) C
4 5 B B (2,1) B
5 7 A B C (5,2) C
第 12 頁(yè)
4
如果“否”：輸出前向緩沖存儲(chǔ)器中的第1個(gè)字符，然后把編碼位置向前移動(dòng)一個(gè)字符。
(4) 如果前向緩沖存儲(chǔ)器不是空的，就返回到步驟2。
[例4.5] 編碼字符串如表4-11所示，編碼過(guò)程如表4-12所示。現(xiàn)說(shuō)明如下：
(1) “步驟”欄表示編碼步驟。
(2) “位置”欄表示編碼位置，輸入數(shù)據(jù)流中的第1個(gè)字符為編碼位置1。
(3) “匹配”欄表示窗口中找到的最長(zhǎng)的匹配串。
(4) “字符”欄表示匹配之后在前向緩沖存儲(chǔ)器中的第1個(gè)字符。
(5) “輸出”欄的輸出為：
① 如果匹配串本身的長(zhǎng)度Length≥MIN_LENGTH，輸出指向匹配串的指針，格式為(Back_chars,
Chars_length)。該指針告訴譯碼器“在這個(gè)窗口中向后退Back_chars個(gè)字符然后拷貝Chars_length個(gè)字符到
輸出”。
② 如果匹配串本身的長(zhǎng)度Length≤MIN_LENGTH，則輸出真實(shí)的匹配串。
表4-11 輸入數(shù)據(jù)流
表4-12 編碼過(guò)程(MIN_LENGTH = 2)
在相同的計(jì)算環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡(jiǎn)單。這也就是為什么這種算
法成為開(kāi)發(fā)新算法的基礎(chǔ)，許多后來(lái)開(kāi)發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip, ARJ, LHArc和
ZOO等等，其差別僅僅是指針的長(zhǎng)短和窗口的大小等有所不同。
LZSS同樣可以和熵編碼聯(lián)合使用，例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用，它的后
續(xù)版本也采用霍夫曼編碼。
4.4.4 LZ78算法
在介紹LZ78算法之前，首先說(shuō)明在算法中用到的幾個(gè)術(shù)語(yǔ)和符號(hào)：
(1) 字符流(Charstream)：要被編碼的數(shù)據(jù)序列。
(2) 字符(Character)：字符流中的基本數(shù)據(jù)單元。
(3) 前綴(Prefix)： 在一個(gè)字符之前的字符序列。
(4) 綴-符串(String)：前綴＋字符。
(5) 碼字(Code word)：碼字流中的基本數(shù)據(jù)單元，代表詞典中的一串字符。
(6) 碼字流(Codestream)： 碼字和字符組成的序列，是編碼器的輸出。
(7) 詞典(Dictionary)： 綴-符串表。按照詞典中的索引號(hào)對(duì)每條綴-符串(String)指定一個(gè)碼字(Code
位置 1 2 3 4 5 6 7 8 9 10 11
字符 A A B B C B B A A B C
步驟 位置 匹配串 輸出
1 1 -- A
2 2 A A
3 3 -- B
4 4 B B
5 5 -- C
6 6 B B (3,2)
7 8 A A B (7,3)
8 11 C C
第 13 頁(yè)
4
word)。
(8) 當(dāng)前前綴(Current prefix)：在編碼算法中使用，指當(dāng)前正在處理的前綴，用符號(hào)P表示。
(9) 當(dāng)前字符(Current character)：在編碼算法中使用，指當(dāng)前前綴之后的字符，用符號(hào)C表示。
(10) 當(dāng)前碼字(Current code word)： 在譯碼算法中使用，指當(dāng)前處理的碼字，用W表示當(dāng)前碼字，
String.W表示當(dāng)前碼字的綴-符串。
1. 編碼算法
LZ78的編碼思想是不斷地從字符流中提取新的綴-符串(String)，通俗地理解為新“詞條”，然后用“代
號(hào)”也就是碼字(Code word)表示這個(gè)“詞條”。這樣一來(lái)，對(duì)字符流的編碼就變成了用碼字(Code word)去替
換字符流(Charstream)，生成碼字流(Codestream)，從而達(dá)到壓縮數(shù)據(jù)的目的。
在編碼開(kāi)始時(shí)詞典是空的，不包含任何綴-符串(string)。在這種情況下編碼器就輸出一個(gè)表示空字符串
的特殊碼字(例如“0”)和字符流中(Charstream)的第一個(gè)字符C，并把這個(gè)字符C添加到詞典中作為一個(gè)由一
個(gè)字符組成的綴-符串(string)。在編碼過(guò)程中，如果出現(xiàn)類(lèi)似的情況，也照此辦理。
在詞典中已經(jīng)包含某些綴-符串(String)之后，如果“當(dāng)前前綴P +當(dāng)前字符C”已經(jīng)在詞典中，就用字符C
來(lái)擴(kuò)展這個(gè)前綴，這樣的擴(kuò)展操作一直重復(fù)到獲得一個(gè)在詞典中沒(méi)有的綴-符串(String)為止。此時(shí)就輸出表
示當(dāng)前前綴P的碼字(Code word)和字符C，并把P+C添加到詞典中，然后開(kāi)始處理字符流(Charstream)中的下一
個(gè)前綴。
LZ78編碼器的輸出是碼字-字符(W,C)對(duì)，每次輸出一對(duì)到碼字流中，并用字符C擴(kuò)展與碼字W相對(duì)應(yīng)的綴-
符串(String)，生成新的綴-符串(String)，然后添加到詞典中。
LZ78編碼的具體算法如下：
步驟1： 在開(kāi)始時(shí)，詞典和當(dāng)前前綴P都是空的。
步驟2： 當(dāng)前字符C ：= 字符流中的下一個(gè)字符。
步驟3： 判斷P+C是否在詞典中：
(1) 如果“是”：用C擴(kuò)展P，讓P ：= P+C ；
(2) 如果“否”：
① 輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字和當(dāng)前字符C；
② 把字符串P+C 添加到詞典中。
③ 令P ：= 空值。
(3) 判斷字符流中是否還有字符需要編碼
① 如果“是”：返回到步驟2。
② 如果“否”：若當(dāng)前前綴P不是空的，輸出相應(yīng)于當(dāng)前前綴P的碼字，然后結(jié)束編碼。
2. 譯碼算法
在譯碼開(kāi)始時(shí)譯碼詞典是空的，它將在譯碼過(guò)程中從碼字流中重構(gòu)。每當(dāng)從碼字流中讀入一對(duì)碼字-字符
(W,C)對(duì)時(shí)，碼字就參考已經(jīng)在詞典中的綴-符串，然后把當(dāng)前碼字的綴-符串string.W 和字符C輸出到字符流
(Charstream)，而把當(dāng)前綴-符串(string.W+C)添加到詞典中。在譯碼結(jié)束之后，重構(gòu)的詞典與編碼時(shí)生成的
詞典完全相同。
LZ78譯碼的具體算法如下：
步驟1： 在開(kāi)始時(shí)詞典是空的。
步驟2： 當(dāng)前碼字W ：= 碼字流中的下一個(gè)碼字。
步驟3： 當(dāng)前字符C ：= 緊隨碼字之后的字符。
步驟4： 把當(dāng)前碼字的綴-符串(string.W)輸出到字符流(Charstream)，然后輸出字符C。
步驟5： 把string.W+C添加到詞典中。
步驟6： 判斷碼字流中是否還有碼字要譯
第 14 頁(yè)
4
(1) 如果“是”，就返回到步驟2。
(2) 如果“否”，則結(jié)束。
[例4.6] 編碼字符串如表4-13所示，編碼過(guò)程如表4-14所示。現(xiàn)說(shuō)明如下：
(1) “步驟”欄表示編碼步驟。
(2) “位置”欄表示在輸入數(shù)據(jù)中的當(dāng)前位置。
(3) “詞典”欄表示添加到詞典中的綴-符串，綴-符串的索引等于“步驟”序號(hào)。
(4) “輸出”欄以(當(dāng)前碼字W, 當(dāng)前字符C)簡(jiǎn)化為(W, C)的形式輸出。
表4-13 編碼字符串
表4-14 編碼過(guò)程
與LZ77相比，LZ78的最大優(yōu)點(diǎn)是在每個(gè)編碼步驟中減少了綴-符串(String)比較的數(shù)目，而壓縮率與LZ77
類(lèi)似。
4.4.5 LZW算法
在LZW算法中使用的術(shù)語(yǔ)與LZ78使用的相同，僅增加了一個(gè)術(shù)語(yǔ)—前綴根(Root)，它是由單個(gè)字符組成的
綴-符串(String)。在編碼原理上，LZW與LZ78相比有如下差別：
① LZW只輸出代表詞典中的綴-符串(String)的碼字(code word)。這就意味在開(kāi)始時(shí)詞典不能是空的，它
必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。
② 由于所有可能出現(xiàn)的單個(gè)字符都事先包含在詞典中，每次編碼開(kāi)始時(shí)都使用一個(gè)字符前綴(onecharacter
prefix)，因此在詞典中增加的第1個(gè)綴-符串有兩個(gè)字符。
現(xiàn)將LZW編碼算法和譯碼算法介紹如下。
1. 編碼算法
LZW編碼是圍繞稱(chēng)為詞典的轉(zhuǎn)換表來(lái)完成的。這張轉(zhuǎn)換表存放稱(chēng)為前綴(Prefix)的字符序列，并為每個(gè)表
項(xiàng)分配一個(gè)碼字(Code word)，或者叫做序號(hào)，如表4-15所示。這張轉(zhuǎn)換表實(shí)際上是把8位ASCII字符集進(jìn)行擴(kuò)
充，增加的符號(hào)用來(lái)表示在文本或圖像中出現(xiàn)的可變長(zhǎng)度ASCII字符串。擴(kuò)充后的代碼可用9位、10位、11位、
12位甚至更多的位來(lái)表示。Welch的論文中用了12位，12位可以有4096個(gè)不同的12位代碼，這就是說(shuō)，轉(zhuǎn)換表
有4096個(gè)表項(xiàng)，其中256個(gè)表項(xiàng)用來(lái)存放已定義的字符，剩下3840個(gè)表項(xiàng)用來(lái)存放前綴(Prefix)。
表4-15 詞典
位置 1 2 3 4 5 6 7 8 9
字符 A B B C B C A B A
步驟 位置 詞典 輸出
1 1 A (0,A)
2 2 B (0,B)
3 3 B C (2,C)
4 5 B C A (3,A)
5 8 B A (2,A)
碼字(Code word) 前綴(Prefix)
1
第 15 頁(yè)
4
LZW編碼器(軟件編碼器或硬件編碼器)就是通過(guò)管理這個(gè)詞典完成輸入與輸出之間的轉(zhuǎn)換。LZW編碼器的輸
入是字符流(Charstream)，字符流可以是用8位ASCII字符組成的字符串，而輸出是用n位(例如12位)表示的碼
字流(Codestream)，碼字代表單個(gè)字符或多個(gè)字符組成的字符串。
LZW編碼器使用了一種很實(shí)用的分析(parsing)算法，稱(chēng)為貪婪分析算法(greedy parsing algorithm)。在
貪婪分析算法中，每一次分析都要串行地檢查來(lái)自字符流(Charstream)的字符串，從中分解出已經(jīng)識(shí)別的最長(zhǎng)
的字符串，也就是已經(jīng)在詞典中出現(xiàn)的最長(zhǎng)的前綴(Prefix)。用已知的前綴(Prefix)加上下一個(gè)輸入字符C也
就是當(dāng)前字符(Current character)作為該前綴的擴(kuò)展字符，形成新的擴(kuò)展字符串——綴-符串(String)：
Prefix+C。這個(gè)新的綴-符串(String)是否要加到詞典中，還要看詞典中是否存有和它相同的綴-符串String。
如果有，那么這個(gè)綴-符串(String)就變成前綴(Prefix)，繼續(xù)輸入新的字符，否則就把這個(gè)綴-符串(String)
寫(xiě)到詞典中生成一個(gè)新的前綴(Prefix)，并分配給一個(gè)代碼。
LZW編碼算法的具體執(zhí)行步驟如下：
步驟1： 開(kāi)始時(shí)的詞典包含所有可能的根(Root)，而當(dāng)前前綴P是空的；
步驟2： 當(dāng)前字符(C) ：=字符流中的下一個(gè)字符；
步驟3： 判斷綴-符串P+C是否在詞典中
(1) 如果“是”：P ：= P+C // (用C擴(kuò)展P) ；
(2) 如果“否”
① 把代表當(dāng)前前綴P的碼字輸出到碼字流;
② 把綴-符串P+C添加到詞典;
③ 令P ：= C //(現(xiàn)在的P僅包含一個(gè)字符C);
步驟4： 判斷碼字流中是否還有碼字要譯
(1) 如果“是”，就返回到步驟2；
(2) 如果“否”
① 把代表當(dāng)前前綴P的碼字輸出到碼字流;
② 結(jié)束。
LZW編碼算法可用偽碼表示。開(kāi)始時(shí)假設(shè)編碼詞典包含若干個(gè)已經(jīng)定義的單個(gè)碼字。例如，256個(gè)字符的碼
字，用偽碼可以表示成：
… …
193 A
194 B
… …
255
… …
1305 abcdefxyF01234
… …
Dictionary[j] ← all n single-character， j＝1, 2， …，n
j ← n+1
Prefix ← read first Character in Charstream
while((C ← next Character)!=NULL)
第 16 頁(yè)
4
2. 譯碼算法
LZW譯碼算法中還用到另外兩個(gè)術(shù)語(yǔ)：
① 當(dāng)前碼字(Current code word)：指當(dāng)前正在處理的碼字，用cW表示，用string.cW表示當(dāng)前綴-符串；
② 先前碼字(Previous code word)：指先于當(dāng)前碼字的碼字，用pW表示，用string.pW表示先前綴-符
串。
LZW譯碼算法開(kāi)始時(shí)，譯碼詞典與編碼詞典相同，它包含所有可能的前綴根(roots)。LZW算法在譯碼過(guò)程
中會(huì)記住先前碼字(pW)，從碼字流中讀當(dāng)前碼字(cW)之后輸出當(dāng)前綴-符串string.cW，然后把用string.cW的
第一個(gè)字符擴(kuò)展的先前綴-符串string.pW添加到詞典中。
LZW譯碼算法的具體執(zhí)行步驟如下：
步驟1： 在開(kāi)始譯碼時(shí)詞典包含所有可能的前綴根(Root)。
步驟2： cW ：= 碼字流中的第一個(gè)碼字。
步驟3： 輸出當(dāng)前綴-符串string.cW到碼字流。
步驟4： 先前碼字pW ：= 當(dāng)前碼字cW。
步驟5： 當(dāng)前碼字cW ：= 碼字流中的下一個(gè)碼字。
步驟6： 判斷當(dāng)前綴-符串string.cW是否在詞典中
(1) 如果“是”，則：
① 把當(dāng)前綴-符串string.cW輸出到字符流。
② 把先前綴-符串string.pW + 當(dāng)前前綴-符串string.cW的第一個(gè)字符C添加到詞典。
(2) 如果“否”，則：
① 輸出先前綴-符串string.pW + 先前綴-符串string.pW的第一個(gè)字符到字符流，
② 把它添加到詞典中。
步驟7： 判斷碼字流中是否還有碼字要譯
(1) 如果“是”，就返回到步驟4。
(2) 如果“否”, 結(jié)束。
LZW譯碼算法可用偽碼表示如下：
Codestream ← cW for Prefix
Dictionary[j] ← all n single-character， j＝1, 2， …，n
j ← n+1
cW ← first code from Codestream
Charstream ← Dictionary[cW]
pW ← cW
While((cW ← next Code word)!=NULL)
第 17 頁(yè)
4
[例4.7] 編碼字符串如表4-16所示，編碼過(guò)程如表4-17所示。現(xiàn)說(shuō)明如下：
(1) “步驟”欄表示編碼步驟；
(2) “位置”欄表示在輸入數(shù)據(jù)中的當(dāng)前位置；
(3) “詞典”欄表示添加到詞典中的綴-符串，它的索引在括號(hào)中；
(4) “輸出”欄表示碼字輸出。
表4-16 被編碼的字符串
表4-17 LZW的編碼過(guò)程
表4-18解釋了譯碼過(guò)程。每個(gè)譯碼步驟譯碼器讀一個(gè)碼字，輸出相應(yīng)的綴-符串，并把它添加到詞典中。
例如，在步驟4中，先前碼字(2)存儲(chǔ)在先前碼字(pW)中，當(dāng)前碼字(cW)是(4)，當(dāng)前綴-符串string.cW是輸出
(“A B”)，先前綴-符串string.pW ("B")是用當(dāng)前綴-符串string.cW ("A")的第一個(gè)字符，其結(jié)果("B A")
添加到詞典中，它的索引號(hào)是(6)
表4-18 LZW的譯碼過(guò)程
LZW算法得到普遍采用，它的速度比使用LZ77算法的速度快，因?yàn)樗恍枰獔?zhí)行那么多的綴-符串比較操
位置 1 2 3 4 5 6 7 8 9
字符 A B B A B A B A C
步驟 位置 詞典 輸出
(1) A
(2) B
(3) C
1 1 (4) A B (1)
2 2 (5) B B (2)
3 3 (6) B A (2)
4 4 (7) A B A (4)
5 6 (8) A B A C (7)
6 -- -- -- (3)
步驟 代碼 詞典 輸出
(1) A
(2) B
(3) C
1 (1) -- -- A
2 (2) (4) A B B
3 (2) (5) B B B
4 (4) (6) B A A B
5 (7) (7) A B A A B A
6 (3) (8) A B A C C
第 18 頁(yè)
4
作。對(duì)LZW算法進(jìn)一步的改進(jìn)是增加可變的碼字長(zhǎng)度，以及在詞典中刪除老的綴-符串。在GIF圖像格式和UNIX
的壓縮程序中已經(jīng)采用了這些改進(jìn)措施之后的LZW算法。
LZW算法取得了專(zhuān)利，專(zhuān)利權(quán)的所有者是美國(guó)的一個(gè)大型計(jì)算機(jī)公司—Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)
軟件生產(chǎn)公司之外，可以免費(fèi)使用LZW算法。