⑴ 霍夫曼 解壓縮
哈夫曼編碼(Huffman Coding)是一種編碼方式，以哈夫曼樹—即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用於數據壓縮。 在計算機信息處理中，「哈夫曼編碼」是一種一致性編碼法（又稱"熵編碼法"），用於數據的無損耗壓縮。這一術語是指使用一張特殊的編碼表將源字元（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在於，它是根據每一個源字元出現的估算概率而建立起來的（出現概率高的字元使用較短的編碼，反之出現概率低的則使用較長的編碼，這便使編碼之後的字元串的平均期望長度降低，從而達到無損壓縮數據的目的）。這種方法是由David.A.Huffman發展起來的。 例如，在英文中，e的出現概率很高，而z的出現概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均佔用一個位元組（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對於英文中各個字母出現概率的較准確的估算，就可以大幅度提高無損壓縮的比例。
本文描述在網上能夠找到的最簡單，最快速的哈夫曼編碼。本方法不使用任何擴展動態庫，比如STL或者組件。只使用簡單的C函數，比如：memset，memmove，qsort，malloc，realloc和memcpy。
因此，大家都會發現，理解甚至修改這個編碼都是很容易的。
背景
哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。
編碼使用
我用簡單的C函數寫這個編碼是為了讓它在任何地方使用都會比較方便。你可以將他們放到類中，或者直接使用這個函數。並且我使用了簡單的格式，僅僅輸入輸出緩沖區，而不象其它文章中那樣，輸入輸出文件。
bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
要點說明
速度
為了讓它(huffman.cpp)快速運行，我花了很長時間。同時，我沒有使用任何動態庫，比如STL或者MFC。它壓縮1M數據少於100ms（P3處理器，主頻1G）。
壓縮
壓縮代碼非常簡單，首先用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;
}
⑵ 一、實驗題目：用哈夫曼編碼實現文件壓縮用C++實現
這是我的實驗報告： http://student.csdn.net/space.php?uid=395622&do=blog&id=51206 /** * @brief 哈夫曼編碼 * @date 2010-11-30 */ #include <iostream> #include <string> #include <queue> #include <map> using namespace std; /** * @brief 哈弗曼結點 * 記錄了哈弗曼樹結點的數據、權重及左右兒子 */ struct HTNode { char data; HTNode *lc, *rc; int w; /** 節點構造函數 */ HTNode(char _d, int _w, HTNode *_l = NULL, HTNode *_r = NULL) { data = _d; w = _w; lc = _l; rc = _r; } /** 節點拷貝構造函數 */ HTNode(const HTNode &h) { data = h.data; lc = h.lc; rc = h.rc; w = h.w; } /** 用於優先隊列比較的運算符重載 */ friend bool operator < (const HTNode &a, const HTNode &b) { return a.w > b.w; } }; /** 哈弗曼樹葉子節點數、各葉子結點數據及權重 */ /** 權值從Lolita小說中抽樣取出 */ const char ch[] = { 10, 32, 33, 37, 40, 41, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 161, 164, 166, 168, 170, 173, 174, 175, 176, 177, 180, 186, 255, '\r', '\0' }; const int fnum[] = { 2970, 99537, 265, 1, 496, 494, 9032, 1185, 5064, 108, 180, 132, 99, 105, 82, 64, 62, 77, 126, 296, 556, 548, 818, 443, 543, 435, 225, 271, 260, 797, 3487, 158, 50, 1053, 589, 498, 332, 316, 61, 276, 724, 855, 54, 293, 543, 11, 185, 11, 25, 26, 42416, 7856, 12699, 23670, 61127, 10229, 10651, 27912, 32809, 510, 4475, 23812, 13993, 34096, 38387, 9619, 500, 30592, 30504, 42377, 14571, 4790, 11114, 769, 10394, 611, 1, 4397, 12, 71, 117, 1234, 81, 5, 852, 1116, 1109, 1, 3, 1, 2970 }; const int n = 91; /** 優先隊列 */ priority_queue<HTNode> pq; /** 哈弗曼編碼映射 */ map<string, char> dcode; map<char, string> ecode; /** 根節點以及總權重+邊長 */ HTNode *root; int sum = 0; /** 初始化葉節點，並加入到優先隊列中 */ void Init() { for(int i = 0; i < n; i++) { HTNode p(ch[i], fnum[i]); pq.push(p); } } /** 建立哈夫曼樹 */ void CreateHT() { HTNode *lmin, *rmin; /** 當隊列中不止一個元素時 */ while(!pq.empty() && 1 != pq.size()) { /** 取隊首兩個元素（權值最小） */ lmin = new HTNode(pq.top()); pq.pop(); rmin = new HTNode(pq.top()); pq.pop(); /** 合並元素重新入隊 */ HTNode p(0, lmin->w + rmin->w, lmin, rmin); pq.push(p); } if(!pq.empty()) { /** 根節點 */ root = new HTNode(pq.top()); pq.pop(); } } /** 創建哈夫曼編碼 */ void CreateHTCode(HTNode *p, string str) { if(!p) return; if(0 != p->data) { /** 若是葉節點，則記錄此節點的編碼值 */ dcode[str] = p->data; ecode[p->data] = str; sum += (str.length() * p->w); return; } CreateHTCode(p->lc, str + "0"); CreateHTCode(p->rc, str + "1"); } /** 顯示哈夫曼編碼 */ void DispCode() { printf("輸出哈弗曼編碼：\n"); for(int i = 0; i < n; i++) { printf("\t'%c':\t%s\n", ch[i], ecode[ch[i]].c_str()); } printf("平均長度：%.5lf\n", double(sum) / double(root->w)); } /** 釋放哈夫曼樹 */ void Release(HTNode *p) { if(!p) return; Release(p->lc); Release(p->rc); delete p; } /** 輸出壓縮文 */ void putEncode(FILE *fp, char *buf) { unsigned char code = 0; for(int i = 0; i < 8; i++) code = (code << 1) + (buf[i] - '0'); fwrite(&code, sizeof(unsigned char), 1, fp); } /** 判斷是否在字元串內 */ bool instr(char c, const char str[]) { for(int i = 0; i < strlen(str); i++) if(c == str[i]) return true; return false; } /** 壓縮文件 */ void Encode() { FILE *OF; FILE *IF; char ifn[255]; const char ofn[] = "Encode.txt"; char buf[9]; int cnt = 0, newcnt = 0; printf("Input the filename: "); scanf("%s", ifn); IF = fopen(ifn, "rb"); if(!IF) { printf("Wrong file.\n"); return; } OF = fopen(ofn, "wb+"); if(!OF) { printf("Wrong file.\n"); } /** 開始讀文件 */ memset(buf, 0, sizeof(buf)); while(!feof(IF)) { unsigned char c; fread(&c, sizeof(unsigned char), 1, IF); if(instr(c, ch)); else c = ' '; for(int i = 0; i < ecode[c].length(); i++) { buf[strlen(buf)] = ecode[c][i]; if(8 == strlen(buf)) { newcnt++; putEncode(OF, buf); memset(buf, 0, sizeof(buf)); } } cnt++; } cnt--; if(0 != strlen(buf)) { for(int i = strlen(buf); i < 8; i++) buf[i] = '0'; putEncode(OF, buf); } fwrite(&cnt, 4, 1, OF); fclose(IF); fclose(OF); printf("壓縮成功！壓縮率：%.2f%c\n", (((double)newcnt + 4.0f) / (double)cnt) * 100, '%'); } /** 補0 */ void putZeros(char *buf) { char tmpbuf[9]; memset(tmpbuf, 0, sizeof(tmpbuf)); if(8 != strlen(buf)) { for(int i = 0; i < 8 - strlen(buf); i++) tmpbuf[i] = '0'; strcat(tmpbuf, buf); strcpy(buf, tmpbuf); } } /** 解壓縮 */ void Decode() { char buf[256]; char oldbuf[9]; const char ifn[] = "Encode.txt"; const char ofn[] = "Decode.txt"; FILE *IF = fopen(ifn, "rb"); if(!IF) { printf("Wrong file.\n"); return; } FILE *OF = fopen(ofn, "wb+"); if(!OF) { printf("Wrong file.\n"); return; } int tot, cnt = 0; fseek(IF, -4L, SEEK_END); fread(&tot, 4, 1, IF); fseek(IF, 0L, SEEK_SET); memset(buf, 0, sizeof(buf)); while(true) { if(cnt == tot) break; unsigned char c; fread(&c, sizeof(unsigned char), 1, IF); itoa(c, oldbuf, 2); putZeros(oldbuf); for(int i = 0; i < 8; i++) { if(cnt == tot) break; buf[strlen(buf)] = oldbuf[i]; if(dcode.end() != dcode.find(string(buf))) { fwrite(&dcode[string(buf)], sizeof(char), 1, OF); memset(buf, 0, sizeof(buf)); cnt++; } } } fclose(IF); fclose(OF); printf("解壓成功！文件名Decode.txt。\n"); } int main() { Init(); CreateHT(); CreateHTCode(root, ""); DispCode(); Encode(); Decode(); Release(root); system("pause"); return 0; }
⑶ 有關哈夫曼編碼壓縮與解壓縮的問題.
壓縮代碼非常簡單，首先用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;
}
過程
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<math.h>
#define M 10
typedef struct Fano_Node
{
char ch;
float weight;
}FanoNode[M];
typedef struct node
{
int start;
int end;
struct node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
void EnterQueue(LinkQueue *q,int s,int e)
{
LinkQueueNode *NewNode;
NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(NewNode!=NULL)
{
NewNode->start=s;
NewNode->end=e;
NewNode->next=NULL;
q->rear->next=NewNode;
q->rear=NewNode;
}
else printf("Error!");
}
//***按權分組***//
void Divide(FanoNode f,int s,int *m,int e)
{
int i;
float sum,sum1;
sum=0;
for(i=s;i<=e;i++)
sum+=f.weight;
*m=s;
sum1=0;
for(i=s;i<e;i++)
{
sum1+=f.weight;
*m=fabs(sum-2*sum1)>fabs(sum-2*sum1-2*f.weight)?(i+1):*m;
if(*m==i)
break;
}
}
main()
{
int i,j,n,max,m,h[M];
int sta,mid,end;
float w;
char c,fc[M][M];
FanoNode FN;
LinkQueueNode *p;
LinkQueue *Q;
//***初始化隊Q***//
Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
Q->rear=Q->front;
Q->front->next=NULL;
printf("\t***FanoCoding***\n");
printf("Please input the number of node:"); /*輸入信息*/
scanf("%d",&n);
i=1;
while(i<=n)
{
printf("%d weight and node:",i);
scanf("%f %c",&FN.weight,&FN.ch);
for(j=1;j<i;j++)
{
if(FN.ch==FN[j].ch)
{
printf("Same node!!!\n");
break;
}
}
if(i==j)
i++;
}
for(i=1;i<=n;i++) /*排序*/
{
max=i+1;
for(j=max;j<=n;j++)
max=FN[max].weight<FN[j].weight?j:max;
if(FN.weight<FN[max].weight)
{
w=FN.weight;
FN.weight=FN[max].weight;
FN[max].weight=w;
c=FN.ch;
FN.ch=FN[max].ch;
FN[max].ch=c;
}
}
for(i=1;i<=n;i++) /*初始化h*/
h=0;
EnterQueue(Q,1,n); /*1和n進隊*/
while(Q->front->next!=NULL)
{
p=Q->front->next; /*出隊*/
Q->front->next=p->next;
if(p==Q->rear)
Q->rear=Q->front;
sta=p->start;
end=p->end;
free(p);
Divide(FN,sta,&m,end); /*按權分組*/
for(i=sta;i<=m;i++)
{
fc[h]='0';
h++;
}
if(sta!=m)
EnterQueue(Q,sta,m);
else
fc[sta][h[sta]]='\0';
for(i=m+1;i<=end;i++)
{
fc[h]='1';
h++;
}
if(m==sta&&(m+1)==end) //如果分組後首元素的下標與中間元素的相等，
{ //並且和最後元素的下標相差為1，則編碼碼字字元串結束
fc[m][h[m]]='\0';
fc[end][h[end]]='\0';
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i<=n;i++) /*列印編碼信息*/
{
printf("%c:",FN.ch);
printf("%s\n",fc);
}
system("pause");
}
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];
typedef struct
{
char weight;
int parent;
int LChild;
int RChild;
}HTNode,Huffman[M+1];
typedef struct Node
{
int weight; /*葉子結點的權值*/
char c; /*葉子結點*/
int num; /*葉子結點的二進制碼的長度*/
}WNode,WeightNode[N];
/***產生葉子結點的字元和權值***/
void CreateWeight(char ch[],int *s,WeightNode *CW,int *p)
{
int i,j,k;
int tag;
*p=0;
for(i=0;ch!='\0';i++)
{
tag=1;
for(j=0;j<i;j++)
if(ch[j]==ch)
{
tag=0;
break;
}
if(tag)
{
(*CW)[++*p].c=ch;
(*CW)[*p].weight=1;
for(k=i+1;ch[k]!='\0';k++)
if(ch==ch[k])
(*CW)[*p].weight++;
}
}
*s=i;
}
/********創建HuffmanTree********/
void CreateHuffmanTree(Huffman *ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
for(i=1;i<=n;i++)
{
(*ht).weight =w.weight;
(*ht).parent=0;
(*ht).LChild=0;
(*ht).RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
(*ht).weight=0;
(*ht).parent=0;
(*ht).LChild=0;
(*ht).parent=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!(*ht)[j].parent)
break;
s1=j; /*找到第一個雙親不為零的結點*/
for(;j<=i-1;j++)
if(!(*ht)[j].parent)
s1=(*ht)[s1].weight>(*ht)[j].weight?j:s1;
(*ht)[s1].parent=i;
(*ht).LChild=s1;
for(j=1;j<=i-1;j++)
if(!(*ht)[j].parent)
break;
s2=j; /*找到第一個雙親不為零的結點*/
for(;j<=i-1;j++)
if(!(*ht)[j].parent)
s2=(*ht)[s2].weight>(*ht)[j].weight?j:s2;
(*ht)[s2].parent=i;
(*ht).RChild=s2;
(*ht).weight=(*ht)[s1].weight+(*ht)[s2].weight;
}
}
/***********葉子結點的編碼***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode *h,WeightNode *weight,int m,int n)
{
int i,j,k,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
c=i;
p=ht.parent;
while(p)
{
start--;
if(ht[p].LChild==c)
cd[start]='0';
else
cd[start]='1';
c=p;
p=ht[p].parent;
}
(*weight).num=n-start;
(*h)=(char *)malloc((n-start)*sizeof(char));
p=-1;
strcpy((*h),&cd[start]);
}
system("pause");
}
/*********所有字元的編碼*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode *hc,WeightNode weight,int n,int m)
{
int i,j,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*從(*weight)[k].c中查找與ch相等的下標K*/
if(ch==weight[k].c)
break;
(*hc)=(char *)malloc((weight[k].num+1)*sizeof(char));
for(j=0;j<=weight[k].num;j++)
(*hc)[j]=h[k][j];
}
}
/*****解碼*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf("***StringInformation***\n");
while(i<m)
{
p=2*n-1;
for(j=0;hc[j]!='\0';j++)
{
if(hc[j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf("%c",w[p].c); /*列印原信息*/
i++;
}
}
main()
{
int i,n,m,s1,s2,j; /*n為葉子結點的個數*/
char ch[N],w[N]; /*ch[N]存放輸入的字元串*/
Huffman ht; /*二叉數 */
HuffmanCode h,hc; /* h存放葉子結點的編碼，hc 存放所有結點的編碼*/
WeightNode weight; /*存放葉子結點的信息*/
printf("\t***HuffmanCoding***\n");
printf("please input information :");
gets(ch); /*輸入字元串*/
CreateWeight(ch,&m,&weight,&n); /*產生葉子結點信息，m為字元串ch[]的長度*/
printf("***WeightInformation***\n Node "); /*輸出葉子結點的字元與權值*/
for(i=1;i<=n;i++)
printf("%c ",weight.c);
printf("\nWeight ");
for(i=1;i<=n;i++)
printf("%d ",weight.weight);
CreateHuffmanTree(&ht,weight,n); /*產生Huffman樹*/
printf("\n***HuffamnTreeInformation***\n");
for(i=1;i<=2*n-1;i++) /*列印Huffman樹的信息*/
printf("\t%d %d %d %d\n",i,ht.weight,ht.parent,ht.LChild,ht.RChild);
CrtHuffmanNodeCode(ht,ch,&h,&weight,m,n); /*葉子結點的編碼*/
printf(" ***NodeCode***\n"); /*列印葉子結點的編碼*/
for(i=1;i<=n;i++)
{
printf("\t%c:",weight.c);
printf("%s\n",h);
}
CrtHuffmanCode(ch,h,&hc,weight,n,m); /*所有字元的編碼*/
printf("***StringCode***\n"); /*列印字元串的編碼*/
for(i=0;i<m;i++)
printf("%s",hc);
system("pause");
TrsHuffmanTree(ht,weight,hc,n,m); /*解碼*/
system("pause");
}
⑷ 基於哈夫曼樹的文件壓縮/解壓程序 源代碼
哈夫曼的C++演算法
#define INT_MAX 10000
#define ENCODING_LENGTH 1000
#include "stdio.h"
#include "string.h"
#include "malloc.h"
typedef enum{none,left_child,right_child} Which;//標記是左孩子還是右孩子
typedef char Elemtype;
typedef struct TNode{
Elemtype letter;
int weight;
int parent;
Which sigh;
char *code;
}HTNode,*HuffmanTree;
int n;
char coding[50];//儲存代碼
char str[ENCODING_LENGTH];//保存要翻譯的句子
void InitTreeNode(HuffmanTree &HT)
{//初始前N個結點,後M-N個結點置空
int i;int w;char c;
int m=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((m)*sizeof(HTNode));
printf("input %d database letter and weight",n);
p=HT;
getchar();
for (i=1;i<=n;i++){
scanf("%c%d",&c,&w);
p->code='\0';
p->letter=c;
p->parent=0;
p->sigh=none;
p->weight=w;
p++;
getchar();
}
for (;i<=m;i++,p++){
p->code='\0';
p->letter=' ';
p->parent=0;
p->sigh=none;
p->weight=0;
}
}//INITTREENODE
void Select(HuffmanTree HT,int end,int *s1,int *s2)
{//在0~END之間,找出最小和次小的兩個結點序號,返回S1,S2
int i;
int min1=INT_MAX;
int min2;
for (i=0;i<=end;i++){//找最小的結點序號
if (HT[i].parent==0&&HT[i].weight<min1){
*s1=i;
min1=HT[i].weight;
}
}
min2=INT_MAX;
for(i=0;i<=end;i++){//找次小結點的序號
if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){
*s2=i;
min2=HT[i].weight;
}
}
}
void HuffmanTreeCreat(HuffmanTree &HT)
{//建立HUFFMAN樹
int i;int m=2*n-1;
int s1,s2;
for(i=n;i<m;i++){
Select(HT,i-1,&s1,&s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[s1].sigh=left_child;
HT[s2].sigh=right_child;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
void HuffmanTreeCode(HuffmanTree HT)
{//HUFFMAN解碼
int i;
char *temp;
temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
int p;int s;
for (i=0;i<n;i++){
p=i;
s=n-1;
while (HT[p].parent!=0){//從結點回溯,左孩子為0,右孩子為1
if (HT[p].sigh==left_child)
temp[--s]='0';
else if (HT[p].sigh==right_child)
temp[--s]='1';
p=HT[p].parent;
}
HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配結點碼長度的內存空間
strcpy(HT[i].code,temp+s);
printf("%s\n",HT[i].code);
}
}
void GetCodingSen(char *sencence)
{//輸入要編碼的句子
int l;
gets(sencence);
l=strlen(sencence);
sencence[l]='\0';
}
void HuffmanTreeEncoding(char sen[],HuffmanTree HT)
{//將句子進行編碼
int i=0;int j;
while(sen[i]!='\0'){
for(j=0;j<n;j++){
if (HT[j].letter==sen[i]) //字母吻合則用代碼取代
{strcat(coding,HT[j].code);
break;
}
}
i++;
if (sen[i]==32) i++;
}
printf("\n%s",coding);
}
void HuffmanTreeDecoding(HuffmanTree HT,char code[])
{//HUFFMAN解碼過程,將代碼翻譯為句子
char sen[100];
char temp[50];
char voidstr[]=" ";
int i;int j;
int t=0;int s=0;
for(i=0;i<strlen(code);i++){
temp[t++]=code[i];
for(j=0;j<n;j++){
if (strcmp(HT[j].code,temp)==0){//代碼段吻合
sen[s]=HT[j].letter;s++;
strcpy(temp,voidstr);//將TEMP置空
t=0;
break;
}
}
}
printf("\n%s",sen);
}
void main()
{
HTNode hnode;
HuffmanTree huff;
huff=&hnode;
printf("input the letter for coding number\n");
scanf("%d",&n);
InitTreeNode(huff);
HuffmanTreeCreat(huff);
HuffmanTreeCode(huff);
GetCodingSen(str);
HuffmanTreeEncoding(str,huff);
HuffmanTreeDecoding(huff,coding);
}
⑸ 利用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==================
祝你好運！
⑹ 哈夫曼樹怎麼壓縮和解壓 c++
http://blog.csdn.net/leex_brave/article/details/51598359
⑺ 用huffman演算法實現「文件的壓縮與解壓」怎麼做啊
我寫過一個Huffman編碼，但只是生成了編碼表，沒做成壓縮，但可以利用查表做成文件壓縮，另外用的是C++，改成C的話比較容易，只要把動下內存分配就行了，想要的話,msn:[email protected]
⑻ 用哈夫曼樹演算法設計對文件文件的壓縮和解壓縮的實驗程序解析
樓主可以去看看最優二叉樹的編碼問題。
1、哈夫曼編碼
在數據通信中，需要將傳送的文字轉換成二進制的字元串，用0，1碼的不同排列來表示字元。例如，需傳送的報文為「AFTER DATA EAR ARE ART AREA」，這里用到的字元集為「A，E，R，T，F，D」，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要區別6個字母，最簡單的二進制編碼方式是等長編碼，固定採用3位二進制，可分別用000、001、010、011、100、101對「A，E，R，T，F，D」進行編碼發送，當對方接收報文時再按照三位一分進行解碼。顯然編碼的長度取決報文中不同字元的個數。若報文中可能出現26個不同字元，則固定編碼長度為5。然而，傳送報文時總是希望總長度盡可能短。在實際應用中，各個字元的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高於X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以優化整個報文編碼。
為使不等長編碼為前綴編碼，可用字元集中的每個字元作為葉子結點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可將每個字元的出現頻率作為字元結點的權值賦予該結點上，求出此樹的最小帶權路徑長度就等於求出了傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字元集中的所有字元作為葉子結點，由字元出現頻率作為其權值所產生的哈夫曼樹的問題。利用哈夫曼樹來設計二進制的前綴編碼，既滿足前綴編碼的條件，又保證報文編碼總長最短。
哈夫曼靜態編碼：它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字元出現的頻率，利用得到的頻率值創建哈夫曼樹，並必須把樹的信息保存起來，即把字元0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大文件中字元出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，並把編碼後得到的碼字存儲起來。
哈夫曼動態編碼：動態哈夫曼編碼使用一棵動態變化的哈夫曼樹，對第t+1個字元的編碼是根據原始數據中前t個字元得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字元，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字元所需的時間與該字元的編碼長度成正比，所以動態哈夫曼編碼可實時進行。[3]
2、哈夫曼解碼
在通信中，若將字元用哈夫曼編碼形式發送出去，對方接收到編碼後，將編碼還原成字元的過程，稱為哈夫曼解碼。[4]
⑼ 一、實驗題目：用哈夫曼編碼實現文件壓縮用C++實現 急用
這是我的實驗報告：http://student.csdn.net/space.php?uid=395622&do=blog&id=51206/**
* @brief 哈夫曼編碼
* @date 2010-11-30
*/
#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;
/**
* @brief 哈弗曼結點
* 記錄了哈弗曼樹結點的數據、權重及左右兒子
*/
struct HTNode {
char data;
HTNode *lc, *rc;
int w;
/** 節點構造函數 */
HTNode(char _d, int _w, HTNode *_l = NULL, HTNode *_r = NULL)
{
data = _d;
w = _w;
lc = _l;
rc = _r;
}
/** 節點拷貝構造函數 */
HTNode(const HTNode &h)
{
data = h.data;
lc = h.lc;
rc = h.rc;
w = h.w;
}
/** 用於優先隊列比較的運算符重載 */
friend bool operator < (const HTNode &a, const HTNode &b)
{
return a.w > b.w;
}
};
/** 哈弗曼樹葉子節點數、各葉子結點數據及權重 */
/** 權值從Lolita小說中抽樣取出 */
const char ch[] = {
10, 32, 33, 37, 40, 41, 44, 45, 46, 48,
49, 50, 51, 52, 53, 54, 55, 56, 57, 58,
59, 63, 65, 66, 67, 68, 69, 70, 71, 72,
73, 74, 75, 76, 77, 78, 79, 80, 81, 82,
83, 84, 85, 86, 87, 88, 89, 90, 91, 93,
97, 98, 99, 100, 101, 102, 103, 104, 105, 106,
107, 108, 109, 110, 111, 112, 113, 114, 115, 116,
117, 118, 119, 120, 121, 122, 123, 161, 164, 166,
168, 170, 173, 174, 175, 176, 177, 180, 186, 255,
'\r', '\0'
};
const int fnum[] = {
2970, 99537, 265, 1, 496, 494, 9032, 1185, 5064, 108,
180, 132, 99, 105, 82, 64, 62, 77, 126, 296,
556, 548, 818, 443, 543, 435, 225, 271, 260, 797,
3487, 158, 50, 1053, 589, 498, 332, 316, 61, 276,
724, 855, 54, 293, 543, 11, 185, 11, 25, 26,
42416, 7856, 12699, 23670, 61127, 10229, 10651, 27912, 32809, 510,
4475, 23812, 13993, 34096, 38387, 9619, 500, 30592, 30504, 42377,
14571, 4790, 11114, 769, 10394, 611, 1, 4397, 12, 71,
117, 1234, 81, 5, 852, 1116, 1109, 1, 3, 1,
2970
};
const int n = 91;
/** 優先隊列 */
priority_queue<HTNode> pq;
/** 哈弗曼編碼映射 */
map<string, char> dcode;
map<char, string> ecode;
/** 根節點以及總權重+邊長 */
HTNode *root;
int sum = 0;
/** 初始化葉節點，並加入到優先隊列中 */
void Init()
{
for(int i = 0; i < n; i++)
{
HTNode p(ch[i], fnum[i]);
pq.push(p);
}
}
/** 建立哈夫曼樹 */
void CreateHT()
{
HTNode *lmin, *rmin;
/** 當隊列中不止一個元素時 */
while(!pq.empty() && 1 != pq.size())
{
/** 取隊首兩個元素（權值最小） */
lmin = new HTNode(pq.top());
pq.pop();
rmin = new HTNode(pq.top());
pq.pop();
/** 合並元素重新入隊 */
HTNode p(0, lmin->w + rmin->w, lmin, rmin);
pq.push(p);
}
if(!pq.empty())
{
/** 根節點 */
root = new HTNode(pq.top());
pq.pop();
}
}
/** 創建哈夫曼編碼 */
void CreateHTCode(HTNode *p, string str)
{
if(!p) return;
if(0 != p->data)
{
/** 若是葉節點，則記錄此節點的編碼值 */
dcode[str] = p->data;
ecode[p->data] = str;
sum += (str.length() * p->w);
return;
}
CreateHTCode(p->lc, str + "0");
CreateHTCode(p->rc, str + "1");
}
/** 顯示哈夫曼編碼 */
void DispCode()
{
printf("輸出哈弗曼編碼：\n");
for(int i = 0; i < n; i++)
{
printf("\t'%c':\t%s\n", ch[i], ecode[ch[i]].c_str());
}
printf("平均長度：%.5lf\n", double(sum) / double(root->w));
}
/** 釋放哈夫曼樹 */
void Release(HTNode *p)
{
if(!p) return;
Release(p->lc);
Release(p->rc);
delete p;
}
/** 輸出壓縮文 */
void putEncode(FILE *fp, char *buf)
{
unsigned char code = 0;
for(int i = 0; i < 8; i++)
code = (code << 1) + (buf[i] - '0');
fwrite(&code, sizeof(unsigned char), 1, fp);
}
/** 判斷是否在字元串內 */
bool instr(char c, const char str[])
{
for(int i = 0; i < strlen(str); i++)
if(c == str[i]) return true;
return false;
}
/** 壓縮文件 */
void Encode()
{
FILE *OF;
FILE *IF;
char ifn[255];
const char ofn[] = "Encode.txt";
char buf[9];
int cnt = 0, newcnt = 0;
printf("Input the filename: ");
scanf("%s", ifn);
IF = fopen(ifn, "rb");
if(!IF)
{
printf("Wrong file.\n");
return;
}
OF = fopen(ofn, "wb+");
if(!OF)
{
printf("Wrong file.\n");
}
/** 開始讀文件 */
memset(buf, 0, sizeof(buf));
while(!feof(IF))
{
unsigned char c;
fread(&c, sizeof(unsigned char), 1, IF);
if(instr(c, ch));
else c = ' ';
for(int i = 0; i < ecode[c].length(); i++)
{
buf[strlen(buf)] = ecode[c][i];
if(8 == strlen(buf))
{
newcnt++;
putEncode(OF, buf);
memset(buf, 0, sizeof(buf));
}
}
cnt++;
}
cnt--;
if(0 != strlen(buf))
{
for(int i = strlen(buf); i < 8; i++) buf[i] = '0';
putEncode(OF, buf);
}
fwrite(&cnt, 4, 1, OF);
fclose(IF);
fclose(OF);
printf("壓縮成功！壓縮率：%.2f%c\n", (((double)newcnt + 4.0f) / (double)cnt) * 100, '%');
}
/** 補0 */
void putZeros(char *buf)
{
char tmpbuf[9];
memset(tmpbuf, 0, sizeof(tmpbuf));
if(8 != strlen(buf))
{
for(int i = 0; i < 8 - strlen(buf); i++) tmpbuf[i] = '0';
strcat(tmpbuf, buf);
strcpy(buf, tmpbuf);
}
}
/** 解壓縮 */
void Decode()
{
char buf[256];
char oldbuf[9];
const char ifn[] = "Encode.txt";
const char ofn[] = "Decode.txt";
FILE *IF = fopen(ifn, "rb");
if(!IF)
{
printf("Wrong file.\n");
return;
}
FILE *OF = fopen(ofn, "wb+");
if(!OF)
{
printf("Wrong file.\n");
return;
}
int tot, cnt = 0;
fseek(IF, -4L, SEEK_END);
fread(&tot, 4, 1, IF);
fseek(IF, 0L, SEEK_SET);
memset(buf, 0, sizeof(buf));
while(true)
{
if(cnt == tot) break;
unsigned char c;
fread(&c, sizeof(unsigned char), 1, IF);
itoa(c, oldbuf, 2);
putZeros(oldbuf);
for(int i = 0; i < 8; i++)
{
if(cnt == tot) break;
buf[strlen(buf)] = oldbuf[i];
if(dcode.end() != dcode.find(string(buf)))
{
fwrite(&dcode[string(buf)], sizeof(char), 1, OF);
memset(buf, 0, sizeof(buf));
cnt++;
}
}
}
fclose(IF);
fclose(OF);
printf("解壓成功！文件名Decode.txt。\n");
}
int main()
{
Init();
CreateHT();
CreateHTCode(root, "");
DispCode();
Encode();
Decode();
Release(root);
system("pause");
return 0;
}