无损数据压缩LZW算法

一、实验目的

1．掌握LZW算法的编码过程；

2．掌握LZW算法的译码过程。

二、实验设备与环境

Dev-C++ 5.9.2，Windows 7 操作系统

三、实验内容、程序清单及运行结果

实验要求：

用Dev-C ++编写LZW算法程序。

1. 实现LZW编码程序。

2. 实现LZW解码程序。

实验参考步骤：

1．打开Dev-C ++，进入编程环境，新建一个源代码文件，文件名任意；

2．将下面我所编写的代码拷贝到所新建的源代码文件中；

3．点击编译运行。

C++源代码：

/**
*	作者：戴文治
*	时间：2017年11月3日
*	描述：LZW编码译码算法
*	特点：该代码具有可移植性，可在Dev-C++、VC++6.0、VS2010等多种平台完美运行
*		  该代码具有可重用性，运行后可对多个测试用例进行顺序测试而不受影响
*/
#include<iostream>
#include<cstring>
#define N 1000
using namespace std;
class LZW{ //LZW算法类
public:
	char encodeStr[N];		//要编码的字符串
	int decodeList[N];		//要译码的数组
	int firstDictionaryNum; //先前词典的大小 
	int length;				//当前词典的大小 
	char dictionary[N][N];	//先前词典
	
	
	LZW(){					//构造函数 
		encodeStr[0] = '\0';
		
		for(int i=0;i<N;i++){
			this->decodeList[i]=-INT_MAX;
		}
		
		for(int i=0;i<N;i++){
			this->dictionary[i][0] = '\0';
		}
		
		firstDictionaryNum = 0;
		length = 0;
	}
	
	
	bool initDictionary() 		//初始化先前词典
	{	
		if(encodeStr[0]=='\0'){			//若没有要编码的字符串，则不能生成先前词典 
			return false;
		}
		dictionary[0][0] = encodeStr[0];//将要编码的字符串的第一个字符加入先前词典 
		dictionary[0][1] = '\0';
		length = 1;
		int i,j; 
		for(i=1;encodeStr[i]!='\0';i++){//将要编码的字符串中所有不同的字符加入先前词典 
			for(j=0;dictionary[j][0]!='\0';j++){
				if(dictionary[j][0]==encodeStr[i]){
					break;
				}
			}
			if(dictionary[j][0]=='\0'){
				dictionary[j][0] = encodeStr[i];
				dictionary[j][1] = '\0';
				length++;
			}
		}
		firstDictionaryNum = length;			//先前词典的大小
		return true;
	}
	
	
	void Encode() 	 		 	//编码
	{
		for(int g=0;g<firstDictionaryNum;g++){	//先前词典中的初始编码没有输出编码，故设置为-1 
			decodeList[g]=-1;
		}
		int num = firstDictionaryNum;
		char *q,*p,*c;
		q =  encodeStr;						  	//q为标志指针，用来确认位置的 
		p =  encodeStr; 						//p指针作为字符串匹配的首字符 
		c = p;									//通过不断移动c指针实现匹配 
		while(p-q != strlen(encodeStr)){		//若还没匹配完所有字符，则循环 
			int i,j;
			int index=0;
			for(i=0;dictionary[i][0]!='\0'&&c-q!=strlen(encodeStr);i++){//通过不断向后移动c指针实现匹配
				char temp[N]; 
				strncpy(temp,p,c-p+1);			//每添加一个匹配字符，则已匹配字符串temp增加一个字符 
				temp[c-p+1]='\0';
				if(strcmp(temp,dictionary[i])==0){//字符匹配成功 
					c++;
					index = i;
				}
			}
			decodeList[num++]=index;			//遇到一个不匹配的字符或者已经没有字符可以匹配，则输出已匹配的字符串 
			if(c-q!=strlen(encodeStr)){			//若到一个不匹配的字符且还有字符未匹配，则说明出现了新的词典字段，加入词典 
				strncpy(dictionary[length],p,c-p+1);
				dictionary[length][c-p+1]='\0';
				length++;
			}
			p = c;								//匹配下一个时，p指向c的指向 
		}

	} 
	
	
	void Decode()    			//译码 
	{
		for(int i=1;decodeList[i]!=-INT_MAX;i++){	//根据输入代码来循环 
			if(decodeList[i]<=length){				//若出现输入代码在先前词典可以找到，则输出上一个输出的全部+当前输出的第一个 
				strcpy(dictionary[length],dictionary[decodeList[i-1]-1]);
				char temp[2];
				strncpy(temp,dictionary[decodeList[i]-1],1);
				temp[1]='\0';
				strcat(dictionary[length],temp);
			}
			else{									//若出现输入代码在先前词典找不到，则输出上一个输出的全部+上一个输出的第一个 
				strcpy(dictionary[length],dictionary[decodeList[i-1]-1]);
				char temp[2];
				strncpy(temp,dictionary[decodeList[i-1]-1],1);
				temp[1]='\0';
				strcat(dictionary[length],temp);
			}
			length++;
		}
	}	
};


int main(){
	while(true){
		cout<<"\n\t1.编码\t\t2.译码\t\t3.退出\n\n";
		cout<<"请选择:";
		char x;
		cin>>x;
		LZW lzw;
		if(x=='1'){
			cout<<"请输入要编码的字符串:"<<endl<<endl;
			cin>>lzw.encodeStr;
			if(lzw.initDictionary()==false){
				cout<<"请先设置要编码的字符串encodeStr属性"<<endl;
			}
			lzw.Encode();	//开始编码
			cout<<endl<<"编码过程为:"<<endl<<endl;
			cout<<"\t索引号\t\t\t词典\t\t\t输出"<<endl;
			for(int i=0;i<lzw.length;i++){
				cout<<"\t"<<i+1<<"\t\t\t"<<lzw.dictionary[i]<<"\t\t\t";
				if(i>=lzw.firstDictionaryNum){
					cout<<lzw.decodeList[i]+1;
				}
				cout<<endl;
			}
			cout<<"\t-\t\t\t-\t\t\t"<<lzw.decodeList[lzw.length]+1<<endl<<endl<<endl;
		} 
		else if(x=='2'){
			cout<<"请按顺序输入初始先前词典：（例：1 A）(输入0结束)"<<endl;
			int tempNum;
			cin>>tempNum;
			int index = 1; 
			while(tempNum!=0){
				if(tempNum<0){
					cout<<"输入序号错误,重新输入该行"<<endl<<endl;
					getchar();//两个getchar()是删除掉该行已经输入的字符 
					getchar();
					cin>>tempNum;
					continue;
				}
				if(tempNum!=index){
					cout<<"请以递增顺序输入序号,重新输入该行"<<endl<<endl;
					getchar();
					getchar();
					cin>>tempNum;
					continue;
				}
				cin>>lzw.dictionary[tempNum-1];
				cin>>tempNum;
				index++; 
			}
			lzw.firstDictionaryNum = index-1;
			lzw.length = lzw.firstDictionaryNum; 
			
			cout<<endl<<"请输入要译的编码(输入0结束):"<<endl<<endl;
			int temp;
			int j=0;
			cin>>temp;
			while(temp!=0){
				if(temp<0){
					cout<<"输入要译的编码错误,重新输入该编码"<<endl<<endl;
					cin>>temp;
					continue;
				}
				lzw.decodeList[j] = temp;
				j++;
				cin>>temp;
			}
			lzw.Decode();	//开始译码 
			cout<<endl<<"译码过程为:"<<endl<<endl;
			
			cout<<"    输入代码\t\t索引号\t\t词典\t\t输出"<<endl;
			for(int i=0;i<lzw.firstDictionaryNum;i++){
				cout<<"      \t\t\t   "<<i+1<<"  \t\t "<<lzw.dictionary[i]<<endl;
			}
			cout<<"\t"<<lzw.decodeList[0]<<"\t\t   -\t\t -\t\t  "<<lzw.dictionary[lzw.decodeList[0]-1]<<endl;
			for(int i=1;lzw.decodeList[i]!=-INT_MAX;i++){
				cout<<"\t"<<lzw.decodeList[i]<<"\t\t   "<<i+3<<"  \t\t "<<lzw.dictionary[i+3-1]<<"\t\t  "<<lzw.dictionary[lzw.decodeList[i]-1]<<endl;
			}
			cout<<endl<<endl;
		}
		else if(x=='3'){
			break;
		} 
		else{
			cout<<"请输入正确的选择!"<<endl<<endl<<endl;
		}
	}
	return 0;
}

测试用例1截图：

编码：

译码：

测试用例2截图：

编码：

译码：

四、注意事项

注意指针的使用。

要求熟练掌握字符串处理函数，对这些函数的功能和效果要有很明确的意识，否则会出现很多BUG。

最后，这次实验我遇见许多细微的问题，最后还是通过DEBUG调试才发现的。事实证明Dev-C++和VC++非常地难以调试，很不直观！而用VS2010调试程序的话，它会有一个程序变量的窗口，每执行一条语句，它会显示出当前所有变量的值，还会把此次修改的变量用红色标注出来，在此推荐通过VS2010来调试程序。