目录

一、什么是哈夫曼编码？

二、utf-8编码

三、压缩流程

1.哈夫曼节点及汉字判断

2.获取字符权重

3.根据权重构造哈夫曼树

4.根据哈夫曼树构造译码表

5.压缩

四、解压缩

五、效果展示

哈夫曼编码，又称为哈夫曼编码（Huffman Coding）是一种可变长编码（ VLC, variable length coding)）方式，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。

UTF-8是Unicode的实现方式之一 并不是唯一 也不等同于Unicode。除了UTF-8 还有UTF-16和UTF-32 只是很少被使用。

UTF-8的特点是对不同范围的字符使用不同长度的编码 它可以使用1~4个字节表示一个符号 根据不同的符号而变化字节长度。

其编码规则很简单对于单字节的符号 ，字节的第一位设为0 ，后面7位为这个符号的Unicode码。因此对于英语字母 UTF-8编码和ASCII码是相同的。对于n字节的符号,其第一个字节的前n位都设为1 第n+1位设为0 后面字节的前两位一律设为10 剩下的没有提及的二进制位 全部为这个符号的Unicode码。

在utf-8中一个英文字符占一个字节，用一个char表示足矣，但对中文而言，汉字占了三个字节，所以在这里我采用c++string类来统一表示中英文。

typedef struct huffmannode {
	std::string ch;
	int weight = 0;
	int father = 0;
	int lc = 0, rc = 0;
}huffmanNode;

在读取文件之前我们要先判断所读取的字符是汉字还是英文，由上面的utf-8编码规则我们可以知道汉字的第一个字节的编码一定是 1110 xxxx 而英文字符的编码一定是 0xxx xxxx，所以我们只要判断字节的第一位是不是1就行。

bool judgeEng(unsigned char c)
{
	if (!(c & 0x80))
		return true;
	return false;
}

在判断一个字符是否为汉字后，如果是汉字，就接着再读两个字节，这三个连着的字节就是一个汉字。按此方法将文本遍历到结尾，统计出每个字符的出现次数。（为方便，在这里我用了map）

void getWeightMap(ifstream& fin, const char* fileName, map& _weightMap)
{
	fin.open(fileName, std::ios::in);
	unsigned char c;
	std::string s;
	while (fin.peek()!=EOF)
	{
		c = fin.get();
		s = "";
		if (judgeEng(c))
			s += c;
		else
		{
			s += c;
			c = fin.get();
			s += c;
			c = fin.get();
			s += c;
		}
		_weightMap[s]++;
	}
	fin.close();
}

void getHuffmanTree(map& _weightMap, vector& _huffmanTree)
{
	int n = _weightMap.size();
	for (auto it : _weightMap) {
		huffmannode t;
		t.ch = it.first;
		t.weight = it.second;
		_huffmanTree.push_back(t);
	}
	int s1 = 0, s2 = 0;
	for (int i = n; i< 2 * n - 1; ++i) {
		huffmannode t;
		selectTwo(_huffmanTree, i, s1, s2); //从前i个选出两个权重最小的俩个
		_huffmanTree.at(s1).father = i;
		_huffmanTree.at(s2).father = i;
		t.lc= s1;
		t.rc = s2;
		t.weight = _huffmanTree.at(s1).weight + _huffmanTree.at(s2).weight;
		_huffmanTree.push_back(t);
	}
}

void getPassworld(vector& _huffmanTree, map& _passworldMap)
{
	int n = (_huffmanTree.size() + 1) / 2;
	for (int i = 0; i< n; ++i) {
		std::string passworld = "";
		int t = i;
		int fa = _huffmanTree.at(i).father;
		while (fa) {
			if (_huffmanTree.at(fa).lc == t)
				passworld = '0' + passworld;
			else if (_huffmanTree.at(fa).rc == t)
				passworld = '1' + passworld;
			t = fa;
			fa = _huffmanTree.at(t).father;
		}
		_passworldMap.emplace(huffmanTree.at(i).ch, passworld);
	}
}

得到译码表后，将原文的每个字符（包括中文）翻译成对应的不定长二进制字符串，然后以8位为一个uchar再重新输入到另一个文件中即为压缩后的文件。

//将原文翻译成二进制字符串
std::string binary = "";
	fin.open(fileName, std::ios::in);
	unsigned char c;
	binary = "";
	while (fin.peek()!=EOF)
	{
		c = fin.get();
		std::string s = "";
		if (judgeEng(c))
			s += c;
		else
		{
			s += c;
			c = fin.get();
			s += c;
			c = fin.get();
			s += c;
		}
		binary+=passworldMap[s];
	}
	fin.close();

//将得到的二进制字符串每8位转为一个uchar类型写入压缩文件
	for (int i = 0; i< binary.size(); i += 8)
	{
		std::string k = binary.substr(i, 8);
		c = binaryStringToChar(k);
		fout<< c;
	}

在这个过程中我们需要解决两个问题：

1.原文翻译后的二进制字符串长度不是8的倍数

这个问题很简单，不足8位在末尾补0或者1都行。

//在末尾补0 
int add0Num = binary.size() % 8;
	if (add0Num)
		add0Num = 8 - add0Num;
	for (int i = 0; i< add0Num; ++i, binary += '0');

2.压缩文件如何解压

因为需要对压缩文件解压，所以我们在压缩时还需要加入一些辅助信息，比如哈夫曼树的权重图和上个问题中末尾补0或1的个数都是我们解压时需要的。所以在压缩时这些信息也需要一同放入压缩文件中。

// 将 辅助信息写入压缩文件中
	fout<< weightMap.size()<< " "<

unsigned char c;
	int size, add0;//字符个数和末尾补0的个数
	std::map_weightmap;//权重图
	fin >>size >>add0;
	fin.get();
	for (int i = 0; i< size; ++i)//从压缩文件读取原权重图
	{
		std::string s = "";
		int weight = 0;
		c=fin.get();
		if (judgeEng(c))
			s += c;
		else 
		{
			s += c;
			c = fin.get();
			s += c;
			c = fin.get();
			s += c;
		}
		c=fin.get();
		c = fin.get();
		for (; c!= ' '; c=fin.get()) 
		{
			weight = weight * 10 + c - '0';
		}
		_weightmap.emplace(s, weight);
	}

	//还原哈夫曼树
	std::vector_huffmantree;
	getHuffmanTree(_weightmap, _huffmantree);

	std::string binary = "";
	while (fin.peek()!=EOF)//将压缩文件的内容转为二进制字符串
	{
		c = fin.get();
		binary += ucharToBinaryString(c);
	}
	fin.close();

	for (int i = 0; i< add0; binary.pop_back(), ++i);//删去压缩时末尾补充的0