1/10
文档分类:通信/电子

文本文件统计Huffman编解码.doc


下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

特别说明:文档预览什么样,下载就是什么样。

下载所得到的文件列表
文本文件统计Huffman编解码.doc
文档介绍:
JISHOU UNIVERSITY

专业课课程论文



题 目:
文本文件统计Huffman编解码


作 者:

学 号:

所属学院:
信息科学与工程学院
专业年级:
09级
总 评 分:

完成时间:
2012年10月24日




吉首大学信息科学与工程学院




文本文件统计Huffman编解码

1、编程思想
霍夫曼(Huffman)编码是1952年为文本文件而建立,是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度较短;而对于出现频率低的信息,编码长度较长。这样,处理全部信息的总码长一定小于实际信息的符号长度。
计算机编程实现时,首先统计带编码的文本文件中各个字符出现的概率,然后将概率作为节点的权值构建huffman树。编码时从叶子节点出发,如果这个节点在左子树上,则编码0,否则编码1,直到根节点为止,所得到的01序列即为该叶子节点的编码。所有叶子节点的编码构成一个码本。
有两种译码方法:(1)按位读入码字,从已建好的Huffman树的根节点开始,若码字为“0”,则跳到左子树,若为“1”则跳到右子树,直到叶子结点为止,输出叶子接点所表示的符号。(2)由于Huffman编码是唯一码,还有另一种译码方法,每读入一位编码就去码本中去匹配相应的码字,若匹配不成功,则继续读入下一个编码,直到匹配成功为止。显然前一种方法比较简便,本程序采用便是该方法。

2、程序流程图






















N
N
Y
Y
N
开始编码
读入文本文件
统计各符号概率
构建Huffman树
保存码本
读入1位码字
编码
输出编码文件
编码结束
开始译码
读入码本
定位到根节点
码字为1?
跳到右子树
译码结束
叶子结点?

跳到左子树
输出字符
Y
码字读完?




内容:
问题重述:从电脑上打开一个文件,统计其字符数及每一字符出现的频数概率,然后进行Huffman编码;编码后将其解码,并与原数据比较
算法描述:(1)统计字符数,及每一字符出现的频数和概率。创立一个足够大的字符型数组,然后遍历整个文件,将文件中每一字符拷贝到字符数组中;然后建立一个结构体类型数组p[](足够大),此类型包括三个成员char chh型的字符变量、int n型的变量用以统计每个字符出现的频数和float rate用以存储每个字符出现的概率。
(2)建立Huffman树。创建一个结构体类型如下
typedef struct


float rate;//字符出现的概率
int parent;//节点的双亲结点
int Lchild;//节点的左孩子
int Rchild;//节点的右孩子
}HTNode,*HuffmanTree;
typedef char * *HuffmanCode;
对有n个叶子节点的Huffman树共有2*n-1个节点,就可以用2*n—1个一维数组来存放各个节点,每个节点同时还包含双亲节点和孩子节点的信息,构成一个静态三叉链表.令m=2*n—1,
内容来自淘豆网www.taodocs.com转载请标明出处.