哈夫曼編碼/譯碼
點擊數：2601    發布日期：2006-12-4 0:37:00  
【收藏】 【評論】 【打印】 【編程愛好者論壇】 【關閉】


 
                                   哈夫曼編碼/譯碼

一、【實驗內容】
【問題描述】
      利用哈夫曼編碼進行住處通訊可以大大提高信道利用率,縮短住處傳輸時間,降低成本,但是,這要求在發送端通過一個編碼系統將傳輸的數據預先編碼,在接收端通過一個譯碼系統對傳來的數據進行譯碼(復原),對于雙向傳輸信息的信道,每端都一個完整的編碼譯碼系統,試為這樣的住處收發站寫一個哈夫曼友的編碼譯碼系統.

【基本要求】：一個完整的系統應以下功能:
(1) I. 初始化(Initialization)。從終端讀入字符集大小n，以及n個字符和n個權值,建立哈夫曼樹,并將它存放在文件hfmTree中.
(2) E. 編碼(Encoding)。利用已建立好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼,然后將結果代碼存(傳輸)到文件CodeFile中.
(3) D. 譯碼(Decoding)。利用已建好的哈夫曼樹,對傳輸到達的CodeFile中的數據代碼進行譯碼,將譯碼結果存入文件TextFile中. 
(4) P. 印文件代碼(Print)。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。 
(5) T. 印哈夫曼樹(TreePrinting)。將已在內存中的哈夫曼樹以直觀的方式(樹或凹入表的形式)顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。
　　　　　　
測試數據：
(1) 利用教科書例6-2中的數據調試程序。
(2) 用下表給出的字符集和頻度的計數據建立哈曼樹,并實現以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”.。
字符       A   B    C    D    E    F    G    H    I    J    K    L    M
頻數 186  64   13   22   32   103  21   15   47   57   1    5    32   20
字符 N    O    P    Q    R    S    T    U    V    W    X    Y    Z
頻數 57   63   15   1    48   51   80   23   8    18   1    16   1 


二、實驗目的
樹型結構是一種應用極為廣泛的非線性數據結構,也是本課程的重點內容,哈夫曼樹(最優二叉樹)是樹型結構的典型應用,本次實驗突出了數據結構加操作的程序設計觀點,希望能根據樹型結構的非線性特點,熟悉各種存儲結構的特性,達到如何應用樹型結構的非線性特點,熟悉各種存儲結構的特性,達到如何應用樹型結構解決具體問題的目的.

 

 


三、實驗文檔：
                  哈夫曼編碼/譯碼
一、 需求分析
1、 利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時
間，降低傳輸成本。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端將傳來的數據進行譯碼（復原）。對于雙工信道（既可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統。本次設計就是為這樣的信息收發站寫的一個哈夫曼的編/譯碼器。
本實驗要求：
2、本演示程序中，用戶可以輸入鍵盤中的任意字符，長度為任意長，字符輸入順序不限，且允許出現重碼
3、演示程序以用戶與計算機的對話方式執行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規定的運算命令，相應的輸入數據（可慮去輸入中的非法字符）和運算結果顯示在其后。
4、本演示程序中，當用戶選擇的功能錯誤時，系統會輸出相應的提示。
5、在本系統中，用戶可以對任意長的字符串可進行編碼/譯碼。
6、程序執行的命令包括：
　1) 初始化(I)　　　2) 編碼(E)　　　　3) 譯碼(D) 
4) 印代碼文件(P)　5) 印哈夫曼樹(T)　6) 退出(Q)
７、測試數據：
　　（１）利用教科書例6-2中的數據調試程序。
（２）用下表給出的字符集和頻度的計數據建立哈曼樹,并實現以下報文的
　　　編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”.。
字符     A   B   C   D   E   F   G   H   I   J   K   L   M
頻數 186  64    13    22    32   103    21   15   47    57    1    5     32    20
字符 N  O   P   Q   R    S    T   U    V   W   X    Y   Z
頻數 57   63    15    1    48     51     80    23     8      18    1      16    1 

二、概要設計
為實現上述程序功能，應以指針存儲結點。為此，需要定義一個抽象數據類型。
1. 抽象數據類型定義為：
ADT HuffmanTree{
數據對象：D={ai| ai∈CharSet,i=1,2,……,n,  n≥0}
數據關系：R={< ai-1, ai > ai-1, ai∈D, ai-1<ai ,i=2，3，……，n}
基本操作P：
HuffmanTree();       構造函數
~ HuffmanTree();     析構函數
Initialization(int WeightNum);
操作結果：構造哈夫曼樹。
Encoder()
初始條件：哈夫曼樹已存在或者哈夫曼樹已存到文件中。
操作結果：對字符串進行編碼
Decoder();
初始條件：哈夫曼樹已存在且已編碼。
操作結果：對二進制串進行譯碼
Print()
初始條件：編碼文件已存在。
操作結果：把已保存好的編碼文件顯示在屏幕
TreePrinting()
初始條件：哈夫曼樹已存在。
操作結果：將已在內存中的哈夫曼樹以直觀的方式顯示在終端上
2.本程序包含三個模塊：
1)主程序模塊：
void main(){
    初始化；
do{
   接受命令；
   處理命令；
}while(“命令”=”退出”)
}
2)、建樹模塊——實現定義的抽象數據類型
3)、編/譯碼模塊——實現字符串的編/譯碼
各模塊之間的調用關系如下：
                    主程序模塊
                     
                     
                      建樹模塊                  

                     
                     
編/譯碼模塊
三、詳細設計
程序代碼如下
//        程序名：HuffmanTree.h
//      程序功能：哈夫曼樹類的頭文件(并用其來實現編/譯碼)
//          作者：劉偉高
//          日期：2006.11.27
//          版本：1.0


//對應類實現文件: HuffmanTree.cpp
//對應主程序文件: main.cpp

 

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
struct HuffmanNode        //定義哈夫曼樹各結點
{
 int weight;        //存放結點的權值，假設只考慮處理權值為整數的情況
 int parent;        //記錄結點父親位置，-1表示為根結點，否則表示為非根結點
 int lchild,rchild;   //分別存放該結點的左、右孩子的所在單元的編號
};
class HuffmanTree     //建立哈夫曼樹類
{
private:
 HuffmanNode *Node;      //哈夫曼樹中結點的存儲結構
 char *Info;           //用來保存各字符信息
 int LeafNum;          //樹中的葉子結點總數
public:
 HuffmanTree();     //構造函數
 ~HuffmanTree();    //析構函數
 void Initialization(int WeightNum);   //初始化函數：根據WeightNum個權值建立一棵哈夫曼樹
 void Encoder();           //編碼函數：利用構造好的哈夫曼樹對字符進行編碼
 void Decoder();          //譯碼函數：對二進制串進行譯碼
 void Print();            //印文件函數：把已保存好的編碼文件顯示在屏幕
 void TreePrinting();     //印哈夫曼樹函數：將已在內存中的哈夫曼樹以直觀的方式顯示在終端上
};


//        程序名：HuffmanTree.cpp
//      程序功能：實現哈夫曼樹類的源文件(并用其來實現編/譯碼)
//          作者：劉偉高
//          日期：2006.11.27
//          版本：1.0


#include"HuffmanTree.h"
#include<string>
using namespace std;

//////////////////////////////////////////////////////////////////////////////
//  構造函數
//  函數功能：將結點指針初始化為NULL
//  函數參數：無
//  參數返回值：無
HuffmanTree::HuffmanTree()
{
 Node=NULL;          //將樹結點初始化為空 
 Info=NULL;          //將字符數組初始化為空
 LeafNum=0;          //將葉子數初始化為0
}
//////////////////////////////////////////////////////////////////////////////
// 析構函數
// 函數功能：將所有結點的空間釋放
// 函數參數：無
// 參數返回值：無
HuffmanTree::~HuffmanTree()
{
 delete[] Node;         //釋放結點空間
 delete[] Info;         //釋放字符存儲空間
}
//////////////////////////////////////////////////////////////////////////////
//  初始化函數
//  函數功能：從終端讀入字符集大小n，以及n個字符和n個權值,
//            建立哈夫曼樹,并將它存放在文件hfmTree中.
//  函數參數：int WeightNum表示代碼個數
//  參數返回值：無 
void HuffmanTree::Initialization(int WeightNum)        //初始化
{
 int i,j,pos1,pos2,max1,max2;     //
 
 Node=new HuffmanNode[2*WeightNum-1];  //WeightNum權值對應的哈夫曼樹中的結點總數為2*WeightNum-1個
 Info=new char[2*WeightNum-1];
 for(i=0;i<WeightNum;i++)
 {
  cout<<"請輸入第"<<i+1<<"個字符值";
  getchar();           //丟棄字符'\t'與'\n'
  Info[i]=getchar();   //輸入一個字符,主要是考慮輸入空格而采用這種形式的
  getchar();
  cout<<"請輸入該字符的權值或頻度";
  cin>>Node[i].weight;       //輸入權值
  Node[i].parent=-1;      //為根結點
  Node[i].lchild=-1;      //無左孩子
  Node[i].rchild=-1;      //無右孩子
 }
 
 for(i=WeightNum;i<2*WeightNum-1;i++) //表示需做WeightNum-1次合并
 {
  pos1=-1;
  pos2=-1;          //分別用來存放當前最小值和次小值的所在單元編號 
  max1=32767;      //32767為整型數的最大值 
  max2=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;                  //修改次小值所在的單元編號
     }
    //for
  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=WeightNum;
 
 
 char ch;
 cout<<"是否要替換原來文件(Y/N):";
 cin>>ch;
 if(ch=='y'||ch=='Y')
 {
 ofstream fop;   //以二進制方式打開hfmTree.dat文件，并當重新運行時覆蓋原文件
 fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);
 if(fop.fail())                     //文件打開失敗
  cout<<"文件打開失敗！\n";
 fop.write((char*)&WeightNum,sizeof(WeightNum));  //寫入WeightNum
 for(i=0;i<WeightNum;i++)         //把各字符信息寫入文件
 {
  fop.write((char*)&Info[i],sizeof(Info[i]));
  flush(cout);
 }
 for(i=0;i<2*WeightNum-1;i++)        //把個節點內容寫入文件
 {
  fop.write((char*)&Node[i],sizeof(Node[i]));
  flush(cout);
 }
 fop.close();            //關閉文件
 }
 cout<<"哈夫曼樹已構造完成。\n";
}//Initialization

//////////////////////////////////////////////////////////////////////////////
//  編碼函數
//  函數功能：利用已建立好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），
//            對文件ToBeTran中的正文進行編碼,然后將結果代碼存(傳輸)到文件CodeFile中.
//  函數參數：無
//  參數返回值：無
void HuffmanTree::Encoder()
{
 if(Node==NULL)       //哈夫曼樹不在內存，從文件hfmTree中讀入
 {
  ifstream fip;        //以二進制方式打開hfmTree.dat文件
  fip.open("hfmTree.dat",ios::binary|ios::in);
  if(fip.fail())       //文件打開失敗
  {
   cout<<"文件打開失敗！\n";
   return;          //結束本函數
  }
  fip.read((char*)&LeafNum,sizeof(LeafNum));  //讀取葉子數
  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(i=0;i<2*LeafNum-1;i++)              //讀取結點信息
   fip.read((char*)&Node[i],sizeof(Node[i]));
 }
 
 char *Tree;          //用于存儲需編碼內容
 int i=0,num;
 char Choose;         //讓用戶選擇讀取文件或重新輸入需編碼內容
 cout<<"你要從文件中讀取內容(1)，還是重新輸入(2):";
 cin>>Choose;
 if(Choose=='1')          //讀取文件ToBeTran.txt
 {
  ifstream fip1("ToBeTran.txt");
  if(fip1.fail())      //文件不存在
  {
   cout<<"文件打開失敗!\n";
   return;          //結束本函數
  }
  char ch;
  int k=0;
  while(fip1.get(ch))            
  {
   k++;                     //計算CodeFile中代碼長度
  } 
  fip1.close();  
 
  Tree=new char[k+1];
  ifstream fip2("ToBeTran.txt");

  k=0; 
  while(fip2.get(ch))
  {
   Tree[k]=ch;           //讀取文件內容，并存到Tree中