用C++实现数据无损压缩、解压(使用LZW算法)_图文

1、用C+实现数据无损压缩、解压（使用LZW算法）LZW压缩算法由Lemple-Ziv-Welch三人共同创造，用他们的名字命名。LZW就是通过建立一个字符串表，用较短的代码来表示较长的字符串来实现压缩。LZW压缩算法是Unisys的专利，有效期到2003年，所以对它的使用是有限制的。字符串和编码的对应关系是在压缩过程中动态生成的，并且隐含在压缩数据中，解压的时候根据表来进行恢复，算是一种无损压缩。个人认为LZW很适用于嵌入式系统上。因为：1、压缩和解压速度比较快，尤其是解压速度；2、占用资源少；3、压缩比也比较理想；4、适用于文本和图像等出现连续重复字节串的数据流。LZW算法有一点比较特别，就是

2、压缩过程中产生的字符串对应表，不需要保存到压缩数据中，因为这个表在解压过程中能自动生成回来。LZW算法比较简单，我是按照这本书上写的算法来编程的： 10227717016.jpg (124.6 KB2009-1-5 11:5710227717017.jpg (123.14 KB2009-1-5 11:57以下是源代码： 复制内容到剪贴板 代码:class LZWCoder private:         struct TStr             &

3、#160;            char *string;                 unsigned int len;                  TStr StrTable4097;         unsigned int Ite

4、mPt;         unsigned int BytePt;         unsigned char BitPt;         unsigned char Bit8;         unsigned char Bits;         unsigned int OutBytes;

5、        void InitStrTable(;         void CopyStr(TStr *d, TStr s;         void StrJoinChar(TStr *s, char c;         unsigned int InStrTable(TStr s;        

6、 void AddTableEntry(TStr s;         void WriteCode(char *dest, unsigned int b;         unsigned int GetNextCode(char *src;         void StrFromCode(TStr *s, unsigned int c;        

7、 void WriteString(char *dest, TStr s; public:         unsigned int Encode(char *src, unsigned int len, char *dest;         unsigned int Decode(char *src, unsigned int *len, char *dest;         LZWCoder(; &

8、#160;       LZWCoder(; ; void LZWCoder:InitStrTable(         unsigned int i;         for(i = 0; i < 256; i +                         

9、; StrTablei.string = (char *realloc(StrTablei.string, 1;                 StrTablei.string0 = i;                 StrTablei.len = 1;                

10、0; StrTable256.string = NULL;         StrTable256.len = 0;         StrTable257.string = NULL;         StrTable257.len = 0;         ItemPt = 257;       

11、0; Bits = 9; void LZWCoder:CopyStr(TStr *d, TStr s         unsigned int i;         d->string = (char *realloc(d->string, s.len;         for(i = 0; i < s.len; i +         &

12、#160;       d->stringi = s.stringi;         d->len = s.len; void LZWCoder:StrJoinChar(TStr *s, char c         s->string = (char *realloc(s->string, s->len + 1;         s->s

13、trings->len + = c; unsigned int LZWCoder:InStrTable(TStr s         unsigned int i,j;         bool b;         for(i = 0; i <= ItemPt; i +                &#

14、160;         if(StrTablei.len = s.len                                         b = true;              

15、;           for(j = 0; j < s.len; j +                                 if(StrTablei.stringj != s.stringj            &#

16、160;                                                             b = false;      

17、0;                                  break;                                  

18、0;                       if(b return i;                                  return 65535; void LZWCoder:AddTableEntry(

19、TStr s         CopyStr(&StrTable+ItemPt, s; void LZWCoder:WriteCode(char *dest, unsigned int b         unsigned char i;         for(i = 0; i < Bits; i+             

20、;             BitBitPt + = (b & (1 << (Bits - i - 1 != 0;                 if(BitPt = 8                            &

21、#160;            BitPt = 0;                         destBytePt + = (Bit0 << 7                       

22、;                  + (Bit1 << 6                                         + (Bit2 << 5     

23、;                                    + (Bit3 << 4                               

24、;          + (Bit4 << 3                                         + (Bit5 << 2             

25、;                            + (Bit6 << 1                                      

26、   + Bit7;                          unsigned int LZWCoder:GetNextCode(char *src         unsigned char i;         unsigned int c = 0;      &#

27、160;  for(i = 0; i < Bits; i +                          c = (c << 1 + (srcBytePt & (1 << (8 - (BitPt + - 1 != 0;                 if(BitPt = 8

28、                                         BitPt = 0;                         BytePt +; 

29、0;                                return c; void LZWCoder:StrFromCode(TStr *s, unsigned int c         CopyStr(s, StrTablec; void LZWCoder:WriteString(char *dest, TSt

30、r s         unsigned int i;         for(i = 0; i < s.len; i+                 destOutBytes + = s.stringi; unsigned int LZWCoder:Encode(char *src, unsigned int len, char *dest    

31、     TStr Omega, t;         char k;         unsigned int i;         unsigned int p;         BytePt = 0;         BitPt = 0;  

32、      InitStrTable(;         WriteCode(dest, 256;         Omega.string = NULL;         Omega.len = 0;         t.string = NULL;       &#

33、160; t.len = 0;         for(i = 0; i < len; i +                          k = srci;                 CopyStr(&t, Omega;  

34、60;             StrJoinChar(&t, k;                 if(InStrTable(t != 65535                         CopyStr(&Omega, t;

35、60;               else                                         WriteCode(dest, InStrTable(Omega;       &#

36、160;                 AddTableEntry(t;                         switch(ItemPt                     

37、0;                                    case 512: Bits = 10; break;                          

38、60;     case 1024: Bits = 11; break;                                 case 2048: Bits = 12; break;                 

39、               case 4096: WriteCode(dest, 256; InitStrTable(;                                            

40、      Omega.string = (char *realloc(Omega.string, 1;                         Omega.string0 = k;                         

41、Omega.len = 1;                                  WriteCode(dest, InStrTable(Omega;         WriteCode(dest, 257;         Bits = 7; &

42、#160;       WriteCode(dest, 0;         free(Omega.string;         free(t.string;         return BytePt; unsigned int LZWCoder:Decode(char *src, unsigned int *len, char *dest   

43、0;     unsigned int code, oldcode;         TStr t, s;         BytePt = 0;         BitPt = 0;         OutBytes = 0;         t.strin

44、g = NULL;         t.len = 0;         s.string = NULL;         s.len = 0;         InitStrTable(;         while(code = GetNextCode(src != 257  

45、60;                      if(code = 256                                         InitStrTable(;  

46、                       code = GetNextCode(src;                         if(code = 257 break;             &

47、#160;           StrFromCode(&s, code;                         WriteString(dest, s;                       

48、 oldcode = code;                                 else                                 

49、60;      if(code <= ItemPt                                                          Str

50、FromCode(&s, code;                                 WriteString(dest, s;                          

51、60;     StrFromCode(&t, oldcode;                                 StrJoinChar(&t, s.string0;                 

52、;                AddTableEntry(t;                                 switch(ItemPt             

53、60;                                                            case 511: Bits = 10; break;    &

54、#160;                                    case 1023: Bits = 11; break;                           

55、0;             case 2047: Bits = 12; break;                                                   &

56、#160;              oldcode = code;                                                  else &

57、#160;                                                        StrFromCode(&s, oldcode;       

58、;                          StrJoinChar(&s, s.string0;                                 WriteStrin

59、g(dest, s;                                 AddTableEntry(s;                               

60、  switch(ItemPt                                                                          case 511: Bits = 10; break;