背景
假如我們要傳輸一段文本，比如“hello”，怎么辦？最容易想到的方法是，直接依次傳輸每個字符的Unicode，每個字符都用8個位元來傳輸，這樣就需要5*8=40個位元來傳輸，但是如果我們要傳輸一段很長的文本怎么辦呢？產生的資料量是非常大的，為了節省成本，我們必須要把資料壓縮，并且能保證對方接收到壓縮的資料可以百分百解讀出來原始的資訊，
事實上，一段文本中每個字符出現的頻率是不同的，比如英文中字母e出現的頻率通常是最高的，而z的出現頻率要遠遠低于e，因此可以想到，讓出現頻率高的字符占用較少的位元，
還是以上面的“hello”為例，因為l出現了2次，而h、e、o只出現了1次，所以l就用1個位元來表示，比如用1來表示，而h、e、o就用2個位元，比如分別用00、11、10來表示，那么“hello”的編碼就可以寫成這樣：
00111110
只需要8個位元，跟前面的40個位元相比，少了80%，
但是，事情發生了轉折，當對方接收到這樣一個編碼的時候就懵逼了，11到底代表兩個l呢，還是一個e呢？也就是說，對方通過這段編碼，不能還原出原始資訊，
為什么會發生這樣的情況呢？原因是因為l的編碼1形成了e的編碼11的前綴，為了使整個編碼沒有歧義，需要任何一個字符的編碼不能是其余字符編碼的前綴，這就是所謂的前綴碼（Prefix code），通俗來講，假如l的編碼是1的話，那么h、e、o的編碼不能以1開頭，否則的話，e的編碼就成了某個其他字符的編碼的前綴，
為了滿足前綴碼的特性，h、e、o的編碼可以分別是01、001、000，
那么，整個“hello”字串的編碼就變成了：
0100111000，
這樣對方在接收到編碼的時候，就可以完美的還原出原始資訊了，可以看到，這個編碼跟剛才那個編碼多了兩個位元，但是卻換來了無歧義性，
構建二叉樹
那怎樣去構建這樣的前綴碼呢？
我們可以構建一棵二叉樹，葉節點代表字符，從根節點到葉節點的路徑代表位元（規定左0右1），像這樣：
比如從根節點到字母e的路徑為“左、左、右”，那么e的編碼就為001，
這怎樣就能保證整個編碼存在前綴碼特性呢？證明很簡單，如果存在某個字符的編碼是其他某個字符的編碼的前綴，那么從該節點往下就有路可走，他就不該在葉節點上，
構建最優二叉樹
那怎樣讓二叉樹最優化呢？換句話說，怎么樣確保出現頻率高的字符的路徑越短，而出現頻率低的字符的路徑就越長呢？
這里要引入一個概念，叫“帶權路徑長度（Weighted path length, WPL）”，給每個節點賦予一個數值，叫做“權”，一個節點的帶權路徑長度就是從根節點到該節點的路徑長度乘上該節點的權值，設葉節點的權值為它在整個字串中的出現次數，那么我們要做的就是使所有葉節點的帶權路徑長度之和最小，怎樣做到呢？
上個世紀50年代，在麻省理工學院攻讀博士學位的哈夫曼(David Albert Huffman)發現了這樣一種方法，并證明了這種方法可以使二叉樹的所有葉節點的帶權路徑長度之和最小，這樣的二叉樹叫做哈夫曼樹（Huffman Tree），
整個程序如下：
- 從n個節點中選出權值最小的節點，構建一棵新的二叉樹，根節點的權值為這兩個節點的權值之和，左右子節點分別為這兩個節點，
- 將這兩個節點移出去，將新的節點加進來，
- 重復上述步驟，直到只剩下一個節點，
如圖所示：
代碼實作：
// 定義哈夫曼樹節點
struct TreeNode {
size_t weight;
char c;
TreeNode *left;
TreeNode *right;
// 判斷是否為葉節點
bool isLeaf() const {
return left == nullptr && right == nullptr;
}
};
// 該struct用于通過節點指標比較兩個節點的權值大小
struct TreeNodeGreater {
bool operator()(TreeNode *lhs, TreeNode *rhs) {
return lhs->weight > rhs->weight;
}
};
// 定義型別別名
// 優先佇列（priority_queue）具有先進大（小）出的特性（即佇列頂部元素為最大或最小元素），
// 模板引數分別是：存盤的型別、底層容器、比較器，
// 這里定義為存盤節點指標的先進小出的優先佇列，
using TreeNodeQueue = std::priority_queue<TreeNode *, std::vector<TreeNode *>, TreeNodeGreater>;
// 構建哈夫曼樹，回傳根節點，
TreeNode *buildHuffmanTree(TreeNodeQueue &queue) {
while (queue.size() >= 2) {
auto node1 = queue.top();
queue.pop();
auto node2 = queue.top();
queue.pop();
auto newNode = new TreeNode{node1->weight + node2->weight, 0, node1, node2};
queue.push(newNode);
}
return queue.top();
}
構建編碼表
只需深度優先搜索這棵哈夫曼樹，遍歷到葉節點就加入到哈希表里，
為了方便，這里使用迭代法，具體參見這篇博文，
// vector<bool>是vector模板類的特化，
// 只不過特化成了既不是vector也不存盤bool的東西，
// 而是存盤位元，是個位元序列，所以正好可以拿來表示字符編碼，
using codeMap_t = std::unordered_map<char, std::vector<bool>>;
// 多載流輸出運算子
std::ostream &operator<<(std::ostream &os, std::vector<bool> &bits) {
for (bool bit: bits) {
os << bit;
}
return os;
}
codeMap_t buildCodeMap(TreeNode *root) {
using Path = std::pair<TreeNode *, std::vector<bool>>;
std::stack<Path> pathStack;
codeMap_t codeMap;
pathStack.push({root, {}});
std::cout << "Code Chart:" << std::endl;
while (!pathStack.empty()) {
auto path = pathStack.top();
TreeNode *node = path.first;
auto &bits = path.second;
// 遍歷到葉節點就加入到哈希表，
if (node->isLeaf()) {
std::cout << node->c << " : " << bits << std::endl;
codeMap.insert({node->c, bits});
pathStack.pop();
continue;
}
pathStack.pop();
// 將右子節點及路徑插入哈希表
if (node->right) {
auto bits1 = bits;
bits1.push_back(true); // 位元序列后面加個1
pathStack.push({node->right, bits1});
}
// 將左子節點及路徑插入哈希表
if (node->left) {
auto bits0 = bits;
bits0.push_back(false); // 位元序列后面加個0
pathStack.push({node->left, bits0});
}
}
return codeMap;
}
將整個字串進行編碼
這個沒啥可說的，直接上代碼
std::vector<bool> encode(std::string &message, codeMap_t &codeMap) {
std::vector<bool> bits;
for (char c: message) {
std::vector<bool> &code = codeMap.at(c);
bits.insert(bits.end(), code.begin(), code.end());
}
return bits;
}
從編碼中還原資訊
從根節點開始，按照左0右1的原則不斷向下走，遇到葉節點就認為還原了一個字符，并回到根節點，
std::string decode(std::vector<bool> &code, TreeNode *root) {
std::string message;
TreeNode *current = root;
for (bool bit: code) {
current = bit ? current->right : current->left;
if (current->isLeaf()) {
message.append(1, current->c);
current = root;
}
}
return message;
}
完整代碼
#include <unordered_map>
#include <string>
#include <queue>
#include <stack>
#include <iostream>
struct TreeNode {
size_t weight;
char c;
TreeNode *left;
TreeNode *right;
bool isLeaf() const {
return left == nullptr && right == nullptr;
}
};
struct TreeNodeGreater {
bool operator()(TreeNode *lhs, TreeNode *rhs) {
return lhs->weight > rhs->weight;
}
};
using TreeNodeQueue = std::priority_queue<TreeNode *, std::vector<TreeNode *>, TreeNodeGreater>;
using countMap_t = std::unordered_map<char, size_t>;
using codeMap_t = std::unordered_map<char, std::vector<bool>>;
std::ostream &operator<<(std::ostream &os, std::vector<bool> &bits) {
for (bool bit: bits) {
os << bit;
}
return os;
}
countMap_t buildCountMap(const std::string &message) {
std::unordered_map<char, size_t> freq;
for (char c : message) {
if (!freq.count(c)) {
freq.insert({c, 0});
}
freq.at(c)++;
}
return freq;
}
TreeNodeQueue buildQueue(const countMap_t &map) {
TreeNodeQueue queue;
for (auto &pair : map) {
char c = pair.first;
size_t freq = pair.second;
auto node = new TreeNode{freq, c, nullptr, nullptr};
queue.push(node);
}
return queue;
}
TreeNode *buildHuffmanTree(TreeNodeQueue &queue) {
while (queue.size() >= 2) {
auto node1 = queue.top();
queue.pop();
auto node2 = queue.top();
queue.pop();
auto newNode = new TreeNode{node1->weight + node2->weight, 0, node1, node2};
queue.push(newNode);
}
return queue.top();
}
codeMap_t buildCodeMap(TreeNode *root) {
using Path = std::pair<TreeNode *, std::vector<bool>>;
std::stack<Path> pathStack;
codeMap_t codeMap;
pathStack.push({root, {}});
std::cout << "Code Chart:" << std::endl;
while (!pathStack.empty()) {
auto path = pathStack.top();
TreeNode *node = path.first;
auto &bits = path.second;
if (node->isLeaf()) {
std::cout << node->c << " : " << bits << std::endl;
codeMap.insert({node->c, bits});
pathStack.pop();
continue;
}
pathStack.pop();
if (node->right) {
auto bits1 = bits;
bits1.push_back(true);
pathStack.push({node->right, bits1});
}
if (node->left) {
auto bits0 = bits;
bits0.push_back(false);
pathStack.push({node->left, bits0});
}
}
return codeMap;
}
std::vector<bool> encode(std::string &message, codeMap_t &codeMap) {
std::vector<bool> bits;
for (char c: message) {
std::vector<bool> &code = codeMap.at(c);
bits.insert(bits.end(), code.begin(), code.end());
}
return bits;
}
std::string decode(std::vector<bool> &code, TreeNode *root) {
std::string message;
TreeNode *current = root;
for (bool bit: code) {
current = bit ? current->right : current->left;
if (current->isLeaf()) {
message.append(1, current->c);
current = root;
}
}
return message;
}
void release(TreeNode *node) {
if (node->left) {
release(node->left);
}
if (node->right) {
release(node->right);
}
delete node;
}
int main() {
std::string message;
std::cout << "Input message: " << std::endl;
std::getline(std::cin, message);
auto originalSize = message.size() * 8;
std::cout << "Size of message: " << originalSize << " bits" << std::endl;
auto countMap = buildCountMap(message);
auto nodeQueue = buildQueue(countMap);
auto root = buildHuffmanTree(nodeQueue);
auto codeMap = buildCodeMap(root);
auto code = encode(message, codeMap);
auto compressedSize = code.size();
std::cout << "Encode result: " << std::endl
<< code << std::endl
<< "Size: " << compressedSize << " bits" << std::endl
<< "compress ratio: " << (long double)compressedSize * 100 / originalSize << '%' << std::endl;
auto decodedMessage = decode(code, root);
std::cout << "Decode result: " << std::endl << decodedMessage << std::endl;
release(root);
return 0;
}
測驗：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511077.html
標籤：其他