用C實(shí)現(xiàn)數(shù)據(jù)無損壓縮、解壓(使用LZW算法)

1、用C+實(shí)現(xiàn)數(shù)據(jù)無損壓縮、解壓（使用LZW算法）LZW壓縮算法由Lemple-Ziv-Welch三人共同創(chuàng)造，用他們的名字命名。LZW就是通過建立一個(gè)字符串表，用較短的代碼來表示較長的字符串來實(shí)現(xiàn)壓縮。LZW壓縮算法是Unisys的專利，有效期到2003年，所以對(duì)它的使用是有限制的。字符串和編碼的對(duì)應(yīng)關(guān)系是在壓縮過程中動(dòng)態(tài)生成的，并且隱含在壓縮數(shù)據(jù)中，解壓的時(shí)候根據(jù)表來進(jìn)行恢復(fù)，算是一種無損壓縮。個(gè)人認(rèn)為LZW很適用于嵌入式系統(tǒng)上。因?yàn)椋?、壓縮和解壓速度比較快，尤其是解壓速度；2、占用資源少；3、壓縮比也比較理想；4、適用于文本和圖像等出現(xiàn)連續(xù)重復(fù)字節(jié)串的數(shù)據(jù)流。LZW算法有一點(diǎn)比較特別，就是

2、壓縮過程中產(chǎn)生的字符串對(duì)應(yīng)表，不需要保存到壓縮數(shù)據(jù)中，因?yàn)檫@個(gè)表在解壓過程中能自動(dòng)生成回來。LZW算法比較簡單，我是按照這本書上寫的算法來編程的： (124.6 KB2009-1-5 11:57 (123.14 KB2009-1-5 11:57以下是源代碼： 復(fù)制內(nèi)容到剪貼板 代碼:class LZWCoder private:         struct TStr                    

3、      char *string;                 unsigned int len;                  TStr StrTable4097;         unsigned int ItemPt;       

4、  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;         void AddTableEntry(TStr s

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

7、st, 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、 LZWCoder(; ; void LZWCoder:InitStrTable(         unsigned int i;         for(i = 0; i < 256; i +                          StrTablei.string = (char *rea

9、lloc(StrTablei.string, 1;                 StrTablei.string0 = i;                 StrTablei.len = 1;                  StrTable256.string = NU

10、LL;         StrTable256.len = 0;         StrTable257.string = NULL;         StrTable257.len = 0;         ItemPt = 257;         Bits = 9; void LZWCoder

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

12、 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->strings->len + = c; unsigned

13、int LZWCoder:InStrTable(TStr s         unsigned int i,j;         bool b;         for(i = 0; i <= ItemPt; i +                       

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

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

16、#160;                                                      b = false;             

17、60;                           break;                                          &#

18、160;               if(b return i;                                  return 65535; void LZWCoder:AddTableEntry(TStr s      

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

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

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

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

23、60;                            + (Bit3 << 4                                     

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

25、0;                     + (Bit6 << 1                                         + Bit7;    &#

26、160;                     unsigned int LZWCoder:GetNextCode(char *src         unsigned char i;         unsigned int c = 0;         for(i = 0; i &l

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

28、0;                                 BitPt = 0;                         BytePt +;         &#

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

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

31、mega, 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;         t.len = 0;  

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

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

35、#160;       else                                         WriteCode(dest, InStrTable(Omega;              

36、          AddTableEntry(t;                         switch(ItemPt                             &#

37、160;                            case 512: Bits = 10; break;                                 cas

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

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

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

41、60;                             WriteCode(dest, InStrTable(Omega;         WriteCode(dest, 257;         Bits = 7;        

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

43、gned int code, oldcode;         TStr t, s;         BytePt = 0;         BitPt = 0;         OutBytes = 0;         t.string = NULL;      &

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

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

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

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

48、160;                             else                                         if

49、(code <= ItemPt                                                          StrFromCode(&s, code;   &

50、#160;                             WriteString(dest, s;                                 Str

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

52、60;        AddTableEntry(t;                                 switch(ItemPt                     &

53、#160;                                                    case 511: Bits = 10; break;           

54、                              case 1023: Bits = 11; break;                                  

55、60;      case 2047: Bits = 12; break;                                                          

56、        oldcode = code;                                                  else        

57、                                                  StrFromCode(&s, oldcode;             

58、0;                   StrJoinChar(&s, s.string0;                                 WriteString(dest, s;     

59、                           AddTableEntry(s;                                 switch(ItemPt  

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