溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“C++哈夫曼樹的概念是什么與怎么實現”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“C++哈夫曼樹的概念是什么與怎么實現”文章能幫助大家解決問題。
結點的權： 有某種現實含義的數值
結點的帶權路徑長度： 從結點的根到該結點的路徑長度與該結點權值的乘積
樹的帶權路徑長度： 樹上所有葉結點的帶權路徑長度之和
哈夫曼樹： 在含有 n n n個帶權葉結點的二叉樹中， w p l wpl wpl 最小 的二叉樹稱為哈夫曼樹，也稱最優二叉樹（給定葉子結點，哈夫曼樹不唯一）。
比較簡單，此處不贅述步驟
每個初始結點最終都是葉結點，且權值越小的結點到根結點的路徑長度越大
具有 n n n個根結點的哈夫曼樹的結點總數為 2 n − 1
哈夫曼樹中不存在度為1的結點
哈夫曼樹不唯一，但 w p l必然相同且最優
目的：為給定的字符集合構建二進制編碼，使得編碼的期望長度達到最短
在考試中，小渣利用哈夫曼編碼老渣發電報傳遞100道選擇題的答案，小渣傳遞了10個A、8個B、80個C、2個D，老渣利用哈夫曼編碼的方式解碼。
小渣構造的哈夫曼樹如下：
可以發現，A、B、C、D的編碼分別為10、111、0、110。
這樣小渣只要根據1~100題的答案順序發送01序列，老渣收到后進行解碼就能正確收到答案了。而且哈夫曼編碼的方式不會有歧義，因為哈夫曼編碼是一種前綴編碼。
前綴編碼： 沒有一個編碼是另一個編碼的前綴，因為數據節點都是葉子節點。如果出現一個字符的編碼是另一個字符編碼的前綴，那這個字符一定處于內部節點，這是不可能的
由哈夫曼樹得到的哈夫曼編碼： 字符集中的每個字符都是以葉子結點出現在哈夫曼樹中，各個字符出現的頻率為結點的權值。
給字符串進行編碼的時候，由于出現頻率越高（權值大）的字符距離根節點越進，編碼越短；只有出現頻率越低（權值小）的字符距離根節點較遠，編碼長。沒關系，由于頻率高的字符編碼都短，所以哈夫曼編碼可以得到最短的編碼序列
哈夫曼編碼不同于ASCII和Unicode這些字符編碼，這些字符集中的碼長都采用的是長度相同的編碼方案，而哈夫曼編碼使用的是變長編碼，而且哈夫曼編碼滿足立刻可解碼性（就是說任一字符的編碼都不會是另一個更長字符編碼的前綴），只要當某個字符的編碼中所有位被全部接收時，可以立即進行解碼而無須等待后面接收的位來決定是否存在另一個合法的更長的編碼
第一張表不滿足立刻可解碼性，第二張表滿足
我們接收100的時候，需要考慮是立刻解碼成D還是等待接收下一位，如果下一位是0就可以解碼成B，這就說明表中的編碼不具有立刻可解碼性
第二張表就具有立刻可解碼性，因為任一字符的編碼都不是另一個更長字符編碼的前綴。只要收到的序列對應了某個字符的編碼，直接解碼成對應字符即可，無需等待后面的數據
我們的代碼實現是用字符串構建哈夫曼樹，只能針對由該字符串包含的字符組成的字符串進行編解碼。代碼里使用字符串存儲的編碼，實際上應該用bit進行存儲
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <unordered_map>
#include <queue>
using namespace std;
using uint = unsigned int;
class HuffmanTree {
public:
// 這里的lambda表達式用來初始化function函數對象
// priority_queue的構造函數指出，如果傳入一個參數，那這個參數用來初始化比較器對象
// 如果傳入兩個參數，第一個是比較器對象，第二個是底層容器
HuffmanTree()
:min_heap_([](Node* n1, Node* n2)->bool {return n1->weight_ > n2->weight_; })
, root_(nullptr)
{}
~HuffmanTree() {
init();
cout << "已釋放所有內存！" << endl;
}
// 根據字符串創建哈夫曼樹
void create(const string& str) {
if (root_ != nullptr) {
cout << "哈夫曼樹初始化..." << endl;
init();
cout << "初始化完成！" << endl;
}
// 統計頻率（權重）
unordered_map<char, uint> w_map;
for (char c : str) {
w_map[c]++;
}
// 遍歷w_map，把所有的字符對應的權重放入小根堆，按照權重排序
for (pair<const char, uint>& p : w_map) {
min_heap_.push(new Node(p.first, p.second));
}
// 根據優先級隊列，從小根堆中取出節點，構建哈夫曼樹
while (min_heap_.size() > 1) {
Node* n1 = min_heap_.top();
min_heap_.pop();
Node* n2 = min_heap_.top();
min_heap_.pop();
Node* node = new Node('\0', n1->weight_ + n2->weight_); // 內部節點存\0
node->left_ = n1;
node->right_ = n2;
min_heap_.push(node);
}
root_ = min_heap_.top();
min_heap_.pop();
// 創建完哈夫曼樹，直接對傳入的海量字符進行編碼并存儲到code_map_
create_huffman_code(str);
}
string get_code(const string& str) {
// 利用哈夫曼樹對str編碼并返回
string code;
for (char c : str) {
code += code_map_[c];
}
return code;
}
void show_huffman_code() const {
// 打印哈夫曼編碼
for (const auto& pair : code_map_) {
cout << pair.first << " : " << pair.second << endl;
}
}
string decode(const string& encode_str) {
Node* cur = root_;
string decode_str;
for (char c : encode_str) {
if (c == '0') {
cur = cur->left_;
}
else {
cur = cur->right_;
}
if (cur->left_ == nullptr && cur->right_ == nullptr) {
// 到達葉子節點
decode_str.push_back(cur->data_);
cur = root_;
}
}
return decode_str;
}
uint get_wpl() {
if (root_ == nullptr) {
return 0;
}
if (root_->left_ == nullptr && root_->right_ == nullptr) {
// 對于葉子節點，直接返回自己的weight * depth
return root_->weight_ * 1;
}
else {
// 對于內部節點，直接返回從子節點拿到的weight之和
return get_w(root_->left_, 2) + get_w(root_->right_, 2);
}
}
private:
struct Node {
Node(char data, uint weight)
:data_(data)
, weight_(weight)
, left_(nullptr)
, right_(nullptr)
{}
char data_;
uint weight_;
Node* left_;
Node* right_;
};
private:
// 防止當前對象重新構建哈夫曼樹，釋放所有的節點，然后初始化私有成員
void init() {
// 釋放哈夫曼樹的節點
if (root_ != nullptr) {
queue<Node*> q;
q.push(root_);
while (!q.empty()) {
Node* node = q.front();
q.pop();
if (node->left_ != nullptr) {
q.push(node->left_);
}
if (node->right_ != nullptr) {
q.push(node->right_);
}
delete node;
}
MinHeap empty([](Node* n1, Node* n2)->bool {return n1->weight_ > n2->weight_; });
swap(empty, min_heap_);
code_map_.clear();
}
}
void create_huffman_code(const string& str) {
string code;
create_huffman_code(root_, code);
}
void create_huffman_code(Node* node, string code) {
if (node->left_ == nullptr && node->right_ == nullptr) {
code_map_[node->data_] = code;
return;
}
create_huffman_code(node->left_, code + "0");
create_huffman_code(node->right_, code + "1");
}
uint get_w(Node* node, int depth) {
if (node == nullptr) {
return 0;
}
if (node->left_ == nullptr && node->right_ == nullptr) {
// 對于葉子節點，直接返回自己的weight * depth
return node->weight_ * depth;
}
else {
// 對于內部節點，直接返回從子節點拿到的weight之和
return get_w(node->left_, depth + 1) + get_w(node->right_, depth + 1);
}
}
private:
Node* root_;
unordered_map<char, string> code_map_; // 存儲字符對應的哈夫曼編碼
using MinHeap = priority_queue<Node*, vector<Node*>, function<bool(Node*, Node*)>>;
MinHeap min_heap_; // 構建哈夫曼樹的時候使用小根堆
};
int main() {
string str = "Aa";
HuffmanTree htree;
htree.create(str);
htree.show_huffman_code();
cout << htree.get_wpl() << endl;
str = "ABC";
htree.create(str);
htree.show_huffman_code();
cout << htree.get_wpl() << endl;;
string encode = htree.get_code(str);
cout << "encode:" << encode << endl;
cout << "decode:" << htree.decode(encode) << endl;
return 0;
}我們利用哈夫曼編碼壓縮文件的時候，如果文件是100M，我們可以壓縮成20M，如果文件時1K，我們可能壓縮成2K，當文件較小的時候，我們得到的壓縮文件反而更大了，這是為什么？
文件的壓縮過程如下：
按字節讀取原文件的所有內容，并統計字節數據的權值，構建哈夫曼樹
通過哈夫曼樹，得到文件的哈夫曼編碼
把文件的內容按字節進行編碼，將編碼內容按bit存儲成壓縮文件，還要存儲文件字節數據以及權值
解碼的過程如下：
讀取原始文件的字節數據以及權值，構建哈夫曼樹
讀取壓縮文件的01碼，利用哈夫曼樹對01進行解碼，將解碼數據存儲成新的文件，就解碼出了原始文件
由于壓縮文件不僅存儲01碼，還需要存儲文件字節數據以及權值用來重建哈夫曼樹（就是代碼中的w_map）。當原始文件較小時，文件字節數據以及權值可能大于原始文件的大小，故小文件壓縮后可能變大
關于“C++哈夫曼樹的概念是什么與怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
