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

　　一、霍夫曼編碼介紹

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

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

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

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

　　二、霍夫曼編碼特點(diǎn)

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

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

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

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

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

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

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

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

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

　　采用霍夫曼編碼時(shí)有兩個(gè)問(wèn)題值得注意：

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

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

　　/*

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

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

　　作為字符的唯一編碼。

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

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

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

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

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

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

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

　　兩個(gè)處理過(guò)程：

　　1）建立huffman樹(shù)：

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

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

　　2） 從huffman樹(shù)得到葉子節(jié)點(diǎn)的huffman編碼：

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

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

　　*/

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

　　#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é)點(diǎn)和分支節(jié)點(diǎn)

　　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ù)，設(shè)置n-1個(gè)分支節(jié)點(diǎn)（非葉子），

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

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

　　int nCurMinWeight，nCurSecondMinWeight;

　　int nCurLeftChild， nCurRightChild;

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

　　{

　　nCurMinWeight = nCurSecondMinWeight = MAXWEIGHT;

　　nCurLeftChild = nCurRightChild = 0;

　　// 確定一個(gè)分支節(jié)點(diǎn)，需要對(duì)n + i個(gè)節(jié)點(diǎn)進(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é)點(diǎn)，設(shè)置節(jié)點(diǎn)關(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;

　　}

　　// 測(cè)試用

　　/*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）;

　　}*/

　　// 記錄下來(lái)每個(gè)葉子節(jié)點(diǎn)的huffman編碼

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

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

　　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;

　　}

　　// 因?yàn)檫f減了需要增加，得到正確的起始下標(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;

　　}