Huffman霍夫曼壓縮編碼算法實現(xiàn)分析

　　一、霍夫曼編碼介紹

　　霍夫曼編碼（Huffman Coding）是一種編碼方式，是一種用于無損數(shù)據(jù)壓縮的熵編碼（權(quán)編碼）算法。

　　霍夫曼編碼是可變字長編碼（VLC）的一種。 Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就稱Huffman編碼。下面引證一個定理，該定理保證了按字符出現(xiàn)概率分配碼長，可使平均碼長最短。

　　定理：在變字長編碼中，如果碼字長度嚴(yán)格按照對應(yīng)符號出現(xiàn)的概率大小逆序排列，則其平 均碼字長度為最小。

　　霍夫曼編碼的具體方法：先按出現(xiàn)的概率大小排隊，把兩個最小的概率相加，作為新的概率 和剩余的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最后變成1。每次相 加時都將“0”和“1”賦與相加的兩個概率，讀出時由該符號開始一直走到最后的“1”， 將路線上所遇到的“0”和“1”按最低位到最高位的順序排好，就是該符號的霍夫曼編碼。

　　二、霍夫曼編碼特點

　　1） 編出來的碼都是異字頭碼，保證了碼的唯一可譯性。

　　2） 由于編碼長度可變。因此譯碼時間較長，使得霍夫曼編碼的壓縮與還原相當(dāng)費時。

　　3） 編碼長度不統(tǒng)一，硬件實現(xiàn)有難度。

　　4） 對不同信號源的編碼效率不同，當(dāng)信號源的符號概率為2的負(fù)冪次方時，達(dá)到100％的編碼效率；若信號源符號的概率相等，則編碼效率最低。

　　5） 由于0與1的指定是任意的，故由上述過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數(shù)據(jù)壓縮性能。

　　三、Huffman霍夫曼編碼的壓縮原理

　　我們把文件中一定位長的值看作是符號，比如把8位長的256種值，也就是字節(jié)的256種值看作是符號。我們根據(jù)這些符號在文件中出現(xiàn)的頻率，對這些符號重新編碼。對于出現(xiàn)次數(shù)非常多的，我們用較少的位來表示，對于出現(xiàn)次數(shù)非常少的，我們用較多的位來表示。這樣一來，文件的一些部分位數(shù)變少了，一些部分位數(shù)變多了，由于變小的部分比變大的部分多，所以整個文件的大小還是會減小，所以文件得到了壓縮。

　　四、Huffman霍夫曼壓縮編碼算法實現(xiàn)分析

　　哈夫曼編碼Huffman方法于1952年問世，迄今為止仍經(jīng)久不衰，廣泛應(yīng)用于各種數(shù)據(jù)壓縮技術(shù)中，且仍不失為熵編碼中的最佳編碼方法，deflate等壓縮算法也是結(jié)合了huffman算法的。

　　采用霍夫曼編碼時有兩個問題值得注意：

　?、倩舴蚵a沒有錯誤保護(hù)功能，在譯碼時，如果碼串中沒有錯誤，那么就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，哪僅是1位出現(xiàn)錯誤，不但這個碼本身譯錯，更糟糕的是一錯一大串，全亂了套，這種現(xiàn)象稱為錯誤傳播（error propagation）。計算機(jī)對這種錯誤也無能為力，說不出錯在哪里，更談不上去糾正它。

　?、诨舴蚵a是可變長度碼，因此很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲代碼之前加以考慮。盡管如此，霍夫曼碼還是得到廣泛應(yīng)用。

　　/*

　　霍夫曼編碼模型：思想是壓縮數(shù)據(jù)出現(xiàn)概率高的用短編碼，出現(xiàn)概率低的用長編碼，且每個字符編碼都不一樣。

　　壓縮數(shù)據(jù)單個字符出現(xiàn)的概率抽象為葉子節(jié)點的權(quán)值，huffman樹葉子節(jié)點到根節(jié)點的編碼（是父節(jié)點左子節(jié)點那么填0，否則填1）

　　作為字符的唯一編碼。

　　實現(xiàn)時候需要注意的規(guī)則：

　　1）最左的放置在左邊，作為父節(jié)點的左節(jié)點。

　　2）每次都從沒有設(shè)置父節(jié)點的所用節(jié)點中（葉子和分支節(jié)點一樣對待），從數(shù)組小下標(biāo)到大下標(biāo)優(yōu)先順序遍歷。

　　3）當(dāng)前搜尋的次數(shù)i + n作為新生成的分支節(jié)點的數(shù)組下標(biāo)。

　　實現(xiàn)的過程和具體算法思想：

　　兩個數(shù)據(jù)結(jié)構(gòu)：

　　一個是huffman樹節(jié)點結(jié)構(gòu)體，一個是從霍夫曼樹葉子節(jié)點編碼的結(jié)構(gòu)體。

　　兩個處理過程：

　　1）建立huffman樹：

　　基本思想是：對于沒有設(shè)置父節(jié)點的節(jié)點集選出最小的兩個，最小的放置在左邊，次小的放置在右邊

　　設(shè)置好父節(jié)點和左右子節(jié)點關(guān)系，方便獲得霍夫曼編碼。

　　2） 從huffman樹得到葉子節(jié)點的huffman編碼：

　　基本思想：對于建立好的Huffman樹的每個葉子節(jié)點，由編碼的數(shù)組的末端也是從葉子節(jié)點最底端，往上遍歷

　　如果是父節(jié)點的左節(jié)點那么用編碼數(shù)組填1，如果是父節(jié)點的右節(jié)點那么編碼數(shù)組填0，一直往上追溯到根節(jié)點。

　　*/

　　// 以下是實現(xiàn)的代碼，在win32編譯通過。

　　#include “stdafx.h”

　　#define MAXCODELEN 7

　　#define MAXWEIGHT 10000

　　struct tagHuffmanNode

　　{

　　int m_nWeight;

　　int m_nParent;

　　int m_nLChild;

　　int m_nRChild;

　　};

　　struct tagHuffmanCode

　　{

　　int m_nWeight;

　　int m_nStart;

　　int m_nBit［MAXCODELEN］;

　　};

　　void Huffman（int w［］， int n， tagHuffmanNode ht［］， tagHuffmanCode hc［］）

　　{

　　int nTotalCount = 2 * n - 1;

　　// 初始化填充好ht的所有權(quán)值，包括葉子節(jié)點和分支節(jié)點

　　for（int i = 0; i 《 nTotalCount; i++）

　　{

　　if（ i 《 n）

　　{

　　ht［i］.m_nWeight = w［i］;

　　}

　　else

　　{

　　ht［i］.m_nWeight = 0;

　　}

　　ht［i］.m_nParent = 0;

　　ht［i］.m_nLChild = ht［i］.m_nRChild = -1;

　　}

　　// 構(gòu)造一顆huffman樹，設(shè)置n-1個分支節(jié)點（非葉子），

　　// 基本思想是：對于沒有設(shè)置父節(jié)點的節(jié)點集選出最小的兩個，最小的放置在左邊，次小的放置在右邊

　　// 設(shè)置好父節(jié)點和左右子節(jié)點關(guān)系，方便獲得霍夫曼編碼

　　int nCurMinWeight，nCurSecondMinWeight;

　　int nCurLeftChild， nCurRightChild;

　　for（ int i = 0; i 《 n-1; i++）

　　{

　　nCurMinWeight = nCurSecondMinWeight = MAXWEIGHT;

　　nCurLeftChild = nCurRightChild = 0;

　　// 確定一個分支節(jié)點，需要對n + i個節(jié)點進(jìn)行篩選

　　for（ int j = 0; j 《 n + i; j++）

　　{

　　if（ ht［j］.m_nWeight 《 nCurMinWeight && ht［j］.m_nParent == 0）

　　{

　　nCurSecondMinWeight = nCurMinWeight;

　　nCurRightChild = nCurLeftChild;

　　nCurMinWeight = ht［j］.m_nWeight;

　　nCurLeftChild = j;

　　}

　　else if（ht［j］.m_nWeight 《 nCurSecondMinWeight && ht［j］.m_nParent == 0）

　　{

　　nCurSecondMinWeight = ht［j］.m_nWeight;

　　nCurRightChild = j;

　　}

　　}

　　// 得到分支節(jié)點，設(shè)置節(jié)點關(guān)系

　　ht［n + i］.m_nLChild = nCurLeftChild;

　　ht［n + i］.m_nRChild = nCurRightChild;

　　ht［n + i］.m_nWeight =nCurMinWeight + nCurSecondMinWeight;

　　ht［nCurLeftChild］.m_nParent = n + i;

　　ht［nCurRightChild］.m_nParent = n + i;

　　}

　　// 測試用

　　/*for（int i = 0; i 《 nTotalCount; i++）

　　{

　　printf（“--------------------------------\n”）;

　　printf（“ht［%d］.m_nWeight： %d\n”， i， ht［i］.m_nWeight）;

　　printf（“ht［%d］.m_nParent： %d\n”， i， ht［i］.m_nParent）;

　　printf（“ht［%d］.m_nLChild： %d\n”， i， ht［i］.m_nLChild）;

　　printf（“ht［%d］.m_nRChild： %d\n”， i， ht［i］.m_nRChild）;

　　}*/

　　// 記錄下來每個葉子節(jié)點的huffman編碼

　　// 基本思想：對于建立好的Huffman樹的每個葉子節(jié)點，由編碼的數(shù)組的末端也是從葉子節(jié)點最底端，往上遍歷

　　// 如果是父節(jié)點的左節(jié)點那么用編碼數(shù)組填1，如果是父節(jié)點的右節(jié)點那么編碼數(shù)組填0，一直往上追溯到根節(jié)點。

　　for（int k = 0; k 《 n; k++）

　　{

　　hc［k］.m_nWeight = ht［k］.m_nWeight;

　　hc［k］.m_nStart = n - 1;// start等于最大的值

　　int nChild = k;

　　int nParent = ht［k］.m_nParent;

　　while（nParent ！= 0）

　　{

　　if（nChild == ht［nParent］.m_nLChild）

　　{

　　hc［k］.m_nBit［hc［k］.m_nStart］ = 0;

　　}

　　else if（nChild == ht［nParent］.m_nRChild）

　　{

　　hc［k］.m_nBit［hc［k］.m_nStart］ = 1;

　　}

　　hc［k］.m_nStart--;

　　nChild = nParent;

　　nParent = ht［nChild］.m_nParent;

　　}

　　// 因為遞減了需要增加，得到正確的起始下標(biāo)

　　hc［k］.m_nStart++;

　　}

　　}

　　int _tmain（int argc， _TCHAR* argv［］）

　　{

　　int nDataNum = 7;

　　int nWeigt［］ = {4， 2， 6， 8， 3， 2， 1};

　　const int nMaxLen = 2 * nDataNum - 1;

　　tagHuffmanNode *ht = new tagHuffmanNode［nMaxLen］;

　　tagHuffmanCode *hc = new tagHuffmanCode［nDataNum］;

　　Huffman（nWeigt， nDataNum， ht， hc）;

　　for（int i = 0; i 《 7; i++）

　　{

　　printf（“index： %d， weight： %d， hc［%d］.m_nBit： ”， i， hc［i］.m_nWeight， i）;

　　for（int j = hc［i］.m_nStart; j 《 7; j++）

　　{

　　printf（“%d”， hc［i］.m_nBit［j］）;

　　}

　　printf（“\n”）;

　　}

　　delete ［］ht;

　　delete ［］hc;

　　while（1）;

　　return 0;

　　}