LZW压缩与解压

青旅半醒 2022-08-20 04:23 344阅读 0赞

# LZW压缩算法 #

LZW算法流程图

核心：LZW算法基于转换串表（字典）T，将输入字符串映射成定长（通常为12位）的码字。在12位4096种可能的代码中，256个代表单字符，剩下3840给出现的字符串。

LZW字典中的字符串具有前缀性，即 ωK∈T=>；ω

![c83d70cf3bc79f3d0cdf1b4cb9a1cd11728b2994.jpg][]

T。

## **压缩算法**： ##

**步骤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的码字输出到码字流;  
　　② 结束。**

# LZW解压算法 #

## 解压算法： ##

(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：结束译码 。

#define _CRT_SECURE_NO_WARNINGS
    #include<iostream>
    #include<string>
    #include<fstream>
    #include<vector>
    #include<algorithm>
    #include<queue>
    #include<time.h>
    #include<map>
    using namespace std;
    class LZW
    {
    private:
    	double B_bit = 0;
    	double C_bit = 0;
    	string filename;//文件名
    	map<unsigned short, string>form;//压缩表
    	map<string, unsigned short>find_string;
    public:
    	LZW();
    	void initialize_form_findP();
    	void compress();//压缩
    	void decompress();//解压
    	void action();//外部接口
    };
    LZW::LZW()
    {
    	cout << "LZW压缩" << endl;
    	cout << "请输入要压缩的文件名：";
    	getline(cin, filename);
    }
    void LZW::initialize_form_findP()
    {
    	string P;
    	for (int i = -128; i < 128; i++)
    	{
    		P.push_back(i);
    		form.insert(pair<unsigned short, string>(i, P));
    		find_string.insert(pair<string, unsigned short>(P, i));
    		P.clear();
    	}
    }
    void LZW::compress()
    {
    	ofstream fin("LZW.bin", ios::binary);
    	if (fin.is_open() == false)
    	{
    		cout << "不能打开LZW.bin" << endl;
    		return;
    	}
    	FILE *f = fopen(filename.c_str(), "rb+");
    	if (f == NULL)
    	{
    		cout << "不能打开" << filename << endl;
    		return;
    	}
    	char nextChar;
    	string test, P;
    	int count = 128;
    	while (fread(&nextChar, sizeof(char), 1, f))//LZW压缩算法
    	{
    		B_bit++;
    		test = P + nextChar;
    		map<string, unsigned short>::iterator it1;
    		it1 = find_string.find(test);
    		if (it1 == find_string.end())
    		{
    			map<string, unsigned short>::iterator it2;
    			it2 = find_string.find(P);
    			fin.write((char*)&it2->second, sizeof(unsigned short));
    			form.insert(pair<unsigned short, string>(count, test));
    			find_string.insert(pair<string, unsigned short>(test, count));
    			P = nextChar;
    			count++;
    		}
    		else
    		{
    			P += nextChar;
    		}
    	}
    	B_bit *= 8;
    	map<string, unsigned short>::iterator it;
    	it = find_string.find(P);
    	fin.write((char*)&it->second, sizeof(unsigned short));
    	fclose(f);
    	fin.close();
    }
    void LZW::decompress()//解压
    {
    	ifstream fin("LZW.bin", ios::binary);
    	if (!fin.is_open())
    	{
    		cout << "不能打开LZW.bin" << endl;
    		return;
    	}
    	ofstream fout("LZW decompress.txt");
    	if (!fout.is_open())
    	{
    		cout << "不能打开LZW decompress.txt" << endl;
    		return;
    	}
    	string P;
    	map<unsigned short, string>dictionary;//解压字典
    	for (int i = -128; i < 128; i++)
    	{
    		P.push_back(i);
    		dictionary.insert(pair<unsigned short, string>(i, P));
    		P.clear();
    	}
    	unsigned short cW, pW;//解压算法
    	fin.read((char*)&cW, sizeof(unsigned short));
    	C_bit++;
    	map<unsigned short, string>::iterator it;
    	it = dictionary.find(cW);
    	P = it->second;
    	fout << P;
    	pW = cW;
    	int count = 128;
    	char C;
    	while (fin.read((char*)&cW, sizeof(unsigned short)))
    	{
    		C_bit++;
    		it = dictionary.find(cW);
    		if (it == dictionary.end())
    		{
    			it = dictionary.find(pW);
    			P = it->second;
    			C = P[0];
    			dictionary.insert(pair<unsigned short, string>(count, P + C));
    			count++;
    			fout << P + C;
    		}
    		else
    		{
    			P = it->second;
    			fout << P;
    			C = P[0];
    			it = dictionary.find(pW);
    			P = it->second;
    			dictionary.insert(pair<unsigned short, string>(count, P + C));
    			count++;
    		}
    		pW = cW;
    	}
    	C_bit *= 16;
    	fin.close();
    	fout.close();
    }
    void LZW::action()
    {
    	time_t start, end;
    	time(&start);
    	initialize_form_findP();
    	compress();
    	time(&end);
    	cout << "LZW 压缩时间:" << end - start << "s" << endl;
    	time(&start);
    	decompress();
    	time(&end);
    	cout << "LZW 解压时间:" << end - start << "s" << endl;
    	double answer = C_bit / B_bit;
    	answer /= 0.01;
    	cout << "LZW压缩比：" << answer << "%" << endl;
    }
    
    int main()
    {
        LZW lzw;
        lzw.action();
        system("pause");
        return 0;
    }

[c83d70cf3bc79f3d0cdf1b4cb9a1cd11728b2994.jpg]: /images/20220731/816b1783d13e457cb9723e2ae4030216.png