Huffman编码实现文本文件压缩

整理旧的博客 2009-03-10 21:36:25

这是当初大二时候的课程设计文档

--------------------------------------------------------------------

辛苦做完了估计老师也不看~~~

貌似这是俺的劳动成果~~~~~O(∩_∩)O~

数据结构课程设计报告【一】

课程设计题目：文本文件压缩【一】

题目: 文本文件压缩解压

需求分析：

输入：文本文件(压缩文件)

输出：压缩文件(文本文件) (压缩率)

知识点：堆排序、霍夫曼树、二叉树遍历、存储数据结构设计

　　　　 文件流操作、字符汉字编码方式、二进制文件读写

备注：字符文件、汉字文件的压缩与解压

解决问题要点：

1. 文本文件，二进制文件及数据流的操作

2. 英文字符，中文字符的存储与识别【难点】

3. 压缩及解压的主要思想【重点】

4. Huffman树的构造

5. 编码的获取

6. 压缩文件的存储形式[huffman编码信息及数据存储]

7. 对文本文件最后一个字符的处理[补位数：压缩，解压无错误]

　 以上七点即解决问题的关键，仅仅了解整个思想是远远不够的，整个过程中，很多细节需要注意，把握要点的同时，要在具体实现中注意细节。

模块及框架设计：

按功能需求，主要分为五个模块

主要模块：

1. 压缩模块

2. 解压模块

辅助模块：

1. 字符识别及权重获取

2. Huffman树构造

3. 获取huffman编码

主要设计及具体实现　【实现代码(带注释)】

l 压缩解压的实现思想及原理

定义：利用算法将文件有损或无损地处理，以达到保留最多文件信息，而令文件体积变小。

在文本文件中，一个ASCII码占用一个字节空间（1Byte），汉字由两个字节构成（区码和位码），区码和位码分别用ASCII码的161-255字符表示，共94*94=8836个【GB2312编码】

即，无论字符还是汉字，均可由ASCII码表示，我们可以以二进制文件形式将一个文本文件读入，分析每个ASCII码的频数，构造huffman树，并得到相应的编码。

编码是由0、1组成的一串数字，出现频率越高的字符，其编码越短，通过这个特性，我们可以将每8位组成一个新的字符（1Byte），输出到压缩文件中，达到压缩的目的。

例如：

已知 a: 000 b:10 c: 001 d:01 e:11

如果其中的一段是:：abcde 则处理如下：

补上两位

a b c d e

000 10 00 1 01 11 00

每次取7位【取8位亦可，但此处为了处理最后一个字符，只取7位】

0+7位凑成1Byte，转化为相应AscII码输出

最后一位一般不能刚好凑够8 bit 所以需要补上0

而补上的0的个数记录为补位数 【补位数的处理】

原来： 5*1Byte=8 Byte

处理后：2*1Byte=2 Byte

仅为原来的四分之一，达到了压缩的目的

l 字符，汉字处理方式

字符，即ASCII码，ASCII编码由8位组成，共256个字符，足够表示英文文本。

汉字，是考虑的重点，多方考虑下，我选择了系统支持的GB2312编码表，而非转化为UNICODE编码。GB2312的汉字编码占用两个字节，区码和位码分别由ASCII码表的161-255字符表示，共8836个汉字，足以承担汉字处理，而UNICODE编码表是变长编码，处理困难且不利于压缩。

汉字ASCII码八位1******* 一般字符编码八位0*******

处理的思想：

以字符形式读入，每次读入一个字节（1Byte）进行处理，不去判断区分是字符还是汉字，只识别ASCII码，进行处理。

l 设计字符所存储的数据结构

读入的字符所需要存储的信息：字符，频数以及各自编码

仅仅以char数组存储将带来非常大的缺陷。

作用：提高效率，减小复杂性

class huffmanchar

{

char c;//字符

int count;//字符出现的次数

intbit[20];//用于存储huffman编码

int codelength;//bit中编码的长度

}

实例化 huffmanchar huff[256]; //ASCII字符总数

Int totalcount;//记录字符总数 ，

l 设计树节点的数据结构

在压缩时，为了解压时能够顺利获取该文件相应的huffman编码，我们可以设计一个表头，以存储编码信息，但是这种形式不但造成读入困难，而且占用空间巨大。

解决方法：压缩时，将整棵huffman以对象的形式写入压缩文件开头，解压整棵读出，强制类型转换即可方便地得到huffman树

class BinaryTreeNode

{

Int data;//频数，即权重

char character;//相应字符

BinaryTreeNode<T> *LeftChild,*RightChild;

};

设计Huffman树的数据结构

Huffman具有一般二叉树的所有特性，但是，在压缩处理过程中遇到一个情况，我们无法正确处理最后一个字符，因为通常到最后一位，编码不会满8位，这就在解压时输出多余字符。

解决方法，每次令始终第一位为0，仅取7位编码：0*******

处理到最后一位时，首位为1，并记录缺位数lackcount

Lackcount传入huffman树对象，以写入压缩文件

class BinaryTree

{

BinaryTree(){ root=0;lackcount=0;}

BinaryTreeNode<T> *root;

int lackcount;//构造对象是用于存储最后一位的缺位数~~~~~

}

：

整体构架及处理流程：

主类：Oper.h 字符获取，文件读取，流处理，压缩，解压缩

辅助类：BinaryTree.h 构造huffman树及获取相应编码

MinHeap.h 用于辅助构造huffman树

Chain.h 存储遍历huffman时产生的编码

BinaryTreeNode.h 存储huffman树结点

Huffmanchar.h 存储字符及权重，编码

Huffman.h 存储huffman

OutOfBounds.h huffman结点，存储树及权重

压缩主要流程：

读入文件 #include <fstream>

Ifstream input;

Input.open(“d://test.txt”);

计算频数 huffmanchar huff[256]；//字符数组

Int totalcount;//记录字符总数 ，

辅助函数

bool Oper::judge(int c)//判断c所对应字符是否在数组里出现

//若是出现过，该字符count++;

void Oper::add(char c)//添加新出现的字符totalcount++;

主函数：

void Oper::getFrequency()//计算频数

{

while(!input.eof())

{

input.get(temp);

if(!judge((int)temp))

add(temp);

}

}

构造huffman树

构造霍夫曼树

思想：

1.为了构造霍夫曼树，首先从仅含一个外部节点的二叉树集合开始，每个外部节点代表字符串中一个不同的字符，其权重等于该字符的频率。

2.此后不断地从集合中选择两棵具有最小权重的二叉树，并把它们合并成一棵新的二叉树，合并方法是把这两棵二叉树分别作为左右子树，然后增加一个新的根节点。新二叉树的权重为两棵子树的权重之和。

3.这个过程可一直持续到仅剩下一棵树为止。

实现：

利用最小堆，将每个权重作为一颗仅有根节点的树传入，每次取出权值最小两个，组成一颗新树并放回到最小堆，直到仅剩一棵树

BinaryTree<int> HuffmanTree(int a[],char c[],int n)

{

Huffman<int> *w=new Huffman<int>[n+1];

BinaryTree<int> z,zero;

MinHeap<Huffman<T> > H(1);//实例化最小堆对象

H.Initialize(w,n,n);

Huffman<int> x,y;

for(i=1;i<n;i++)

{

H.DeleteMin(x);//每次取权值最小两个

H.DeleteMin(y);

z.MakeTree(0,' ',x.tree,y.tree);//组成新树

z.weight=x.weight+y.weight;

H.Insert(z);//再次加入

}

return x.tree;//最终返回即huffman树

}

获取huffman编码

伪代码：

Chain A;//由于存储链表huffman编码

void OutputCode(root)

{

if(t->LeftChild ) //若是左子树不为空

{

往左走，0加入链表

OutputCode(root->leftChild)//递归处理

}

if(t->RightChild)

{

往右走，1加入链表

OutputCode(root->rightChild)//递归处理

}

if(t->LeftChild==NULL && t->RightChild==NULL)

{

若为叶节点，将链表内编码传到相应字符的bit数组

删除链表最后一个节点

Return;

}

Return；

}

再次读入文件

压缩模块开始

主要思想：

将源文件字符一个一个读入，判断，寻找其相应编码

将编码一位一位加入缓冲区

缓冲区满8位时，转化为相应的形影ASCII编码

将编码输出

BinaryTree<int>& bc；//将树对象先写到文件头

output.write((char *)&bc,sizeof(bc));

int buffer[8];//用作缓冲区~~~

int bufcount;//记录缓冲字节数~~，初始为1

主函数：

void encoding(BinaryTree<int>& bc)

//调用辅助函数

//读入文件，处理每个字符，得到其编码

//将编码加入缓冲区

辅助函数：

int changeinto(int *a)

//缓冲区满时调用，将8位数组转化为一个int

void addToBuff(int a,ofstream output)

//将编码加入缓冲函数~~~

//缓冲区满时，转化为一个int ,写出output<<(char)intA void flushbuffer(ofstream output)

//处理完最后一位字符后，缓冲区存在编码

//将首位设为1，将缓冲区剩余的输出

压缩结束

解压流程：

读入文件

重构Huffman树

直接将其存于压缩文件表头的对象读出

BinaryTree<int> bc;

input.read((char *)&bc,sizeof(bc));

并得到编码的缺位数

Lackcount=bc.lackcount;

开始解压

解压思想：

1. 每次一个Byte ，

2. 转化为相应二进制串，识别首位是否

3. 开始遍历huffman树(0左 1右)

若为叶节点，输出相应字符

指针回到根节点，重复此过程

void Oper::gothrough(BinaryTree<int> bc,int a,ofstream output)

//遍历树，若是叶节点输出~~~~

{

if(a==0 && tnode->LeftChild )

{

tnode=tnode->LeftChild;

}

else if(a==1 && tnode->RightChild)

{

tnode=tnode->RightChild;

}

if(tnode->LeftChild==NULL && tnode->RightChild==N

解压结束 {

output<<tnode->character;

output.flush();

tnode=bc.root;

}

压缩率：

表头Bytes+字符编码长（codelength）总和/8

总字符数Bytes

测试：

操作界面

测试文件：

l 小文件

1.英文文本：

test1.txt 《I have a dream》全文

压缩前：8.84KB

压缩后：5.51KB

压缩率：63%

测试结果：

压缩，解压成功！压缩效果不错

内容与原文件相同

英文压缩测试成功

2.中文文本：

test2.txt 《GB2312编码表》

压缩前：15.4KB

压缩后：11.6KB

压缩率：75%

测试结果：压缩，解压成功！

内容于原文件相同，无乱码

中文汉字测试成功

l 略大文件

test3.txt 《平凡的世界》

压缩前：1.62M

压缩后：1.39M

压缩率：86%

压缩时间14.23秒

解压时间 16.85秒

测试结果：压缩，解压成功！

压缩解压时间在可接受范围之内

----------------------------------------------------------

当初貌似写得挺详细

整理的时候看了下，其实

每次取7位【取8位亦可，但此处为了处理最后一个字符，只取7位】

这里就是改进的地方，因为最后一个字符的处理，导致了前面每次只取七位，造成极大浪费

改进处理：每次取8位，最后一个字符另存