LZW编码实现（C)

程序员文章站 2022-07-14 19:01:42

...

LZW压缩算法由Lemple-Ziv-Welch 三人共同创造，用他们的名字命名。它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢弃。

LZW算法中，首先建立一个字符串表，把每一个第一次出现的字符串放入串中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如"print" 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将"print"字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出266所代表的字符串"print"，在解压缩时，串表可以根据压缩数据重新生成。

2. lzw编解码举例：

2.1 编码

输入流：a a b b b a a b b .....
初始标号集：

0	1	2	3
a	b

压缩过程：

第几步	前缀	后缀	Entry	认识(Y/N)	输出	标号
1	a	（，a）
2	a	a	(a,a)	N	0	4
3	a	b	(a,b)	N	0	5
4	b	b	(b,b)	N	1	6
5	b	b	(b,b)	Y
6	6	a	(6,a)	N	6	7
7	a	a	(a,a)	Y
8	4	b	(4,b)	N	4	8
9	b	b	(b,b)	Y
10	6	(6,)	N	6

当进行到第12步的时候，标号集应该为：

0	1	2	3	4	5	6	7	8
A	B	aa	ab	bb	6a	4b

编码为：001646

1.2 解码

1）读入第一个编码Code=0H，由于字符串表中存在该索引，因此输出字符串表中0H对应的字符串"a"，同时使OldCode=Code=0H。

2）读下一个编码Code=0H，字符串表中存在该索引，输出0H所对应的字符串"a"，然后将OldCode=0H所对应的字符串"a"加上Code=0H所对应的字符串的第一个字符"a"，即"aa"添加到字串表中，其索引为4H，同时使OldCode=Code=0H。

3）读下一个编码Code=1H，字串表中存在该索引，输出1H所对应的字符串"b"，然后将OldCode=0H所对应的字符串"a"加上Code=1H所对应的字符串的第一个字符"b"，即"ab"添加到字串表中，其索引为5H，同时使OldCode=Code=1H。

4）读入下一个编码Code=6H，由于字串表中不存在该索引，因此输出OldCode=1H所对应的字符串"b"加上OldCode的第一个字符"b“，即"bb"，同时将"bb"添加到字符串表中，其索引为6H，同时使OldCode=Code=6H。

5）读下一个编码Code=4H，字串表中存在该索引，输出4H所对应的字符串"aa"，然后将OldCode=6H所对应的字符串"bb"加上Code=4H所对应的字符串的第一个字符"a"，即"bba"添加到字串表中，其索引为7H，同时使OldCode=Code=4H。

6）读下一个编码Code=6H，字串表中存在该索引，输出6H所对应的字符串"bb"，然后将OldCode=4H所对应的字符串"aa"加上Code=6H所对应的字符串的第一个字符"b"，即"aab"添加到字串表中，其索引为8H，同时使OldCode=Code=6H。

7）读下一个编码Code=3H，它等于LZW_EOI，数据解码完毕。

3. lzw编解码步骤

编码算法：

步骤1：开始时的词典包含所有可能的根(Root)，而当前前缀P是空的；
　　步骤2：当前字符(C) ：=字符流中的下一个字符；
　　步骤3：判断缀-符串P+C是否在词典中
　　(1) 如果“是”：P ：= P+C // (用C扩展P) ；
　　(2) 如果“否”
　　① 把代表当前前缀P的码字输出到码字流;
　　② 把缀-符串P+C添加到词典;
　　③ 令P ：= C //(现在的P仅包含一个字符C);
　　步骤4：判断码字流中是否还有码字要译
　　(1) 如果“是”，就返回到步骤2；
　　(2) 如果“否”
　　① 把代表当前前缀P的码字输出到码字流;
　　② 结束。
　　

解压算法

具体解压步骤如下：

(1)译码开始时Dictionary包含所有的根。

(2)读入在编码数据流中的第一个码字 cW(它表示一个Root)。

(3)输出String.cW到字符数据流Charstream。

(4)使pW=cW 。

(5)读入编码数据流的下一个码字cW 。

(6)目前在字典中有String.cW吗?

YES：1)将String．cW输出给字符数据流；

2)使P=String.pW；

3)使C=String.cW的第一个字符；

4)将字符串P+C添加进Dictionray。

NO ：1)使P=String.pW ；

2)使C=String.pW的第一个字符；

3)将字符串P+C输出到字符数据流并将其添加进Dictionray(现在它与cW相一致)。

(7)在编码数据流中还有Codeword吗?

YES：返回(4)继续进行译码。

NO：结束译码。

二．数据结构

1. 字典节点结构体




struct {



    int suffix;  //后缀字符




    int parent, firstchild, nextsibling; //母节点，第一个孩子节点，下一个兄弟节点




} dictionary[MAX_CODE+1];  //数组下标即为编码

2. 二进制文件结构体





typedef struct{




    FILE *fp;  //输出文件指针




    unsigned char mask;  //按位写入字节时，掩码




    int rack;  //类似于缓存，每写完8位，将rack输出到文件中




}BITFILE;

三．lzw编码分析

1. lzw编码流程图

LZW编码实现（C)

2. lzw编码代码分析

2.1 lzw编码总流程





void LZWEncode( FILE *fp, BITFILE *bf){



    int character;



    int string_code;



    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);  /*将输入文件的大小写入输出文件中，4*8代表file_length是32位数字*/




    InitDictionary();  //初始化字典，设置各根节点




    string_code = -1;  //初始化前缀





while( EOF!=(character=fgetc( fp))){	//扫描输入文件，得到各字符




 



		/*判断(string_code，character)是否在字典中，如果在则返回对应编码，否则返回-1*/




        index = InDictionary( character, string_code);



        if( 0<=index){	// (string_code，character)在字典中




            string_code = index;  //将(string_code，character)对应的编码作为前缀




        }else{	//(string_code，character)不在字典中




            output( bf, string_code);	//输出前缀




            if( MAX_CODE > next_code){  //字典空间充足时




                //将(string_code，character)添加到字典中




                AddToDictionary( character, string_code);



            }



            string_code = character;  //将新字符做为前缀




        }



    }



    output( bf, string_code);  //输入文件扫描完毕，将最后未输出的前缀输出




}

2.2 初始化字典，设置各根节点





void InitDictionary( void){  //初始化字典，将0-255根节点初始化




    int i;



 



    for( i=0; i<256; i++){  //下标值为ASCII码值




        dictionary[i].suffix = i;  //根的后缀字符为对应ASCII码




        dictionary[i].parent = -1;  //前缀字符长度为0，没有前缀




        dictionary[i].firstchild = -1;  //暂时没有第一个孩子




        dictionary[i].nextsibling = i+1;	 /*下一个兄弟根节点下标为下一个ASCII码值*/




    }



    dictionary[255].nextsibling = -1;  //最后一个根节点没有下一个兄弟




    next_code = 256;  //为全局变量，标记下一个编码为256




}

2.3 判断(string_code，character)（前缀，后缀）是否在字典中，如果在则返回对应编码，否则返回-1





int InDictionary( int character, int string_code){




int sibling;



 



/*string_code小于0说明该字符是文件第一个字符，一定有对应根节点并存在于字典中，所以返回(string_code，character)的编码---character的ASCII码*/




if( 0>string_code) return character;



 



//自左向右遍历string_code节点的所有孩子（第一个孩子的所有兄弟）



//以string_code的第一个孩子为长兄



sibling = dictionary[string_code].firstchild;



 




while( -1<sibling){  //sibling等于-1说明所有兄弟遍历结束




 



/*如果找到一个兄弟的后缀是character，则返回(string_code，character)的编码¬---该兄弟的下标*/



        if( character == dictionary[sibling].suffix) return sibling;



 



	//如果该兄弟的后缀不是该字符，则寻找下一个兄弟




        sibling = dictionary[sibling].nextsibling;



}



 



/*所有兄弟的后缀均不等于该字符，说明(string_code，character)不在字典中，返回-1*/



    return -1;



}

2.4 将(string_code,character)添加到字典中，编码为next_code





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; //新节点下一个兄弟暂时不存在，设为-1




    dictionary[next_code].firstchild = -1;  //新节点第一个孩子暂时不存在，设为-1




    firstsibling = dictionary[string_code].firstchild;



   



	//下面设置新节点的兄弟关系




	 if( -1<firstsibling){	//新节点的母亲原本有孩子




        nextsibling = firstsibling;



		//循环找到最后一个兄弟




        while( -1<dictionary[nextsibling].nextsibling ) 



            nextsibling = dictionary[nextsibling].nextsibling;



 



		//把新节点设为最后一个兄弟的下一个兄弟




        dictionary[nextsibling].nextsibling = next_code;



}else{  //新节点的母亲原本没有孩子




 



		//把新节点设为母亲的第一个孩子




        dictionary[string_code].firstchild = next_code;    



}



    next_code ++;  //下一个编码增加1




}

2.5 打开二进制输出文件，不存在则新建，存在则覆盖已有文件





BITFILE *OpenBitFileOutput( char *filename){  //参数是文件名




    BITFILE *bf;



    bf = (BITFILE *)malloc( sizeof(BITFILE));




if( NULL == bf) return NULL;



	//如果参数是NULL，则文件指向屏幕




    if( NULL == filename)   bf->fp = stdout;



    else bf->fp = fopen( filename, "wb");  //以二进制只写的方式打开文件




    if( NULL == bf->fp) return NULL;



    bf->mask = 0x80;  //初始化掩码为1000 0000




    bf->rack = 0;  //初始化rack为0




    return bf;



}

2.6 按位输出数据到输出文件中





void BitsOutput( BITFILE *bf, unsigned long code, int count){



    unsigned long mask;



 



	/*output宏定义缺省count为16。count为16时，mask为1000 0000 0000 0000。count为32时，mask为1000 0000 0000 0000 0000 0000 0000 0000*/




    mask = 1L << (count-1);




while( 0 != mask){  /*mask为0时，说明code共count位数字输出完毕，lzw是等长码*/




		/*按位输出code*/




        BitOutput( bf, (int)(0==(code&mask)?0:1));



        mask >>= 1;  //掩码向右移位




    }



}  //注：不同于huffman编码，huffman编码是不等长码，lzw可以看成是等长码，这里编码长度是16位





void BitOutput( BITFILE *bf, int bit){



	/*如果bit为1，则在rack下一个未写码位置由0变为1。如果bit为0，则rack不作处理，mask直接向右移位，代表下一个未写码位置为0*/




    if( 0 != bit) bf->rack |= bf->mask;



bf->mask >>= 1;



 



/*每次mask移位后，都要判断mask是否溢出为0。若溢出，则代表成功累计写入八位，即该字节已写满。直接输出rack后，rack初始化为0，mask初始化为1000 0000*/



	if( 0 == bf->mask){ 



        fputc( bf->rack, bf->fp);



        bf->rack = 0;



        bf->mask = 0x80;



    }



}

2.7 输出剩下未输出的二进制数字，关闭二进制输出文件





void CloseBitFileOutput( BITFILE *bf){



//如果还存在为输出的二进制数，则直接输出



    if( 0x80 != bf->mask) fputc( bf->rack, bf->fp);



    fclose( bf->fp);  //关闭二进制输出文件




    free( bf);  //释放输出结构体的内存




}

四．lzw解码分析

1. lzw解码流程图

LZW编码实现（C)

2 lzw解码代码分析

2.1 解码总流程代码





void LZWDecode( BITFILE *bf, FILE *fp){



    int character;  /*当新读取的编码不存在于字典中时，character为旧编码last_code的首字母。当新读取的编码字典中存在时，character为新编码new_code的首字母*/




    int new_code, last_code;



    int phrase_length;  //输出字符串的长度




    unsigned long file_length;  //输出文件长度




 



    file_length = BitsInput( bf, 4*8);  /*输入文件起始处存储输出文件的大小，存储为unsigned int类型，占32位*/




    if( -1 == file_length) file_length = 0;



    InitDictionary();  //初始化字典，设置0-256根节点




    last_code = -1;  //开始时旧编码处空缺，故设置last_code为-1




    while( 0<file_length){  //是否读取到最后一个编码




        new_code = input( bf);  //以16位读取新编码




        if( new_code >= next_code){   //字典中没有新编码




            d_stack[0] = character;  /*character为旧编码last_code的首字母，将其放置在栈数组顶部d_stack[0]*/




 



/*遍历旧编码last_code所在树，将last_code对应字符串放置于d_stack栈数组中。前缀放于栈底方向，后缀位于d_stack[1]。得到字符总数，即要输出字符串的长度*/



            phrase_length = DecodeString( 1, last_code);



        }else{  //字典中有新编码




 



/*遍历新编码new_code所在树，将new_code对应字符串放置于d_stack栈数组中。前缀放于栈底方向，后缀位于栈顶d_stack[0]。得到字符总数，即要输出字符串的长度*/



            phrase_length = DecodeString( 0, new_code);



        }



 



/*当新读取的编码不存在于字典中时，character为旧编码last_code的首字母。当新读取的编码字典中存在时，character为新编码new_code的首字母*/



        character = d_stack[phrase_length-1];



 



/*当新读取的编码不存在于字典中时，输出(旧编码last_code对应字符串，last_code对应首字母)。当新读取的编码存在于字典中时，输出新编码new_code对应字符串*/



        while( 0<phrase_length){



            phrase_length --;



            fputc( d_stack[ phrase_length], fp);



            file_length--;



        }



 



/*当新读取的编码不存在于字典中时，将(last_code对应字符串，last_code对应首字母)}添加到字典中。当新读取的编码存在于字典中时，将(last_code对应字符串，new_code对应首字母)添加到字典中。*/



        if( MAX_CODE>next_code){  



            AddToDictionary( character, last_code);



        }



 



		//新编码变为旧编码




        last_code = new_code;



    }



}

2.2 以count位为单位，从输入文件中得到数据（lzw编码是等长码）





unsigned long BitsInput( BITFILE *bf, int count){



    unsigned long mask;




unsigned long value;



	/*假设count为16，则mask为1000 0000 0000 0000*/




    mask = 1L << (count-1);



value = 0L;  //初始化value为0




	/*mask由1000 0000 0000 0000向右移位至溢出为0时循环结束，取得16位的等长码*/





while( 0!=mask){



	/*输出文件中下一位为1时，value相应位置变为1。为0时，不作操作，直接跳至下一位*/




        if( 1 == BitInput( bf))



            value |= mask;  //value在mask所表示位置的二进制数字变为1




        mask >>= 1;  //mask所表示位置向右一位




    }



    return value;



}

得到输出文件中下一位二进制数（从右向左）





int BitInput( BITFILE *bf){



    int value;



 



    if( 0x80 == bf->mask){  //mask为1000 0000时，从文件中得到一字节数据




        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;  //取得mask所表示位置的二进制数字




bf->mask >>= 1;  //mask所表示位置向右一位




	/*若掩码溢出为0，则mask重新变为1000 0000*/




    if( 0==bf->mask) bf->mask = 0x80;




return( (0==value)?0:1);  //value为0时返回0，为非零值时返回1




}

2.3 将code对应字符串放置于d_stack栈数组中。前缀放于栈底方向，后缀位于d_stack[start]。得到字符总数，即要输出字符串的长度





int DecodeString( int start, int code){



    int count;  //count标记数组下标




    count = start;



    while( 0<=code){  //code为-1时，到达树根，循环结束




        d_stack[ count] = dictionary[code].suffix;  /*将下标为code节点中的后缀字母放置于数组相应位置*/




        code = dictionary[code].parent;  //节点上移至母节点处




        count ++;  //数组下标增加1




    }



    return count;



}

五．实验结果

文件类型	压缩前大小(单位:k)	压缩后大小(单位:k)	压缩效率
word文档	31	15	51.6%
ppt演示文稿	340	228	32.9%
gif图片	2	3	-50%
MP3文件	4513	5564	-23.3%
MP4视频	9964	13101	-31.5%
excel表格	32	14	56.3%
html网页	333	240	27.9%
jpg图片	1306	1516	-16.1%
pdf文档	29641	32999	-11.3%
avi视频	27902	33688	-20.7%

LZW编码实现（C)

二．数据结构

三．lzw编码分析

五．实验结果

C#使用SignalR实现进度条

C#实现将字符串转换成代码并执行

括号匹配（c语言实现）

c#实现多线程局域网聊天系统

C#实现窗口之间的传值

C#实现矩阵乘法实例分析

C#实现windows form拷贝内容到剪贴板的方法

C#实现异步连接Sql Server数据库的方法

C#实现简单屏幕监控的方法

C#实现rar压缩与解压缩文件的方法