huffman壓縮c

1. 演算法解析：哈夫曼（huffman）壓縮演算法

本篇將介紹 哈夫曼壓縮演算法（Huffman compression）

眾所周知，計算機存儲數據時，實際上存儲的是一堆0和1（二進制）。

如果我們存儲一段字元：ABRACADABRA!

那麼計算機會把它們逐一翻譯成二進制，如A：01000001；B: 01000010; !: 00001010.

每個字元佔8個bits, 這一整段字元則至少佔12*8=96 bits。

但如果我們用一些特殊的值來代表這些字元，如：

圖中，0代表A; 1111代表B；等等。此時，存儲這段字元只需30bits，比96bits小多了，達到了壓縮的目的。

我們需要這么一個表格來把原數據翻譯成特別的、占空間較少的數據。同時，我們也可以用這個表格，把特別的數據還原成原數據。

首先，為了避免翻譯歧義，這個表格需滿足一個條件： 任何一個字元用的值都不能是其它字元的前綴 。

我們舉個反例：A: 0; B: 01;這里，A的值是B的值的前綴。如果壓縮後的數據為01xxxxxx,x為0或者1，那麼這個數據應該翻譯成A1xxxxxx, 還是Bxxxxxxx?這樣就會造成歧義。

然後，不同的表格會有不同的壓縮效果，如：

這個表格的壓縮效果更好。

那麼我們如何找到 最好的表格 呢？這個我們稍後再講。

為了方便閱讀，這個表格是可以寫成一棵樹的：

這棵樹的節點左邊是0，右邊是1。任何含有字元的節點都沒有非空子節點。（即上文提及的前綴問題。）

這棵樹是在壓縮的過程中建成的，這個表格是在樹形成後建成的。用這個表格，我們可以很簡單地把一段字元變成壓縮後的數據，如：

原數據：ABRACADABRA!

表格如上圖。

令壓縮後的數據為S；

第一個字元是A，根據表格，A：11，故S=11;

第二個字元是B，根據表格，B：00，故S=1100;

第三個字元是R，根據表格，R：011，故S=1100011;

如此類推，讀完所有字元為止。

壓縮搞定了，那解壓呢？很簡單，跟著這棵樹讀就行了：

壓縮後的數據S=11000111101011100110001111101

記住，讀到1時，往右走，讀到0時，往左走。

令解壓後的字元串為D；

從根節點出發，第一個數是1，往右走：

第二個數是1，往右走：

讀到有字元的節點，返回此字元，加到字元串D里。D:A;

返回根節點，繼續讀。

第三個數是0，往左走：

第四個數是0，往左走：

讀到有字元的節點，返回此字元，加到字元串D里。D:AB;

返回根節點，繼續讀。

第五個數是0，往左走：

第六個數是1，往右走：

第七個數是1，往右走：

讀到有字元的節點，返回此字元，加到字元串D里。D:ABR;

返回根節點，繼續讀。

如此類推，直到讀完所有壓縮後的數據S為止。

壓縮與解壓都搞定了之後 我們需要先把原數據讀一遍，並把每個字元出現的次數記錄下來。如：

ABRACADABRA!中，A出現了5次;B出現了2次;C出現了1次;D出現了1次;R出現了2次;!出現了1次。

理論上，出現頻率越高的字元，我們給它一個佔用空間越小的值，這樣，我們就可以有最佳的壓縮率

由於哈夫曼壓縮演算法這塊涉及內容較多 ，文章篇幅很長；全文全方面講解了Compose布局的各方面知識。更多Android前言技術進階，我自薦一套《 完整的Android的資料，以及一些視頻課講解 》 現在私信發送「進階」或者「筆記」即可免費獲取

最後我想說：

對於程序員來說，要學習的知識內容、技術有太多太多，要想不被環境淘汰就只有不斷提升自己，從來都是我們去適應環境，而不是環境來適應我們

技術是無止境的，你需要對自己提交的每一行代碼、使用的每一個工具負責，不斷挖掘其底層原理，才能使自己的技術升華到更高的層面

Android 架構師之路還很漫長，與君共勉

2. 哈夫曼編碼的壓縮實現

壓縮代碼非常簡單，首先用ASCII值初始化511個哈夫曼節點：
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
其次，計算在輸入緩沖區數據中，每個ASCII碼出現的頻率：
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然後，根據頻率進行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
哈夫曼樹，獲取每個ASCII碼對應的位序列：
int nNodeCount = GetHuffmanTree(nodes); 構造哈夫曼樹非常簡單，將所有的節點放到一個隊列中，用一個節點替換兩個頻率最低的節點，新節點的頻率就是這兩個節點的頻率之和。這樣，新節點就是兩個被替換節點的父節點了。如此循環，直到隊列中只剩一個節點（樹根）。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 有一個好的訣竅來避免使用任何隊列組件。ASCII碼只有256個，但實際分配了511個(CHuffmanNode nodes[511])，前255個記錄ASCII碼，而用後255個記錄哈夫曼樹中的父節點。並且在構造樹的時候只使用一個指針數組(ChuffmanNode *pNodes[256])來指向這些節點。同樣使用兩個變數來操作隊列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接著，壓縮的最後一步是將每個ASCII編碼寫入輸出緩沖區中：
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位為界限右移後到達右邊位元組的前面
(nDesIndex&7): &7 得到最高位.
此外，在壓縮緩沖區中，必須保存哈夫曼樹的節點以及位序列，這樣才能在解壓縮時重新構造哈夫曼樹（只需保存ASCII值和對應的位序列）。 解壓縮比構造哈夫曼樹要簡單的多，將輸入緩沖區中的每個編碼用對應的ASCII碼逐個替換就可以了。只要記住，這里的輸入緩沖區是一個包含每個ASCII值的編碼的位流。因此，為了用ASCII值替換編碼，我們必須用位流搜索哈夫曼樹，直到發現一個葉節點，然後將它的ASCII值添加到輸出緩沖區中：
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}

3. Huffman編碼不適合圖像壓縮么，為什麼。有相關的資料么。能給我看看不QQ504278770

下面是我從網上搜索到的資料，希望對你有幫助。

1.哈夫曼圖像壓縮演算法引言

隨著網路與多媒體技術的興起，人們需要存儲和傳輸的數據越來越多，數據量越來越大，以前帶寬有限的傳輸網路和容量有限的存儲介質難以滿足用戶的需求。

特別是聲音、圖像和視頻等媒體在人們的日常生活和工作中的地位日益突出，這個問題越發顯得嚴重和迫切。如今，數據壓縮技術早已是多媒體領域中的關鍵技術之一。

Huffman(哈夫曼)演算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明Huffman演算法在無損壓縮演算法中是最優的。Huffman原理簡單，實現起來也不困難，在現在的主流壓縮軟體得到了廣泛的應用。對應用程序、重要資料等絕對不允許信息丟失的壓縮場合，Huffman演算法是非常好的選擇。

2.哈夫曼圖像壓縮演算法原理

Huffman編碼是1952年由Huffman提出的對統計獨立信源能達到最小平均碼長的編碼方法。這一年，他發表了著名論文「A Method for the Construction of Minimum Rendancy Codes」，即最短冗餘碼的構造方法.之後，Huffman編碼及其一些改進方法一直是數據壓縮領域的研究熱點之一。

Huffman碼是一種變長碼，其基本思想是：先統計圖像(已經數字化)中各灰度出現的概率，出現概率較大的賦以較短的碼字，而出現概率較小的則賦以較長的碼字。我們可以用下面的框圖來表示Huffman編碼的過程：

在整個編碼過程中，統計圖像各灰度級出現的概率和編碼這兩步都很簡單，關鍵的是Huffman樹的構造。不但編碼的時候需要用到這顆樹，解碼的時候也必須有這顆樹才能完成解碼工作，因此，Huffman樹還得完整的傳輸到解碼端。

Huffman樹的構造可以按照下面圖2的流程圖來完成。首先對統計出來的概率從小到大進行排序，然後將最小的兩個概率相加;到這兒的時候，先把已經加過的兩個概率作為樹的兩個節點，並把他們從概率隊列中刪除;然後把相加所得的新概率加入到隊列中，對這個新隊列進行排序。

如此反復，直到最後兩個概率相加為1的時候停止。這樣，Huffman樹就建立起來了。

3. 哈夫曼圖像壓縮演算法軟體實現

這兒，我們以Turbo C為例來說明軟體實現Huffman圖像壓縮演算法的一些關鍵技術。

為了敘述方便，我們不妨假設處理的圖像的灰度級變化范圍從0到255，即具有256個灰度級。我們先來統計輸入圖像的概率，實際上是要統計各個灰度級在整幅圖像中出現的次數。為此，我們先定義一個具有256個元素的數組。

然後對輸入圖像信號進行掃描，每出現一個灰度，就把它存入實現定義好的一個數組中的相應元素中(讓這個元素的值自增1)。最後，通過讀取數組中各元素的值就可以求出各個灰度出現的頻數。

接下來就該構造Huffman樹了。為了構造Huffman樹，我們要用到C語言中鏈表的概念。我們必須用一個結構體來表示Huffman樹的節點。對於每個節點而言我們需要這樣幾個信息：本節點的權重(就是灰度的頻數)、指向父節點的指針和分別指向左右子葉節點的指針。於是，我們可以定義這樣一個結構體：

Struct Node{

Floatweight;

Node * father;

Node * left;

Node * right;}Huffman_Node

我們需要先確定權最低的兩個自由結點，這將是最初的left和right節點。然後建立這兩個結點的父結點，並讓它的權等於這兩個結點的權之和。

接著將這個父結點增加到自由結點的序列中，而兩個子結點則從序列中去掉。重復前面的步驟直到只剩下一個自由結點，這個自由結點就是Huffman樹的根。

Huffman編碼樹作為一個二叉樹從葉結點逐步向上建立。Huffman樹建立好以後，為了把權、概率等數值轉化碼字，我們還得對整個Huffman樹進行掃描。請注意，在建立Huffman樹的時候，我們是從樹葉開始的，而在對Huffman樹分配碼字的時候卻剛好相反，是從樹根開始，沿著各個樹枝的走向「順藤摸瓜」似的對各個系數進行編碼。

對於一個節點的兩個子節點(left和right)，其中一個節點對應的位為0，而另一個結點則人為地設置成為l。解碼的時候也是完全相同的一顆Huffman樹完成的。下面的循環是實現壓縮的關鍵語句之一[ 1 ]。

for (i = length-1; i >= 0; ――i) {

if ((current_code >> i) & 1)

thebyte |= (char) (1 << curbit);

if (--curbit < 0) {

putc (thebyte, ofile);

thebyte = 0;

curbyte++;

curbit = 7;

}

}

注意：這幾行代碼執行了數據壓縮的功能，但是還沒有生成編碼和解碼所需要的代碼表。

4.哈夫曼圖像壓縮演算法性能評價

我們主要從三方面[ 2 ]來評價Huffman的性能：

(1)壓縮比的大小;

(2)恢復效果的好壞，也就是能否盡可能的恢復原始數據;

(3)演算法的簡單易用性以及編、解碼的速度。

首先分析一下對壓縮比的影響因素(不同的著作中對壓縮比的定義不盡相同，這兒我們採用如下定義：壓縮比等於壓縮之前的以比特計算的數據量比上壓縮之後的數據量)。對於Huffman編碼來說，我們因為要用額外的位保存和傳輸Huffman樹而「浪費」掉一些存儲位，也就是說，為了編、解碼的方便，我們把本已減少的數據量又增加了一些。

如果文件比較大的話，這一點多餘的數據根本算不了什麼，所佔比例很小。但是，如果壓縮的文件本來就很小的話，那麼這筆數據就很可觀了。一般來說，經典的Huffman演算法的壓縮比不是很高，這是無損壓縮的「通病」。

第二點就不用說了，由於它是無損壓縮，能夠完全恢復壓縮之前圖像的本來面貌。

最後，讓我們來分析一下Huffman壓縮方法的速度問題。大家在第三節中已經看到了，在壓縮的過程中，我們進行了兩次掃描，第一次是為了統計各個灰度出現的頻數而掃描整幅圖像，第二次則是為了分配碼字而掃描整個Huffman樹。

這樣一來，對較大的文件進行編碼時，頻繁的磁碟讀寫訪問必然會降低數據編碼的速度，如果用於網路的話，還會因此帶來一些延時，不利於實時壓縮和傳輸。另外，Huffman演算法的編碼和解碼的速度是不對稱的，解碼快於編碼，因為解碼不需要生成Huffman樹的環節。

5.圖像壓縮演算法結束語

Huffman演算法目前已經得到了廣泛的應用，軟體和硬體都已經實現。基於Huffman經典演算法的缺陷，不少人提出了一些自適應演算法。前面的演算法中，Huffman樹是整個圖像全部輸入掃描完成後構造出來的，而自適應演算法(或稱動態演算法)則不必等到全部圖像輸入完成才開始樹的構造，並且可以根據後面輸入的數據動態的對Huffman樹進行調整。實際上，實用的Huffman樹都是經過某種優化後的動態演算法。

網路資源