亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

歷史

1951年，霍夫曼和他在MIT信息論的同學(xué)得選擇是完成學(xué)期報告還是期末考試。導(dǎo)師羅伯特·法諾出的學(xué)期報告題目是，查找最有效的二進制編碼。由于無法證明哪個已有編碼是最有效的，霍夫曼放棄對已有編碼的研究，轉(zhuǎn)向新的探索，最終發(fā)現(xiàn)了基于有序頻率二叉樹編碼的想法，并很快證明了這個方法是最有效的?；舴蚵褂米缘紫蛏系姆椒?gòu)建二叉樹，避免了次優(yōu)算法香農(nóng)-范諾編碼的最大弊端──自頂向下構(gòu)建樹。

1952年，于論文《一種構(gòu)建極小多余編碼的方法》（ A Method for the Construction of Minimum-Redundancy Codes ）中發(fā)表了這個編碼方法。

問題定義與解法

Fig.1

Fig.2 霍夫曼編碼演算步驟, 左右樹排列順序可以加限制或不加限制

Fig.3

廣義

給定

欲知

狹義

輸入

輸出

目標

示例

霍夫曼樹常處理符號編寫工作。根據(jù)整組數(shù)據(jù)中符號出現(xiàn)的頻率高低，決定如何給符號編碼。如果符號出現(xiàn)的頻率越高，則給符號的碼越短，相反符號的號碼越長。假設(shè)我們要給一個英文單字 "F O R G E T" 進行霍夫曼編碼，而每個英文字母出現(xiàn)的頻率分別列在 Fig.1 。

演算過程

（一）進行霍夫曼編碼前，我們先創(chuàng)建一個霍夫曼樹。

最后產(chǎn)生的樹狀圖就是霍夫曼樹，參考 Fig.2 。 （二）進行編碼

實現(xiàn)方法

數(shù)據(jù)壓縮

實現(xiàn)霍夫曼編碼的方式主要是創(chuàng)建一個二叉樹和其節(jié)點。這些樹的節(jié)點可以存儲在數(shù)組里，數(shù)組的大小為符號（symbols）數(shù)的大小 n ，而節(jié)點分別是終端節(jié)點（葉節(jié)點）與非終端節(jié)點（內(nèi)部節(jié)點）。

一開始，所有的節(jié)點都是終端節(jié)點，節(jié)點內(nèi)有三個字段：

1.符號（Symbol）

2.權(quán)重（Weight、Probabilities、Frequency）

3.指向父節(jié)點的鏈接（Link to its parent node）

而非終端節(jié)點內(nèi)有四個字段：

1.權(quán)重（Weight、Probabilities、Frequency）

2.指向兩個子節(jié)點的鏈接（Links to two child node）

3.指向父節(jié)點的鏈接（Link to its parent node）

基本上，我們用"0"與"1"分別代表指向左子節(jié)點與右子節(jié)點，最后為完成的二叉樹共有 n 個終端節(jié)點與 n-1 個非終端節(jié)點，去除了不必要的符號并產(chǎn)生最佳的編碼長度。

過程中，每個終端節(jié)點都包含著一個權(quán)重（Weight、Probabilities、Frequency），兩兩終端節(jié)點結(jié)合會產(chǎn)生一個新節(jié)點， 新節(jié)點的權(quán)重 是由 兩個權(quán)重最小的終端節(jié)點權(quán)重之總和 ，并持續(xù)進行此過程直到只剩下一個節(jié)點為止。

實現(xiàn)霍夫曼樹的方式有很多種，可以使用優(yōu)先隊列（Priority Queue）簡單達成這個過程，給與權(quán)重較低的符號較高的優(yōu)先級（Priority），算法如下：

⒈把n個終端節(jié)點加入優(yōu)先隊列，則n個節(jié)點都有一個優(yōu)先權(quán)Pi，1 ≤ i ≤ n

⒉如果隊列內(nèi)的節(jié)點數(shù)>1，則：

⒊最后在優(yōu)先隊列里的點為樹的根節(jié)點（root）

而此算法的時間復(fù)雜度（Time Complexity）為O（ n log n ）；因為有n個終端節(jié)點，所以樹總共有2n-1個節(jié)點，使用優(yōu)先隊列每個循環(huán)須O（log n ）。

此外，有一個更快的方式使時間復(fù)雜度降至線性時間（Linear Time）O（ n ），就是使用兩個隊列（Queue）創(chuàng)件霍夫曼樹。第一個隊列用來存儲n個符號（即n個終端節(jié)點）的權(quán)重，第二個隊列用來存儲兩兩權(quán)重的合（即非終端節(jié)點）。此法可保證第二個隊列的前端（Front）權(quán)重永遠都是最小值，且方法如下：

⒈把n個終端節(jié)點加入第一個隊列（依照權(quán)重大小排列，最小在前端）

⒉如果隊列內(nèi)的節(jié)點數(shù)>1，則：

⒊最后在第一個隊列的節(jié)點為根節(jié)點

雖然使用此方法比使用優(yōu)先隊列的時間復(fù)雜度還低，但是注意此法的第1項，節(jié)點必須依照權(quán)重大小加入隊列中，如果節(jié)點加入順序不按大小，則需要經(jīng)過排序，則至少花了O（ n log n ）的時間復(fù)雜度計算。

但是在不同的狀況考量下，時間復(fù)雜度并非是最重要的，如果我們今天考慮英文字母的出現(xiàn)頻率，變量n就是英文字母的26個字母，則使用哪一種算法時間復(fù)雜度都不會影響很大，因為n不是一筆龐大的數(shù)字。

數(shù)據(jù)解壓縮

簡單來說，霍夫曼碼樹的解壓縮就是將得到的前置碼（Prefix Huffman code）轉(zhuǎn)換回符號，通常借由樹的追蹤（Traversal），將接收到的比特串（Bits stream）一步一步還原。但是要追蹤樹之前，必須要先重建霍夫曼樹 ；某些情況下，如果每個符號的權(quán)重可以被事先預(yù)測，那么霍夫曼樹就可以預(yù)先重建，并且存儲并重復(fù)使用，否則，發(fā)送端必須預(yù)先發(fā)送霍夫曼樹的相關(guān)信息給接收端。

最簡單的方式，就是預(yù)先統(tǒng)計各符號的權(quán)重并加入至壓縮之比特串，但是此法的運算量花費相當(dāng)大，并不適合實際的應(yīng)用。若是使用Canonical encoding，則可精準得知樹重建的數(shù)據(jù)量只占 B 2^ B 比特（其中B為每個符號的比特數(shù)（bits））。如果簡單將接收到的比特串一個比特一個比特的重建，例如："0"表示父節(jié)點，"1"表示終端節(jié)點，若每次讀取到1時，下8個比特則會被解讀是終端節(jié)點（假設(shè)數(shù)據(jù)為8-bit字母），則霍夫曼樹則可被重建，以此方法，數(shù)據(jù)量的大小可能為2~320字節(jié)不等。雖然還有很多方法可以重建霍夫曼樹，但因為壓縮的數(shù)據(jù)串包含"traling bits"，所以還原時一定要考慮何時停止，不要還原到錯誤的值，如在數(shù)據(jù)壓縮時時加上每筆數(shù)據(jù)的長度等。

數(shù)據(jù)長度

設(shè)符號集合 S = { s 1 , s 2 , ? ? --> , s n } {\displaystyle S=\left\{s_{1},s_{2},\cdots ,s_{n}\right\}} ， P ( s j ) {\displaystyle P\left(s_{j}\right)} 為 s j {\displaystyle s_{j}} 發(fā)生的概率 ， L ( s j ) {\displaystyle L\left(s_{j}\right)} 為 s j {\displaystyle s_{j}} 編碼的長度

熵（Entropy）

霍夫曼碼平均長度

霍夫曼碼的長度

霍夫曼碼的平均編碼長度： 設(shè) b = m e a n ( L ) N {\displaystyle b=mean\left(L\right)N} ， N {\displaystyle N} 為數(shù)據(jù)長度

示范程序

//以下為C++程式碼，在GCC下編譯通過//僅用於示範(fàn)如何根據(jù)權(quán)值建構(gòu)霍夫曼樹，//沒有經(jīng)過性能上的優(yōu)化及加上完善的異常處理。#include#include#include#includeusingnamespacestd;constintsize=10;structnode//霍夫曼樹節(jié)點結(jié)構(gòu){unsignedkey;//保存權(quán)值node*lchild;//左孩子指針node*rchild;//右孩子指針};dequeforest;dequecode;//此處也可使用bitsetnode*ptr;intfrequency[size]={0};voidprintCode(dequeptr);//用於輸出霍夫曼編碼boolcompare(node*a,node*b){returna->keykey;}intmain(intargc,char*argv[]){for(inti=0;i>frequency[i];//輸入10個權(quán)值ptr=newnode;ptr->key=frequency[i];ptr->lchild=NULL;ptr->rchild=NULL;forest.push_back(ptr);}//形成森林，森林中的每一棵樹都是一個節(jié)點//從森林構(gòu)建霍夫曼樹for(inti=0;ikey=forest[0]->key+forest[1]->key;ptr->lchild=forest[0];ptr->rchild=forest[1];forest.pop_front();forest.pop_front();forest.push_back(ptr);}ptr=forest.front();//ptr是一個指向根的指針system("PAUSE");returnEXIT_SUCCESS;}voidprintCode(dequeptr){//dequefor(inti=0;i<ptr.size();i++){if(ptr[i])cout<<"1";elsecout<<"0";}}

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。