哈夫曼编码---树的构造与压缩、解压实现

  最近在q群聊天，闲着没事，就教别人写哈夫曼编码用于压缩，教学的回报是5元，以前写过行程编码用于图像的压缩，由于那时候水平有限没选择使用哈夫曼编码去实现，也算是弥补一下大三时候的遗憾吧。
  在上学的时候，很多课程都听过哈夫曼树or哈夫曼编码，都没有去实现过，主要还是以前基础不行，于是也就打算来实现一下练练手，记录一下自己碰到的一些问题，顺便赚赚零花钱。

  在本文中，几个名词说明一下：
  符号：即有一个序列 AABBCDEA，其中符号的集合位{A,B,C,D,E}，而其中的元素就是符号。
  编码：一串二进制数字，如010011…
  权值：如AABBCDEA，A的权重为3，B为2，C为1…

  PS：由于写得太过随意，代码中的变量名字有点随意，只要求能正常运行，而函数的实现效率低下需要改一下树的构造以及后面压缩的过程所以就不打算改了，在接下来的内容中我会说出哪些地方是影响效率并给出一个我自己觉得能够提升效率的方法。
  而哈夫曼编码并没有什么难度，但是在压缩那里，需要思考清楚怎么把字典以及编码写入文件才算是紧凑，这很大的影响了压缩后文件的大小，我的代码在

  哈夫曼的原理挺容易理解的，就不多说了，详情百度百科：https://baike.baidu.com/item/哈夫曼树/2305769?fr=aladdin

二叉树结点的结构：

struct node {
	//存储文件内容
	BYTE _val;
	//节点的编码
	string code;
	//权重
	int _wval;
	node *_left;
	node *_right;
	node(int weight) :_left(NULL), _right(NULL), _wval(weight),code(\"\") {}
};

哈夫曼树的构建：

  哈夫曼树的构建思路为从下至上构建：
    1、先构造所有节点放于一个列表。
    2、选取权重最小的两个节点，生成一个新的节点作为这两个节点的父节点，并从列表中移除这两个节点，把父节点加入列表。
    3、重复步骤2，直到列表只有一个节点，即二叉树的根节点。

  在我的代码中，由于在编写的过程中先试了一下根据二叉树权重列表来构建哈夫曼树，所以传入的参数为权重列表list<int>ary，后面就懒得改了，我这样做的坏处就是，我还需额外构建一个节点列表去存储生成的节点，这样就造成了在构建树找最小的两个权重节点中，我需要顺序遍历两个列表，效率低下，而且还不方便给节点赋值，使得节点初始只有权重和编码，没有其符号_val值，需要再次编写一个函数遍历树并遍历一个符号与权重组成的map/hashmap来进行赋值，所以我这里写得是很烂，不过也懒得改了…

  其中findNode函数为从list<node*>节点列表中找最小的函数，findMin函数为从list<int>权重列表中找最小值。

node *createTree(list<int> ary) {
	node *res = NULL;
	node *left=NULL, *right=NULL;
	list<node*>save;
	while (ary.size()!=1) {
		int lval, rval, sval;
		node *ln = NULL, *rn = NULL;
		if (left == NULL) {
			lval = findMin(ary);
			auto iter = findNode(save, lval);
			if (iter != save.end()) {
				ln = *iter;
				save.erase(iter);
			}
			else {
				ln = new node(lval);
			}
		}
		if (right == NULL) {
			rval = findMin(ary);
			auto iter = findNode(save, rval);
			if (iter != save.end()) {
				rn = *iter;
				save.erase(iter);
			}
			else {
				rn = new node(rval);
			}
		}
		sval = lval + rval;
		ary.push_back(sval);
		auto parent = new node(sval);
		parent->_left = ln;
		parent->_right = rn;
		save.push_back(parent);
	}
	for (auto i : save) {
		int val = i->_wval;
		if (val == ary.front()) {
			res = i;
			break;
		}
	}
	if (res != NULL) {
		buildcode(res, \"\");
		return res;
	}
	return NULL;
}

树节点编码构建：

void buildcode(node *tree, string parent=“”) {
	if (tree == NULL) {
		return;
	}
	if (tree->_right != NULL) {
		if (parent == \"\") {
			tree->_right->code = \"1\";
		}
		else {
			tree->_right->code = parent + \"1\";
		}
	}
	if (tree->_left != NULL) {
		if (parent == \"\") {
			tree->_left->code = \"0\";
		}
		else {
			tree->_left->code = parent + \"0\";
		}
	}
	if (tree->_right != NULL)
		buildcode(tree->_right, tree->_right->code);
	if (tree->_left != NULL)
		buildcode(tree->_left, tree->_left->code);

}

清理树节点：

void deleteTree(node *tree) {
	node *r = NULL, *l = NULL;
	if (tree != NULL) {
		r = tree->_right;
		l = tree->_left;
		delete tree;
		tree = NULL;
		deleteTree(r);
		deleteTree(l);
	}
}

符号的构建：

  
  由于在编写树的构建方式不太好，所以就编写了这个来为哈夫曼树每个叶子节点赋予符号
  其中参数dict为符号-权重的map，res为记录符号-编码的map，因为res在压缩的时候用到，就直接写在这里了。

void buildTreeCode(node *tree, unordered_map<BYTE, int>&dict, unordered_map<BYTE, string>&res) {
	if (tree == NULL) {
		return;
	}
	if (tree->_right == NULL && tree->_left == NULL) {
		for (auto i = dict.begin(); i != dict.end(); i++) {
			BYTE key = i->first;
			if (dict[key] == tree->_wval) {
				tree->_val = key;
				res[key] = tree->code;
				dict.erase(i);
				break;
			}
		}
		return;
	}
	if (tree->_right != NULL) {
		buildTreeCode(tree->_right, dict, res);
	}
	if (tree->_left != NULL) {
		buildTreeCode(tree->_left, dict, res);
	}
}

---------------------------------------------------------------------以上为哈夫曼树的构建--------------------------------------------------------------

压缩

  
  实现压缩的大概原理我大概理解为，当每个符号的编码，码长平均小于8位，那么我们有可能可以用一个字节去表示多个符号（每个符号占用1字节），这样就实现了压缩，而且还是无损压缩，但是这里我们可以看到一个问题，如果平均码长大于等于8的话，那就没必要去压缩了，压缩率很低。

  
  以下便是我实现压缩的过程编写的，压缩函数，由于写得太随意…我自己都不想看
  主要步骤就是：
    1、将符号-编码写入文件中，用于解压的时候使用。
    2、将需要压缩的文件内容转换为编码（在代码中用字符串存储），然后把编码转换位多个32位即4字节的unsigned long变量存储，因为c++的bitset提供的转换只有tolong，tostring，如果不使用bitset也可以自己编写一个按位设置的函数，但是为了方便还是使用bitset吧。
    3、由于在步骤2中，把编码转换为整形变量存储的时候，我们的编码并不是mod 32=0，那么在编码末尾转换的时候会填充0，我们需要记录填充了多少个0，之后在解压的时候通过移位填充的数目从而得到我们原始的编码。

  这部分代码的实现的缺点在步骤1，我在实现的时候，是把符号对应编码的map直接写入文件，为了让解压的时候能够正确读取到符号与编码我还使用了\"gs\"、\"ge\"两个字符串去分割那一串是字典那一串是文件内容的编码，这就造成生成的压缩文件很大，压缩效果及其垃圾。
  好的做法应该是把编码转换为整形变量，然后再写入文件，这样我们就需要一个结构体，存储编码在转换成整形变量时所填充0的个数。
  结构体大概为这样：

struct msg{
	char _key; //符号
	unsigned int _code; //编码所转换为的整形变量
	char fillzero;  //转换时填充的0的个数
};

  这样在步骤1中写入文件的内容就是_key,_code,fillzero，也就是写入6个字节，而我原先的是写入_key与编码，如果编码长的话就大于6个字节，而且加上我自己额外加的gs、ge等字节，就更大了，所以应该把编码转换了再写进去，这样既方便读写还可以不用增加额外的字符去分割。

void encode(const char *path, const char *respath) {
	auto vec = getFileDate(path);
	unordered_map<BYTE, int>keycount;
	unordered_map<BYTE, string>keycode;

	for (auto i : vec) {
		keycount[i]++;
	}
	list<int>weight;
	for (auto i : keycount) {
		weight.push_back(i.second);
	}
	auto res = createTree(weight);
	buildTreeCode(res, keycount, keycode);

	auto fp = fopen(respath, \"wb+\");
	BYTE ch[] = \"gs\";
	//写入字典
	for (auto i : keycode) {
		fwrite(&i.first, 1, sizeof(i.first), fp);
		fwrite(i.second.c_str(), 1, strlen(i.second.c_str()), fp);
		//cout << i.first << \" \" << i.second << endl;
		fwrite(&ch, 1, sizeof(ch)-1, fp);
	}
	cout << \"写入的字典项数：\" << keycode.size() << endl;
	BYTE endch[] = \"ge\";
	fwrite(&endch, 1, sizeof(endch) - 1, fp);
	//编码构成
	string code = \"\";
	unsigned long bcnt = 0;
	int vecsize = vec.size();
	for (int i = 0; i < vecsize; i++) {
		code += keycode[vec[i]];
	}
	int codelen = code.length();
	cout <<\"写入编码长度:\"<< codelen << endl;
	string tcode = \"\";
	vector<unsigned long>cnm;
	for (int i = 0;i< code.length();i++) {
		bcnt++;
		tcode += code[i];
		if (bcnt == 32 || i == codelen - 1) {
			bitset<32>m_bit(tcode);
			auto var = m_bit.to_ulong();
			cnm.push_back(var);
			fwrite(&var, 1, sizeof(var), fp);
			if (i == codelen - 1) {
				cout << \"填充0个数：\" << 32 - bcnt << endl;
				cout << \"写入的填充字符串：\" << tcode << endl;
				bcnt = 32 - bcnt;
				break;
			}
			tcode = \"\";
			bcnt = 0;
		}
	}
	cnm.push_back(bcnt);
	cout << \"写入数据数目：\"<<cnm.size() << endl;
	fwrite(&bcnt, 1, sizeof(bcnt), fp);
	fclose(fp);
	deleteTree(res);
}

解压

  
  怎么压缩的就怎么解压，把数据怎么写进去的，就怎么读出来，并解码写入新文件中。

void decode(const char *path) {

	string code = \"\";
	BYTE tmp;
	unordered_map<string, BYTE>keycode;
	BYTE key = \'\\0\';
	bool iskey = false;
	string val = \"\";
	auto fp = fopen(path, \"rb\");
	vector<BYTE>bytes;
	string checkborad = \"\";
	while (fread(&tmp,1, 1, fp) > 0){
		checkborad += tmp;
		bytes.push_back(tmp);
		if (checkborad.length() == 2) {
			if (checkborad == \"ge\") {
				break;
			}
			checkborad =tmp;
		}
	}
	unsigned long numscode=0;
	vector<unsigned long>nums;
	while (fread(&numscode, 1, sizeof(numscode), fp) > 0) {
		nums.push_back(numscode);
	}
	fclose(fp);
	cout << \"读取的数据数目： \"<<nums.size() << endl;
	//读取编码
	string res = \"\";
	unsigned long fillzero = nums[nums.size() - 1];
	for (int i = 0; i < nums.size()-1; i++) {
		bitset<32> tmp(nums[i]);
		if (i == nums.size() - 2) {
			tmp = tmp << (fillzero);
			auto strtmp = tmp.to_string();
			cout << \"填充0的个数：\" << fillzero << endl;
			cout << \"读取的填充字符串：\"<<strtmp << endl;
			for (int j = 0; j < (32-fillzero); j++) {
				res += tmp[j];
			}
			break;
		}
		res += tmp.to_string();
		
	}
	cout << \"读取的编码长度：\" << res.length() << endl;
	
	//读取字典
	for (int i = 0; i<bytes.size();i++) {
		char check[3];
		if (i + 2 < bytes.size()) {
			for (int j = 0; j < 2; j++) {
				check[j] = bytes[i + j];
			}
			check[2] = \'\\0\';
			if (!strcmp(check,\"gs\")) {
				keycode[val] = key;
				key = \'\\0\';
				val = \"\";
				iskey = false;
				i += 1;
				continue;
			}
			else if (!strcmp(check, \"ge\")) {
				break;
			}
		}
		if (iskey == false) {
			key = bytes[i];
			iskey = true;
			continue;
		}
		else {
			val += bytes[i];
		}
	}
	cout << \"读取的字典项数:\" << keycode.size() << endl;
	string dest = path + string(\".dat\");
	auto wfp = fopen(dest.c_str(), \"wb+\");
	string decode = \"\";
	//翻译编码
	for (int i = 0; i < res.length(); i++) {
		decode += res[i];
		if (keycode.find(decode) != keycode.end()) {
			BYTE ch = keycode[decode];
			fwrite(&ch, 1, 1, fp);
			decode = \"\";
		}
	}
	fclose(wfp);
	//std::cout << keycode.size();
}