哈弗曼壓縮
❶ 霍夫曼 解壓縮
哈夫曼編碼(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;
}
❷ 哈夫曼實現壓縮
我的作業，哈弗曼樹的建立，不過那個字元的頻率要自己編的。
//main.cpp
#include"HuffmanTree.h"
#include<string.h>
#include<stdlib.h>
//#include<iostream>
//using namespace std;
int main(){
HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n\n**********************歡迎使用哈夫曼編碼/解碼系統**********************\n"<<endl<<endl;
cout<<" 您可以進行以下操作:\n";
cout<<" 1 建立哈夫曼樹\n";
cout<<" 2 編碼(源文已在文件ToBeTran中，或鍵盤輸入)\n";
cout<<" 3 解碼(碼文已在文件CodeFile中)\n";
cout<<" 4 顯示碼文\n";
cout<<" 5 顯示哈夫曼樹\n";
cout<<" 6 退出\n\n";
cout<<" 請選擇一個操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感謝使用本系統!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main
//Huffmannode.h
#ifndef _HuffmanNode_
#define _HuffmanNode_
struct HuffmanNode
{
int weight; //存放結點的權值，假設只考慮處理權值為整數的情況
int parent; //-1表示為根結點，否則表示為非根結點
int lchild,rchild; //分別存放該結點的左右孩子的所在單元的編號
};
#endif
//huffmantree.h
#ifndef _HuffmanTree_
#define _HuffmanTree_
#include"HuffmanNode.h"
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
class HuffmanTree //哈夫曼樹
{
public:
struct HuffmanNode *Node; //Node[]存放哈夫曼樹
char *Info; //Info[]存放源文用到的字元——源碼，如'a','b','c','d','e'，此內容可以放入結點中，不單獨設數組存放
int LeafNum; //哈夫曼樹的葉子個數，也是源碼個數
public:
HuffmanTree();
~HuffmanTree();
void CreateHuffmanTree(); /*在內存中建立哈夫曼樹，存放在Node[]中。 讓用戶從兩種建立哈夫曼樹的方法中選擇：
1.從鍵盤讀入源碼字元集個數，每個字元，和每個字元的權重，建立哈夫曼樹，
並將哈夫曼樹寫入文件hfmTree中。2.從文件hfmTree中讀入哈夫曼樹信息，建立哈夫曼樹*/
void CreateHuffmanTreeFromKeyboard();
void CreateHuffmanTreeFromFile();
void Encoder(); /*使用建立好的哈夫曼樹（如果不在內存，則從文件hfmTree中讀入並建立內存里的哈夫曼樹），
對文件ToBeTran中的正文進行編碼，並將碼文寫入文件CodeFile中。
ToBeTran的內容可以用記事本等程序編輯產生。*/
void Decoder(); /*待解碼的碼文存放在文件CodeFile中，使用建立好的哈夫曼樹（如果不在內存，
則從文件hfmTree中讀入並建立內存里的哈夫曼樹）將碼文解碼，
得到的源文寫入文件TextFile中，並同時輸出到屏幕上。*/
void PrintCodeFile(); /*將碼文文件CodeFile顯示在屏幕上*/
void PrintHuffmanTree(); /*將哈夫曼樹以直觀的形式（凹入表示法，或廣義表，或其他樹形表示法）顯示在屏幕上，
同時寫入文件TreePrintFile中*/
void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法顯示哈夫曼樹，由PrintHuffmanTree()調用*/
};
#endif
//huffmantree.cpp
#include"HuffmanTree.h"
#include<string>
#include<limits> //為使用整型最大值
//#include<iostream>
using namespace std;
//******************************************************
HuffmanTree::HuffmanTree()
{
LeafNum=0;
Node=NULL;
Info+NULL;
}
//******************************************************
HuffmanTree::~HuffmanTree()
{
delete []Node;
Node=NULL;
delete []Info;
Info=NULL;
}
//******************************************************
void HuffmanTree::CreateHuffmanTree()
{
char Choose;
cout<<"你要從文件中讀入哈夫曼樹(按1)，還是從鍵盤輸入哈夫曼樹(按2)？";
cin>>Choose;
if(Choose=='2') {//鍵盤輸入建立哈夫曼樹
CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
CreateHuffmanTreeFromFile();
}
}
//******************************************************
void HuffmanTree::CreateHuffmanTreeFromKeyboard()
{
int Num;
int i,j,pos1,pos2,max1,max2;
cout<<"\n請輸入源碼字元集個數：";
cin>>Num;
if (Num<=1)
{
cout<<"無法建立少於2個葉子結點的哈夫曼樹。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
Info=new char[2*Num-1];
for( i=0;i<Num;i++) {//讀入哈夫曼樹的葉子結點信息
cout<<"請輸入第"<<i+1<<"個字元值";
getchar();
Info[i]=getchar(); //源文的字元存入字元數組Info[]
getchar();
cout<<"請輸入該字元的權值或頻度";
cin>>Node[i].weight; //源文的字元權重存入Node[].weight
Node[i].parent=-1; //為根結點
Node[i].lchild=-1; //無左孩子
Node[i].rchild=-1; //無右孩子
}
for( i=Num;i<2*Num-1;i++) //循環建立哈夫曼樹內部結點 表示需做Num-1次合並
{
pos1=-1;pos2=-1; //分別用來存放當前最小值和次小值的所在單元編號
max1=32767; max2=32767; //32767為整形數的最大值 分別用來存放當前找到的最小值和次小值
for(j=0;j<i;j++) //在根結點中選出權值最小的兩個
{
if(Node[j].parent==-1) //是否為根結點
if(Node[j].weight<max1) //是否比最小值要小
{
max2=max1; //原最小值變為次小值
max1=Node[j].weight; //存放最小值
pos2=pos1; //修改次小值所在的單元編號
pos1=j; //修改最小值所在的單元編號
}
else
if(Node[j].weight<max2) //比原最小值大但比原此小值小
{
max2=Node[j].weight;
pos2=j;
}
}
Node[pos1].parent=i;
Node[pos2].parent=i;
Node[i].lchild=pos1;
Node[i].rchild=pos2;
Node[i].parent=-1;
Node[i].weight=Node[pos1].weight+Node[pos2].weight;
} //for
LeafNum=Num;
cout<<"哈夫曼樹已成功構造完成。\n";
//把建立好的哈夫曼樹寫入文件hfmTree.dat
char ch;
cout<<"是否要替換原來的哈夫曼樹文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打開文件
if(fop.fail()) {
cout<<"\n哈夫曼樹文件打開失敗，無法將哈夫曼樹寫入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先寫入哈夫曼樹的葉子結點個數
for( i=0;i<Num;i++) { //再寫入源文字元集的所有字元（存儲在Info[]中）
fop.write((char*)&Info[i],sizeof(Info[i]));
flush(cout);
}
for( i=0;i<2*Num-1;i++) { //最後寫入哈夫曼樹的各個結點（存儲在Node[]中）
fop.write((char*)&Node[i],sizeof(Node[i]));
flush(cout);
}
fop.close(); //關閉文件
cout<<"\n哈夫曼樹已成功寫入hfmTree.dat文件。\n";
}
//******************************************************
void HuffmanTree::CreateHuffmanTreeFromFile()
{
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼樹文件hfmTree.dat打開失敗，無法建立哈夫曼樹。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼樹文件中的數據有誤，葉子結點個數少於2個，無法建立哈夫曼樹。\n";
fip.close();
return;
}
Info=new char[LeafNum];
Node=new HuffmanNode[2*LeafNum-1];
for( int i=0;i<LeafNum;i++)
fip.read((char*)&Info[i],sizeof(Info[i]));
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼樹已成功構造完成。\n";
}
//******************************************************
void HuffmanTree::Encoder()
{
if(Node==NULL) //內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}//if
char *SourceText; //字元串數組，用於存放源文
//讓用戶選擇源文是從鍵盤輸入，還是從源文文件ToBeTran.txt中讀入
char Choose;
cout<<"你要從文件中讀入源文(按1)，還是從鍵盤輸入源文(按2)？";
cin>>Choose;
if(Choose=='1')
{
ifstream fip1("ToBeTran.txt");
if(fip1.fail())
{
cout<<"源文文件打開失敗!無法繼續執行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次讀文件只統計文件中有多少個字元，將字元數存入k
fip1.close();
SourceText=new char[k+1]; //申請存放源文的字元數組空間
ifstream fip2("ToBeTran.txt");//第二次讀源文文件，把內容寫入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
cout<<"需編碼的源文為：";
cout<<SourceText<<endl;
}
else { //從鍵盤輸入源文
string SourceBuff;
cin.ignore();
cout<<"請輸入需要編碼的源文(可輸入任意長，按回車鍵結束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}
ofstream fop("CodeFile.dat",ios::trunc); //打開碼文存放文件
char *code;
code=new char[LeafNum]; //存放一個源文字元的編碼
int k=0;
int i,j,start;
while(SourceText[k]!='\0') //源文串中從第一個字元開始逐個編碼
{
start=0;
for(i=0;i<LeafNum;i++)
if(Info[i]==SourceText[k]) //求出該文字所在單元的編號
break;
j=i;
while(Node[j].parent!=-1) //結點j非根
{
j=Node[j].parent; //求結點j的雙親結點
if(Node[j].lchild==i) //是左子樹，則生成代碼0
code[start++]='0';
else
code[start++]='1'; //是右子樹，則生成代碼1
i=j;
}
code[start]='\0'; //置串結束符
for(i=0;i<start/2;i++)
{
j=code[i];
code[i]=code[start-1-i];
code[start-1-i]=j;
}
i=0; //將源文的當前字元的對應編碼寫入碼文文件
while(code[i]!='\0')
{
fop<<code[i];
i++;
}
k++; //源文串中的字元後移一個
}
fop.close();
cout<<"已完成編碼，碼文已寫入文件CodeFile.dat中。\n\n";
}
//******************************************************
void HuffmanTree::Decoder()
{
//如果內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}
//將碼文從文件CodeFile.dat中讀入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail())
{
cout<<"沒有碼文，無法解碼。\n";
return;
}
char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch))
{
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';
cout<<"經解碼得到的源文為：";
ofstream fop("TextFile.dat");
int j=(LeafNum-1)*2; //j指向哈夫曼樹的根
int i=0; //碼文從第一個符號開始，順著哈夫曼樹由根下行，按碼文的當前符號決定下行到左孩子還是右孩子
while(CodeStr[i]!='\0') //下行到哈夫曼樹的葉子結點處，則譯出葉子結點對應的源文字元
{
if(CodeStr[i]=='0')
j=Node[j].lchild; //往左走
else
j=Node[j].rchild; //往右走
if(Node[j].rchild==-1) //到達葉子結點
{
cout<<Info[j]; //輸出葉子結點對應的字元
j=LeafNum*2-1-1; //表示重新從根結點開始往下搜索
}
i++;
}
fop.close();
cout<<"\n解碼成功且已存到文件TextFile.dat中。\n\n";
}
//******************************************************
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"沒有碼文文件，無法顯示碼文文件內容。\n";
return;
}
while(fip.get(ch))
{
cout<<ch;
fop<<ch;
if(i==50)
{
cout<<endl;
fop<<endl;
i=0;
}
i++;
}
cout<<endl;
fop<<endl;
fip.close();
fop.close();
}
//******************************************************
void HuffmanTree::PrintHuffmanTree()
{
//如果內存沒有哈夫曼樹，則從哈夫曼樹文件hfmTree.dat中讀入信息並建立哈夫曼樹
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"內存無哈夫曼樹。操作撤銷。\n\n";
return;
}
}
ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
//******************************************************
void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer)//凹入表示法
{
if(Node[T].lchild!=-1)
PrintHuffmanTree_aoru(Node[T].lchild,layer+1);//左子樹
for(int i=1;i<=layer;i++)// 根
cout<<'\0'<<'\0'<<'\0';
cout<<Node[T].weight<<endl;
if(Node[T].rchild!=-1)
PrintHuffmanTree_aoru(Node[T].rchild,layer+1); // 右子樹
}
❸ 有關哈夫曼編碼壓縮與解壓縮的問題.
壓縮代碼非常簡單，首先用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");
}
❹ 如何用哈夫曼編碼實現英文文本的壓縮和解壓縮
哈夫曼壓縮是個無損的壓縮演算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度演算法一族。意思是個體符號（例如，文本文件中的字元）用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列
❺ 如何寫壓縮軟體，運用哈夫曼演算法實現
到文件壓縮大家很容易想到的就是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三個二進制位。
效果顯而易見。
❻ 利用哈夫曼編碼進行壓縮壓縮率一般達到多少
哈夫曼編碼進行壓縮的壓縮率是根據平均碼長來計算的，壓縮率比較低。
例如：用三位二進行數進行的等長編碼平均長度為3，而根據哈夫曼樹編碼的平均碼長為：
4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61
2.61/3=0.87=87%
其平均碼長是等長碼的87%，所以平均壓縮率為13%。
哈夫曼編碼，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。
Huffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。
壓縮率，描述壓縮文件的效果名，是文件壓縮後的大小與壓縮前的大小之比，例如：把100m的文件壓縮後是90m，壓縮率為90/100*100%=90%，壓縮率一般是越小越好，但是壓得越小，解壓時間越長。
(6)哈弗曼壓縮擴展閱讀
哈夫曼編碼的具體方法：先按出現的概率大小排隊，把兩個最小的概率相加，作為新的概率 和剩餘的概率重新排隊，再把最小的兩個概率相加，再重新排隊，直到最後變成1。
每次相 加時都將「0」和「1」賦與相加的兩個概率，讀出時由該符號開始一直走到最後的「1」， 將路線上所遇到的「0」和「1」按最低位到最高位的順序排好，就是該符號的哈夫曼編碼。