C语言数据结构+代码(2)

2.5 w压缩过程的算法流程图

2.5 解压模块

Lzw解压原理：

通过上面压缩原理，大概可以知道了解到压缩过程就是不找子串，旧的子串不作处理，新的子旧就为其添加新的标记，交输出前缀到输出流。

解压其实就是压缩的逆过程，因为lzw是动态生成编译表，所以本人认为解压过程就相对难解理一些，下面说明一下解压过程：

否 是 否 大 于 是 基本标志

是否在 是 后缀变前缀 编译表

否

前缀+后缀（当前字符）

输出 后缀变前缀 读入字符（直到文件结束） 开始 赋给后缀 遍历编译表 添加当前字符到编译

三、祥细设计

3.1 lzw压缩的实现：

压缩的基本原理在概要分析已经讲述过，在这里主要是把每个步聚祥细的说一编，并且把此模块的主要功能实现过程与核心代码解释一遍。

以下是具体过程：

在讲之前，还要说明几个名词以及它们的作用，为了区别编译表中串值与单个字符，要用到清除标志CLEAR和结束标志end ,比如说，基本标志有8位，能表示的基本单个字符范围就是256（0-255），如果超过256，就要有新的标志，为了区别原来的标志与新的标志，就要用清除标志CLEAR和结束标志end，清除标志CLEAR一般比单个字符最大标志大1，而结束标志end又比清除标志CLEAR大1，所以8位基本标志的清除标志CLEAR和结束标志end 分别为256，257。如果有新的标志就从258开始。

LZW压缩码长度最长是12bits。超过这个长度将要重新开始编码解码。

事实上压缩一个文件时，常常要对串表进行多次初始化，往往一文件中出现的第一次出现的基 本字符串个数会超过4096个，在压缩过程中只要字符串的长度超过了4096，就要将当前前缀和当前码 输入代码流，并向代码流中加入一个清除码，初始化串表，继续按上述方法进行压缩。

例 如：

有一个字符串，是由A、B、C、D四个字符构成的，那么就可以用0 1 2 3 来表示，两位就够了。

A B A D C A B A A A A B .....

首先要扩充一位，变成3位，定义 Clear＝4，End＝5。那么以后的标号就从6开始。 缩过程中要用的主要字段与函数：

A 最在标志：p (p<=65535)

B ASSCII代码的数量 256 表的基本标志 C void hashinit(void)//表初始化

D void hashinsert(Element element)//表的插入 E struct Element//hash表中的元素

{ int key; int code; Element *next; }*table[MAX];//表

F hashfind(int key,Element &element)//表的查找 fclose(fp1);// 文件关闭 fclose(fp2);

同时还在用到文件的输入输出： FILE *fp1,*fp2;

用到的文件读写函数： fwrite(file1,20,1,fp2);

ch=fgetc(fp1);

下面是压缩过程的具体过程： ：

Initialize String Table;

[.c.] = Empty;

[.c.]k = First Character in CharStream; while ([.c.]k != EOF ) {

if ( [.c.]k is in the StringTable) {

[.c.] = [.c.]k; } else

{

add [.c.]k to the StringTable;

Output the Index of [.c.] in the StringTable to the

CodeStream; [.c.] = k; }

[.c.]k = Next Character in CharStream;

}

Output the Index of [.c.] in the StringTable to the CodeStream;

3.2 lzw解压过程：

在解压前先说明一下，读出一个字符时，如果小于基本标志（前面压缩的定义为0-255），就直接输出》

如果大基本标志（258，有清除与结束标志），并在编译表中存在代码值时，就到编译表找到中它对应的字符，并输出。

如果没找到，就把前缀的第1个字符作为当前字符，把这个当前字符和前缀同时输出，并且把他们存储在编译表中》

以下是具体的解压步骤：

1、 读取第一个字符，输出它，并且把它赋给前缀。

2、 读取下一个字符，如果没有结束，把它赋给当前字符，同时判断是否大于基本标志N。

3、 如果大于N，有两种情况：在编译表中或不在。

4、 没在编译表中，把前缀与后缀组成的当前字符的第一个字符输出 ，并把当前字符存储到编译表中，同时把当前字符赋给前缀，回到2重新执行。

5、 在编译表中，遍历编译表的所有标记所对应的字符，并且输出它，把当前字符赋给前缀，并回到2重新执行。

6、 如果小于N，输出当前字符，并且把当前字符赋给前缀，回到2重新执行。 7、 直到最后一个字符，输出标记同时结束。

下面是压缩过程的该心过程：

Initialize String Table;

[code] = First Code in the CodeStream;

Output the String for [code] to the CharStream; [old] = [code];

[code] = Next Code in the CodeStream; while ([code] != EOF )

{

if ( [code] is in the StringTable)

{

Output the String for [code] to the CharStream; // 输出[code]所对 …… 此处隐藏：544字，全部文档内容请下载后查看。喜欢就下载吧 ……