可能是最通俗的Lempel-Ziv-Welch (LZW)无损压缩算法详述

  最近工作正好接触到这一块,试着自己总结了一下,给需要的人提供一点帮助。

一、概述

     首先看看百度百科里的一句话介绍:“LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩。” 简单来说,就是尝试用短的编码代替长的编码达到压缩的目的。LZW其实是三个大牛的名字,这个算法最开始是 Ziv和Lempel这两个人在1977,1978年发明的,在1984年的时候由另一位大牛Terry Welch进行了改进,所以这个算法的名字才叫LZW。它的一个最为人所占的应用是在gif压缩里面的使用。

二、示例

 假设我们要通过互联网发送一本英文牛津字典,一个字符在计算机中需要8个bit表示,假设一本子字典里有20万个单词,每个单词平均长度为5个字符,那么这样一个字典需要800万个bit表示完。如果我们换一种思维方式,20万个单词都编上号,20万个单词18个比特就能全部表示完,20万乘以18bit,只需要360万个bit就能表示所有的单词,相对于第一种办法,数据量只有一半不到。但是这种方法有一个重要问题就是每个人都需要一个对应表,用来查每个数字对应哪个单词,这样才能得到正确的信息。LZW算法就是利用这样一种思想并且能够自适应的生成字典并且保存在最后的编码本身之中。

     原始的LZW算法的采用4k长的字典(实际上很难用到这么多),最开始的256个字典项就是ASCII码值。后面的字典项在编码过程中根据输入码本身自动的产生。对于这种算法,可以用以下伪码表示其逻辑:  

1.string P = 第一个被读入的字符并输出p
2.WHILE(输入字符串未读入结束)
3.{
4.   char C= 紧接着的下一个输入字符
5.   if(p+c 存在于已产生的字典中)
6.   {
7.         p = p+c
8.   }
9.   else
10.   {
11.       生成新的字典编号代表pc
12.       输出p的字典项编号
13.    p = c
14.   }  
15.}
16.输出p 

    为了深入理解算法思想,从一个具体的例子开始,比如对于一个字符串BABAABAAA,如何将这样长的一个字符串编码成更短的字符串呢?当一个字符串被读入时,首先读入B,这时候直接输出B(或者说B的ASCII码,66)。接着读入A,这时p+c没有存在于字典中,生成新的字典编号(256)代表"BA"同时输出A(ASCII码,65)。现在p是"A",接着读入下一个字符,B,现在p+c是"AB",没有存在于字典之中,一样生成新的字典编号(257)代表"AB",同时输出66代表B。然后p=B,接着读入c,c=A,这时p+c是“BA",存在于字典项中(256),暂时不输出,接着读入下一个字符"A”,这时产生了新的不在字典项总的p,“BAA”,用258代替这个字符串之后并且输出256用意代表"BA",看,已经短了一点了。依次类推,最后得到的压缩编码是"66,65,256,257,65,260",在此过程中产生的非ASCII码的字典项是“256-BA","257-AB","258-BAA","259-ABA","260-AA"。这里至少要用9bit代表新产生的压缩码,但是压缩之后只要54bits,相对于原理啊72bits还是减少了,所以在现实使用中,压缩在读入的字节不大于一个特定值(比如100bits)并不进行压缩。

     那么得到编码流"66,65,256,257,65,260",怎样解压缩得到原始的数据呢?LZW的解压缩算法用伪码表示是这样的: 

1. 读入一个码p
2. 输出p对应字符
3. p = c;
4. while ( 继续读入下一个码c )    
5.{
6.     entry = 寻找码c的字典对应项
7.     输出entry
8.     将p+entry[0]加入字典项  
9.      p = entry
10. }

  还是从实例中理解下这个解压缩算法(这里我们假设一次读入9个bit的码),首先读入的是66,输出”B",接着读入下一个码“65”,现在entry=A,输入entry,并且将BA加入字典项,p=A,并且知道256对应的是这个字典项“BA”,下一个读进来的是256,找到这个entry是"BA“,并且生成出下一个字典项257为"A(p)B(entry[0])",这时候p=”BA“,下一次是257,那么输出"AB”,并且生成下一个字典项258为“BAA",以此类推,字典项总能在码之前生成,所以每一个9bit的码都能正确的被解析。这样在最后不仅得到了正确的解码序列并且一起自动的生成了字典。

三、实现

  既然伪码已经有了,那么实现就不是太困难了。在这里我展示一下我的C#的实现版本,同时因为项目需要,我还实现了一份C/C++实现版本,如果需要的话可以发信给我的邮箱(rogerzhu0710@gmail.com)来索取。     

  1  class Compress 
  2  {
  3         static System.Int16        ms_nOutputBitCount;
  4         static ulong            ms_nOutputBitBuffer;
  5         static int              ms_nOutputBufferIdx = 0;             
  6         static byte[]           ms_byOutputBuffer;        
  7 
  8         static byte[]            append_character;
  9     static System.UInt16[]    prefix_code;     
 10 
 11         static int              TABLE_SIZE = 1229;
 12         static short[]          ms_nCodeValue;
 13         static int              HASHING_SHIFT = 2;
 14         static short            ms_nOutput_bit_count = 0;
 15         static int              m_nCount = 0;
 16         static int              m_nOffset = 0;
 17 
 18         static long lzw_compress(byte[] input, byte[] output,long size)
 19         {
 20             System.UInt16 next_code;
 21             System.UInt16 character;
 22             System.UInt16 string_code;
 23             System.UInt16 index;
 24 
 25             System.UInt16 i;
 26             
 27         next_code = 256;
 28 
 29             ms_nOutputBitCount = 0;
 30             ms_nOutput_bit_count = 0;
 31             ms_nOutputBitBuffer = 0L;
 32             ms_nOutputBufferIdx = 0;
 33 
 34             append_character = new Byte[TABLE_SIZE];
 35             prefix_code = new ushort[TABLE_SIZE];
 36 
 37             ms_nCodeValue = new short[TABLE_SIZE];
 38             
 39             m_nCount = 0;
 40         for(i = 0; i < TABLE_SIZE; i++)
 41         {
 42                 ms_nCodeValue[i] = -1;
 43         }
 44             
 45             string_code = input[m_nCount++];
 46 
 47              
 48          while((--size)!=0)
 49          {
 50                 character = input[m_nCount++];
 51 
 52                 index = (System.UInt16)find_match(string_code, character);
 53 
 54                 if (ms_nCodeValue[index] != -1)
 55         {
 56                     string_code = (ushort)ms_nCodeValue[index];
 57         }
 58         else
 59         {
 60                   if (next_code <= MAX_CODE)
 61                     {
 62                         ms_nCodeValue[index] = (short)next_code++;
 63             prefix_code[index] = string_code;
 64             append_character[index] = Convert.ToByte(character);
 65             }
 66                     output_code(string_code);
 67             string_code = character;
 68         }
 69           }
 70           
 71               output_code(string_code);
 72           output_code(MAX_VALUE);
 73           output_code(0);
 74               
 75               Buffer.BlockCopy(ms_byOutputBuffer, 0, output, 0, ms_byOutputBuffer.Length);
 76             return ms_nOutputBufferIdx  ;
 77         }
 78 
 79         static void output_code(ushort code)
 80         {
 81 
 82             ms_nOutputBitBuffer |= ((ulong)code << (32 - BITS - ms_nOutput_bit_count));
 83             ms_nOutput_bit_count += BITS;
 84             int k = 0;
 85 
 86             while (ms_nOutput_bit_count >= 8)
 87         {
 88                 ms_byOutputBuffer[ms_nOutputBufferIdx++] = (byte)(ms_nOutputBitBuffer >> 24);
 89                 ms_nOutputBitBuffer <<= 8;
 90                 ms_nOutput_bit_count -= 8;
 91          }
 92         }
 93 
 94         static int find_match(int hash_prefix, uint hash_character)
 95         {
 96             short index;
 97             short offset;
 98             
 99             index = (short)((hash_character << HASHING_SHIFT) ^ hash_prefix);
100             
101             if(index == 0)
102             {
103                 offset = 1;
104             }
105             else
106             {
107                 offset = (short)(TABLE_SIZE - index);
108             }
109             
110             while(true)
111             {
112                 if (ms_nCodeValue[index] == -1)
113                 {
114                     return(index);
115                 }
116 
117                 if(prefix_code[index] == hash_prefix && append_character[index] == hash_character)
118                 {
119                     return(index);
120                 }
121                 
122                 index -= offset;
123                 if(index < 0)
124                 {
125                     index += (short)TABLE_SIZE;
126                 }
127             }
128         }
129 }              

  解压缩的代码如下:    

  1 class Decompress
  2 {
  3       static System.Int16        ms_nInputBitCount;
  4       static System.UInt32    ms_nInputBitBuffer;
  5       static int                ms_nInputBufferIdx;            
  6       static byte[]            ms_byInputBuffer;    
  7 
  8       static byte[]            decode_stack;
  9       static byte[]            append_character;        
 10       static System.UInt16[]    prefix_code;
 11       static bool                ms_bSuppressOutput;
 12       static short                    ms_nKey;    
 13 
 14       static int LzwExpand(byte[] input, byte[] output)
 15      {
 16         int nOutputIdx = 0; 
 17         System.UInt16 next_code;
 18         System.UInt16 new_code;
 19         System.UInt16 old_code;
 20             
 21         System.Int16  character;
 22     
 23         int nDecodeOffset = 0;         
 24 
 25         int count = 0;
 26         next_code = 256;
 27                 ms_nInputBitCount = 0;
 28         ms_nInputBitBuffer = 0;
 29         ms_nInputBufferIdx = 0;
 30         ms_byInputBuffer = input;
 31  
 32         old_code = (ushort) input_code();
 33         character = (short) old_code;
 34 
 35 
 36         if (output != null && nOutputIdx < output.Length)
 37             output[nOutputIdx++] = (byte) old_code;
 38 
 39         count++;
 40 
 41         while((new_code = (ushort) input_code()) != MAX_VALUE)
 42         {    
 43             if(new_code >= next_code)
 44             {
 45                 decode_stack[0] = (byte) character;
 46                 nDecodeOffset = decode_string(decode_stack, 1, old_code);
 47             }
 48             else
 49             {
 50                 nDecodeOffset = decode_string(decode_stack, 0, new_code);
 51             }
 52                 
 53             if(nDecodeOffset < 0)
 54                 return 0;
 55                 
 56             character = decode_stack[nDecodeOffset];
 57             while(nDecodeOffset >= 0)
 58             {
 59                 if (output != null && nOutputIdx < output.Length)
 60                     output[nOutputIdx++] = decode_stack[nDecodeOffset];
 61 
 62                 count++;
 63 
 64                 nDecodeOffset--;
 65             }
 66             
 67                         if(next_code <= MAX_CODE)
 68             {
 69                 prefix_code[next_code] = old_code;
 70                 append_character[next_code] = (byte) character;
 71                 next_code++;
 72             }
 73             old_code = new_code;
 74         }
 75             
 76         return count;
 77     }
 78 
 79 
 80         static int decode_string(byte[] buffer, int nStartIdx, System.UInt16 code)
 81         {
 82             System.Int16 i = 0;
 83 
 84             while(code > 255)
 85             {
 86                 buffer[nStartIdx++] = append_character[code];
 87                 code = prefix_code[code];
 88                 
 89                 if (i++ >= 4000)
 90                 {
 91                      
 92                     return -1;
 93                 }
 94             }
 95 
 96             buffer[nStartIdx] = (byte) code;
 97 
 98             return nStartIdx;
 99         }
100    
101             static int input_code()
102         {
103             System.UInt16 nReturnValue;
104 
105             while (ms_nInputBitCount <= 24)
106             {
107                 ms_nInputBitBuffer |= ((System.UInt32)(ms_byInputBuffer[ms_nInputBufferIdx])) << (24 - ms_nInputBitCount);
108                 ms_nInputBufferIdx++;
109                 ms_nInputBitCount += 8;
110             }
111     
112             nReturnValue = (System.UInt16) (ms_nInputBitBuffer >> (32 - BITS));
113             ms_nInputBitBuffer <<= BITS;
114             ms_nInputBitCount -= BITS;
115             return nReturnValue;
116         }
117 }

     代码比较长,我会在我自己的博客(http://www.richinmemory.com/)来详细解释这些代码,如果有兴趣话,请继续关注吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Vijos P1116 一元三次方程求解【多解,暴力,二分】

一元三次方程求解 描述 有形如:ax^3+bx^2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三...

381120
来自专栏小樱的经验随笔

Vijos P1113 不高兴的津津【模拟】

不高兴的津津 描述 津津上初中了。妈妈认为津津应该更加用功学习,所以津津除了上学之外,还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢...

28380
来自专栏小樱的经验随笔

Vijos P1785 同学排序【模拟】

同学排序 描述 现有m位同学,第1位同学为1号,第2位同学为2号,依次第m位同学为m号。要求双号的学生站出来,然后余下的重新组合,组合完后,再次让双号的学生站出...

27740
来自专栏小樱的经验随笔

Vijos P1035 贪婪的送礼者【模拟】

贪婪的送礼者 描述 对于一群要互送礼物的朋友,你要确定每个人送出的礼物比收到的多多少。 在这一个问题中,每个人都准备了一些钱来送礼物,而这些钱将会被平均分给那些...

30450
来自专栏小樱的经验随笔

Vijos P1127 级数求和【模拟】

级数求和 描述 已知:Sn= 1+1/2+1/3+…+1/n。显然对于任意一个整数K,当n足够大的时候,Sn大于K。 现给出一个整数K(1<=k<=15),要求...

27750
来自专栏小樱的经验随笔

Vijos P1784 数字统计【模拟】

数字统计 背景 来自 NOIP2010 普及组 第一题 描述 请统计某个给定范围[L, R]的所有整数中,数字2出现的次数。 比如在给定范围[2, 22],数...

27490
来自专栏小樱的经验随笔

Vijos P1448 校门外的树【多解,线段树,树状数组,括号序列法+暴力优化】

校门外的树 描述 校门外有很多树,有苹果树,香蕉树,有会扔石头的,有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段...

59870
来自专栏小樱的经验随笔

Codeforces 626F Group Projects(滚动数组+差分dp)

F. Group Projects time limit per test:2 seconds memory limit per test:256 megaby...

36970
来自专栏小樱的经验随笔

Vijos P1103 校门外的树【线段树,模拟】

校门外的树 描述 某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;...

29240
来自专栏小樱的经验随笔

Vijos P1497 立体图【模拟】

立体图 描述 小渊是个聪明的孩子,他经常会给周围的小朋友们讲些自己认为有趣的内容。最近,他准备给小朋友讲解立体图,请你帮他画出立体图。 小渊有一块面积为m*n的...

39560

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励