1.LZW的全稱是什么?

　　Lempel-Ziv-Welch (LZW).

2. LZW的簡(jiǎn)介和壓縮原理是什么？

　　LZW壓縮算法是一種新穎的壓縮方法，由Lemple-Ziv-Welch 三人共同創(chuàng)造，用他們的名字命名。它采用了一種先進(jìn)的串表壓縮，將每個(gè)第一次出現(xiàn)的串放在一個(gè)串表中，用一個(gè)數(shù)字來(lái)表示串，壓縮文件只存貯數(shù)字，則不存貯串，從而使圖象文件的壓縮效率得到較大的提高。奇妙的是，不管是在壓縮還是在解壓縮的過(guò)程中都能正確的建立這個(gè)串表，壓縮或解壓縮完成后，這個(gè)串表又被丟棄。

　　LZW算法中，首先建立一個(gè)字符串表，把每一個(gè)第一次出現(xiàn)的字符串放入串表中，并用一個(gè)數(shù)字來(lái)表示，這個(gè)數(shù)字與此字符串在串表中的位置有關(guān)，并將這個(gè)數(shù)字存入壓縮文件中，如果這個(gè)字符串再次出現(xiàn)時(shí)，即可用表示它的數(shù)字來(lái)代替，并將這個(gè)數(shù)字存入文件中。壓縮完成后將串表丟棄。如"print" 字符串，如果在壓縮時(shí)用266表示，只要再次出現(xiàn)，均用266表示，并將"print"字符串存入串表中，在圖象解碼時(shí)遇到數(shù)字266，即可從串表中查出266所代表的字符串"print"，在解壓縮時(shí)，串表可以根據(jù)壓縮數(shù)據(jù)重新生成。

3.在詳細(xì)介紹算法之前，先列出一些與該算法相關(guān)的概念和詞匯

　　1)'Character': 字符，一種基礎(chǔ)數(shù)據(jù)元素，在普通文本文件中，它占用1個(gè)單獨(dú)的byte，而在圖像中，它卻是 一種代表給定像素顏色的索引值。
　　2)'CharStream'：數(shù)據(jù)文件中的字符流。
　　3)'Prefix':前綴。如這個(gè)單詞的含義一樣，代表著在一個(gè)字符最直接的前一個(gè)字符。一個(gè)前綴字符長(zhǎng)度可以為0,一個(gè)prefix和一個(gè)character可以組成一個(gè)字符串(string),
　　4)'Suffix': 后綴，是一個(gè)字符，一個(gè)字符串可以由(A,B)來(lái)組成，A是前綴,B是后綴,當(dāng)A長(zhǎng)度為0的時(shí)候，代表Root，根
　　5)'Code:碼,用于代表一個(gè)字符串的位置編碼
　　6)'Entry'，一個(gè)Code和它所代表的字符串(string)

4.壓縮算法的簡(jiǎn)單示例，不是完全實(shí)現(xiàn)LZW算法，只是從最直觀的角度看lzw算法的思想

　　對(duì)原始數(shù)據(jù)ABCCAABCDDAACCDB進(jìn)行LZW壓縮

　　原始數(shù)據(jù)中，只包括4個(gè)字符(Character),A,B,C,D,四個(gè)字符可以用一個(gè)2bit的數(shù)表示，0-A,1-B,2-C,3-D,從最直觀的角度看，原始字符串存在重復(fù)字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以替代表示為:45A4CDDAA5DB,這樣是不是就比原數(shù)據(jù)短了一些呢！

5.LZW算法的適用范圍

　　為了區(qū)別代表串的值(Code)和原來(lái)的單個(gè)的數(shù)據(jù)值(String)，需要使它們的數(shù)值域不重合，上面用0-3來(lái)代表A-D,那么AB就必須用大于3的數(shù)值來(lái)代替，再舉另外一個(gè)例子，原來(lái)的數(shù)值范圍可以用8bit來(lái)表示，那么就認(rèn)為原始的數(shù)的范圍是0～255，壓縮程序生成的標(biāo)號(hào)的范圍就不能為0～255（如果是0-255，就重復(fù)了）。只能從256開(kāi)始，但是這樣一來(lái)就超過(guò)了8位的表示范圍了，所以必須要擴(kuò)展數(shù)據(jù)的位數(shù)，至少擴(kuò)展一位，但是這樣不是增加了1個(gè)字符占用的空間了么？但是卻可以用一個(gè)字符代表幾個(gè)字符，比如原來(lái)255是8bit,但是現(xiàn)在用256來(lái)表示254，255兩個(gè)數(shù)，還是劃得來(lái)的。從這個(gè)原理可以看出LZW算法的適用范圍是原始數(shù)據(jù)串最好是有大量的子串多次重復(fù)出現(xiàn)，重復(fù)的越多，壓縮效果越好。反之則越差，可能真的不減反增了。

6.LZW算法中特殊標(biāo)記

　　隨著新的串(string)不斷被發(fā)現(xiàn)，標(biāo)號(hào)也會(huì)不斷地增長(zhǎng)，如果原數(shù)據(jù)過(guò)大，生成的標(biāo)號(hào)集（string table)會(huì)越來(lái)越大，這時(shí)候操作這個(gè)集合就會(huì)產(chǎn)生效率問(wèn)題。如何避免這個(gè)問(wèn)題呢?Gif在采用lzw算法的做法是當(dāng)標(biāo)號(hào)集足夠大的時(shí)候，就不能增大了，干脆從頭開(kāi)始再來(lái)，在這個(gè)位置要插入一個(gè)標(biāo)號(hào)，就是清除標(biāo)志CLEAR，表示從這里我重新開(kāi)始構(gòu)造字典，以前的所有標(biāo)記作廢，開(kāi)始使用新的標(biāo)記。
這時(shí)候又有一個(gè)問(wèn)題出現(xiàn)，足夠大是多大？這個(gè)標(biāo)號(hào)集的大小為比較合適呢？理論上是標(biāo)號(hào)集大小越大，則壓縮比率就越高，但開(kāi)銷也越高。 一般根據(jù)處理速度和內(nèi)存空間連個(gè)因素來(lái)選定。GIF規(guī)范規(guī)定的是12位，超過(guò)12位的表達(dá)范圍就推倒重來(lái)，并且GIF為了提高壓縮率，采用的是變長(zhǎng)的字長(zhǎng)。比如說(shuō)原始數(shù)據(jù)是8位，那么一開(kāi)始，先加上一位再說(shuō)，開(kāi)始的字長(zhǎng)就成了9位，然后開(kāi)始加標(biāo)號(hào)，當(dāng)標(biāo)號(hào)加到512時(shí)，也就是超過(guò)9為所能表達(dá)的最大數(shù)據(jù)時(shí)，也就意味著后面的標(biāo)號(hào)要用10位字長(zhǎng)才能表示了，那么從這里開(kāi)始，后面的字長(zhǎng)就是10位了。依此類推，到了2^12也就是4096時(shí)，在這里插一個(gè)清除標(biāo)志，從后面開(kāi)始，從9位再來(lái)。
GIF規(guī)定的清除標(biāo)志CLEAR的數(shù)值是原始數(shù)據(jù)字長(zhǎng)表示的最大值加1，如果原始數(shù)據(jù)字長(zhǎng)是8，那么清除標(biāo)志就是256，如果原始數(shù)據(jù)字長(zhǎng)為4那么就是16。另外GIF還規(guī)定了一個(gè)結(jié)束標(biāo)志END，它的值是清除標(biāo)志CLEAR再加1。由于GIF規(guī)定的位數(shù)有1位（單色圖），4位（16色）和8位（256色），而1位的情況下如果只擴(kuò)展1位，只能表示4種狀態(tài)，那么加上一個(gè)清除標(biāo)志和結(jié)束標(biāo)志就用完了，所以1位的情況下就必須擴(kuò)充到3位。其它兩種情況初始的字長(zhǎng)就為5位和9位。此處參照了http://blog.csdn.net/whycadi/

7.用lzw算法壓縮原始數(shù)據(jù)的示例分析

　　輸入流，也就是原始的數(shù)據(jù)為:255,24,54,255,24,255,255,24,5,123,45,255,24,5,24,54..................
　　這個(gè)正好可以看到是gif文件中像素?cái)?shù)組的一部分，如何對(duì)它進(jìn)行壓縮
　　因?yàn)樵紨?shù)據(jù)可以用8bit來(lái)表示，故清除標(biāo)志Clear=255+1 =256,結(jié)束標(biāo)志為End=256+1=257，目前標(biāo)號(hào)集為
　　0 1 2 3 .................................................................................255 CLEAR END
　　第一步,讀取第一個(gè)字符為255,在標(biāo)記表里面查找，255已經(jīng)存在，我們已經(jīng)認(rèn)識(shí)255了，不做處理
　　第二步,取第二個(gè)字符，此時(shí)前綴為A,形成當(dāng)前的Entry為(255,24),在標(biāo)記集合不存在，我們并不認(rèn)識(shí)255,24好，這次你小子來(lái)了，我就記住你，把它在標(biāo)記集合中標(biāo)記為258,然后輸出前綴A,保留后綴24，并作為下一次的前綴（后綴變前綴)
　　第三步，取第三個(gè)字符為54，當(dāng)前Entry(24,54),不認(rèn)識(shí)，記錄(24,54)為標(biāo)號(hào)259,并輸出24,后綴變前綴
　　第四部：取第四個(gè)字符255,Entry=(54,255),不認(rèn)識(shí)，記錄(54,255)為標(biāo)號(hào)260,輸出54,后綴變前綴
　　第五步   取第5個(gè)字符24，entry=(255,24),啊，認(rèn)識(shí)你，這不是老258么，于是把字符串規(guī)約為258，并作為前綴
　　第六步  取第六個(gè)字符255,entry=(258,255)，不認(rèn)識(shí)，記錄(258,255)為261,輸出258,后綴變前綴
　　.......
　　一直處理到最后一個(gè)字符,
　　用一個(gè)表記錄處理過(guò)程
　　CLEAR=256,END=257

.....

上面這個(gè)示例有些不能完整體現(xiàn)，另外一個(gè)例子是
原輸入數(shù)據(jù)為:A B A B A B A B B B A B A B A A C D A C D A D C A B A A A B A B .....
采用LZW算法對(duì)其進(jìn)行壓縮，壓縮過(guò)程用一個(gè)表來(lái)表述為:
注意原數(shù)據(jù)中只包含4個(gè)character,A,B,C,D
用兩bit即可表述，根據(jù)lzw算法，首先擴(kuò)展一位變?yōu)?為,Clear=2的2次方+1=4; End=4+1=5;
初始標(biāo)號(hào)集因該為

而壓縮過(guò)程為:

.....
當(dāng)進(jìn)行到第12步的時(shí)候，標(biāo)號(hào)集應(yīng)該為

8.LZW算法的偽代碼實(shí)現(xiàn)

STRING = get input character
WHILE there are still input characters DO
 CHARACTER = get input character
 IF STRING+CHARACTER is in the string table then
  STRING = STRING+character
 ELSE
  output the code for STRING
  add STRING+CHARACTER to the string table
  STRING = CHARACTER
 END of IF
END of WHILE
output the code for STRING 

9.LZW算法的流程圖

沒(méi)有安visio,畫(huà)了一個(gè)，比較難看，

以上就是本文的全部?jī)?nèi)容，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論