第C++詳解哈夫曼樹(shù)的概念與實(shí)現(xiàn)步驟目錄一、基本概念二、構(gòu)造哈夫曼樹(shù)三、哈夫曼樹(shù)的基本性質(zhì)四、哈夫曼編碼五、哈夫曼解碼六、文件的壓縮和解壓縮

一、基本概念

結(jié)點(diǎn)的權(quán)：有某種現(xiàn)實(shí)含義的數(shù)值

結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從結(jié)點(diǎn)的根到該結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)值的乘積

樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)上所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和

哈夫曼樹(shù)：在含有nnn個(gè)帶權(quán)葉結(jié)點(diǎn)的二叉樹(shù)中，wplwplwpl最小的二叉樹(shù)稱為哈夫曼樹(shù)，也稱最優(yōu)二叉樹(shù)（給定葉子結(jié)點(diǎn)，哈夫曼樹(shù)不唯一）。

二、構(gòu)造哈夫曼樹(shù)

比較簡(jiǎn)單，此處不贅述步驟

三、哈夫曼樹(shù)的基本性質(zhì)

每個(gè)初始結(jié)點(diǎn)最終都是葉結(jié)點(diǎn)，且權(quán)值越小的結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度越大具有nnn個(gè)根結(jié)點(diǎn)的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為2n1哈夫曼樹(shù)中不存在度為1的結(jié)點(diǎn)哈夫曼樹(shù)不唯一，但wpl必然相同且最優(yōu)

四、哈夫曼編碼

目的：為給定的字符集合構(gòu)建二進(jìn)制編碼，使得編碼的期望長(zhǎng)度達(dá)到最短

在考試中，小渣利用哈夫曼編碼老渣發(fā)電報(bào)傳遞100道選擇題的答案，小渣傳遞了10個(gè)A、8個(gè)B、80個(gè)C、2個(gè)D，老渣利用哈夫曼編碼的方式解碼。

小渣構(gòu)造的哈夫曼樹(shù)如下：

可以發(fā)現(xiàn)，A、B、C、D的編碼分別為10、111、0、110。

這樣小渣只要根據(jù)1~100題的答案順序發(fā)送01序列，老渣收到后進(jìn)行解碼就能正確收到答案了。而且哈夫曼編碼的方式不會(huì)有歧義，因?yàn)楣蚵幋a是一種前綴編碼。

前綴編碼：沒(méi)有一個(gè)編碼是另一個(gè)編碼的前綴，因?yàn)閿?shù)據(jù)節(jié)點(diǎn)都是葉子節(jié)點(diǎn)。如果出現(xiàn)一個(gè)字符的編碼是另一個(gè)字符編碼的前綴，那這個(gè)字符一定處于內(nèi)部節(jié)點(diǎn)，這是不可能的

由哈夫曼樹(shù)得到的哈夫曼編碼：字符集中的每個(gè)字符都是以葉子結(jié)點(diǎn)出現(xiàn)在哈夫曼樹(shù)中，各個(gè)字符出現(xiàn)的頻率為結(jié)點(diǎn)的權(quán)值。

給字符串進(jìn)行編碼的時(shí)候，由于出現(xiàn)頻率越高（權(quán)值大）的字符距離根節(jié)點(diǎn)越進(jìn)，編碼越短；只有出現(xiàn)頻率越低（權(quán)值?。┑淖址嚯x根節(jié)點(diǎn)較遠(yuǎn)，編碼長(zhǎng)。沒(méi)關(guān)系，由于頻率高的字符編碼都短，所以哈夫曼編碼可以得到最短的編碼序列

五、哈夫曼解碼

哈夫曼編碼不同于ASCII和Unicode這些字符編碼，這些字符集中的碼長(zhǎng)都采用的是長(zhǎng)度相同的編碼方案，而哈夫曼編碼使用的是變長(zhǎng)編碼，而且哈夫曼編碼滿足立刻可解碼性（就是說(shuō)任一字符的編碼都不會(huì)是另一個(gè)更長(zhǎng)字符編碼的前綴），只要當(dāng)某個(gè)字符的編碼中所有位被全部接收時(shí)，可以立即進(jìn)行解碼而無(wú)須等待后面接收的位來(lái)決定是否存在另一個(gè)合法的更長(zhǎng)的編碼

第一張表不滿足立刻可解碼性，第二張表滿足

我們接收100的時(shí)候，需要考慮是立刻解碼成D還是等待接收下一位，如果下一位是0就可以解碼成B，這就說(shuō)明表中的編碼不具有立刻可解碼性

第二張表就具有立刻可解碼性，因?yàn)槿我蛔址木幋a都不是另一個(gè)更長(zhǎng)字符編碼的前綴。只要收到的序列對(duì)應(yīng)了某個(gè)字符的編碼，直接解碼成對(duì)應(yīng)字符即可，無(wú)需等待后面的數(shù)據(jù)

我們的代碼實(shí)現(xiàn)是用字符串構(gòu)建哈夫曼樹(shù)，只能針對(duì)由該字符串包含的字符組成的字符串進(jìn)行編解碼。代碼里使用字符串存儲(chǔ)的編碼，實(shí)際上應(yīng)該用bit進(jìn)行存儲(chǔ)

#includeiostream

#includestring

#includevector

#includefunctional

#includeunordered_map

#includequeue

usingnamespacestd;

usinguint=unsignedint;

classHuffmanTree{

public:

//這里的lambda表達(dá)式用來(lái)初始化function函數(shù)對(duì)象

//priority_queue的構(gòu)造函數(shù)指出，如果傳入一個(gè)參數(shù)，那這個(gè)參數(shù)用來(lái)初始化比較器對(duì)象

//如果傳入兩個(gè)參數(shù)，第一個(gè)是比較器對(duì)象，第二個(gè)是底層容器

HuffmanTree()

:min_heap_([](Node*n1,Node*n2)-bool{returnn1-weight_n2-weight_;})

,root_(nullptr)

~HuffmanTree(){

init();

cout"已釋放所有內(nèi)存！"endl;

//根據(jù)字符串創(chuàng)建哈夫曼樹(shù)

voidcreate(conststringstr){

if(root_!=nullptr){

cout"哈夫曼樹(shù)初始化..."endl;

init();

cout"初始化完成！"endl;

//統(tǒng)計(jì)頻率（權(quán)重）

unordered_mapchar,uintw_map;

for(charc:str){

w_map[c]++;

//遍歷w_map，把所有的字符對(duì)應(yīng)的權(quán)重放入小根堆，按照權(quán)重排序

for(pairconstchar,uintp:w_map){

min_heap_.push(newNode(p.first,p.second));

//根據(jù)優(yōu)先級(jí)隊(duì)列，從小根堆中取出節(jié)點(diǎn)，構(gòu)建哈夫曼樹(shù)

while(min_heap_.size()1){

Node*n1=min_heap_.top();

min_heap_.pop();

Node*n2=min_heap_.top();

min_heap_.pop();

Node*node=newNode('\0',n1-weight_+n2-weight_);//內(nèi)部節(jié)點(diǎn)存\0

node-left_=n1;

node-right_=n2;

min_heap_.push(node);

root_=min_heap_.top();

min_heap_.pop();

//創(chuàng)建完哈夫曼樹(shù)，直接對(duì)傳入的海量字符進(jìn)行編碼并存儲(chǔ)到code_map_

create_huffman_code(str);

stringget_code(conststringstr){

//利用哈夫曼樹(shù)對(duì)str編碼并返回

stringcode;

for(charc:str){

code+=code_map_[c];

returncode;

voidshow_huffman_code()const{

//打印哈夫曼編碼

for(constautopair:code_map_){

coutpair.first":"pair.secondendl;

stringdecode(conststringencode_str){

Node*cur=root_;

stringdecode_str;

for(charc:encode_str){

if(c=='0'){

cur=cur-left_;

else{

cur=cur-right_;

if(cur-left_==nullptrcur-right_==nullptr){

//到達(dá)葉子節(jié)點(diǎn)

decode_str.push_back(cur-data_);

cur=root_;

returndecode_str;

uintget_wpl(){

if(root_==nullptr){

return0;

if(root_-left_==nullptrroot_-right_==nullptr){

//對(duì)于葉子節(jié)點(diǎn)，直接返回自己的weight*depth

returnroot_-weight_*1;

else{

//對(duì)于內(nèi)部節(jié)點(diǎn)，直接返回從子節(jié)點(diǎn)拿到的weight之和

returnget_w(root_-left_,2)+get_w(root_-right_,2);

private:

structNode{

Node(chardata,uintweight)

:data_(data)

,weight_(weight)

,left_(nullptr)

,right_(nullptr)

chardata_;

uintweight_;

Node*left_;

Node*right_;

private:

//防止當(dāng)前對(duì)象重新構(gòu)建哈夫曼樹(shù)，釋放所有的節(jié)點(diǎn)，然后初始化私有成員

voidinit(){

//釋放哈夫曼樹(shù)的節(jié)點(diǎn)

if(root_!=nullptr){

queueNode*

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_);

deletenode;

MinHeapempty([](Node*n1,Node*n2)-bool{returnn1-weight_n2-weight_;});

swap(empty,min_heap_);

code_map_.clear();

voidcreate_huffman_code(conststringstr){

stringcode;

create_huffman_code(root_,code);

voidcreate_huffman_code(Node*node,stringcode){

if(node-left_==nullptrnode-right_==nullptr){

code_map_[node-data_]=code;

return;

create_huffman_code(node-left_,code+"0");

create_huffman_code(node-right_,code+"1");

uintget_w(Node*node,intdepth){

if(node==nullptr){

return0;

if(node-left_==nullptrnode-right_==nullptr){

//對(duì)于葉子節(jié)點(diǎn)，直接返回自己的weight*depth

returnnode-weight_*depth;

else{

//對(duì)于內(nèi)部節(jié)點(diǎn)，直接返回從子節(jié)點(diǎn)拿到的weight之和

returnget_w(node-left_,depth+1)+get_w(node-right_,depth+1);

private:

Node*root_;

unordered_mapchar,stringcode_map_;//存儲(chǔ)字符對(duì)應(yīng)的哈夫曼編碼

usingMinHeap=priority_queueNode*,vectorNode*,functionbool(Node*,Node*);

MinHeapmin_heap_;//構(gòu)建哈夫曼樹(shù)的時(shí)候使用小根堆

intmain(){

stringstr="Aa";

HuffmanTreehtree;

htree.create(str);

htree.show_huffman_code();

couthtree.get_wpl()endl;

str="ABC";

htree.create(str);

htree.show_huffman_code();

couthtree.get_wpl()endl;;

stringencode=htree.get_code(str);

cout"encode:"encodeendl;

cout"decode:"htree.decode(encode)endl;

return0;

}

六、文件的壓縮和解壓縮

我們利用哈夫曼編碼壓縮文件的時(shí)候，如果文件是100M，我們可以壓縮成20M，如果文件時(shí)1K，我們可能壓縮成2K，當(dāng)文件較小的時(shí)候，我們得到的壓縮文件反而更大了，這是為