30、：計算機科學與技術
班 級：11級（1）班
指導教師姓名及職稱：陳正銘 講師
起止時間： 2013 年 3 月—— 2013 年 4 月
1 需求分析
1.1課題背景及意義
近年來，隨著計算機技術的發(fā)展，多媒體計算機技術、計算機網(wǎng)絡技術以及現(xiàn)代多媒體通信技術正在向著信息化、高速化、智能化迅速發(fā)展。各個領域的應用與發(fā)展，各個系統(tǒng)的數(shù)據(jù)量越來越大，給數(shù)據(jù)的存儲、傳輸以及有效、快速獲取信息帶來了嚴重的障礙。數(shù)據(jù)壓縮技術能夠比較有效地解決這個問題。
還有在最近幾年中興起的物聯(lián)網(wǎng)和云計算都是對海量的數(shù)據(jù)進行處理和傳輸?shù)?，如果不對?shù)據(jù)進行壓縮，那么數(shù)據(jù)傳輸所需的帶
31、寬要求就很高，物理成本上也隨之上升。所以說數(shù)據(jù)壓縮在計算機通信中占有很重要的位置，且涉及領域多，應用廣泛，與我們的生活息息相關。
1.2課題要求
1.2.1．實現(xiàn)一個基于哈夫曼樹的文件壓縮程序和文件解壓程序。
1.2.2.壓縮程序能輸入源文件進行壓縮，輸出壓縮文件；
1.2.3．解壓程序讀入壓縮文件，根據(jù)相應的哈夫曼編碼解壓還原 ，得到對應的源文件。
1.2.4．可選做：求出壓縮率；打印哈夫曼樹；對文件夾壓縮；圖形圖形化窗口操作界面。
1.3任務和要求
1.3.1選擇1時：
輸入一個待壓縮的文本文件名稱(可帶路徑)。
如:D:\1\XXX.txt
壓縮文件名稱= D
32、:\1\YYY.txt
1.3.2選擇2時：
輸入一個待解壓的壓縮文件名稱(可帶路徑)。
如:D:\1\YYY.txt
解壓文件名稱=D:\XXX.txt
2概要設計
2.1問題解決的思路概述建立哈夫曼樹
根據(jù)哈夫曼樹解碼
對二進制文件進行解碼
統(tǒng)計字符，得出統(tǒng)計出字符的權值n
根據(jù)哈夫曼樹編碼
對編碼進行壓縮
生成哈夫曼樹
生成對應文件
生成二進制文件
圖1 主程序流程圖
2.2 算法思想：
2.2.1輸入要壓縮的文件
首先運行
33、的時候，用戶主界面上有菜單提示該如何使用軟件，根據(jù)菜單提示選擇所要執(zhí)行的項，依次進行，因為各個環(huán)節(jié)之間有先后順序。第一步為輸入壓縮軟件的名稱，由鍵盤輸入文件路徑和文件名稱，讀入字符數(shù)組中，打開該文件，按照提示進行壓縮。若打不開，則繼續(xù)輸入。
2.2.2讀文件并計算字符頻率
文件將信息存放在字符數(shù)組中；計算每個字符出現(xiàn)的次數(shù)，申請一個結構體數(shù)組空間， 用讀取的字符減去字符結束符作為下標記錄字符的頻率。
2.2.3根據(jù)字符的頻率，利用Huffman編碼思想創(chuàng)建Huffman樹
將所記錄的字符的頻率作為權值來創(chuàng)建Huffman樹，依次選擇權值最小的兩個字符作為左右孩子，其和作為父結點的權值，
34、依次進行下去，直到所有的字符結點都成為葉子結點。
2.2.4由創(chuàng)建的Huffman樹來決定字符對應的編碼，進行文件的壓縮
根據(jù)創(chuàng)建的Huffman樹來確定個字符的01編碼，左孩子為0，右孩子為1。讀取文件，依次將每個字符用他們的編碼表示，即完成一次編碼。
2.2.5解碼壓縮即根據(jù)Huffman樹進行譯碼
讀取編碼文件，依據(jù)創(chuàng)建的Huffman樹，定義一個指針指向根結點。從根結點開始，每讀一個字符，指針變化一次（當讀取的字符是‘1’時，指針指向當前所指結點的右孩子，當讀取的字符是‘0’時，指針指向當前所指結點的左孩子），直至該指針所指結點為葉子結點時結束（即當結點的左右孩子均為空時）。將
35、當前葉子結點所代表的字符值輸出到譯碼文件中，依次讀取編碼文件中的字符，按照上述方法依次進行下去直至文件
2.3數(shù)據(jù)結構定義
//huffman樹的結點結構體
typedef struct HTnode
{
long weight; //記錄結點的權值
int parent; //記錄結點的雙親結點位置
int lchild; /結點的左孩子
int rchild; //結點的右孩子
int *code; //記錄該結點的huffman編碼
int codelen; //記錄該結點huffman編碼的長度
HTnode()
{
weigh
36、t = MAX;
parent = -1;
lchild = -1;
rchild = -1;
codelen = 0;
}
}HTnode;
2.4定義huffman數(shù)類及其函數(shù)
class huffmanTree
{
public:
huffmanTree();
virtual ~huffmanTree();
bool count(char *input); //壓縮時統(tǒng)計各字符出現(xiàn)的次數(shù)，將其寫入對應結點的權值
void create(); //壓縮時根據(jù)各結點的權值構造huffman樹
void code(); //壓縮時
37、利用huffman樹計算每個字符的huffman編碼
void addbit(int bit); //壓縮時對一個未滿8個bit的byte中加入一個bit
void resetbyte(); //將byte清空
bool compress(char *input, char *output);//壓縮函數(shù),成功返回 true 失敗 false
bool decompress(char *input, char *output); //解壓函數(shù),成功返回 true 失敗false
void compare(char *input, char *output); //將原文件與
38、壓縮后的文件比較
private:
int root; //記錄根結點的位置
int leafnum; //記錄不同字符的個數(shù)
HTnode HT[leaf*2-1]; //HTnode結構的數(shù)組，用來表示huffman樹，樹的最大結點個數(shù)不會超過leaf*2-1
char byte; //壓縮文件時用來緩沖bit的變量
int bitsnum; //byte中bit的個數(shù)
int lacknum; //壓縮到最后byte中的bit不滿8個時填充的0的個數(shù)
};
2.5主程序的流程及模塊間關系
主函數(shù)實例化huffmanTree類，并實現(xiàn)菜單工具欄，通過用戶
39、的選擇輸入，用switch語句進行分支執(zhí)行huffmanTree類中功能函數(shù)：
1:壓縮函數(shù) bool compress(char *input, char *output)
2:解壓函數(shù) bool decompress(char *input, char *output)
并可在完成相應功能后安全退出，壓縮或解壓的文件在同文件夾下生成。
3. 詳細設計
核心算法----huffman算法：
3.1根據(jù)給定的n個權值｛w1,w2,……,wn｝構成n棵二叉樹的集合F=｛T1,T2,……,Tn｝,其中每棵二叉樹T1中只有一個帶權的 w1的根據(jù)點，其左右子樹均空。
3.2在F中
40、選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左右樹上根結點的權值之和。
3.3在F中刪除這兩棵樹，同時將所得到的二叉樹加入F中。
3.4重復3.2,3.3,直到F中只含一棵樹為止。這棵樹便是Huffman樹。Huffman樹可用于構造代碼總長度最短的編碼方案。
為了詳細說明這個問題，特以下面例子來說明:[4]
假設我們有這么一串20個字母的數(shù)據(jù)：
默認情況下，用2位2進制碼來表示這四個字母：
A
B
C
D
00
01
10
11
每個字符在字符串中各自出現(xiàn)的次數(shù)并不相等：
A:6次 B
41、:10次 C:3次 D:1次
而在計算機中，數(shù)據(jù)則是以2進制碼的形式儲存在硬盤上的：
00 00 01 00 00 01 01 10 01 00 01 01 01 10 01 01 00 01 11 10
壓縮過程如下：
①注明每個字符的出現(xiàn)次數(shù)。把兩個出現(xiàn)次數(shù)最小的字符圈到一起，看作一個新字符，新字符的次數(shù)為兩個組成字符的次數(shù)之和。
②重復上述操作，直至完成對所有字符的處理。這種操作形成的結構看起來像棵樹（下圖），被稱為——霍夫曼(Huffman)樹。
圖2 構造哈夫曼樹
③在每一層的分支線上
42、，按下圖所示分別標上0和1。
圖3 哈弗曼編碼
從最頂端往下讀，每個字符都有唯一的分支編號連到它那里，無重復也無遺漏，這樣就得到了ABCD這四個字符的新的代碼：
A
B
C
D
10
0
110
111
用以上新編碼代入原字符串中，得到：
10 10 0 10 10 0 0 110 0 10 0 0 0 110 0 0 10 0 111 110
主程序模塊:
主函數(shù)
菜 單
huffmanTree類
壓縮函數(shù)
compress
恢復函數(shù)
decompress
對比函數(shù)
compare2
43、
圖 4 程序模塊
Huffman編碼流程
NO
YES
哈夫曼編碼位操作壓縮存儲
壓縮文件成功!
計算壓縮率%
打開文本文件統(tǒng)計文件長度
初始化節(jié)點
構建哈夫曼樹
計算左右分支權值大小,進行無重復前綴編碼
壓縮文件失敗
圖 5 編碼流程
Huffman解碼流程
NO
YES
解壓壓縮文件成功!
解壓縮文件失敗!
打開壓縮文件讀取原文件長度進行文件定位
根據(jù)哈夫曼編碼的長短,對節(jié)點進行排序
通過哈夫曼編碼的長短,依次解碼,從原來的位存儲還原到字節(jié)存儲
在單字節(jié)內(nèi)對相應位
44、置補0
圖 6 解碼流程
4.調(diào)試分析報告
實現(xiàn)壓縮率時出現(xiàn)了主觀上的錯誤，壓縮率=(total1-total2)/total1*100%，
經(jīng)百度后發(fā)現(xiàn)：壓縮率（Compression ratio），描述壓縮文件的效果名，是文件壓縮后的大小與壓縮前的大小之比，比如你把100m的文件壓縮后是90m，壓縮率就是90/100*100%=90%，壓縮率一般是越小越好，但是壓得越小，時間越長。[5]
如下圖：
圖 7 壓縮率測試結果
將壓縮率改正為： total2/total1*100%，再進行測試的結果如下圖：
45、 圖 8 改正后的測試結果
5.用戶使用說明
在運行程序之前，首先在e盤先建立一個待壓縮的文件222.txt，
運行程序如下圖所示。
圖9 版本測試結果圖
壓縮：
在命令行下輸入1對文件進行壓縮，根據(jù)提示輸入剛剛建的文本文件（222.txt），和要生成的壓縮文件名稱，按回車確認進行壓縮。
圖 10 執(zhí)行壓縮操作圖
成功執(zhí)行完畢后如下圖所示。
圖 11 執(zhí)行壓縮操作圖
46、
解壓：
在命令行下輸入2對本程序壓縮的文件進行恢復，根據(jù)提示輸入待恢復的
文件名稱和恢復后的文件名稱，按回車確定，成功執(zhí)行后如下圖所示。
圖12 執(zhí)行解壓操作圖
對比：
原文件222.txt
圖 13 待壓縮文件222.txt
壓縮后的文件111.txt
圖14 壓縮后的文件111.txt
解壓后的文件333.txt
圖 15
47、 解壓后的文件333.txt
6.測試結果
詳細測試結果請參見 5 使用功能。
6.1測試報告
原文件
壓縮后
解壓后
1
txt文件(7kb)
6 kb
7 kb
2
pdf文件(1080kb)
1052 kb
無法解壓得到原文件
3
jpg文件(81kb)
80 kb
無法解壓得到原文件
4
Mp3文件(924kb)
913 kb
無法解壓得到原文件
打開解壓后的pdf文件時提示如下：
圖 16 打開解壓后pdf文件的提示
打開解壓后的jpg和mp3文件同樣遇到無法打
48、開的提示。
參考文獻
[1]嚴蔚敏，李冬梅，吳偉民 .數(shù)據(jù)結構(C語言版) [M].北京:人民郵電出版社，2011.
[2]譚浩強 .C++面向?qū)ο蟪绦蛟O計(第二版) [M].北京：中國鐵道出版社，2009.
[3]潘瑋華 . 用Huffman編碼進行文件壓縮的方法 [J].電腦知識與技術,2010年07期.
[4]kaikai.數(shù)據(jù)是怎么被壓縮的[OL].
[5]百度百科.[OL]. .
附錄：源程序
#include
#include
#include
49、> //隊列容器
using namespace std;
const int leaf = 256; //最多可能出現(xiàn)的不同字符數(shù)
const long MAX = 99999999; //表示無窮大
typedef struct HTnode
{
long weight; //記錄結點的權值
int parent; //記錄結點的雙親結點位置
int lchild; //結點的左孩子
int rchild; //結點的右孩子
int *code; //記錄該結點的huffman編碼
int codel
50、en; //記錄該結點huffman編碼的長度
HTnode()
{
weight = MAX;
parent = -1;
lchild = -1;
rchild = -1;
codelen = 0;
}
}HTnode;
class huffmanTree
{
public:
huffmanTree();
virtual ~huffmanTree();
bool count(char *input); //統(tǒng)計各字符出現(xiàn)的次數(shù)，將其寫入對應結點的權值
void create(); //構造huffman
51、樹
void code(); //計算每個字符的huffman編碼
void addbit(int bit); //壓縮時對一個未滿8個bit的byte中加入一個bit
void resetbyte(); //將byte清空
bool compress(char *input, char *output); //壓縮函數(shù) 成功執(zhí)行返回 true 失敗 false
bool decompress(char *input, char *output); //解壓函數(shù) 成功執(zhí)行返回 true 失敗 false
void compare(char *inpu
52、t, char *output); //將原文件與壓縮后的文件比較
private:
int root; //記錄根結點的位置
int leafnum; //記錄不同字符的個數(shù)
HTnode HT[leaf*2-1]; //HTnode結構的數(shù)組，用來表示huffman樹，樹的最大結點個數(shù)不會超過leaf*2-1
char byte; //壓縮文件時用來緩沖bit的變量
int bitsnum; //byte中bit的個數(shù)
int lacknum; //壓縮到最后byte中的bit不滿8個時填充的0的個數(shù)
};
huff
53、manTree::huffmanTree()
{
//初始化成員變量
root = 0;
leafnum = 0;
byte = 0;
bitsnum = 0;
lacknum = 0;
}
huffmanTree::~huffmanTree()
{
for(int i=0; i
54、ream ifs;
char c;
ifs.open(input,ios::binary);
if(!ifs){
cout << "無法打開文件 " << input << ! << endl;
return false;
}
while(ifs.get(c)){
if(HT[c+128].weight==MAX){ //若該字符是第一次出現(xiàn)，先初始化權值
HT[c+128].weight = 0;
leafnum++;
}
HT[c+128].weight++; //權值+1
}
ifs.close();
re
55、turn true;
}
//選權值最小的兩棵樹組成新的數(shù)
void huffmanTree::create()
{
for(int i=leaf; i<2*leaf-1; i++)
{
int loc1=-1, loc2=-1;
for(int j=0; j
56、 else if(loc2==-1 || HT[j].weight < HT[loc2].weight)
loc2 = j;
}
if(HT[loc1].weight==MAX || HT[loc2].weight==MAX || loc2==-1) //只剩一棵樹，結束
break;
HT[i].weight = HT[loc1].weight + HT[loc2].weight;
//為了減少壓縮文件中需要寫入的huffman樹的信息，約定小標小的結點做為雙親結點的左孩子
HT[i].lchild = loc1>loc2 ? loc2 :
57、 loc1;
HT[i].rchild = loc1>loc2 ? loc1 : loc2;
HT[loc1].parent = i; HT[loc2].parent = i;
root = i;
}
}
//計算每個字符的huffman編碼
void huffmanTree::code()
{
for(int i=0; i
58、 = HT[loc].parent;
}
HT[i].codelen = len;
HT[i].code = new int[len];
loc = i;
for(int j=len-1; j>=0; j--)
{ //從后往前找，記錄結點的huffman編碼
if(loc==HT[HT[loc].parent].lchild)
HT[i].code[j] = 0;
else
HT[i].code[j] = 1;
loc = HT[loc].parent;
}
}
}
//壓縮時對一個未滿8個bi
59、t的byte中加入一個bit
void huffmanTree::addbit(int bit)
{
if(bit == 0)
byte = byte << 1; //若新增的bit為0，則直接將byte按位左移
else
byte = ((byte << 1) | 1); //若新增的bit為1，先將byte按位左移，再與1按位或運算
bitsnum++;
}
//將byte清空
void huffmanTree::resetbyte()
{
byte = 0;
bitsnum = 0;
}
//壓縮函數(shù) 成功執(zhí)行返回 true
60、 失敗 false
bool huffmanTree::compress(char *input, char *output)
{
if( !count(input) )
return false;
create();
code();
ifstream ifs;
ofstream ofs;
ifs.open(input,ios::binary);
ofs.open(output,ios::binary);
char c;
if(!ifs)
{
cout << "無法打開文件 " << input << ! << endl;
61、return false;
}
if(!ofs)
{
cout << "無法打開文件 " << output << ! << endl;
return false;
}
ofs.put(0); //預留一個字符，等壓縮完后在該位置寫入不足一個byte的bit個數(shù)
ofs.put(root-384); //將根節(jié)點的位置-384寫入（為使該值不超過char的最大表示范圍）
for(int i=0; i
62、入127(一個字節(jié)所能表示的最大值)
ofs.put(127);
else //否則將雙親結點的位置-384再寫入（為使該值不超過char的最大表示范圍）
ofs.put(HT[i].parent-384);
}
while(ifs.get(c))
{ //將字符的huffman編碼并加入byte中
int tmp = c+128;
for(int i=0; i
63、te已滿8位，則輸出該byte并將byte清空
ofs.put(byte);
resetbyte();
}
}
}
if(bitsnum!=0){ //處理最后未滿8個字符的byte，用0填充并記錄填充的個數(shù)
for(int i=bitsnum; i<8; i++)
{
addbit(0);
lacknum++;
}
ofs.put(byte);
resetbyte();
}
ofs.seekp(0,ios::beg); //將寫指針移動到文件開頭
ofs.put(lacknum); //寫入
64、最后一個字節(jié)缺失的bit個數(shù)
ifs.close();
ofs.close();
return true;
}
//解壓函數(shù) 成功執(zhí)行返回 true 失敗 false
bool huffmanTree::decompress(char *input, char *output)
{
queue q;
char c;
ifstream ifs;
ofstream ofs;
ifs.open(input,ios::binary);
ofs.open(output,ios::binary);
if(!ifs)
{
cout <
65、< "無法打開文件 " << input << ! << endl;
return true;
}
if(!ofs)
{
cout << "無法打開文件 " << output << ! << endl;
return false;
}
ifs.get(c);
lacknum = c; //讀出最后一個字節(jié)缺失的bit個數(shù)
ifs.get(c);
root = c+384; //讀出根結點的位置
for(int i=0; i
66、if(c==127)
continue;
else
{
HT[i].parent = c+384;
if(HT[c+384].lchild==-1)
HT[c+384].lchild = i;
else
HT[c+384].rchild = i;
}
}
int point = root;
//為了方便處理最后一個可能有缺失bit的字節(jié)，先將讀出的數(shù)據(jù)放入隊列
while(ifs.get(c))
q.push(c);
//還原文件過程
while(q.size()>1)
{ //還未到最后一個字節(jié)
c = q.front();
for(int i=0; i<8; i++)
{
if(int(c&128)==0)
c++哈夫曼樹的文件壓縮解壓程序全部代碼及設計報告
