一、定义
霍夫曼树
又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为
WPL =(W1*L1 + W2*L2 + W3*L3 +...+ Wn*Ln)
,N
个权值Wi(i=1,2,...n)
构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)
。可以证明霍夫曼树的 WPL 是最小的。
霍夫曼编码
是一种基于霍夫曼树的用于无损数据压缩的熵编码(权编码)算法。
由于霍夫曼树具有 WPL 最小的特性,可认为霍夫曼树中权值越大的叶子结点路径越短,可用霍夫曼树所有叶子结点的路径生成编码方案,其特点是权重越大的结点路径编码越短,反之则越长。
用途
按照 Wikipedia 的说法:
霍夫曼树常处理符号编写工作。根据整组资料中符号出现的频率高低,决定如何给符号编码。如果符号出现的频率越高,则给符号的码越短,相反符号的号码越长。
显然,这种编码适用于对高频出现的数据进行编码上的无损压缩,只要知道如何构造一颗霍夫曼树,就能对生成的编码进行解码。
二、实现
霍夫曼树的结点
结点包含如下要素:
- data: 存储的数据(本例中为单个字符)
- weight: 权重
- leftChild/rightChild: 下接的左右子树(形成一个递归的二叉树结构)
- IsLeaf(): 判断本结点是否为叶子结点
- 构造函数
1 2 3 4 5 6 7 8 9 10 11 12 |
/** * Huffman 树的结点,递归数据结构 */ class HuffmanTreeNode { public: char data; float weight; HuffmanTreeNode *leftChild{}; HuffmanTreeNode *rightChild{}; bool IsLeaf(); HuffmanTreeNode(float weight, char data); }; |
结点的实现:
1 2 3 4 5 6 7 8 |
HuffmanTreeNode::HuffmanTreeNode(float weight, char data) { this->weight = weight; this->data = data; } bool HuffmanTreeNode::IsLeaf() { return this->leftChild == nullptr && this->rightChild == nullptr; }; |
霍夫曼树的概念结构
树本身是一个概念结构, 包含如下要素:
- nodesTree: 结点数据(用于生成霍夫曼树)
- codingMap: 字符和它的编码映射关系
- huffmanTree: 运行时生成的最优二叉树(霍夫曼树)
- PickMinWeightNode(): 从结点数据中选择一个 weight 最小的结点
- CalcWPL(): 生成某个结点的 WPL
- GenerateCodingMap(): 生成字符和它的编码映射关系
- WPL: 加权路径长度
- GetHuffmanCode(): 获取字符的编码
- Encode(): 编码(tuple 元素分别为编码的 字符串 和 布尔串 形式)
- Decode(): 解码
- 构造函数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <vector> #include <tuple> #include <map> using namespace std; /** * 由 Huffman 树结点构成的树的整体概念,及围绕它的一系列功能 */ class HuffmanTree { private: vector<HuffmanTreeNode*> nodesTree; map<char, string> codingMap; HuffmanTreeNode* huffmanTree; HuffmanTreeNode* PickMinWeightNode(); void CalcWPL(HuffmanTreeNode *root, int depth); void GenerateCodingMap(HuffmanTreeNode *root, string codePath); float WPL = 0.0; public: explicit HuffmanTree(vector<tuple<float, char>> nodes); float GetWPL(); string GetHuffmanCode(char ch); tuple<string, vector<bool>> Encode(string content); string Decode(vector<bool> code); }; |
树的构造
- 不断地查找结点数据 nodesTree 中 weight 最小的结点,并将其从nodesTree 中删除,每两个最小结点以组成一颗新的结点,其 weight 为两结点 weight 之和,两结点成为新结点的左右子结点,将新结点再次回入到 nodesTree 中
- 重复以上过程,直至清空 nodesTree
- 生成的 huffmanTree 即为最优二叉树
- 使用 huffmanTree 生成编码表
- 使用 huffmanTree 算出 WPL
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
HuffmanTree::HuffmanTree(vector<tuple<float, char>> nodes) { if (nodes.empty()) { cout << "[HuffmanTree] nodes are empty" << endl; return; } this->nodesTree.resize(nodes.size()); for(int i = 0; i < this->nodesTree.size(); i++) { auto node = nodes[i]; this->nodesTree[i] = new HuffmanTreeNode(get<0>(node), get<1>(node)); } // 生成最优二叉树的过程 while(!this->nodesTree.empty()) { auto minNode1 = this->PickMinWeightNode(); if (this->nodesTree.empty()) { this->huffmanTree = minNode1; break; } auto minNode2 = this->PickMinWeightNode(); this->huffmanTree = new HuffmanTreeNode( minNode1->weight + minNode2->weight, ' '); this->huffmanTree->leftChild = minNode1; this->huffmanTree->rightChild = minNode2; this->nodesTree.push_back(this->huffmanTree); } this->GenerateCodingMap(this->huffmanTree, ""); this->CalcWPL(this->huffmanTree, 0); } |
查找权重最小的结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
HuffmanTreeNode* HuffmanTree::PickMinWeightNode() { if (this->nodesTree.empty()) return nullptr; int min_index; float min = INT_MAX; for (int i = 0; i < this->nodesTree.size(); i++) { if (this->nodesTree[i]->weight < min) { min = this->nodesTree[i]->weight; min_index = i; } } auto node = this->nodesTree[min_index]; this->nodesTree.erase(this->nodesTree.begin() + min_index); return node; } |
生成编码表
路径编码方法:
- 任一结点到其左子结点编码为 “0”
- 任一结点到其右子结点编码为”1″
任一叶结点的编码,就是由根到叶结点的路径编码串
1 2 3 4 5 6 7 8 9 10 |
void HuffmanTree::GenerateCodingMap(HuffmanTreeNode *root, string codePath) { if (root != nullptr) { if (root->IsLeaf()) { this->codingMap[root->data] = codePath; } else { this->GenerateCodingMap(root->leftChild, codePath + "0"); this->GenerateCodingMap(root->rightChild, codePath + "1"); } } }; |
树的 WPL
1 2 3 4 5 6 7 8 9 10 11 |
void HuffmanTree::CalcWPL(HuffmanTreeNode *root, int depth) { if (root != nullptr) { if (root->IsLeaf()) this->WPL += depth * root->weight; this->CalcWPL(root->leftChild, depth + 1); this->CalcWPL(root->rightChild, depth + 1); } } float HuffmanTree::GetWPL() { return this->WPL; } |
编码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
/** * 将明文编码成 Huffman 码 * @param content 明文 * @return Huffman码 <编码的字符串形式, 编码的 vector<bool>> */ tuple<string, vector<bool>> HuffmanTree::Encode(string content) { tuple<string, vector<bool>> result; if (this->codingMap.empty()) { cout << "please generate the map at first!" << endl; return result; } stringstream buffer; for (int i = 0; i < content.size(); i++) { buffer << this->GetHuffmanCode(content[i]); } get<0>(result) = buffer.str(); get<1>(result).resize(get<0>(result).size()); for (int i = 0; i < get<0>(result).size(); i++) get<1>(result)[i] = get<0>(result)[i] == '1'; return result; }; |
解码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
/** * 将 Huffman 码解码成明文 * @param code 表示 Huffman 码的 vector<bool> * @return code 对应的明文 */ string HuffmanTree::Decode(vector<bool> code) { if (this->codingMap.empty()) { cout << "please generate the coding map at first!" << endl; return ""; } stringstream buffer, temp; HuffmanTreeNode *current = this->huffmanTree; for (int i = 0; i < code.size(); i++) { if (current->IsLeaf()) { buffer << current->data;; temp.str(""); temp.clear(); current = this->huffmanTree; } auto c = code[i]; temp << c; if (!c) current = current->leftChild; else current = current->rightChild; } if (!temp.str().empty()) { buffer << current->data; } return buffer.str(); }; |
三、小结
要利用好霍夫曼编码,需在生成树结构前,提炼出大部分应用场景中数据结点(字符或是词组之类元数据)的使用频率,以此做为结点的权重,方能最大化使用编码的收益。
打赏作者
您的支持将激励我继续创作!