LZW無損壓縮算法的研究與改進(jìn)

1、收稿日期 :2008-07-08基金項(xiàng)目 :陜西省自然科學(xué)基金 (2005F38 ; 陜西省教育科研基金(07J K306作者簡介 :許 霞 (1983- , 女 , 陜西榆林人 , 碩士研究生 , 研究方向 為算法設(shè)計(jì)、 框架技術(shù) ; 馬光思 , 教授 , 研究方向?yàn)橛?jì)算理論、 信息安 全、 Web 技術(shù)。L ZW 無損壓縮算法的研究與改進(jìn)許 霞 , 馬光思 , 魚 濤(西安建筑科技大學(xué) 信息與控制工程學(xué)院 , 陜西 西安 710055摘 要 :研究了數(shù)據(jù)壓縮技術(shù)領(lǐng)域中一種較有效的無損壓縮算法 L ZW 。 L ZW 的原理在于用字典中詞條的編碼代替被 壓縮數(shù)據(jù)中的字符串。 因此字典中的詞條

2、越長越多 , 壓縮比就越高。 加大字典的容量可以提高壓縮比。但字典的容量要 受到計(jì)算機(jī)內(nèi)存的限制 , 而且其字典也存在被填滿的可能。 這樣當(dāng)字典不能再加入新詞條后 , 過老的字典就不能保證高 的壓縮比。 為了解決這個(gè)問題 , 設(shè)計(jì)并實(shí)現(xiàn)了一種改進(jìn)算法 ; 分析了改進(jìn)算法對(duì)復(fù)雜度的影響 , 并選用一些典型文件對(duì)改 進(jìn)后的算法進(jìn)行了應(yīng)用測(cè)試。 測(cè)試結(jié)果表明 , 改進(jìn)后的算法具有較好的壓縮比和較理想的壓縮效率。 關(guān)鍵詞 :LZW 算法 ; 壓縮比 ; 字典 ; 匹配率中圖分類號(hào) :TP301. 6 文獻(xiàn)標(biāo)識(shí)碼 :A 文章編號(hào) :1673-629X (2009 04-0125-03R esearch

3、and Improvement on L ZW , (School of ,Xi and Tech. ,Xi an 710055,China Abstract :kind lossless compression algorithm in the data compression area of technology L ZW. The L ZW principle lies in the code replaces by the string of character in the packed data. Therefore in the dictionary entry is longe

4、r are more , the compression ratio is higher. Enlarges the dictionary capacity to be possible to enhance the compression ratio. But the dictionary capaci 2ty is limited by the computer memory , moreover it is possible to fill up the dictionary. After like this when the dictionary can t join the new

5、entry again , the excessively old dictionary can t guarantee the high compression ratio. In view of the L ZW algorithm s question , we designed and implemented one kind of improved algorithm ; After analyzed the effect of improved algorithm on the complexity ,selected some typical documents to test

6、the algorithm on the application. The test result indicated that the improved algorithm has the good com 2pression ratio and the ideal efficiency of compression.K ey w ords :L ZW algorithm ;compression ration ;dictionary ;matching rate0 引 言LZW 算法的實(shí)質(zhì)在于用字典中詞條的編碼代替被壓縮數(shù)據(jù)中的字符串。字典中的詞條越長越多 , 壓 縮比就越高 , 所以加大

7、字典的容量可以提高壓縮比 。 但字典容量受計(jì)算機(jī)內(nèi)存的限制 , 且其字典也存在被 填滿的可能 。 這樣當(dāng)字典不能再加入新詞條后 , 老字 典就不能保證高壓縮比。為了解決這個(gè)問題 , 可在壓 縮時(shí)監(jiān)視壓縮比 , 當(dāng)壓縮比下降時(shí) , 清除匹配率較小的 詞條而保留匹配率較大的詞條 , 這樣就能在重建字典 的同時(shí)提高壓縮比 1。1 L ZW 算法簡介LZW 繼承了 LZ77和 LZ78壓縮效果好、 速度快的優(yōu)點(diǎn) , 且算法描述易于接受。該算法能在不了解數(shù)據(jù) 統(tǒng)計(jì)特性前提下 , 使壓縮比接近已知統(tǒng)計(jì)特性時(shí)所能 達(dá)到的壓縮比 , 且易于實(shí)現(xiàn) , 是目前最常用的算法 。1. 1 LZW 算法基本原理LZW

8、壓縮算法的基本思想是建立一個(gè)編碼表 (轉(zhuǎn)換表 也稱串表 2, 將輸入字符串映射成定長的碼字 輸出 , 通常碼長設(shè)為 12bit 。 把數(shù)字圖像當(dāng)作一個(gè)一維 的比特串 , 算法在產(chǎn)生輸出串的同時(shí)動(dòng)態(tài)地更新編碼 表 , 這樣碼表與串表對(duì)應(yīng)產(chǎn)生壓縮圖像的特殊性質(zhì)。 串表是動(dòng)態(tài)產(chǎn)生的 , 編碼前先初始化 , 使其包含所有的 單字符串。 壓縮過程中 , 串表中不斷產(chǎn)生新字符串 (串 表中沒有的字符串 , 存儲(chǔ)新字符串時(shí)也保存與新串的 前綴相應(yīng)的子碼 3。 LZW 算法編碼是圍繞被稱為詞 典的轉(zhuǎn)換表來完成的 , 這張轉(zhuǎn)換表用來存放稱為前綴 的字符序列 (綴 -字符串表 , 并為每個(gè)表項(xiàng)分配一個(gè)第 19卷

9、第 4期 2009年 4月 計(jì) 算 機(jī) 技 術(shù) 與 發(fā) 展 COMPU TER TECHNOLO GY AND DEV ELOPMEN T Vol. 19 No. 4Apr. 2009碼字 , 或者叫做序號(hào) 。1. 2 LZW 算法描述STEP1開始時(shí)的詞典包含所有可能的根 (Root , 當(dāng)前前綴 P 為空 ;STEP2當(dāng)碼字流有碼字要譯時(shí) , 反復(fù)執(zhí)行 STEP3和 STEP4;STEP3當(dāng)前字符 C 置字符流中下一個(gè)字符 ; STEP4如果綴 -字符串 P +C 在詞典中 , 則(1 P 置 P +C (用 C 擴(kuò)展 P ;(2 把代表當(dāng)前前綴 P 的碼字輸出到碼字流 否則(3 把代表當(dāng)

10、前前綴 P 的碼字輸出到碼字流 ;(4 把綴 -字符串 P +C 添加到詞典 ;(5 P 置 C (現(xiàn)在 P 僅含單字符 C ;STEP5結(jié)束 。實(shí)現(xiàn) LZW 算法時(shí) , 按照上述流程進(jìn)行 。壓縮開 始 , 從原文件讀入第一個(gè)字符作為基碼 ;,為擴(kuò)展 ,否存在。 , 再讀入一個(gè)字符作 為擴(kuò)展符 , 重復(fù)上述過程。 若不存在 , 則形成新串的變 換碼 , 并輸出此變換碼 , 作為該新串字符的壓縮碼。將 字符串的擴(kuò)展符作為下一字符串的前綴 , 重復(fù)以上步 驟 , 繼續(xù)讀入字符 , 重復(fù)上述查找 、 填表 、 輸出操作 , 直 至文件末尾 4。1. 3 對(duì) LZW 算法進(jìn)一步分析就其外部特征來說 ,

11、LZW 壓縮技術(shù)對(duì)于可預(yù)測(cè)性 不大的數(shù)據(jù)具有較好的處理效果 , 常用于 GIF 格式的 圖像壓縮 , 其平均壓縮比在 2 1以上 , 最高壓縮比可達(dá) 到 3 1; 對(duì)于數(shù)據(jù)流中連續(xù)出現(xiàn)的字節(jié)和字串 ,LZW 具 有很高的壓縮比 ;LZW 除了用于圖像數(shù)據(jù)處理以外 , 還被用于文本程序等數(shù)據(jù)壓縮領(lǐng)域 ;LZW 是無損壓 縮 , 文件在壓縮前和解壓縮后完全一樣 , 不會(huì)有一位的 差錯(cuò) , 完整地保持了原文件的特點(diǎn) ;LZW 壓縮技術(shù)有 很多變體。例如常見的 ARC 、 PKARC 、 PKZIP 等高壓 縮程序 ; 對(duì)于任意寬度和像素位長度的圖像 , 都具有穩(wěn) 定的壓縮過程 。 壓縮和解壓縮速度較

12、快 ; 對(duì)機(jī)器硬件 要求不高 , 在 Intel80386計(jì)算機(jī)上即可進(jìn)行壓縮和解 壓縮。從其內(nèi)部原理來說 ,LZW 壓縮算法是基于字典的 LZ 系列算法的改進(jìn)型 , 其精義在于它不斷地讀取字符 串 , 如果在字典中找到匹配 , 那么繼續(xù)下去 , 一直讀到 字典里沒有為止 , 然后把它加入字典。初始狀態(tài)的字 典并非為空 , 字典初始狀態(tài)具有 256個(gè)項(xiàng) , 所以第一步 的時(shí)候要初始化 , 使詞典包含所有可能的根 , 這樣這個(gè) 算法就能循環(huán)起來。字典大小是有限制的 , 字典滿了 以后 , 復(fù)位字典再從頭開始。 LZW 的精華就在這里 , 為什么可以復(fù)位字典 ? 因?yàn)?LZW 壓縮算法不需要放 一

13、個(gè)大塊頭字典到它的壓縮數(shù)據(jù)里 , 在解壓縮的時(shí)候 , 可以根據(jù)輸入重新生成字典。傳統(tǒng) LZW 算法壓縮的原理在于用字典中詞條的 編碼代替被壓縮數(shù)據(jù)中的字符串 。 因此字典中的詞條 越長越多 , 壓縮比就越高 。加大字典的容量可以提高 壓縮比。 但字典的容量要受到計(jì)算機(jī)內(nèi)存的限制 , 而 且其字典也存在被填滿的可能 。 這樣當(dāng)字典不能再加 入新詞條后 , 過老的字典就不能保證高的壓縮比 5。 為了解決這個(gè)問題 , 在壓縮時(shí)必須監(jiān)視壓縮比 , 當(dāng)壓縮 比下降時(shí) ,較大詞條。 。針對(duì)原算法其字典存在被填滿的可能 , 而且字典 的容量要受到計(jì)算機(jī)內(nèi)存限制的不足 , 采用改進(jìn)的閾 值判斷操作和字典填滿之

14、后淘汰匹配率小的詞條的方 法。當(dāng)字典填滿時(shí) , 輸入一定長比特?cái)?shù)據(jù)流 , 用現(xiàn)有字 典對(duì)其進(jìn)行壓縮 , 然后判斷這個(gè)被壓縮的比特?cái)?shù)據(jù)流的壓縮比 (壓縮比 =輸出流的大小是否大于所指定 的閾值 , 如所得到的壓縮比大于所指定的閾值 , 則繼續(xù) 前面的操作 , 進(jìn)行壓縮、 判斷 ; 如所得到的壓縮比小于 所指定的閾值 , 則進(jìn)行刪除字典中多余詞條的操作 。 刪除字典中多余的詞條 , 首先在字典中設(shè)置清除 標(biāo)志 , 當(dāng)字典填滿后 , 在進(jìn)行閾值判斷時(shí) , 對(duì)每一個(gè)碼 字 (Code Word 的使用情況計(jì)數(shù) 。當(dāng)進(jìn)行閾值判斷所 得到的壓縮比小于指定的閾值時(shí) , 發(fā)出清除標(biāo)志 , 這時(shí) 根據(jù)字典中每一

15、個(gè)碼字使用的計(jì)數(shù)值大小進(jìn)行排序 , 對(duì)字典進(jìn)行相應(yīng)的重構(gòu) , 然后刪除排序靠后的若干項(xiàng) 。 這樣做不僅解決了字典被填滿和計(jì)算機(jī)內(nèi)存不足的問 題 , 而且在一定程度上避免了多余的計(jì)算 , 提高了算法 的壓縮比。2. 2 LZW 改進(jìn)算法描述STEP 1初始化 , 使開始詞典包含所有可能的根 (Root , 當(dāng)前前綴 P 置空 ;STEP2當(dāng)碼字流有碼字要譯時(shí) , 反復(fù)執(zhí)行 STEP3, STEP4, STEP5和 STEP6;STEP3讀入字符數(shù)據(jù)流中的下一個(gè)字符 C ; STEP4如果字符串 P +C 在當(dāng)前詞典中 ,(1 P 置 P +C (用字符 C 擴(kuò)展 P ;621 計(jì)算機(jī)技術(shù)與發(fā)展

16、第 19卷(2 把代表當(dāng)前前綴 P 的碼字輸出到碼字流 否則(3 輸出表示 P 的碼字到編碼數(shù)據(jù)流 ;(4 把字符串 P +C 添加到詞典 ;(5 P 置 C (此時(shí) P 僅含一個(gè)字符 C ;STEP5若字典未滿 , 則執(zhí)行 STEP3;STEP6如果壓縮比小于指定閾值 , 則清除匹配率 小的詞條 , 否則 , 返回 STEP1;STEP7結(jié)束 。3 算法分析LZW 算法大量依賴快速的字典查找 , 若直接檢索 字典 , 代碼執(zhí)行速度慢 , 其時(shí)間復(fù)雜度為 O (n 2 6。 引 入哈希表能有效提高字符串表的檢索效率及整體執(zhí)行 效率。 哈希表的容量與字典的容量均為表中不定長元 素的代碼數(shù)組 ,

17、用于存放哈希值相同的字符串代碼 。 實(shí) 際上 , 較好的哈希函數(shù)產(chǎn)生的重復(fù)值極少 ,近于 O (n , 但是 , , 壓縮比就會(huì)降 低。 為了提高壓縮比 , 就要重新對(duì)字典進(jìn)行初始化 , 即 重新構(gòu)造哈希表 。 這樣將會(huì)加大內(nèi)存開銷 , 也難以保證 新構(gòu)造哈希表中詞條的匹配率 。改進(jìn)的 LZW 算法刪除了匹配率小的詞條 , 并根據(jù) 字典中每個(gè)碼字的使用計(jì)數(shù)值大小進(jìn)行排序 。 一方面 釋放了大量無效內(nèi)存 ; 另一方面 , 對(duì)有序哈希表可以采 取二分查找 , 其時(shí)間復(fù)雜度降為 O (log n 。 由此可見 , 改進(jìn)算法不會(huì)影響經(jīng)典算法的復(fù)雜度 。4 應(yīng)用測(cè)試及性能分析為了測(cè)試改進(jìn)后算法的有效性

18、, 筆者選擇了幾個(gè) 不同類型的文件 , 分別用經(jīng)典 LZW 和改進(jìn) LZW 對(duì)其 壓縮 , 記錄壓縮前文件的大小 , 壓縮后文件的大小 , 壓 縮比及壓縮時(shí)間 。 應(yīng)用測(cè)試結(jié)果分別見表 1和表 2。 表 1 經(jīng)典 LZW 算法測(cè)試結(jié)果文件 類型壓縮前大小 (kb 壓縮后大小 (kb 壓縮比 (%所用 時(shí)間. doc 740. 0355. 221 101. 5秒 . ppt 1031. 0690. 715 101. 8秒 . bmp 786. 1188. 742 102. 7秒 . jpg 1888. 61885. 61 11. 7秒 . wmv 6451. 16386. 51 13. 7秒 .

19、 rar 8312. 28316. 11 13. 8秒 比較表 1與表 2的測(cè)試結(jié)果可見 :表 2 改進(jìn) LZW 算法測(cè)試結(jié)果文件類型壓縮前大小 (kb 壓縮后大小 (kb 壓縮比 (%所用時(shí)間. doc 740. 0309. 224 100. 8秒 . ppt 1031. 0580. 918 101. 1秒 . bmp 786. 1117. 445 101. 9秒 . jpg 1888. 61885. 61 11. 0秒 . wmv 6451. 16269. 81 12. 9秒 . rar 8312. 28316. 11 13. 1秒 (1 改進(jìn)后的 LZW 算法依然保留著經(jīng)典 LZW 算

20、法的本質(zhì)特點(diǎn) , 即壓縮 . doc ,. ppt 等文件時(shí) , 壓縮比較 高 , 壓縮效果好 ; 壓縮圖像類文件 . bmp (16位 時(shí) , 壓 縮比較高 , 壓縮效果好 , 而壓縮 . jpg 和 . wmv 時(shí) , 壓縮 比較低 , 因?yàn)?.J PG 、 . WMV , 一 , ; 對(duì) , 其 ,(2 對(duì)于幾類文件的壓縮 , 改進(jìn)的 LZW 算法不僅 壓縮比較高 , 且壓縮用時(shí)也較短 , 由此驗(yàn)證了改進(jìn)算法 的正確性和有效性。5 結(jié)束語LZW 壓縮算法是一種有效的數(shù)據(jù)壓縮算法。文 中在認(rèn)真研究 LZW 算法工作原理的基礎(chǔ)上 , 設(shè)計(jì)了一 種改進(jìn)算法 。 改進(jìn)算法實(shí)現(xiàn)了壓縮過程中自動(dòng)釋放內(nèi) 存 , 測(cè)試結(jié)果令人滿意 ,