哈夫曼樹

哈夫曼樹（Huffman Tree）也是一種特殊的二叉樹，這種樹的所有葉子結點都帶有權值，從中構造出帶權路徑長度最短的二叉樹，即哈夫曼樹。

哈夫曼樹的定義

? 設二叉樹具有n個帶權值的葉子結點,那么從根結點到各個葉子結點的路徑長度與相應結點權值的乘積的和,叫做二叉樹的帶權路徑長度,記作:

其中,為第i個葉子結點的權值,l為第i個葉子結點的路徑長度。如圖6.19所示的二叉樹, 它的帶權路徑長度值WPL=1×3+3×3+2×2+4×1=20

如果給定一組具有確定權值的葉子結點· 可以構造出不同的帶權二叉樹， 它們的帶權路徑長度并不相同· 我們把其中具有最小帶權路徑長度的二叉樹稱為哈夫曼樹·.

哈夫曼樹的構造

哈夫曼編碼

? 哈夫曼編碼具有廣泛的應用， 利用哈夫曼樹構造的用于通信的二進制編碼稱為哈夫曼編碼。例如： 有一段電文“ CAST囗TAT囗A囗SA "（ 其中,“ 囗” 表示一個空格） 。統計電文中字母的頻度 f('C')=1,f('S')=2,f('T')=3,f('囗')=3,f('A')=4 。

用頻度{ 1 ， 2 ， 3 ， 3 ， 4 } 為權值生成哈夫曼樹． 并在每個葉子上注明對應的字符。樹中從根到每個葉子都有一條路徑， 對路徑上的各分枝約定指向左子樹根的分枝表示“ 0 ” 碼， 指向右子樹的分枝表示“ 1 ” 碼， 取每條路徑上的“ 0 ” 或“ 1 ” 的序列作為和各個葉子對應的字符的編碼， 這就是哈夫曼編碼。對應圖6- 22 的哈夫曼樹，上述字符編碼為：

編碼過程：

信源熵

在信息論中，熵（英語：entropy）是接收的每條消息中包含的信息的平均量，又被稱為信息熵、信源熵、平均自信息量。這里，“消息”代表來自分布或數據流中的事件、樣本或特征。（熵最好理解為不確定性的量度而不是確定性的量度，因為越隨機的信源的熵越大。）來自信源的另一個特征是樣本的概率分布。這里的想法是，比較不可能發生的事情，當它發生了，會提供更多的信息。由于一些其他的原因，把信息（熵）定義為概率分布的對數的相反數是有道理的。事件的概率分布和每個事件的信息量構成了一個隨機變量，這個隨機變量的均值（即期望）就是這個分布產生的信息量的平均值（即熵）。熵的單位通常為比特，但也用Sh、nat、Hart計量，取決于定義用到對數的底。

采用概率分布的對數作為信息的量度的原因是其可加性。例如，投擲一次硬幣提供了1 Sh的信息，而擲m次就為m位。更一般地，你需要用log2(n)位來表示一個可以取n個值的變量。

在1948年，克勞德·艾爾伍德·香農將熱力學的熵，引入到信息論，因此它又被稱為香農熵。

熵的計算

當取自有限的樣本時，熵的公式可以表示為：

在這里b是對數所使用的底，通常是2,自然常數e，或是10。當b = 2，熵的單位是bit；當b = e，熵的單位是nat；而當b = 10,熵的單位是Hart。

程序實現：

文件結構

. ├── code │ ├── huffmanClass.h │ └── huffmanCode.cpp //主程序 ├── data │ ├── 1.txt //待壓縮文本文件 │ ├── pic.bmp //待壓縮圖像文件 │ ├── 1.txt.data //壓縮后的文本文件 │ ├── pic.bmp.data //壓縮后的圖像文件 │ ├── 1.txt.txt //解碼后恢復的文本文件 │ └── pic.bmp.bmp //解碼后恢復的圖像文件 │ ├── huffmanEncode //vs2019工程文件夾 ├── huffmanEncode.sln //點擊打開工程 └── 哈夫曼編碼.md

核心代碼介紹

字頻統計code

對每個出現的字節進行統計void Huffman::count() {ifstream readfile;readfile.open(fileAddress, ios::in | ios::binary);unsigned char *now = new unsigned char; //存儲當前讀取到的字符CountVector* temp = new CountVector; for (int i = 0; i < 256; i++) {temp->value = i;temp->frequency=0;charCountFrequency.push_back(*temp);}while (!readfile.eof()){readfile.read((char*)now, sizeof(unsigned char));charCountFrequency[*now].frequency++;//只需要在對應的位置上將字頻增加NumOfChar++;}charCountFrequency[*now].frequency--;readfile.close();}

構建哈夫曼樹code

根據字頻表，每次選取頻率最小的兩個組成一組，然后權值相加放入字頻表，再選字頻最小的兩個。void Huffman::CreateHuffmanTree(vector<CountVector> charFrequency) {vector<CountVector> buildtree;//HuffmanNode newNode;HuffmanNode* rootnode = new HuffmanNode;buildtree = charFrequency;sort(buildtree.begin(), buildtree.end(), mysortfunction);vector<CountVector>::iterator last = buildtree.begin();for (int i = 0; i < buildtree.size(); i++) {if (buildtree[i].frequency != 0) {if (last != buildtree.begin()) {buildtree.erase(buildtree.begin(), last);}break;}last++;}int treedepth = 0;while (buildtree.size() > 1){HuffmanNode* nodeLeft = new HuffmanNode,* nodeRight = new HuffmanNode,* newNode = new HuffmanNode;CountVector insertnew;if (buildtree[0].nodeAddress != NULL){ //如果是葉子節點的話 左右子樹的地址都為NULLnodeLeft->Lchild = buildtree[0].nodeAddress->Lchild;nodeLeft->Rchild = buildtree[0].nodeAddress->Rchild;}else{nodeLeft->Lchild = NULL;nodeLeft->Rchild = NULL;}if (buildtree[1].nodeAddress != NULL){nodeRight->Lchild = buildtree[1].nodeAddress->Lchild;nodeRight->Rchild = buildtree[1].nodeAddress->Rchild;}else{nodeRight->Lchild = NULL;nodeRight->Rchild = NULL;}nodeLeft->frequency = buildtree[0].frequency;nodeLeft->value = buildtree[0].value;nodeRight->frequency = buildtree[1].frequency;nodeRight->value = buildtree[1].value;newNode->frequency = nodeRight->frequency + nodeLeft->frequency;newNode->Lchild = nodeLeft;newNode->Rchild = nodeRight;insertnew.frequency = newNode->frequency;insertnew.value = 0;insertnew.nodeAddress = newNode;buildtree.erase(buildtree.begin());buildtree.erase(buildtree.begin());buildtree.insert(buildtree.begin(), insertnew);sort(buildtree.begin(), buildtree.end(), mysortfunction); //每次更新完要排序rootnode = newNode;treedepth++;}root = rootnode; }

生成哈夫曼碼表

遞歸的方法找到每個葉子的路徑，走左邊為0，走右邊為1.void Huffman::GetHuffmanCode(HuffmanNode* root, int depth) {static char code[512];//判斷左兒子if (root->Lchild != NULL){code[depth] = '0';code[depth + 1] = '0';GetHuffmanCode(root->Lchild, depth + 1);}if (root->Rchild != NULL){code[depth] = '1';code[depth + 1] = '0';GetHuffmanCode(root->Rchild, depth + 1);}else{int codelength = 0;for (int j = 0; code[j] != '0'; j++){codelength++;}HuffmanCodeTable[root->value].codelen = codelength;HuffmanCodeTable[root->value].code = (string)code;//直接把編碼放到對應value位置上}}

總結

在實現字頻查找和編碼表的生成，都采用直接建表，在對應value位置上賦值，提高了壓縮速度。
[3]中生成字頻代碼如下,需要對每個讀取的字符與已有的字頻表進行匹配，時間復雜度很高。優化以后，效率提高了近十倍。void Huffman::count() {ifstream readfile;readfile.open(fileAddress, ios::in | ios::binary);unsigned char *now = new unsigned char; //存儲當前讀取到的字符while (!readfile.eof()){CountVector *presentChar = new CountVector; //讀取到的字符信息readfile.read((char*)now, sizeof(unsigned char));int flag = 0; //標志是否是新出現的字符for (int i = 0; i < charCountFrequency.size(); i++){if (*now == charCountFrequency[i].value){charCountFrequency[i].frequency++;NumOfChar++;flag = 1;}}if (flag == 0){presentChar->value = *now;presentChar->frequency++;NumOfChar++;charCountFrequency.push_back(*presentChar);}}readfile.close(); }

結果顯示：

• 對一個文本文件進行編碼壓縮和解碼，如下：

運行結果：

生成文件：（1.txt.data是編碼后的輸出文件，1.txt.txt是解碼文件）

• 輸入一張bmp圖片。

編碼壓縮后：

大小是原來的48%。

• 選取了三張圖片，對比一下理想信源熵和平均碼長

圖片1信源熵：3.755210 .平均碼長：3.814355 圖片2信源熵：4.914732 .平均碼長：4.942633 圖片3信源熵：3.586430 .平均碼長：3.654054

可以看到哈夫曼編碼很接近香農熵。

github：https://github.com/zldz/huffmanEncode

參考：

[1]數據結構與算法教程-李春葆-125頁
[2]https://github.com/FLHonker/HffmanCompress
[3]https://github.com/PiggyGaGa/Information-Theory-Source-Coding
[4]Matlab霍夫曼編碼器

總結

以上是生活随笔為你收集整理的信息论与编码_哈夫曼编码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。