可能是最通俗的Lempel-Ziv-Welch (LZW)无损压缩算法详述
可能是最通俗的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/）来详细解释这些代码，如果有兴趣话，请继续关注吧。