當前位置:成語大全網 - 新華字典 - 用lzw算法壓縮用TC3.0的getimage函數提取的圖像數據進行壓縮和解壓

用lzw算法壓縮用TC3.0的getimage函數提取的圖像數據進行壓縮和解壓

在字典表之外單獨維護壹個散列表,該表中的每個元素都可以保存壹個字典表的索引值。例如,對於新字符串“al”,我們可以按照LZW傳統的做法,在字典表中依順序找出第壹個空的字典項,然後,通過散列函數,將該字典項的索引值(如257)存在散列表中的相應位置。實際輸出時,輸出字典表的索引值(而不是散列表的索引值)。這樣,解壓程序看到的數據內容和沒有使用散列算法時的數據內容完全壹致,只要按照LZW的傳統做法依次解壓就行了。

其實,關於在LZW中使用散列的具體做法有很多種,開發者基於時間/空間上的不同考慮,會選擇不同的解決方案。

LZW算法中,首先建立壹個字符串表,把每壹個第壹次出現的字符串放入串表中,並用壹個數字來表示,這個數字與此字符串在串表中的位置有關,並將這個數字存入壓縮文件中,如果這個字符串再次出現時,即可用表示它的數字來代替,並將這個數字存入文件中。壓縮完成後將串表丟棄。如"print" 字符串,如果在壓縮時用266表示,只要再次出現,均用266表示,並將"print"字符串存入串表中,在圖象解碼時遇到數字266,即可從串表中查出266所代表的字符串"print",在解壓縮時,串表可以根據壓縮數據重新生成。

壓縮算法的簡單示例,不是完全實現LZW算法,只是從最直觀的角度看lzw算法的思想

對原始數據ABCCAABCDDAACCDB進行LZW壓縮

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

-------------------------------------------------------

LZW數據壓縮算法的原理分析

我希望通過本文的介紹,能給那些目前不太了解lzw算法和該算法在gif圖像中應用,但渴望了解它的人壹些啟發和幫助。拋磚引玉而已,更希望園子裏面兄弟提出寶貴的意見。

1.LZW的全稱是什麽?

Lempel-Ziv-Welch (LZW).

2. LZW的簡介和壓縮原理是什麽?

LZW壓縮算法是壹種新穎的壓縮方法,由Lemple-Ziv-Welch 三人***同創造,用他們的名字命名。它采用了壹種先進的串表壓縮,將每個第壹次出現的串放在壹個串表中,用壹個數字來表示串,壓縮文件只存貯數字,則不存貯串,從而使圖象文件的壓縮效率得到較大的提高。奇妙的是,不管是在壓縮還是在解壓縮的過程中都能正確的建立這個串表,壓縮或解壓縮完成後,這個串表又被丟棄。

LZW算法中,首先建立壹個字符串表,把每壹個第壹次出現的字符串放入串表中,並用壹個數字來表示,這個數字與此字符串在串表中的位置有關,並將這個數字存入壓縮文件中,如果這個字符串再次出現時,即可用表示它的數字來代替,並將這個數字存入文件中。壓縮完成後將串表丟棄。如"print" 字符串,如果在壓縮時用266表示,只要再次出現,均用266表示,並將"print"字符串存入串表中,在圖象解碼時遇到數字266,即可從串表中查出266所代表的字符串"print",在解壓縮時,串表可以根據壓縮數據重新生成。

3.在詳細介紹算法之前,先列出壹些與該算法相關的概念和詞匯

1)'Character': 字符,壹種基礎數據元素,在普通文本文件中,它占用1個單獨的byte,而在圖像中,它卻是 壹種代表給定像素顏色的索引值。

2)'CharStream':數據文件中的字符流。

3)'Prefix':前綴。如這個單詞的含義壹樣,代表著在壹個字符最直接的前壹個字符。壹個前綴字符長度可以為0,壹個prefix和壹個character可以組成壹個字符串(string),

4)'Suffix': 後綴,是壹個字符,壹個字符串可以由(A,B)來組成,A是前綴,B是後綴,當A長度為0的時候,代表Root,根

5)'Code:碼,用於代表壹個字符串的位置編碼

6)'Entry',壹個Code和它所代表的字符串(string)

4.壓縮算法的簡單示例,不是完全實現LZW算法,只是從最直觀的角度看lzw算法的思想

對原始數據ABCCAABCDDAACCDB進行LZW壓縮

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

5.LZW算法的適用範圍

為了區別代表串的值(Code)和原來的單個的數據值(String),需要使它們的數值域不重合,上面用0-3來代表A-D,那麽AB就必須用大於3的數值來代替,再舉另外壹個例子,原來的數值範圍可以用8bit來表示,那麽就認為原始的數的範圍是0~255,壓縮程序生成的標號的範圍就不能為0~255(如果是0-255,就重復了)。只能從256開始,但是這樣壹來就超過了8位的表示範圍了,所以必須要擴展數據的位數,至少擴展壹位,但是這樣不是增加了1個字符占用的空間了麽?但是卻可以用壹個字符代表幾個字符,比如原來255是8bit,但是現在用256來表示254,255兩個數,還是劃得來的。從這個原理可以看出LZW算法的適用範圍是原始數據串最好是有大量的子串多次重復出現,重復的越多,壓縮效果越好。反之則越差,可能真的不減反增了。

6.LZW算法中特殊標記

隨著新的串(string)不斷被發現,標號也會不斷地增長,如果原數據過大,生成的標號集(string table)會越來越大,這時候操作這個集合就會產生效率問題。如何避免這個問題呢?Gif在采用lzw算法的做法是當標號集足夠大的時候,就不能增大了,幹脆從頭開始再來,在這個位置要插入壹個標號,就是清除標誌CLEAR,表示從這裏我重新開始構造字典,以前的所有標記作廢,開始使用新的標記。

這時候又有壹個問題出現,足夠大是多大?這個標號集的大小為比較合適呢?理論上是標號集大小越大,則壓縮比率就越高,但開銷也越高。 壹般根據處理速度和內存空間連個因素來選定。GIF規範規定的是12位,超過12位的表達範圍就推倒重來,並且GIF為了提高壓縮率,采用的是變長的字長。比如說原始數據是8位,那麽壹開始,先加上壹位再說,開始的字長就成了9位,然後開始加標號,當標號加到512時,也就是超過9為所能表達的最大數據時,也就意味著後面的標號要用10位字長才能表示了,那麽從這裏開始,後面的字長就是10位了。依此類推,到了2^12也就是4096時,在這裏插壹個清除標誌,從後面開始,從9位再來。

GIF規定的清除標誌CLEAR的數值是原始數據字長表示的最大值加1,如果原始數據字長是8,那麽清除標誌就是256,如果原始數據字長為4那麽就是16。另外GIF還規定了壹個結束標誌END,它的值是清除標誌CLEAR再加1。由於GIF規定的位數有1位(單色圖),4位(16色)和8位(256色),而1位的情況下如果只擴展1位,只能表示4種狀態,那麽加上壹個清除標誌和結束標誌就用完了,所以1位的情況下就必須擴充到3位。其它兩種情況初始的字長就為5位和9位。此處參照了/whycadi/

7.用lzw算法壓縮原始數據的示例分析

輸入流,也就是原始的數據為:255,24,54,255,24,255,255,24,5,123,45,255,24,5,24,54..................

這個正好可以看到是gif文件中像素數組的壹部分,如何對它進行壓縮

因為原始數據可以用8bit來表示,故清除標誌Clear=255+1 =256,結束標誌為End=256+1=257,目前標號集為

0 1 2 3 .................................................................................255 CLEAR END

第壹步,讀取第壹個字符為255,在標記表裏面查找,255已經存在,我們已經認識255了,不做處理

第二步,取第二個字符,此時前綴為A,形成當前的Entry為(255,24),在標記集合不存在,我們並不認識255,24好,這次妳小子來了,我就記住妳,把它在標記集合中標記為258,然後輸出前綴A,保留後綴24,並作為下壹次的前綴(後綴變前綴)

第三步,取第三個字符為54,當前Entry(24,54),不認識,記錄(24,54)為標號259,並輸出24,後綴變前綴

第四部:取第四個字符255,Entry=(54,255),不認識,記錄(54,255)為標號260,輸出54,後綴變前綴

第五步 取第5個字符24,entry=(255,24),啊,認識妳,這不是老258麽,於是把字符串規約為258,並作為前綴

第六步 取第六個字符255,entry=(258,255),不認識,記錄(258,255)為261,輸出258,後綴變前綴

.......

壹直處理到最後壹個字符