LZW碼的編譯碼實現(xiàn)與應用探討

摘 要

現(xiàn)代社會中，信息無處不存在于我們的周圍。信息的傳遞是信息源通過某種渠道傳遞到信宿。從熵的角度來講，信息里包含一些冗余的信息。這無疑給信息的存儲和傳輸帶來很大的不方便。那么有沒有方法解決這個問題呢？人們應用了數(shù)據(jù)壓縮技術(shù)，使得信息里包含的冗余信息減少。數(shù)據(jù)壓縮已經(jīng)被廣泛地應用到當今的網(wǎng)絡環(huán)境和多媒體環(huán)境中。
在數(shù)據(jù)壓縮的分類里，可分為無損壓縮和有損壓縮，在無損壓縮技術(shù)里實現(xiàn)算法有霍夫曼編碼，香農(nóng)編碼，算數(shù)編碼，字典碼編碼。
本文從介紹數(shù)據(jù)壓縮的背景，研究意義及發(fā)展入手，然后討論了字典碼模型，介紹LZ77算法，LZ78算法以及LZW算法。其中，主要研究探討LZW算法及其優(yōu)缺點。針對LZW算法的缺點，給出了相應的解決方法。   
在本項工作中，LZW算法的實現(xiàn)是基于VS2008這個開發(fā)平臺的，所用的開發(fā)語言為C++，主要內(nèi)容是實現(xiàn)LZW算法的編碼和譯碼。LZW算法與其他算法相比具有編譯碼容易，易于軟硬件實現(xiàn)，且其價格低廉，運算速度快等特點，不失為一種有效的信源壓縮編碼方法，本項工作對LZW編譯碼的應用具有一定的實際意義。

關鍵字：LZW算法，數(shù)據(jù)壓縮，字典碼

Abstract

In this modern society,information surrounds us everywhere.Information transfetion means information transfers form information source to destination through some way. From a certain angle of entropy,information includes some redundancy,which,of course,brings much inconvenience to the storage and the transfer of information.Then,is there any way to solve this problem？Naturally,people can reach this goal through data compression,which makes redundancy more less.Data compression has already applied in network enviroment and mutimedia enviroment,because of its effect.
Data conpression can be divided to lossless compression and lossy compression.In lossless compression,there are Huffman coding,Shannon coding,dictionary coding and arithmetic coding.
This article starts with background ,research significance and development of data compression.And then discusses the model of the dictionary coding,which includes LZ77 algorithm,LZ78 algorithm and LZW algorithm.Among them,we will  
emphasize LZW algorithm.Futher more,we will discuss the disadvantages and disadvantages.At last we come out with improvement according to the disadvantage.
  At this design,the implementation of LZW algorithm is based on VS2008 this platform.The language used in this paper is c++.We will achieve LZW compression and decompression.LZW algorithm,compared with other algorithms has the advantage of easily compiling,easily complement on hardware and software,cheap and work quckily,and of course it’s a good method to compress information source.This work has certain significance for the application of LZW algorithm.

keyword：LZW algorithm,data compression，coding
 

目錄

摘 要 I
Abstract II
第一章 緒論 1
1.1課題背景和意義 1
1.1.1數(shù)據(jù)壓縮的發(fā)展 1
1.1.2 數(shù)據(jù)壓縮的性能 3
1.2 數(shù)據(jù)壓縮的分類 3
1.3本章小結(jié) 4
第二章 字典算法 5
2.1 字典算法產(chǎn)生的背景 5
2.2 LZ77算法 5
2.2.1 LZ77算法 5
2.2.2 LZ77算法的問題 7
2.3 LZ78算法 7
2.3.1 LZ78算法詳述 7
2.3.2 LZ78算法編碼舉例 9
2.3.3 LZ78算法的性能 11
2.4 本章小結(jié) 12
第三章 LZW算法原理 13
3.1 LZW算法編碼原理 13
3.1.1 LZW算法的特點 13
3.1.2 LZW算法的原理 13
3.2 LZW算法譯碼原理 14
3.3 本章小結(jié) 15
第四章LZW算法的討論 16
4.1 LZW算法的優(yōu)缺點 16
4.2 LZW算法的改進 16
4.3 LZ77算法，LZ78算法和LZW算法比較 16
4.4 LZW算法對不同長度信源的壓縮效果 17
4.5 本章小節(jié) 18
第五章 LZW算法的實現(xiàn) 19
5.1 編碼算法 19
5.2 解碼算法 23
5.3 本章小結(jié) 25
結(jié)論與討論 26
參考文獻 28
致謝 29