huffman演算法壓縮演算法
A. 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樹都是經過某種優化後的動態演算法。
網路資源
B. 基於Huffman編碼的數據壓縮演算法的研究與實現
這是我們上學期做的一個上機題：
上機題：設電文字元集D及各字元出現的概率F如下：
D={a，b，c，d，e，f，g，h}（字元數n=8）
F={5，29，7，8，14，23，3，11}(%)
編寫完成下列功能的程序：
①構造關於F的Huffman樹；
②求出並列印D總各字元的Huffman編碼。
程序結構： 類型說明；
構造Huffman樹的函數：Huffman_tree(H[m+1])；
求Huffman編碼的函數：Huffman_code(code[n+1])；
main()
{ 變數說明；
輸入字元集D及頻率F；
調用Huffman_tree(H)；
調用Huffman_code(code)；
列印編碼；Y繼續，N退出}
運行後，輸入8個字元（中間不能有空格，否則將空格視為字元處理），然後輸入概率（整數，空格或回車分隔。如果要支持浮點數，要改程序）然後Enter，出現構造的霍夫曼節點和編碼，程序如下：（因為這只是一個上機題目，所以程序不復雜，也沒有論文，希望對你有幫助）
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define N 8
#define M 2*N-1
#define MAX 32767
typedef char datatype;
typedef struct
{
int wi;
char data;
int Parent,Lchild,Rchild;
}huffm;
typedef struct
{
char bits[N+1];
int start;
char ch;
}ctype;
void Huffman_tree(huffm H[M+1])
{
int i,j,p1,p2;
int w,s1,s2;
for(i=1;i<=M;i++)
{
H[i].wi=MAX;
H[i].Parent=0;
H[i].Lchild=H[i].Rchild=0;
}
printf("please enter the weight:\n");
for(i=1;i<=N;i++)
{
scanf("%d",&H[i].wi);
}
for(i=N+1;i<=M;i++)
{
p1=p2=0;
s1=s2=MAX;
for(j=1;j<=M;j++)
if(H[j].Parent==0)
if(H[j].wi<s1)
{
s2=s1;
s1=H[j].wi;
p2=p1; p1=j;
}
else if(H[j].wi<s2) {s2=H[j].wi; p2=j;}
H[p1].Parent=H[p2].Parent=i;
H[i].Lchild=p1;
H[i].Rchild=p2;
H[i].wi=H[p1].wi+H[p2].wi;
}
printf("Number\tParent\tLchild\tRchild\n");
for(i=1;i<=M;i++)
printf("%d\t%d\t%d\t%d\n",i,H[i].Parent,H[i].Lchild,H[i].Rchild);
}
void Huffman_code(ctype code[N+1])
{
int i,j,p,s;
char c[N];
huffm H[M+1];
ctype md;
printf("please enter char:\n");
/* for(i=1;i<=N;i++)
{
scanf("%c",&c);
H[i].data=code[i].ch=c;
}
*/
scanf("%s",c);
for(i=1;i<=N;i++)H[i].data=code[i].ch=c[i-1];
Huffman_tree(H);
for(i=1;i<=N;i++)
{
md.ch=code[i].ch;
md.start=N+1;
s=i;
p=H[i].Parent;
while(p!=0)
{
md.start--;
if(H[p].Lchild==s)
md.bits[md.start]='1';
else
md.bits[md.start]='0';
s=p;
p=H[p].Parent;
}
code[i]=md;
}
printf("print the code:\n");
for(i=1;i<=N;i++)
printf("%c\t",code[i].ch);
printf("\n");
for(i=1;i<=N;i++)
{
for(j=code[i].start;j<=N;j++)
printf("%c",code[i].bits[j]);
printf("\t");
}
printf("\n");
}
int Continue()
{ char c;
getchar();
printf("continue? y/n\n");
c=getchar();
if(c=='y') return 1;
else return 0;
}
main()
{
do{
/* huffm H[M+1]; */
ctype code[N+1];
Huffman_code(code);
}while(Continue());
}
C. 如何用哈夫曼編碼實現英文文本的壓縮和解壓縮
哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。有人用C函數寫了這個編碼，見下面鏈接
http://ke..com/view/189694.htm
D. 如何寫壓縮軟體，運用哈夫曼演算法實現
到文件壓縮大家很容易想到的就是rar,zip等我們常見的壓縮格式。然而，還有一種就是大家在學習數據結構最常見到的哈夫曼樹的數據結構，以前還不知道他又什麼用，其實他最大的用途就是用來做壓縮，也是一些rar,zip壓縮的祖先，稱為哈弗曼壓縮（什麼你不知道誰是哈弗曼，也不知道哈弗曼壓縮，不急等下介紹）。
隨著網路與多媒體技術的興起，人們需要存儲和傳輸的數據越來越多，數據量越來越大，以前帶寬有限的傳輸網路和容量有限的存儲介質難以滿足用戶的需求。
特別是聲音、圖像和視頻等媒體在人們的日常生活和工作中的地位日益突出，這個問題越發顯得嚴重和迫切。如今，數據壓縮技術早已是多媒體領域中的關鍵技術之一。
一、什麼是哈弗曼壓縮
Huffman(哈夫曼)演算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明Huffman演算法在無損壓縮演算法中是最優的。Huffman原理簡單，實現起來也不困難，在現在的主流壓縮軟體得到了廣泛的應用。對應用程序、重要資料等絕對不允許信息丟失的壓縮場合，Huffman演算法是非常好的選擇。
二、怎麼實現哈弗曼壓縮
哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。
故我們得了解幾個概念：
1、二叉樹：在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。2、哈夫曼編碼(Huffman Coding)：是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。uffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。三、哈夫曼編碼生成步驟：
①掃描要壓縮的文件，對字元出現的頻率進行計算。
②把字元按出現的頻率進行排序，組成一個隊列。
③把出現頻率最低（權值）的兩個字元作為葉子節點，它們的權值之和為根節點組成一棵樹。
④把上面葉子節點的兩個字元從隊列中移除，並把它們組成的根節點加入到隊列。
⑤把隊列重新進行排序。重復步驟③④⑤直到隊列中只有一個節點為止。
⑥把這棵樹上的根節點定義為0（可自行定義0或1）左邊為0，右邊為1。這樣就可以得到每個葉子節點的哈夫曼編碼了。
既如 (a)、(b)、(c)、(d)幾個圖，就可以將離散型的數據轉化為樹型的了。
如果假設樹的左邊用0表示右邊用1表示，則每一個數可以用一個01串表示出來。
則可以得到對應的編碼如下：
1-->110
2-->111
3-->10
4-->0
每一個01串，既為每一個數字的哈弗曼編碼。
為什麼能壓縮：
壓縮的時候當我們遇到了文本中的1、2、3、4幾個字元的時候，我們不用原來的存儲，而是轉化為用它們的01串來存儲不久是能減小了空間佔用了嗎。（什麼01串不是比原來的字元還多了嗎？怎麼減少？）大家應該知道的，計算機中我們存儲一個int型數據的時候一般式佔用了2^32-1個01位，因為計算機中所有的數據都是最後轉化為二進制位去存儲的。所以，想想我們的編碼不就是只含有0和1嘛，因此我們就直接將編碼按照計算機的存儲規則用位的方法寫入進去就能實現壓縮了。
比如：
1這個數字，用整數寫進計算機硬碟去存儲，佔用了2^32-1個二進制位
而如果用它的哈弗曼編碼去存儲，只有110三個二進制位。
效果顯而易見。
E. 霍夫曼演算法
霍夫曼演算法的步驟是這樣的：
·從各個節點中找出最小的兩個節點，給它們建一個父節點，值為這兩個節點之和。
·然後從節點序列中去除這兩個節點，加入它們的父節點到序列中。
重復上面兩個步驟，直到節點序列中只剩下唯一一個節點。這時一棵最優二叉樹就已經建成了，它的根就是剩下的這個節點。
仍以上面的例子來看霍夫曼樹的建立過程。
最初的節點序列是這樣的：
a(6) b(15) c(2) d(9) e(1)
把最小的c和e結合起來
| (3)
a(6) b(15) d(9) +------+------+
| |
c e
不斷重復，最終得到的樹是這樣的：
根
|
+-----33-----+
| |
15 +----18----+
| |
9 +------9-----+
| |
6 +--3--+
| |
2 1
這時各個字元的編碼長度和前面我們說過的方法得到的編碼長度是相同的，因而文件的總長度也是相同的： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63
考察霍夫曼樹的建立過程中的每一步的節點序列的變化：
6 15 2 9 1
6 15 9 3
15 9 9
15 18
33
下面我們用逆推法來證明對於各種不同的節點序列，用霍夫曼演算法建立起來的樹總是一棵最優二叉樹：
對霍夫曼樹的建立過程運用逆推法：
當這個過程中的節點序列只有兩個節點時（比如前例中的15和18），肯定是一棵最優二叉樹，一個編碼為0，另一個編碼為1，無法再進一步優化。
然後往前步進，節點序列中不斷地減少一個節點，增加兩個節點，在步進過程中將始終保持是一棵最優二叉樹，這是因為：
1.按照霍夫曼樹的建立過程，新增的兩個節點是當前節點序列中最小的兩個，其他的任何兩個節點的父節點都大於（或等於）這兩個節點的父節點，只要前一步是最優二叉樹，其他的任何兩個節點的父節點就一定都處在它們的父節點的上層或同層，所以這兩個節點一定處在當前二叉樹的最低一層。
2.這兩個新增的節點是最小的，所以無法和其他上層節點對換。符合我們前面說的最優二叉樹的第一個條件。
3.只要前一步是最優二叉樹，由於這兩個新增的節點是最小的，即使同層有其他節點，也無法和同層其他節點重新結合，產生比它們的父節點更小的上層節點來和同層的其他節點對換。它們的父節點小於其他節點的父節點，它們又小於其他所有節點，只要前一步符合最優二叉樹的第二個條件，到這一步仍將符合。
這樣一步步逆推下去，在這個過程中霍夫曼樹每一步都始終保持著是一棵最優二叉樹。
由於每一步都從節點序列中刪除兩個節點，新增一個節點，霍夫曼樹的建立過程共需 (原始節點數 - 1) 步，所以霍夫曼演算法不失為一種精巧的編碼式壓縮演算法。
附：對於 huffman 樹，《計算機程序設計藝術》中有完全不同的證明，大意是這樣的：
1．二叉編碼樹的內部節點（非葉子節點）數等於外部節點（葉子節點）數減1。
2．二叉編碼樹的外部節點的加權路徑長度（值乘以路徑長度）之和，等於所有內部節點值之和。（這兩條都可以通過對節點數運用數學歸納法來證明，留給大家做練習。）
3．對 huffman 樹的建立過程運用逆推，當只有一個內部節點時，肯定是一棵最優二叉樹。
4．往前步進，新增兩個最小的外部節點，它們結合在一起產生一個新的內部節點，當且僅當原先的內部節點集合是極小化的，加入這個新的內部節點後仍是極小化的。（因為最小的兩個節點結合在一起，並處於最低層，相對於它們分別和其他同層或上層節點結合在一起，至少不會增加加權路徑長度。）
5．隨著內部節點數逐個增加，內部節點集合總維持極小化。
2．實現部分
如果世界上從沒有一個壓縮程序，我們看了前面的壓縮原理，將有信心一定能作出一個可以壓縮大多數格式、內容的數據的程序，當我們著手要做這樣一個程序的時候，會發現有很多的難題需要我們去一個個解決，下面將逐個描述這些難題，並詳細分析 zip 演算法是如何解決這些難題的，其中很多問題帶有普遍意義，比如查找匹配，比如數組排序等等，這些都是說不盡的話題，讓我們深入其中，做一番思考。
F. 利用huffman樹實現文件的壓縮與解壓
這是本人寫的動態哈夫曼壓縮演算法實現，壓縮與解壓縮時，
根據文件內容自動生成哈夫曼樹，並動態調整節點的權重
和樹的形狀。900MHZ的PIII賽揚每秒鍾可以壓縮的好幾MB
的數據，只是壓縮率不高，文本文件的壓縮後容量一般可
以減少25%，比RAR差遠了。
源文件共三個，你在VC6.0中新建一個空的命令行項目，
將它們加進去，編譯完就可以用了。
===========hfm.cpp===================
#include <stdio.h>
#include <string.h>
#include <io.h>
#include <sys/stat.h>
#include <fcntl.h>
#include "Huffman.h"
int wh;
int rh;
bool Write(unsigned char *s,int len){
_write(wh,s,len);
return true;
}
bool OpenFile(char* source,char* target){
int w_flag=_O_WRONLY | _O_CREAT | _O_EXCL | _O_BINARY;
int r_flag=_O_RDONLY | _O_BINARY;
rh=_open(source,r_flag,_S_IREAD | _S_IWRITE);
wh=_open(target,w_flag,_S_IREAD | _S_IWRITE);
if(rh==-1 || wh==-1){
if(rh!=-1){
_close(rh);
printf("\n打開文件：'%s'失敗!",target);
}
if(wh!=-1){
_close(wh);
printf("\n打開文件：'%s'失敗!",source);
}
return false;
}else{
return true;
}
}
void PrintUsage(){
printf("\n以動態哈夫曼演算法壓縮或解壓縮文件。\n\n");
printf("\thfm -?\t\t\t\t顯示幫助信息\n");
printf("\thfm -e -i source -o target\t壓縮文件\n");
printf("\thfm -d -i source -o target\t解壓縮文件\n\n");
}
void main(int argc,char *args[]){
int mode,i,j,K=0;
char src[4096];
char target[4096];
unsigned char buffer[BUFFER_SIZE];
Huffman *h;
mode=0;
for(i=1;i<argc;i++){
if(args[i][0]=='-' || args[i][0]=='/'){
switch(args[i][1]){
case '?':
mode=0;//幫助
break;
case 'e':
case 'E':
mode=1;//壓縮
break;
case 'd':
case 'D':
mode=2;//解壓縮
break;
case 'o':
case 'O':
if(i+1>=argc){
mode=0;
}else{//輸出文件
j=0;
while(args[i+1][j]!='\0' && j<4096){
target[j++]=args[i+1][j];
}
if(j==4096){
mode=0;
}else{
target[j]='\0';
K |= 1;
}
}
break;
case 'i':
case 'I':
if(i+1>=argc){
mode=0;
}else{//輸入文件
j=0;
while(args[i+1][j]!='\0' && j<4096){
src[j++]=args[i+1][j];
}
if(j==4096){
mode=0;
}else{
src[j]='\0';
K |=2;
}
}
break;
}
}
}
if(K!=3)mode=0;
switch(mode){
case 0:
PrintUsage();
return;
case 1://壓縮
if(!OpenFile(src,target))return;
h=new Huffman(&Write,true);
i=BUFFER_SIZE;
while(i==BUFFER_SIZE){
i=_read(rh,buffer,BUFFER_SIZE);
h->Encode(buffer,i);
}
delete h;
_close(rh);
_close(wh);
printf("壓縮完畢!");
break;
case 2://解壓縮
if(!OpenFile(src,target))return;
h=new Huffman(&Write,false);
i=BUFFER_SIZE;
while(i==BUFFER_SIZE){
i=_read(rh,buffer,BUFFER_SIZE);
h->Decode(buffer,i);
}
delete h;
_close(rh);
_close(wh);
printf("解壓縮完畢!");
break;
}
}
=======end of hfm.cpp=======================
=======Huffman.cpp=============================
// Huffman.cpp: implementation of the Huffman class.
//
//////////////////////////////////////////////////////////////////////
#include "Huffman.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
Huffman::Huffman(Output *output,bool mode)
{
Hbtree *tmp;
int i;
this->mode=mode;
//設置輸出函數，當緩沖區滿時，將調用該函數輸出
this->output=output;
//初始化列表
for(i=0;i<LIST_LENGTH;i++)this->list[i]=NULL;
//初始化哈夫曼樹
this->root=this->NewNode(NOT_CHAR,LEFT,NULL);
this->current=this->root;
tmp=this->NewNode(CODE_ESCAPE,RIGHT,root);
tmp->count=1;
tmp=this->NewNode(CODE_FINISH,LEFT,root);
tmp->count=0;
root->count=root->child[LEFT]->count+root->child[RIGHT]->count;
//設置緩沖區指針
this->char_top=BOTTOM_BIT;
this->bit_top=TOP_BIT;
this->buffer[0]=0;
//重構哈夫曼樹的最大計數值
this->max_count=MAX_COUNT;
this->shrink_factor=SHRINK_FACTOR;
this->finished=false;
}
Huffman::~Huffman()
{
if(this->mode==true){//如果是編碼
//輸出結束碼
this->OutputEncode(CODE_FINISH);
this->char_top++;
}
//強制清空緩沖區
this->Flush();
//釋放空間
this->ReleaseNode(this->root);
}
Hbtree * Huffman::NewNode(int value, int index, Hbtree *parent)
{
Hbtree *tmp=new Hbtree;
tmp->parent=parent;
tmp->child[0]=NULL;
tmp->child[1]=NULL;
tmp->count=(1 << SHRINK_FACTOR);
tmp->index=(index==0) ? 0 : 1;
tmp->value=value;
if(value!=NOT_CHAR)this->list[tmp->value]=tmp;
if(parent!=NULL)parent->child[tmp->index]=tmp;
return tmp;
}
void Huffman::ReleaseNode(Hbtree *node)
{
if(node!=NULL){
this->ReleaseNode(node->child[LEFT]);
this->ReleaseNode(node->child[RIGHT]);
delete node;
}
}
//輸出一位編碼
int Huffman::OutputBit(int bit)
{
unsigned char candidates[]={1,2,4,8,16,32,64,128};
if(bit!=0)
this->buffer[this->char_top] |= candidates[this->bit_top];
this->bit_top--;
if(this->bit_top < BOTTOM_BIT){
this->bit_top=TOP_BIT;
this->char_top++;
if(this->char_top >= BUFFER_SIZE){//輸出緩沖區
this->output(this->buffer,BUFFER_SIZE);
this->char_top=0;
}
this->buffer[this->char_top]=0;
}
return 0;
}
//輸出緩沖區
int Huffman::Flush()
{
this->output(this->buffer,this->char_top);
this->char_top=0;
return 0;
}
int Huffman::Encode(unsigned char c)
{
int value=c,
candidates[]={128,64,32,16,8,4,2,1},
i;
if(this->list[value]==NULL){//字元不存在於哈夫曼樹中
//輸出轉義碼
this->OutputEncode(CODE_ESCAPE);
//輸出字元
for(i=0;i<8;i++)this->OutputBit(value & candidates[i]);
this->InsertNewNode(value);
}else{
//輸出字元編碼
this->OutputEncode(value);
//重新調整哈夫曼樹
this->BalanceNode(this->list[value]->parent);
}
//重組哈夫曼樹
if(this->root->count>=this->max_count)
this->RearrangeTree();
return 0;
}
void Huffman::BalanceNode(Hbtree *node)
{
Hbtree *parent,*child,*brother;
int i,j;
parent=node->parent;
if(parent==NULL)return;//根節點無需調整
if(node->value==NOT_CHAR){//非葉子節點
child=node->child[LEFT]->count > node->child[RIGHT]->count ?
node->child[LEFT] : node->child[RIGHT];
if(child->count > parent->count - node->count){
//失衡
i=!(node->index);
j=child->index;
node->count=parent->count - child->count;
brother=parent->child[i];
node->child[j]=brother;
brother->index=j;
brother->parent=node;
parent->child[i]=child;
child->index=i;
child->parent=parent;
}
}
this->BalanceNode(parent);
}
//輸出一個字元的編碼
int Huffman::OutputEncode(int value)
{
int stack[CODE_FINISH+2],top=0;
Hbtree *tmp=this->list[value];
//輸出編碼
if(value<=MAX_VALUE){//字元
while(tmp!=NULL){
stack[top++]=tmp->index;
tmp->count++;
tmp=tmp->parent;
}
}else{//控制碼
while(tmp!=NULL){
stack[top++]=tmp->index;
tmp=tmp->parent;
}
}
top--;
while(top>0){
this->OutputBit(stack[--top]);
}
return 0;
}
void Huffman::PrintNode(Hbtree *node,int level)
{
int i;
if(node){
for(i=0;i<level*3;i++)printf(" ");
printf("%p P:%p L:%p R:%p C:%d",node,node->parent,node->child[0],node->child[1],node->count);
if(node->value!=NOT_CHAR)printf(" V:%d",node->value);
printf("\n");
this->PrintNode(node->child[LEFT],level+1);
this->PrintNode(node->child[RIGHT],level+1);
}
}
int Huffman::Encode(unsigned char *s, int len)
{
int i;
for(i=0;i<len;i++)this->Encode(s[i]);
return 0;
}
void Huffman::PrintTree()
{
this->PrintNode(this->root,0);
}
int Huffman::RecountNode(Hbtree *node)
{
if(node->value!=NOT_CHAR)return node->count;
node->count=
this->RecountNode(node->child[LEFT]) +
this->RecountNode(node->child[RIGHT]);
return node->count;
}
void Huffman::RearrangeTree()
{
int i,j,k;
Hbtree *tmp,*tmp2;
//所有非控制碼的計數值右移shrink_factor位，並刪除計數值為零的節點
for(k=0;k<=MAX_VALUE;k++){
if(this->list[k]!=NULL){
tmp=this->list[k];
tmp->count >>= this->shrink_factor;
if(tmp->count ==0){
this->list[k]=NULL;
tmp2=tmp->parent;
i=tmp2->index;
j=!(tmp->index);
if(tmp2->parent!=NULL){
tmp2->parent->child[i]=tmp2->child[j];
tmp2->child[j]->parent=tmp2->parent;
tmp2->child[j]->index=i;
}else{
this->root=tmp2->child[j];
this->current=this->root;
this->root->parent=NULL;
}
delete tmp;
delete tmp2;
}
}
}
//重新計數
this->RecountNode(this->root);
//重新調整平衡
for(i=0;i<=MAX_VALUE;i++){
if(this->list[i]!=NULL)
this->BalanceNode(this->list[i]->parent);
}
}
void Huffman::InsertNewNode(int value)
{
int i;
Hbtree *tmp,*tmp2;
//將字元加入哈夫曼樹
tmp2=this->list[CODE_FINISH];
tmp=this->NewNode(NOT_CHAR, tmp2->index, tmp2->parent);
tmp->child[LEFT]=tmp2;
tmp2->index=LEFT;
tmp2->parent=tmp;
tmp2=this->NewNode(value,RIGHT,tmp);
tmp->count=tmp->child[LEFT]->count+tmp->child[RIGHT]->count;
i=tmp2->count;
while((tmp=tmp->parent)!=NULL)tmp->count+=i;
//從底向上調整哈夫曼樹
this->BalanceNode(tmp2->parent);
}
int Huffman::Decode(unsigned char c)
{
this->Decode(c,7);
return 0;
}
int Huffman::Decode(unsigned char *s,int len)
{
int i;
for(i=0;i<len;i++)this->Decode(s[i]);
return 0;
}
int Huffman::Decode(unsigned char c, int start)
{
int value=c,
candidates[]={1,2,4,8,16,32,64,128},
i,j;
Hbtree *tmp;
if(this->finished)return 0;
i=start;
if(this->current==NULL){//轉義狀態下
while(this->remain >= 0 && i>=0){
if((candidates[i] & value) !=0){
this->literal |= candidates[this->remain];
}
this->remain--;
i--;
}
if(this->remain < 0){//字元輸出完畢
//輸出字元
this->OutputChar(this->literal);
//將字元插入哈夫曼樹
this->InsertNewNode(literal);
//重組哈夫曼樹
if(this->root->count>=this->max_count)
this->RearrangeTree();
//設置環境
this->current=this->root;
}
}else{
j=((value & candidates[i])!=0)?1:0;
tmp=this->current->child[j];
i--;
while(tmp->value==NOT_CHAR && i>=0){
j=((value & candidates[i])!=0)?1:0;
tmp=tmp->child[j];
i--;
}
if(tmp->value==NOT_CHAR){//中間節點
this->current=tmp;
}else{
if(tmp->value<=MAX_VALUE){//編碼內容
j=tmp->value;
this->OutputChar((unsigned char)j);
//修改計數器
tmp=this->list[j];
while(tmp!=NULL){
tmp->count++;
tmp=tmp->parent;
}
//調整平衡度
this->BalanceNode(this->list[j]->parent);
//重組哈夫曼樹
if(this->root->count>=this->max_count)
this->RearrangeTree();
//設置環境
this->current=this->root;
}else{
if(tmp->value==CODE_ESCAPE){//轉義碼
this->current=NULL;
this->remain=7;
this->literal=0;
}else{//結束碼
this->finished=true;
return 0;
}
}
}
}
if(i>=0)this->Decode(c,i);
return 0;
}
int Huffman::OutputChar(unsigned char c)
{
this->buffer[this->char_top++]=c;
if(this->char_top>=BUFFER_SIZE){//輸出緩沖區
this->output(this->buffer,BUFFER_SIZE);
this->char_top=0;
}
return 0;
}
========end of Huffman.cpp==================
========Huffman.h============================
// Huffman.h: interface for the Huffman class.
//
//////////////////////////////////////////////////////////////////////
#if !defined(NULL)
#include <stdio.h>
#endif
#if !defined(AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_)
#define AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#define MAX_COUNT 65536 //最大計數值，大於此值時
#define MAX_VALUE 255 //編碼的最大值
#define CODE_ESCAPE MAX_VALUE+1 //轉義碼
#define CODE_FINISH MAX_VALUE+2 //結束碼
#define LIST_LENGTH MAX_VALUE+3 //編碼列表長度
#define SHRINK_FACTOR 2 //減小的比例，通過右移位實現
#define LEFT 0 //左孩子索引
#define RIGHT 1 //右孩子索引
#define NOT_CHAR -1 //非字元
#define TOP_BIT 7 //字元最高位
#define BOTTOM_BIT 0 //字元最低位
#define BUFFER_SIZE 81920 //緩沖區大小
//輸出函數
typedef bool (Output)(unsigned char *s,int len);
//哈夫曼樹的節點定義
typedef struct Hnode{
int count;//計數器
int index;//父節點的孩子索引（0--左孩子，1--右孩子）
Hnode* child[2];
Hnode* parent;
int value;
}Hbtree;
class Huffman
{
private:
//輸出一個解碼的字元
int OutputChar(unsigned char c);
//從指定位置開始解碼
int Decode(unsigned char c,int start);
//插入一個新節點
void InsertNewNode(int value);
//重新調整哈夫曼樹構型
void RearrangeTree();
//對各節點重新計數
int RecountNode(Hbtree *node);
//列印哈夫曼樹節點
void PrintNode(Hbtree *node,int level);
//輸出一個值的編碼
int OutputEncode(int value);
//調節哈夫曼樹節點使之平衡
void BalanceNode(Hbtree *node);
//輸出一位編碼
int OutputBit(int bit);
//釋放哈夫曼樹節點
void ReleaseNode(Hbtree *node);
//新建一個節點
Hbtree *NewNode(int value,int index, Hbtree *parent);
//輸出函數地址
Output *output;
//哈夫曼樹根地址
Hbtree *root;
//哈夫曼編碼單元列表
Hbtree *list[LIST_LENGTH];
//輸出緩沖區
unsigned char buffer[BUFFER_SIZE];
//緩沖區頂
int char_top,bit_top;
//收縮哈夫曼樹參數
int max_count,shrink_factor;
//工作模式，true--編碼，false--解碼
bool mode;
//解碼的當前節點
Hbtree *current;
int remain;//當前字元剩餘的位數
unsigned char literal;//按位輸出的字元
bool finished;
public:
//解碼指定長度的字元串
int Decode(unsigned char *s,int len);
//解碼一個字元
int Decode(unsigned char c);
//列印哈夫曼樹
void PrintTree();
//編碼指定長度的字元串
int Encode(unsigned char *s,int len);
//編碼一個字元
int Encode(unsigned char c);
//清空緩沖區
int Flush();
//output指輸出函數，mode指工作模式，true--編碼，false--解碼
Huffman(Output *output,bool mode);
//析構函數
virtual ~Huffman();
};
#endif // !defined(AFX_HUFFMAN_H__B1F1A5A6_FB57_49B2_BB67_6D1764CC04AB__INCLUDED_)
================end of Huffman.h==================
祝你好運！
G. 霍夫曼演算法是否只適合壓縮小型文件（100MB以下的），為什麼用它壓縮500多MB文件，時間都夠我吃兩頓飯了
霍夫曼演算法不是一個流式壓縮演算法，需要統計整個文件的所有信息，才能開始壓縮，所以速度上不行。一般的流式壓縮演算法，例如LZMA，他只要一段文件的局部信息就可以進行壓縮了，所以速度上有優勢。而正因為它用的局部信息，壓縮比又不如霍夫曼。
正所謂凡事有利必有弊，速度快的演算法，壓縮比不夠高，壓縮比高的演算法，速度上又不行。計算機編程之難點，不是什麼高深的演算法，而是要根據需求找到事物之間的平衡點，選取最適合的策略。
H. 跪求哈夫曼編碼壓縮與其它壓縮演算法的比較（復雜性和壓縮效果）
（1）所形成的Huffman編碼的碼字是不是唯一的，但是可以被指定為唯一的編碼效率為「1」大，小的是「0」時，兩個最小概率符號賦值。反之也可以。如果兩個符號的發生的概率是相等的，排列無論前面是可能的，所以霍夫曼碼字的結構不是唯一的，對於相同的信息源，不管如何在上述的順序安排的，它的平均碼字長度是不改變，因此，編碼效率是獨一無二的。
（2）只有當不均勻時，每個符號的信息源的發生的概率，霍夫曼編碼的效果是唯一明顯的。
（3）霍夫曼編碼必須是精確的原始文件中的各符號的發生頻率的統計數據，並且如果沒有準確的統計數據，壓縮將低於預期。 Huffman編碼通常必須經過兩道，第一遍統計的第二次產生編碼，編碼速度是比較慢的。電路的復雜性的另一種實現的各種長度的編碼，解碼處理是相對復雜的，因此，解壓縮處理是相對緩慢。
（4）Huffman編碼只能使用整數來表示一個符號，而不是使用小數，這在很大程度上限制了壓縮效果。
（5）霍夫曼是所有的位，如果改變其中一個可以使數據看起來完全不同
I. 哈夫曼壓縮演算法的內容是什麼
注:哈夫曼和lzss演算法不是同一種演算法,先用哈夫曼再用lzss演算法壓縮後會發現經哈夫曼壓縮後再用lzss壓縮文件會變大,具體原因不明
lzss原理:
把編碼位置置於輸入數據流的開始位置。
在前向緩沖器中查找窗口中最長的匹配串
①
pointer
：=匹配串指針。
②
length
：=匹配串長度。
判斷匹配串長度length是否大於等於最小匹配串長度(min_length)
，
如果「是」：輸出指針，然後把編碼位置向前移動length個字元。
如果「否」：輸出前向緩沖存儲器中的第1個字元，然後把編碼位置向前移動一個字元。
如果前向緩沖器不是空的，就返回到步驟2。
例：編碼字元串如表03-05-3所示，編碼過程如表03-05-4所示。現說明如下：
「步驟」欄表示編碼步驟。
「位置」欄表示編碼位置，輸入數據流中的第1個字元為編碼位置1。
「匹配」欄表示窗口中找到的最長的匹配串。
「字元」欄表示匹配之後在前向緩沖存儲器中的第1個字元。
「輸出」欄的輸出為：
①
如果匹配串本身的長度length
>=
min_length，輸出指向匹配串的指針，格式為(back_chars，
chars_length)。該指針告訴解碼器「在這個窗口中向後退back_chars個字元然後拷貝chars_length個字元到輸出」。
②
如果匹配串本身的長度length
>=
min_length，則輸出真實的匹配串。
表:輸入數據流
位置
1234567891011
字元
aabbcbbaabc
表:編碼過程(min_length
=
2)
步驟位置匹配串輸出
11--a
22aa
33--
b
44bb
55--c
66b
b(3,2)
78
a
a
b(7,3)
811cc