lzw.cpp

关于压缩与解压缩的源码 自己编的 适合数据结构学习 用到了散列

#include"LZW.h"

#define D 1048580
#define codes 1048576   //2^20
#define ByteSize 8       
#define excess 4
#define alpha 256 
#define mask1 255     //2^8-1
#define mask2 15       //2^4-1

ifstream in;
ofstream out;
int size;
int LeftOver;
int status=0;
unsigned long Table[D][2];

void SetFiles(int argc,char*argv[])
{
	char OutputFile[50],InputFile[50];
	if(argc>=2)strcpy(InputFile,argv[1]);
	else
	{
		cout<<"Enter name of file to compress"<<endl;
		cout<<"File name should have no extension"<<endl;
		cin>>InputFile;
	}
	if(strchr(InputFile,'.'))
	{
        cerr<<"File name has extension"<<endl;
		exit(1);
	}

	if(in.fail())
	{
		cerr<<"Cannot open"<<InputFile<<InputFile<<endl;
		exit(1);
	}
	strcpy(OutputFile,InputFile);
	strcat(InputFile,".txt");
	in.open(InputFile,ios::binary);	
	strcat(OutputFile,".zzz");
	out.open(OutputFile,ios::binary);
}

void Output(unsigned long pcode)
{
	unsigned char c,d,e;
	if(status)
	{
		d=pcode&mask1;
		e=(pcode>>ByteSize)&mask1;
	    c=(LeftOver<<excess)|(pcode>>ByteSize*2);
		out<<c;
		out<<e;
		out<<d;
		//cout<<c<<" "<<e<<" "<<d<<" ";
		status=0; 
	}
	else
	{
		LeftOver=pcode&mask2;
		c=(pcode>>excess)&mask1;
		d=(pcode>>(excess+ByteSize));
		//cout<<d<<" "<<c;
		out<<d;
		out<<c;
		status=1;
	}
}

void Insert(element e)
{
	Table[e.code%D][0]=e.key&mask1;
	Table[e.code%D][1]=e.key>>ByteSize;
	//cout<<e.code<<"-"<<Table[e.code%D][0]<<"-"<<Table[e.code%D][1]<<"  ";
}

bool Search(unsigned long k,int used,int &i)
{
	unsigned long a=k&mask1;
	unsigned long b=k>>ByteSize;
	//cout<<a<<"-"<<b<<"-"<<used<<endl;
	for(i;i<used;i++)
		if((Table[i][0]==a)&&(Table[i][1]==b))return true;
    return false;
}
void Compress()
{
	element e;
	for(unsigned long i=0;i<alpha;i++)
	{
		e.key=i;
		e.code=i;
		Insert(e);
	}
	int used=alpha;
	unsigned char c;
	in.get(c);
	unsigned long pcode=c;
	//cout<<c<<" ";
	if(!in.eof())
	{
		do
		{
			in.get(c);
			//cout<<c<<" ";
			if(in.eof())break;
			unsigned long k=(pcode<<ByteSize)+c;
			int i=0;
			if(Search(k,used,i))pcode=i;
			//cout<<pcode<<" ";}
			else
			{
				Output(pcode);
				//cout<<pcode<<endl;
				if(used<codes)
				{
					e.code=used++;
					e.key=(pcode<<ByteSize)|c;
					Insert(e);
				}
				//cout<<c;
				pcode=c;
			}
		}while(true);
	    Output(pcode);
	    if(status)
		{
		    c=LeftOver<<excess;
		    out.put(c);
		}
	}
	out.close();
	in.close();
}

void main(int argc,char*argv[])
{
	//Table=new unsigned long[D];
	//string word;
	//ifstream in("text1.txt");
	//ofstream out("text2.txt");
	//while(getline(in,word))
	//	out<<word<<"\n";
	SetFiles(argc,argv);
	Compress();
	//
}