目录
一、LZW算法
LZW属于第二类词典编码，第二类词典编码的思想是企图从输入的数据中创建一个“短语词典 (dictionary of the phrases)”，这种短语可以是任意字符的组合。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。
LZW算法的编码过程中不断读取被编码的字符串内容，使用词典中的索引来替换连续的字符串，词典一开始初始化后必须包含可能在字符流出现的所有单个字符，即在编码匹配时，至少可以在词典中找到长度为1的匹配串。在编码的过程中逐渐向词典中加入字符串，而后遇到相同的字符串只需用该字符串在词典中的索引来替代即可，索引即为编码后得到的码字，这就是LZW算法的核心思想，在压缩有大量相同的字符串内容的文件时非常有效。
LZW的解码过程与编码过程一样需要先初始化词典，在解码的过程中一边从词典中找到码字对应的字符串一边根据解码得到的字符串更新词典。LZW的编解码过程都是在同步建立完善词典的过程。
下面介绍具体的编解码步骤。
1.1 编码步骤
步骤1：将词典初始化为包含所有可能的单字符，当前前缀字符串P初始化为空。
步骤2：当前字符C=字符流中的下一个字符。
步骤3：判断P＋C是否在词典中：
如果“是”，令P=P＋C，返回到步骤2。
如果“否”，则：
输出与当前前缀P相对应的码字W；
将P＋C添加到词典中；
令P=C，并返回到步骤2。
1.2 解码步骤
步骤1：将词典初始化为包含所有可能的单字符。
步骤2：令当前码字CW=码字流中的第一个码字。
步骤3：输出当前码字CW对应的字符串string.CW到码字流。
步骤4：令先前码字PW=当前码字CW。
步骤5：令当前码字CW=码字流中的下一个码字。
步骤6：判断当前码字CW是否在词典中：
如果“是”，则：
当前前缀字符串P=先前码字PW对应的字符串string.PW；
当前字符C=当前码字CW对应的字符串string.CW的第一个字符；
输出当前码字CW对应的字符串string.CW到字符流；
将字符串P+C添加到词典中。
如果“否”，则：
当前前缀字符串P=先前码字PW对应的字符串string.PW；
当前字符C=先前码字PW对应的字符串string.PW的第一个字符；
输出P+C到字符流；
将字符串P+C添加到词典中。
步骤7：判断码字流中是否还有码字要译：
如果“是”，则返回步骤4。
如果“否”，则结束。
1.3 关于有可能出现当前码字CW不在词典中的情况说明
考虑对以下字符串进行编码
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 字符 | a | b | b | a | b | a | b | a | c |
假设一开始词典已经初始化了所有单字符，对其进行编码，这里直接用码字对应的字符串表示码字，则编码后的码字应为：
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 |
| 码字 | a | b | b | ab | aba | c |
LZW的解码和编码过程一样需要动态更新词典，例如当解码位置2后，就会在词典中添加字符串”ab”，解码位置3后，会在词典中添加字符串”bb”。
而当读到位置5时，会发现词典中没有对应的码字，因为此时”aba”还没有添加到字典中，也就无法对位置5解码。按照正常逻辑，只有当解码位置5后字符串”aba”才会添加到词典中。
原因是位置5字符串的最后一个字符与第一个字符相同，而位置5字符串的第一个字符和位置4字符串连接起来恰好和位置5字符串完全相同。
也就是说编码器在编码原始字符串的第4到第8个字符时，刚把”aba”添加到词典后立刻就又从字符串中读到了”aba”，因此就直接用上了”aba”的码字，然而解码器始终慢一步，因此造成了解码码字不在词典中的情况。
而幸运的是，LZW解码过程中的特殊情况只有这一种，因此在遇到码字不在词典中的情况可以肯定一定是遇上了当前被编码字符串刚好是上一个被编码字符串再拼接上第一个字符的情况，因此只用在解码流程中的步骤6添加对这种情况的特殊处理即可。
二、代码实现
2.1 程序说明
本实验程序采用C语言编写，共包含三个文件（bitio.h、bitio.c、lzw.c），编译完成后会得到对应的可执行文件lzw.exe，打开cmd控制台，切换至lzw.exe文件所在目录，通过输入命令对文件进行编解码操作。
命令格式为：
lzw.exe 参数1 参数2 参数3参数1的值为“E”或“D”，表示执行编码或解码操作
参数2为输入文件路径，即被编码或解码的文件
参数3为输出文件路径，即编码或解码后的文件
注意事项：
- 本程序中设置每个码字占用16bit，即词典最多支持保存2^16=65536个字符串
- 编码后的文件前32bit用于存放文件编码前大小，即最大支持2^32=4,294,967,296B(约4096GB)的文件
2.2 数据结构
为方便对词典进行添加和查询的操作，本实验程序中为词典定义了树状的数据结构，如下图所示。在词典树中，每个节点上会存放一个字符，每一个词典的索引会对应到树中的一个节点，由该节点的父母节点的字符及该节点本身的字符依次连接构成索引对应的字符串，例如在下图中左下角的节点”e”所对应的字符串即为”aae”。
代码中定义了如下的结构体来构建词典树
struct {
int suffix;
int parent, firstchild, nextsibling;
} dictionary[MAX_CODE + 1];suffix表示该节点本身的字符
parent表示父母节点
firstchild表示子节点
nextsibling表示下一个兄弟节点
2.3 bitio.h
该文件为头文件，用于声明函数的信息。
#ifndef __BITIO__
#define __BITIO__
#include <stdio.h>
typedef struct{
FILE *fp;
unsigned char mask;
int rack;
}BITFILE;
BITFILE *OpenBitFileInput( char *filename);
BITFILE *OpenBitFileOutput( char *filename);
void CloseBitFileInput( BITFILE *bf);
void CloseBitFileOutput( BITFILE *bf);
int BitInput( BITFILE *bf);
unsigned long BitsInput( BITFILE *bf, int count);
void BitOutput( BITFILE *bf, int bit);
void BitsOutput( BITFILE *bf, unsigned long code, int count);
#endif // __BITIO__
2.4 bitio.c
该文件定义了用于读写码字的函数。
BitsInput()函数用于读取文件中的码字。
BitsOutput()函数用于将码字写入文件。
#include <stdlib.h>
#include <stdio.h>
#include "bitio.h"
BITFILE *OpenBitFileInput( char *filename){
BITFILE *bf;
bf = (BITFILE *)malloc( sizeof(BITFILE));
if( NULL == bf) return NULL;
if( NULL == filename) bf->fp = stdin;
else bf->fp = fopen( filename, "rb");
if( NULL == bf->fp) return NULL;
bf->mask = 0x80;
bf->rack = 0;
return bf;
}
BITFILE *OpenBitFileOutput( char *filename){
BITFILE *bf;
bf = (BITFILE *)malloc( sizeof(BITFILE));
if( NULL == bf) return NULL;
if( NULL == filename) bf->fp = stdout;
else bf->fp = fopen( filename, "wb");
if( NULL == bf->fp) return NULL;
bf->mask = 0x80;
bf->rack = 0;
return bf;
}
void CloseBitFileInput( BITFILE *bf){
fclose( bf->fp);
free( bf);
}
void CloseBitFileOutput( BITFILE *bf){
// Output the remaining bits
if( 0x80 != bf->mask) fputc( bf->rack, bf->fp);
fclose( bf->fp);
free( bf);
}
int BitInput( BITFILE *bf){
int value;
if( 0x80 == bf->mask){
bf->rack = fgetc( bf->fp);
if( EOF == bf->rack){
fprintf(stderr, "Read after the end of file reached\n");
exit( -1);
}
}
value = bf->mask & bf->rack;
bf->mask >>= 1;
if( 0==bf->mask) bf->mask = 0x80;
return( (0==value)?0:1);
}
unsigned long BitsInput( BITFILE *bf, int count){
unsigned long mask;
unsigned long value;
mask = 1L << (count-1);
value = 0L;
while( 0!=mask){
if( 1 == BitInput( bf))
value |= mask;
mask >>= 1;
}
return value;
}
void BitOutput( BITFILE *bf, int bit){
if( 0 != bit) bf->rack |= bf->mask;
bf->mask >>= 1;
if( 0 == bf->mask){ // eight bits in rack
fputc( bf->rack, bf->fp);
bf->rack = 0;
bf->mask = 0x80;
}
}
void BitsOutput( BITFILE *bf, unsigned long code, int count){
unsigned long mask;
mask = 1L << (count-1);
while( 0 != mask){
BitOutput( bf, (int)(0==(code&mask)?0:1));
mask >>= 1;
}
}
#if 0
int main( int argc, char **argv){
BITFILE *bfi, *bfo;
int bit;
int count = 0;
if( 1<argc){
if( NULL==OpenBitFileInput( bfi, argv[1])){
fprintf( stderr, "fail open the file\n");
return -1;
}
}else{
if( NULL==OpenBitFileInput( bfi, NULL)){
fprintf( stderr, "fail open stdin\n");
return -2;
}
}
if( 2<argc){
if( NULL==OpenBitFileOutput( bfo, argv[2])){
fprintf( stderr, "fail open file for output\n");
return -3;
}
}else{
if( NULL==OpenBitFileOutput( bfo, NULL)){
fprintf( stderr, "fail open stdout\n");
return -4;
}
}
while( 1){
bit = BitInput( bfi);
fprintf( stderr, "%d", bit);
count ++;
if( 0==(count&7))fprintf( stderr, " ");
BitOutput( bfo, bit);
}
return 0;
}
#endif2.5 lzw.c
该文件为程序中的核心文件，定义了编解码的相关函数，详细的过程已经在代码中注释。
#include <stdlib.h>
#include <stdio.h>
#include "bitio.h"
#define MAX_CODE 65535
struct {
int suffix;
int parent, firstchild, nextsibling;
} dictionary[MAX_CODE + 1];
int next_code;
int d_stack[MAX_CODE]; // stack for decoding a phrase
#define input(f) ((int)BitsInput( f, 16))
#define output(f, x) BitsOutput( f, (unsigned long)(x), 16)
int DecodeString(int start, int code);
void InitDictionary(void);
void PrintDictionary(void) {
int n;
int count;
for (n = 256; n < next_code; n++) {
count = DecodeString(0, n);
printf("%4d->", n);
while (0 < count--) printf("%c", (char) (d_stack[count]));
printf("\n");
}
}
int DecodeString(int start, int code) {//该函数将字符串写入d_stack,便于后续写入至输出文件，同时返回字符串长度
int count = start;
while(code>=0){
d_stack[count]=dictionary[code].suffix;
code=dictionary[code].parent;
count++;
}
return count;
}
void InitDictionary(void) {
int i;
for (i = 0; i < 256; i++) {
dictionary[i].suffix = i;
dictionary[i].parent = -1;
dictionary[i].firstchild = -1;
dictionary[i].nextsibling = i + 1;
}
dictionary[255].nextsibling = -1;
next_code = 256;
}
/*
* Input: string represented by string_code in dictionary,
* Output: the index of character+string in the dictionary
* index = -1 if not found
*/
int InDictionary(int character, int string_code) {
int sibling;
if (0 > string_code) return character;
sibling = dictionary[string_code].firstchild;
while (-1 < sibling) {
if (character == dictionary[sibling].suffix) return sibling;
sibling = dictionary[sibling].nextsibling;
}
return -1;
}
void AddToDictionary(int character, int string_code) {
int firstsibling, nextsibling;
if (0 > string_code) return;
dictionary[next_code].suffix = character;
dictionary[next_code].parent = string_code;
dictionary[next_code].nextsibling = -1;
dictionary[next_code].firstchild = -1;
firstsibling = dictionary[string_code].firstchild;
if (-1 < firstsibling) { // the parent has child
nextsibling = firstsibling;
while (-1 < dictionary[nextsibling].nextsibling)
nextsibling = dictionary[nextsibling].nextsibling;
dictionary[nextsibling].nextsibling = next_code;
} else {// no child before, modify it to be the first
dictionary[string_code].firstchild = next_code;
}
next_code++;
}
void LZWEncode(FILE *fp, BITFILE *bf) {//编码函数
int character;//当前字符C
int string_code;//当前前缀P，这里存放的是词典树索引
int index;//词典索引
unsigned long file_length;//文件大小(字符数)
fseek(fp, 0, SEEK_END);//文件指针移到文件末尾
file_length = ftell(fp);//读取文件大小
fseek(fp, 0, SEEK_SET);//文件指针移到文件头部
BitsOutput(bf, file_length, 4 * 8);//将文件大小写入文件bf，文件大小共占32个bit
InitDictionary();//初始化词典树
string_code = -1;//当前还没有开始读取文件数据，前缀字符串为空，值记为-1
while (EOF != (character = fgetc(fp))) {//依次读取输入文件中的字符，直到读到文件结束符
index = InDictionary(character, string_code);//获取P+C在词典中的索引
if (0 <= index) { // P+C在词典中，将前缀字符串置为P+C
string_code = index;
} else { // P+C不在词典中
output(bf, string_code);//将前缀字符串的词典索引写入文件bf，每个索引占16bit
if (MAX_CODE > next_code) { // 由于每个索引占16bit，词典最多可以存放2^16=65536个词，判断词典是否写满
// 若词典还没有写满，将P+C写入词典
AddToDictionary(character, string_code);
}
string_code = character;//将前缀字符串置为C
}
}
output(bf, string_code);//读取到文件结束符，将前缀字符串的词典索引写入文件bf
}
void LZWDecode(BITFILE *bf, FILE *fp) {//解码函数
int character;//当前字符C
int new_code;//当前码字CW
int last_code;//先前码字PW
int phrase_length;//码字译码后的长度（字符串长度）
unsigned long file_length;//文件大小(字符数)
file_length = BitsInput(bf, 4 * 8);
if (-1 == file_length) {
file_length = 0;
}
InitDictionary();
last_code = -1;//先前码字为空
while (0 < file_length) {//判断是否已经译码完成
new_code = input(bf);
if (new_code >= next_code) {//若码字不在字典中
d_stack[0] = character;//输出的字符串最后一个字符为C
phrase_length = DecodeString(1, last_code);//将
} else {
phrase_length = DecodeString(0, new_code);
}
character = d_stack[phrase_length - 1];//当前字符为先前码字PW对应的字符串的第一个字符
while (0 < phrase_length) {//将字符串写入文件
phrase_length--;
fputc(d_stack[phrase_length], fp);//每次写入字符串中的一个字符
file_length--;
}
if (MAX_CODE > new_code) {
AddToDictionary(character, last_code);//将字符串添加到词典中
}
last_code = new_code;//令先前码字PW=当前码字CW
}
}
int main(int argc, char **argv) {
FILE *fp;
BITFILE *bf;
if (4 > argc) {
fprintf(stdout, "usage: \n%s <o> <ifile> <ofile>\n", argv[0]);
fprintf(stdout, "\t<o>: E or D reffers encode or decode\n");
fprintf(stdout, "\t<ifile>: input file name\n");
fprintf(stdout, "\t<ofile>: output file name\n");
return -1;
}
if ('E' == argv[1][0]) { // do encoding
fp = fopen(argv[2], "rb");
bf = OpenBitFileOutput(argv[3]);
if (NULL != fp && NULL != bf) {
LZWEncode(fp, bf);
fclose(fp);
CloseBitFileOutput(bf);
fprintf(stdout, "encoding done\n");
}
} else if ('D' == argv[1][0]) { // do decoding
bf = OpenBitFileInput(argv[2]);
fp = fopen(argv[3], "wb");
if (NULL != fp && NULL != bf) {
LZWDecode(bf, fp);
fclose(fp);
CloseBitFileInput(bf);
fprintf(stdout, "decoding done\n");
}
} else { // otherwise
fprintf(stderr, "not supported operation\n");
}
return 0;
}
三、实验测试
3.1 文本文档测试
新建文本文档input.txt用于测试，文档内容如下：
该文档大小为104字节，将其压缩以测试压缩效果。
输入指令：
LZW.exe E input.txt code.txt而后程序对input.txt进行编码，得到code.txt文件
编码后的code.txt文件大小为70字节，相比源文件input.txt数据量有减少。
打开code.txt，由于此时的内容为编码后的符号，因此无法直接阅读。
接下来将code.txt解码，输入指令：
LZW.exe D code.txt output.txt而后程序对code.txt解码，得到output.txt文件，打开output.txt文件，内容与编码前的input.txt文件内容一致。
3.2 多类型文件测试
下面将多种不同类型文件进行编码，检查编码后的压缩效果，这里用压缩比来作为评价压缩效果的客观指标，压缩比的计算方式为：
压缩比 = 输入文件大小/输出文件大小
各文件压缩结果如下：
| 序号 | 文件格式 | 输入文件大小 | 输出文件大小 | 压缩比 |
| 1 | 273KB | 302KB | 0.904 | |
| 2 | xlsx | 11KB | 16KB | 0.688 |
| 3 |
doc |
49KB | 54KB | 0.907 |
| 4 | png | 14KB | 24KB | 0.583 |
| 5 | cif | 3564KB | 2111KB | 1.688 |
| 6 | yuv | 732KB | 96KB | 7.625 |
| 7 | mp4 | 97.5MB | 119MB | 0.819 |
| 8 | bmp | 676KB | 510KB | 1.325 |
| 9 | m4a | 38KB | 68KB | 0.5588 |
| 10 | mp3 | 16.3MB | 19.9MB | 0.819 |
| 11 | wav | 20.3MB | 25.7MB | 0.790 |
四、总结
LZW是一种简单的词典编码方法，适用于对数据重复率高的文件进行编码，例如yuv或bmp格式的图像文件，这种类型的图像文件由于未经压缩，连续的像素值在文件数据流中经常重复出现，LZW对这一类的文件压缩编码效果较好。
然而对于已经压缩过的文件格式类型，LZW算法的表现稍差，有时非但不能进一步压缩，反而会导致编码后的数据量更大，LZW算法的适用场景比较局限。