数据压缩(LZW算法) -- C++实现


LZW的算法思想是,把出现过的字符串映射到某个标号上,这样就可能用较短的编码来表示长的字符串,实现压缩

实现代码

// LZW.h

#ifndef LZW_H
#define LZW_H

#include "Component.h"
#include "PriorityQueueMinPtr.h"
#include "TST_val.h"

namespace jay{

	class LZW
	{
	public:
		LZW()
		{
			R = 256;
			BIT = 12;
			L = pow(2.0,BIT);

			m_strTable ="abcdefghijklmnopqrstuvwxyz";
			m_strTable += "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
			m_strTable += "0123456789";
			m_strTable +=" ~!@#$%^&*()_+-=;''<>?,";

			m_iTableLength = m_strTable.length();
		}

		~LZW()
		{
		}

		// 压缩
		string Compress(string str)
		{

			if (str.length() == 0)
			{
				return "";
			}

			// 用一颗三向单词查找树来模拟符号表,该树保存的节点的形式是 key是字符 value是int值
			// 对于初始化的节点,key都是不重复的单个的ascii字符,value是该字符对应的十进制数
			// 对于其他入树的节点,key也是字符(该字符是字符串的结尾),value是由257开始增加的整数(不会与ascii的整数冲突)
			TST_val st;
			// 初始化已知字符
			// 树中的value是字符,key是该ascii码字符对应的十进制数
			for (int i = 0; i < m_iTableLength; i++)
			{
				string tmp; 
				tmp += m_strTable.at(i);
				st.put(tmp,m_strTable.at(i));
			}

			// code>256 肯定不是ascii字符
			int code = R+1;

			string strC;
			while (str.length() > 0) 
			{
				// 查找str在符号表里的最长前缀
				string s = st.longestPrefixOf(str);

				// 对应的12位整数的二进制比特串
				strC += GetBitString(st.get(s)->val,BIT);
				strC += " ";

				int t = s.length();

				// t 是目前str在树中的最长前缀的长度古,所以t + 1肯定不存在于符号表中,将其添加进树
				// code < L 限制符号表里的标记的数量不超过某个数(该数和位数编码相关)
				if (t < str.length() && code < L)
				{
					string tmp = str.substr(0, t + 1);
					st.put(str.substr(0, t + 1), code++);
				}

				// 注意上面入树的元素 t + 1的最后1位下一次处理依然会被处理的,下次从这个1开始处理
				// 下次扫描跳过当前的最长前缀
				str = str.substr(t,str.length()-t);            
			}

			return strC;
		}

		// int to bit
		string GetBitString(int d,int r)
		{
			string strb = "";
			for (int i = 0; i < r; i++) 
			{
				// (d >> (r - i -1)) & 1 
				// 第一次获取的是最高位 第二次是次高位,以此类推
				bool bit = ((d >> (r - i - 1)) & 1) == 1;
				if (bit)
				{
					strb += "1";
				}
				else
				{
					strb += "0";
				}
			}

			return strb;
		}

		// 解压
		string Expand(string str) 
		{
			if (str.length() == 0 )
			{
				return "";
			}

			string strExpand;

			string *st = new string[L]();

			// 初始化已知的单个字符
			// st数组初始化值是 st[ascii字符对应的整数] = ascii字符
			int i;
			for (i = 0; i < m_iTableLength; i++)
			{
				string tmp; 
				tmp += m_strTable.at(i);
				st[m_strTable.at(i)] = tmp;
			}

			// i 指向压缩时code的起始大小
			i = R + 1;

			// 获取第一个压缩数
			// 因为初始化的符号表都是由单字符组成,所以第一个压缩数对应的肯定是一个单字符
			// 也就是第一个字符存在于st数组中,肯定不为空
			string tmp = str.substr(0,BIT);
			int codeword = GetIntFromStringBit(tmp,BIT);
			// 获取到第一个原始字符
			string val = st[codeword];

			// 删除当前的BIT位编码
			str = str.substr(BIT,str.length()-BIT);

			while (1)
			{
				strExpand += val;
				if (str.length() == 0)
				{
					break;
				}
				// 获取下一个压缩数
				tmp = str.substr(0,BIT);
 				if (str.length() > BIT)
 				{
					// 删除当前的BIT位编码
					str = str.substr(BIT,str.length()-BIT);
 				}
				else // str长度为 BIT 是最后一个元素
					str = "";

				codeword = GetIntFromStringBit(tmp,BIT);
				string s = st[codeword];

				// 如果codeword指向的位置等于i,对于st数组来说,此时,该位置的值为 "" 肯定不能按照下面 173 行的处理方式
				// 特殊情况处理,可以看5.5.6.15的说明
				if (i == codeword) 
					s = val + val.at(0);

				// 分析现有的字符,添加字符表和压缩时的过程类似
				// val是上一次解压的字符串 s是当前解压获得的字符串
				// 上一次的字符串 + 当前字符串的第一位 相当于 压缩时的最长前缀和下一位也就是 t + 1
				// 然后i++,指向st数组下一个位置
				if (i < L)
					st[i++] = val + s.at(0);

				val = s;
			}

			delete []st;
			st = nullptr;

			return strExpand;
		}

		int GetIntFromStringBit(string str,int r)
		{
			int d = 0;
			for (int i=0;i<r;i++)
			{
				char c = str.at(i);
				// 如果当前位为1
				if (c == 49)
				{
					d += pow(2.0,r-i-1);
				}
			}
			return d; 
		}

	private:

		// alphabet size of extended ASCII
		int R;
		string m_strTable;
		int m_iTableLength;

		int L; // 符号表对应value的最大值 目前使用12位的编码,为 4095 + 1
		int BIT; // 符号表对应value的编码位数,目前是12位
	};

};

#endif

测试代码

//main.cpp
#include "Component.h"
#include "LZW.h"
using namespace jay;

int main(int argc, char* argv[])
{
	LZW lsz;           
	string strSource = "The best of the BBC, with the latest news and sport headlines, weather, TV & radio highlights and much more from across the whole of BBC Online";
//	strSource = "ABABABA";
	cout << "原始字符串:" <<endl;
	cout << strSource <<endl;
	string strC =  lsz.Compress(strSource);
	cout << "压缩后的比特流:" <<endl;
	cout << strC<< endl;
	 
	strC.erase(remove(strC.begin(), strC.end(), ' '), strC.end());
	cout << "解压后的字符串:" <<endl;
	cout << lsz.Expand(strC) << endl;

	cout << "当前压缩率为:" << strC.length() * 100 /(strSource.length()*12) << "%" <<endl;
}

测试结果

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。