赫夫曼編碼及應用

一，目的

實作檔案中資料的加解密與壓縮。

二，描述

将硬碟上的一個文本檔案進行加密，比較加密檔案和原始檔案的大小差别；對加密檔案進行解密，比較原始檔案和

解碼檔案的内容是否一緻。

輸入和輸出：

（1）輸入：硬碟上給定的原始檔案及檔案路徑。

（2）輸出：硬碟上的加密檔案及檔案路徑；

​ 硬碟上的解碼檔案及檔案路徑；

​ 原始檔案和解碼檔案的比對結果。

提取原始檔案中的資料（包括中文、英文或其他字元），根據資料出現的頻率為權重，建構Huffman編碼表；根

據Huffman編碼表對原始檔案進行加密，得到加密檔案并儲存到硬碟上；将加密檔案進行解密，得到解碼檔案并

儲存點硬碟上；比對原始檔案和解碼檔案的一緻性，得出是否一緻的結論。

三，測試過程

1、方案

（一） 測試檔案：

（二）檔案路徑：

F:\\Dataclass\\test.txt（注意檔案路徑用兩個反斜杠）

（三）結果

壓縮檔案展示：

四，部分源碼

1. 主要資料類型與變量

   typedef struct
   {//哈夫曼樹存儲結構 
       unsigned int weight;
       unsigned int parent, lchild, rchild;
   }HTNode, *HuffmanTree;
   
   typedef struct
   {//存儲資料掃描統計結果 
   	char* data;
   	int* num;
   	int length;
   }TNode;
   
   //存儲哈夫曼編碼結果 
   typedef char * * HuffmanCode;
              

2. 函數子產品

   void ReadTxt(vector<char> &v)
   {//讀取檔案
   	char path[50];
   	char ch;
   	cout<<"請輸入加密檔案路徑：" <<endl;
   	cin>>path; 
   	
   	ifstream infile(path,ios::in);
   	if(!infile)
   	{
   		cerr<<"open error"<<endl;
   		exit(1);
   	}
   	while(infile.peek()!=EOF)
   	{
   		infile.get(ch);
   		v.push_back(ch); 
   	}	
   	infile.close();	
   }
   
   void InitList(TNode &T)
   {
   	T.data = new char[256];
   	T.num = new int[256];
   	if(!T.data||!T.num)
   		exit(1);
   	T.length=0;
   }
   
   int Find(TNode T,char ch)
   {
   	int i;
   	for(i=0;i<T.length;i++)
   		if(ch==T.data[i])
   			return true;
   		return false;	
   }
   
   void TCount(vector<char> v1,TNode &T)
   {
   	int i,j=0;
   	char ch;
   	int m=v1.size();
   	for(i=0;i<m;i++)
   	{
   		ch=v1[i];
   		if(!Find(T,ch))
   		{
   			T.data[j]=ch;
   			T.num[j]=count(v1.begin(),v1.end(),ch);
   			j++;
   			T.length++;
   		}		
   	}		
   }
   
   void Select(HuffmanTree HT, int n, int &s1, int &s2){
   	//選取最小的兩個權值 s1,s2 
   	s1 = s2 =0;
   	for(int i = 1; i <= n; i++){
   		if(HT[i].parent == 0){
   			if(s1 == 0){
   				s1 = i;
   			}
   			else if(s2 == 0){
   				s2 = i;
   			}
   			else if(HT[i].weight < HT[s1].weight || HT[i].weight < HT[s2].weight){
   				s1 = HT[s1].weight < HT[s2].weight ? s1 : s2;
   				s2 = i;
   			}
   		}
   	}
   }
   
   void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, TNode T) {
     // 構造哈夫曼樹HT，
     // 并求出n個字元的哈夫曼編碼HC
     int i, j, m, s1, s2, start;
     int n = T.length;
     char *cd;
     unsigned int c, f;
   
     if (n<=1) return;
     m = 2 * n - 1;
     HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));  // 0号單元未用
     for (i=1; i<=n; i++) { //初始化
       HT[i].weight=T.num[i-1];
       HT[i].parent=0;
       HT[i].lchild=0;
       HT[i].rchild=0;
     }
     for (i=n+1; i<=m; i++) { //初始化
       HT[i].weight=0;
       HT[i].parent=0;
       HT[i].lchild=0;
       HT[i].rchild=0;
     }
     for (i=n+1; i<=m; i++) { // 建哈夫曼樹
       // 在HT[1..i-1]中選擇parent為0且weight最小的兩個結點，
       // 其序号分别為s1和s2。
       Select(HT, i-1, s1, s2);
       HT[s1].parent = i;  HT[s2].parent = i;
       HT[i].lchild = s1;  HT[i].rchild = s2;
       HT[i].weight = HT[s1].weight + HT[s2].weight;
     }
   
     //--- 從葉子到根逆向求每個字元的哈夫曼編碼 ---
     HC = (HuffmanCode)malloc((n + 1)*sizeof(char *));
     cd = (char *)malloc(n*sizeof(char));    // 配置設定求編碼的工作空間
     cd[n-1] = '\0';                         // 編碼結束符。
     for (i=1; i<=n; ++i) {                  // 逐個字元求哈夫曼編碼
       start = n-1;                          // 編碼結束符位置
       for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent) 
         // 從葉子到根逆向求編碼
         if (HT[f].lchild==c) cd[--start] = '0';
         else cd[--start] = '1';
       HC[i] = (char *)malloc((n-start)*sizeof(char)); 
            // 為第i個字元編碼配置設定空間
       strcpy(HC[i], &cd[start]);    // 從cd複制編碼(串)到HC
     }
     free(cd);   // 釋放工作空間
   } // HuffmanCoding
   
   
   void Zip(HuffmanCode HC,vector<char> v,TNode T)
   {
   	int i=0,j=0,k=0;
   	ofstream outfile("F:\\Dataclass\\zip.txt",ios::out);
   	if(!outfile)
   	{
   		cerr<<"open error"<<endl;
   		exit(1);
   	}
   	for(i=0;i<v.size();i++)
   	{
   		for(j=0;j<T.length;j++)
   			if(T.data[j]==v[i])
   				break;
   		for(k=0;HC[j+1][k]!='\0';k++)
   			outfile<<HC[j+1][k];			
   	}
   	outfile.close();
   	cout<<"正在壓縮 。";Sleep(500);cout<<" 。";Sleep(500);cout<<" 。"<<endl;
   	cout<<"壓縮成功！可到F:\\Dataclass\\zip.txt中檢視壓縮後檔案"<<endl; 
   } 
   
   
   void RZip(HuffmanCode HC,TNode T)
   {
   	char ch;
   	char ch2[30];
   	int i,j,flag,flag2=0,m=0;
   	ofstream outfile("F:\\Dataclass\\rzip.txt",ios::out);
   	ifstream infile("F:\\Dataclass\\zip.txt",ios::in);
   	if(!outfile)
   	{
   		cerr<<"open error"<<endl;
   		exit(1);
   	}
   	if(!infile)
   	{
   		cerr<<"open error"<<endl;
   		exit(1);
   	}
   	while(infile.peek()!=EOF)
   	{	
   		flag=0;
   		char* cd=new char[T.length];
   		for(i=0;;i++)
   		{
   			infile>>ch;
   			cd[i]=ch;
   			cd[i+1]='\0';
   			for(j=1;j<=T.length;j++)
   				if(strcmp(HC[j],cd)==0)
   				{
   					if(flag2==1)
   					{
   						ch2[m]=T.data[j-1];
   						flag=1;
   						m++;
   						delete cd;
   						break;	
   					}
   					if(flag2==0)
   					{
   						outfile<<T.data[j-1];
   						flag=1;
   						delete cd;
   						break;
   					}
   				}
   			if(flag==1)
   				break;
   		}
   	}
   	cout<<"正在解壓 。";Sleep(500);cout<<" 。";Sleep(500);cout<<" 。"<<endl;
   	cout<<"解壓成功!請到F:\\Dataclass\\rzip.txt中檢視解壓後檔案" <<endl; 
   }
              

   主函數

   int choice, n;
    	vector<char> v;
    	TNode T;
    	InitList(T);
   	HuffmanTree HT;	
   	HuffmanCode HC;
       while(1)
       {
       	system("cls");
           menu();
           printf("選擇你的操作：");
           scanf("%d",&choice);
           switch(choice)
           {
               case 1:
                   ReadTxt(v);
   				TCount(v,T);
   				HuffmanCoding(HT, HC, T);
   				Zip(HC,v,T);
   				RZip(HC,T);
   				system("pause");
   				break;
               case 0:
                   return 0;
               default:
   				cout<<"輸入錯誤！請重新輸入";
   				system("pause");
   				break;
           }
       }
       return 0;
   }