《資料結構、算法與應用 —— C++語言描述》學習筆記 — 優先級隊列 — 應用 — 霍夫曼編碼

一、原理及構造過程
- 1、原理
- 2、擴充二叉樹與霍夫曼編碼
- 3、構造步驟
二、實作
- 1、類圖
- 2、公共常量和結構體
- 3、基類定義
- 4、霍夫曼樹的建構
- 5、生成映射關系
- 6、壓縮類定義
- 7、壓縮類實作
- 8、解壓縮類定義
- 9、解壓縮類實作
- 10、FileReader 的修改
- 11、測試代碼
- 12、總結

一、原理及構造過程

1、原理

前面我們學習了基于 LZW 算法的文本壓縮器，這種算法的依據是子串在文本中的重複出現。而霍夫曼編碼是另外一種文本壓縮算法，這種算法依據的是不同符号在一段文本中相對出現的頻率。假設一個文本是由字元 a、u、x 和 z 組成的字元串，它的長度為1000，每個字元用1位元組來儲存，共需1000位元組（即8000位）。如果每個字元用2位二進制來表示，那麼用2000位空間可以表示1000個字元。此外，我們還需要一定的空間來存放編碼表，它可以采用如下的存儲格式：

符号個數，代碼1，符号1，代碼2，符号2···

符号個數及每個符号分别占8位，每個代碼占 ⌈ log ⁡ 2 （符号個數） ⌉ \lceil \log_2{（符号個數）} \rceil ⌈log2（符号個數）⌉位。是以，編碼表共需48位，壓縮比為 8000 2048 = 3.9 \frac{8000}{2048}=3.9 20488000=3.9

利用上述編碼方式，字元串 aaxuaxz 的編碼為00000110000111。因為每個字元的代碼占2位。是以，從左到右，每次從編碼中提取2位數字通過編碼表編譯，便可獲得原始字元串。

在字元串 aaxuaxz 中，a 出現3次。一個符号出現的次數稱為頻率。符号 a、u、x 和 z 在這個字元串中出現的頻率分别是3、2、1、1.當不同字元出現的頻率有很大差别時，我們可以通過可變長編碼來縮短編碼串的長度。如果使用編碼。如果使用編碼（0=a，10=x，110=u，111=z），則該符号串的編碼為0010110010111，編碼串長度是13位，比原來的14位要稍短一些。當不同字元的出現頻率相差更大時，編碼串的長度差别就會更明顯。

那麼如何解碼呢？字元串 aaxuaxz 的編碼為0010110010111。當從左至右解碼時，我們需要知道第一個字元的代碼是0、00，還是001.因為沒有一個字元的代碼以00開頭，是以第一個字元的代碼必是0。根據編碼表，該字元是 a。下一個代碼為0、01或010.同理，因為不存在以01打頭的代碼，是以代碼必為0.繼續使用這種方法，就可以解碼。這種解碼能夠實作是因為沒有任何一個代碼是另一個代碼的字首。

2、擴充二叉樹與霍夫曼編碼

我們可以利用擴充二叉樹來派生一個特殊的類，對具有上述字首性質的代碼，實作可變長編碼。在一棵擴充二叉樹中，從根到外部節點的路徑可用來編碼，方法是用0表示到左子樹的路徑，1表示到右子樹的路徑。

《資料結構、算法與應用 —— C++語言描述》學習筆記 — 優先級隊列 — 應用 — 霍夫曼編碼一、原理及構造過程二、實作

如圖所示，從根到節點（a，b，c，d，e，f）的路徑分别為（00，010，011,100，101，11）。因為每一個路徑對應一個外部節點，而外部節點之間是互相獨立的，是以沒有一個路徑代碼是另一個的字首。是以，這些代碼可以分别用來對字元 a~f 進行編碼。令 S 是由這些字元組成的字元串， F ( x ) F(x) F(x)是字元 x 出現的頻率。若利用這些代碼對 S 進行編碼，則編碼位串的長度： 2 ∗ F ( a ) + 3 ∗ F ( b ) + 3 ∗ F ( c ) + 3 ∗ F ( d ) + 3 ∗ F ( e ) + 2 ∗ F ( f ) 2*F(a)+3*F(b)+3*F(c)+3*F(d)+3*F(e)+2*F(f) 2∗F(a)+3∗F(b)+3∗F(c)+3∗F(d)+3∗F(e)+2∗F(f)

對于一棵具有 n 個外部節點的擴充二叉樹，且外部節點标記為1，···，n，其對應的編碼位串的長度為： W E P = ∑ 1 n L ( i ) ∗ F ( i ) WEP=\sum_1^nL(i)*F(i) WEP=1∑nL(i)∗F(i)

其中 L ( i ) L(i) L(i)表示從根到外部節點 i 的路徑長度；WEP 是二叉樹的權重外部路徑長度。為了縮短編串的長度，必須使用二叉樹代碼，二叉樹的外部節點要與編碼的字元串的字元對應，且 WEP 最小。一棵二叉樹，如果對一組給定的頻率，其 WEP 最小，那麼這棵二叉樹稱為霍夫曼樹。

3、構造步驟

用霍夫曼編碼對一個字元串進行編碼，需要做的是：

① 确定字元串的符号和它們出現的頻率

② 建立霍夫曼樹，其中外部節點用字元串中的符号表示，外部節點的權用相應符号的頻率表示。

③ 沿着從根到外部節點的路徑周遊，取得每個符号的代碼。

④ 用代碼替代字元串中的符号。

為了便于解碼，需要儲存從符号到代碼的映射表或每個符号的頻率表。如果儲存的是符号的頻率表，那麼采用②可以重構霍夫曼樹。

構造霍夫曼輸的過程是：首先建立一組二叉樹集合，每棵二叉樹僅包含一個外部節點，每個外部節點代表字元串的一個符号，其權等于該符号的頻率。然後，不斷從集合中選擇兩棵權最小的二叉樹，把它們合并成一顆新的二叉樹，合并方法時增加一個根節點，把這兩棵二叉樹分别作為左右子樹。新二叉樹的權是兩棵子樹的權之和。這個過程持續到隻剩一棵二叉樹為止。

《資料結構、算法與應用 —— C++語言描述》學習筆記 — 優先級隊列 — 應用 — 霍夫曼編碼一、原理及構造過程二、實作

二、實作

1、類圖

仔細分析，不難分析，無論是壓縮還是解壓縮，樹的建構過程是完全一樣的。二者生成代碼映射關系的過程也都是通過遞歸，隻不過映射的關系是相對的（從字元到編碼和從編碼到字元）。是以我們提供基類以處理這些相同的操作。

除此之外，我們選擇借助前面實作的 FileReader 和 FileWriter 來處理檔案讀取和寫入。

《資料結構、算法與應用 —— C++語言描述》學習筆記 — 優先級隊列 — 應用 — 霍夫曼編碼一、原理及構造過程二、實作

2、公共常量和結構體

// HuffmanDefine.h
#pragma once
using SymbolType = unsigned char;
using WeightType = int;

struct SymbolAndWeight
{
	SymbolType symbol;
	WeightType weight;
};

enum
{
	SYMBOLNUM_LENGTH = 8,
	SYMBOL_LENGTH = 8,
	WEIGHT_LENGTH = 16
};

3、基類定義

// HuffmanBase.h
#pragma once
#include "HuffmanDefine.h"
#include "../../binaryTree/linkedBinaryTree.h"
#include <map>
#include <memory>
#include <functional>
#include "HuffmanDefine.h"

class HuffmanBase : public linkedBinaryTree<SymbolType>
{
protected:
	std::unique_ptr<SymbolAndWeight[]> symbolAndWeights;
	int symbolNum;

	void makeTree(SymbolAndWeight symbolAndWeights[], int symbolNum);

	void generateCodes(const std::function<void(SymbolType&, std::string&)> &func);

	void generateCodes(binaryTreeNode<SymbolType>* node, std::string currentString, const std::function<void(SymbolType&, std::string&)> &func);
};

4、霍夫曼樹的建構

霍夫曼樹本身并不一定是左高樹或堆，但是我們可以借助堆來構造霍夫曼樹：

#include "HuffmanBase.h"
#include "../heap.h"
using namespace std;

using TreeType = linkedBinaryTree<SymbolType>;
struct HuffmanNode
{
	TreeType* tree;
	WeightType weight;
};

void HuffmanBase::makeTree(SymbolAndWeight symbolAndWeights[], int symbolNum)
{
	auto pred = [](HuffmanNode& left, HuffmanNode& right) {return left.weight < right.weight; };
	heap<HuffmanNode, decltype(pred)> huffmanHeap(symbolNum, pred);

	TreeType emptyTree;
	for (int i = 0; i < symbolNum; ++i)
	{
		auto newTree = new TreeType;
		newTree->makeTree(symbolAndWeights[i].symbol, emptyTree, emptyTree);
		huffmanHeap.push(HuffmanNode{ newTree, symbolAndWeights[i].weight });
	}

	while (huffmanHeap.size() > 1)
	{
		auto left = huffmanHeap.top();
		huffmanHeap.pop();
		auto right = huffmanHeap.top();
		huffmanHeap.pop();

		auto newTree = new TreeType;
		newTree->makeTree(0, *left.tree, *right.tree);

		huffmanHeap.push(HuffmanNode{ newTree, left.weight + right.weight });

		delete left.tree;
		delete right.tree;
	}

	this->swap(*huffmanHeap.top().tree);
	this->symbolAndWeights.reset(new SymbolAndWeight[symbolNum]);
	this->symbolNum = symbolNum;
	copy(symbolAndWeights, symbolAndWeights + symbolNum, this->symbolAndWeights.get());
}

5、生成映射關系

在生成赫夫曼樹之後，我們需要生成編碼和字元的映射關系。在編碼時，我們需要将字元映射成編碼；而在解碼時，我們需要将編碼映射成字元。是以，我們将實際映射關系資料及其處理函數交給子類（此處可以考慮使用模闆方法實作）：

void HuffmanBase::generateCodes(const function<void(SymbolType&, string&)>& func)
{
	generateCodes(root, "", func);
}

void HuffmanBase::generateCodes(binaryTreeNode<SymbolType>* node, string currentString, const function<void(SymbolType&, string&)> &func)
{
	if (node->leftChild == nullptr && node->rightChild == nullptr)
	{
		func(node->element, currentString);
		return;
	}

	if (node->leftChild != nullptr)
	{
		generateCodes(node->leftChild, currentString + "0", func);
	}

	if (node->rightChild != nullptr)
	{
		generateCodes(node->rightChild, currentString + "1", func);
	}
}

6、壓縮類定義

這裡需要由外部提供各代碼的頻率。我們在檔案頭部儲存的是代碼及頻率，用以重構哈夫曼樹。

#pragma once
#include "HuffmanBase.h"

class FileReader;
class FileWriter;
class HuffmanCompress : public HuffmanBase
{
public:
	HuffmanCompress(SymbolAndWeight symbolAndWeights[], int symbolNum);
	void compress(const char* inputFileName, const char* outputFileName);

private:
	std::map<SymbolType, std::string> codes;
	
	void writeSymbolAndWeightsToFile(FileWriter* outputFile);

	void compressContentToFile(FileReader* inputFile, FileWriter* outputFile);
};

7、壓縮類實作

#include "HuffmanCompress.h"
#include "../../public/FileHelper/FileReader.h"
#include "../../public/FileHelper/FileWriter.h"
using namespace std;

HuffmanCompress::HuffmanCompress(SymbolAndWeight symbolAndWeights[], int symbolNum)
{
    makeTree(symbolAndWeights, symbolNum);	
	generateCodes([this](SymbolType& symbol, string& code) {this->codes.insert(make_pair(symbol, code));});
}

void HuffmanCompress::compress(const char* inputFileName, const char* outputFileName)
{
	FileReader inputFile(inputFileName);
	FileWriter outputFile(outputFileName);

	writeSymbolAndWeightsToFile(&outputFile);
	compressContentToFile(&inputFile, &outputFile);
}

void HuffmanCompress::writeSymbolAndWeightsToFile(FileWriter* outputFile)
{
	outputFile->write(symbolNum, SYMBOLNUM_LENGTH);
	for (int i = 0; i < symbolNum; ++i) {
		outputFile->write(symbolAndWeights[i].symbol, SYMBOL_LENGTH);
		outputFile->write(symbolAndWeights[i].weight, WEIGHT_LENGTH);
	}
}

void HuffmanCompress::compressContentToFile(FileReader* inputFile, FileWriter* outputFile)
{
	int currentChar = 0;
	while ((currentChar = inputFile->readChar()) != EOF)
	{
		auto iter = codes.find(currentChar);
		if (iter != codes.end())
		{
			for (auto& ch : iter->second)
			{
				outputFile->write(ch - 48, 1);
			}
		}
	}
}

8、解壓縮類定義

#pragma once
#include "HuffmanBase.h"

class FileReader;
class FileWriter;
class HuffmanDecompress : public HuffmanBase
{
public:
	void decompress(const char* inputFileName, const char* outputFileName);

private:
	std::map<std::string, SymbolType> codes;

	std::unique_ptr<SymbolAndWeight[]> readCodes(FileReader* inputFile, int& symbolNum);

	void decompressContentToFile(FileReader* inputFile, FileWriter* outputFile);
};

9、解壓縮類實作

需要注意讀取到最後一個字元的判斷方式。由于我們每次隻讀取一位，是以不能通過 != EOF 判斷。幸運的是，我們前面提供了 operator bool 用以擷取流狀态。

#include "HuffmanDecompress.h"
#include "../../public/FileHelper/FileReader.h"
#include "../../public/FileHelper/FileWriter.h"
using namespace std;

void HuffmanDecompress::decompress(const char* inputFileName, const char* outputFileName)
{
	FileReader inputFile(inputFileName);
	FileWriter outputFile(outputFileName);

	int symbolNum = 0;
	auto symbolAndWeights = readCodes(&inputFile, symbolNum);
	makeTree(symbolAndWeights.get(), symbolNum);
	generateCodes([this](SymbolType& symbol, string& code) {this->codes.insert(make_pair(code, symbol)); });
	decompressContentToFile(&inputFile, &outputFile);
}

unique_ptr<SymbolAndWeight[]> HuffmanDecompress::readCodes(FileReader* inputFile, int &symbolNum)
{
	symbolNum = inputFile->read(SYMBOLNUM_LENGTH);
	unique_ptr<SymbolAndWeight[]> symbolAndWeights(new SymbolAndWeight[symbolNum]);
	for (int i = 0; i < symbolNum; ++i) {
		symbolAndWeights[i].symbol = inputFile->read(SYMBOL_LENGTH);
		symbolAndWeights[i].weight = inputFile->read(WEIGHT_LENGTH);
	}

	return symbolAndWeights;
}

void HuffmanDecompress::decompressContentToFile(FileReader* inputFile, FileWriter* outputFile)
{
	auto currentNode = this->root;
	int currentBit = 0;
	string currentCode = "";
	while (1)
	{
		currentBit = inputFile->read(1);
		if (!*inputFile)
		{
			break;
		}

		if (currentBit == 0)
		{
			currentNode = currentNode->leftChild;
			currentCode += "0";
		}
		else
		{
			currentNode = currentNode->rightChild;
			currentCode += "1";
		}

		if (currentNode->leftChild == nullptr && currentNode->rightChild == nullptr)
		{
			currentNode = root;
			outputFile->write(codes.find(currentCode)->second, sizeof(SymbolType) * CHAR_BIT);
			currentCode = "";
		}
	}
}

10、FileReader 的修改

FileReader 有一個小問題，在從檔案讀取資料填充緩沖區和輸出時，使用的長度不對。由于前面的 LZW 編碼 unfilledLength 為4位，也就是說 unfilledLength = fileBuffer.getMaxBufferSize() - unfilledLength，是以沒有出現這個問題。

void FileReader::readDataAndFillBuffer(long& data, int unfilledLength)
{
	if (unfilledLength > 0)
	{
		unsigned char ch = inputFileStream.get();
		
		// wrong
		// data += (ch >> unfilledLength);
		
		// right
		data += (ch >> (fileBuffer.getMaxBufferSize() - unfilledLength));

		auto restLength = fileBuffer.getMaxBufferSize() - unfilledLength;
		fileBuffer.AppendDataToBuffer(getLowBitsOfData(ch, restLength), restLength);
	}
}

11、測試代碼

#pragma once
#include "HuffmanCompress.h"
#include "HuffmanDecompress.h"
#include <iostream>
#include <map>
#include <fstream>
#include <memory>
#include <tuple>
using namespace std;

unique_ptr<SymbolAndWeight[]> getSymbolFreq(const char* fileName, int &codesNum)
{
	ifstream ifs(fileName);
	if (!ifs.is_open())
	{
		cerr << "file " << fileName << " cann't open" << endl;
		exit(0);
	}

	int allChars[256] = { 0 };
	int currentChar = 0;
	while ((currentChar = ifs.get()) != EOF)
	{
		allChars[currentChar]++;
	}

	ifs.close();

	unique_ptr<SymbolAndWeight[]> codes(new SymbolAndWeight[256]);
	int indexOfCode = 0;
	codesNum = 0;
	for (int i = 0; i < 256; ++i)
	{
		if (allChars[i] != 0)
		{
			codesNum++;
			codes[indexOfCode++] = { (SymbolType)i, allChars[i] };
		}
	}

	return codes;
}

void test()
{
	int codesNum;
	auto codes = getSymbolFreq("input.txt", codesNum);

	HuffmanCompress compress(codes.get(), codesNum);
	compress.compress("input.txt", "input.huffman");

	HuffmanDecompress decompress;
	decompress.decompress("input.huffman", "output.txt");
}

《資料結構、算法與應用 —— C++語言描述》學習筆記 — 優先級隊列 — 應用 — 霍夫曼編碼一、原理及構造過程二、實作

12、總結

對比霍夫曼編碼和 LZW 編碼，不難發現，二者如果結合起來将會更好。霍夫曼編碼更關注單個字元的出現頻率，而忽略了單詞（連續字元）的重複頻率；LZW 編碼考慮到了連續字元的出現，并對它們使用相同的編碼方式，但是其編碼長度完全取決于字元串出現的順序，而非頻率。

除此之外，霍夫曼編碼還有個問題：上述壓縮率的實作來源于對檔案的兩次掃描，這樣會導緻壓縮時間過長。

《資料結構、算法與應用 —— C++語言描述》學習筆記 — 優先級隊列 — 應用 — 霍夫曼編碼一、原理及構造過程二、實作

《資料結構、算法與應用 —— C++語言描述》學習筆記 — 優先級隊列 — 應用 — 霍夫曼編碼

一、原理及構造過程

1、原理

2、擴充二叉樹與霍夫曼編碼

3、構造步驟

二、實作

1、類圖

2、公共常量和結構體

3、基類定義

4、霍夫曼樹的建構

5、生成映射關系

6、壓縮類定義

7、壓縮類實作

8、解壓縮類定義

9、解壓縮類實作

10、FileReader 的修改

11、測試代碼

12、總結

繼續閱讀

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

Linux裝置模型（中）之上層容器

hdu7108哈希