目錄

一、什么是哈夫曼編碼？

二、utf-8編碼

三、壓縮流程

1.哈夫曼節(jié)點(diǎn)及漢字判斷

2.獲取字符權(quán)重

3.根據(jù)權(quán)重構(gòu)造哈夫曼樹

4.根據(jù)哈夫曼樹構(gòu)造譯碼表

5.壓縮

四、解壓縮

五、效果展示

哈夫曼編碼，又稱為哈夫曼編碼（Huffman Coding）是一種可變長編碼（ VLC, variable length coding)）方式，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時(shí)稱之為最佳編碼。

UTF-8是Unicode的實(shí)現(xiàn)方式之一 并不是唯一 也不等同于Unicode。除了UTF-8 還有UTF-16和UTF-32 只是很少被使用。

UTF-8的特點(diǎn)是對不同范圍的字符使用不同長度的編碼 它可以使用1~4個(gè)字節(jié)表示一個(gè)符號 根據(jù)不同的符號而變化字節(jié)長度。

其編碼規(guī)則很簡單對于單字節(jié)的符號 ，字節(jié)的第一位設(shè)為0 ，后面7位為這個(gè)符號的Unicode碼。因此對于英語字母 UTF-8編碼和ASCII碼是相同的。對于n字節(jié)的符號,其第一個(gè)字節(jié)的前n位都設(shè)為1 第n+1位設(shè)為0 后面字節(jié)的前兩位一律設(shè)為10 剩下的沒有提及的二進(jìn)制位 全部為這個(gè)符號的Unicode碼。

在utf-8中一個(gè)英文字符占一個(gè)字節(jié)，用一個(gè)char表示足矣，但對中文而言，漢字占了三個(gè)字節(jié)，所以在這里我采用c++string類來統(tǒng)一表示中英文。

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

在讀取文件之前我們要先判斷所讀取的字符是漢字還是英文，由上面的utf-8編碼規(guī)則我們可以知道漢字的第一個(gè)字節(jié)的編碼一定是 1110 xxxx 而英文字符的編碼一定是 0xxx xxxx，所以我們只要判斷字節(jié)的第一位是不是1就行。

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

在判斷一個(gè)字符是否為漢字后，如果是漢字，就接著再讀兩個(gè)字節(jié)，這三個(gè)連著的字節(jié)就是一個(gè)漢字。按此方法將文本遍歷到結(jié)尾，統(tǒng)計(jì)出每個(gè)字符的出現(xiàn)次數(shù)。（為方便，在這里我用了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個(gè)選出兩個(gè)權(quán)重最小的倆個(gè)
		_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);
	}
}

得到譯碼表后，將原文的每個(gè)字符（包括中文）翻譯成對應(yīng)的不定長二進(jìn)制字符串，然后以8位為一個(gè)uchar再重新輸入到另一個(gè)文件中即為壓縮后的文件。

//將原文翻譯成二進(jìn)制字符串
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();

//將得到的二進(jìn)制字符串每8位轉(zhuǎn)為一個(gè)uchar類型寫入壓縮文件
	for (int i = 0; i< binary.size(); i += 8)
	{
		std::string k = binary.substr(i, 8);
		c = binaryStringToChar(k);
		fout<< c;
	}

在這個(gè)過程中我們需要解決兩個(gè)問題：

1.原文翻譯后的二進(jìn)制字符串長度不是8的倍數(shù)

這個(gè)問題很簡單，不足8位在末尾補(bǔ)0或者1都行。

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

2.壓縮文件如何解壓

因?yàn)樾枰獙嚎s文件解壓，所以我們在壓縮時(shí)還需要加入一些輔助信息，比如哈夫曼樹的權(quán)重圖和上個(gè)問題中末尾補(bǔ)0或1的個(gè)數(shù)都是我們解壓時(shí)需要的。所以在壓縮時(shí)這些信息也需要一同放入壓縮文件中。

// 將 輔助信息寫入壓縮文件中
	fout<< weightMap.size()<< " "<

unsigned char c;
	int size, add0;//字符個(gè)數(shù)和末尾補(bǔ)0的個(gè)數(shù)
	std::map_weightmap;//權(quán)重圖
	fin >>size >>add0;
	fin.get();
	for (int i = 0; i< size; ++i)//從壓縮文件讀取原權(quán)重圖
	{
		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)//將壓縮文件的內(nèi)容轉(zhuǎn)為二進(jìn)制字符串
	{
		c = fin.get();
		binary += ucharToBinaryString(c);
	}
	fin.close();

	for (int i = 0; i< add0; binary.pop_back(), ++i);//刪去壓縮時(shí)末尾補(bǔ)充的0