哈弗曼编码根据词频译码

院系：计算机学院

实验课程：数据结构预算法

实验项目：哈弗曼树综合实验

指导老师：

开课时间：2009 ～ 2010年度第1学期专业：计算机类

班级：08本6班

学生：

学号：

华南师范大学教务处

华南师范大学实验报告

学生姓名禤欢子学号20082100173

专业计算机类年级、班级08本6 班

课程名称数据结构与算法分析实验项目哈弗曼树综合实验

实验时间2009年12月25日指导老师黄定

实验评分

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

【需求分析】

本实验需要设计程序，输入叶子结点和权值，建立一颗哈弗曼树，并根据哈弗曼树进行编码和译码操作。键盘中输入或者从文件中读入哈弗曼树；键盘中输入或者从源文件中读入需要编码的源文，然后将源文根据哈弗曼树的权值，译码为二进制代码。最后实现凹入显示法显示哈弗曼树。

【概念设计】

本程序由HaffmanTree.h、HaffmanTree.cpp、main.cpp三个文件构成。HaffmanTree.h中定义了哈弗曼树的储存结构体HaffmanNod

实验题目：哈弗曼编码译码

实验目的:（1）熟悉对文件的有关操作

（2）掌握哈弗曼树的概念和存储结构 （3）利用哈弗曼方法对指定文件进行编码和译码

实验内容：给定一个电文文件进行编码，编码后进行哈弗曼译码，译码后的结果

存储在文件2中，对文件2进行解码并将结果储存在文件3中。

一、需求分析

1.本实验需要先给出一个文件1.txt，程序对文件进行统计，构造哈弗曼树，进行哈弗曼编码和解码的相关操作。

2.程序应能输出字符的及每个字符的个数，并输出每个字符的哈弗曼编码 3.程序能将哈弗曼编码后的文件存储在2.txt中，并将解码文件存储在3.txt中

二、概要设计

为了完成本次实验，应以树为存储结构： 首先设计结构体 typedef struct{ int weight;

int parent,lchild,rchild; }HTNode,HuffmanTree;

其中： weight:权值域,保存该结点的权值;

lchild:指针域,保存该结点的左孩子结点在数组中的下标; rchild:指针域,保存该结点的右孩子结点在数组中的下标; pa

课 程 设 计 说 明 书

课程名称：数据结构与算法 设计题目：哈夫曼编\\译码器 院系：计算机科学与信息工程学院 学生姓名：刘文杰

学号： 16031210229 专业班级：软件工程16-2 指导教师：孙高飞

2017年 12 月 11日

设计题目 哈夫曼编\\译码器 限定人数 3 采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度不小于5000字节。 读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。 设字符集及频度如下表： 问题描述 字符 空格 A B C D E F G H I J 1 K L M 5 32 20 频度 186 64 13 22 32 103 21 15 47 57 字符 N O P Q R 1 S T U V W X Y Z 8 18 1 16 1 频度 57 63 15 48 51 80 23 1、根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码 2

华北水利水电大学 数据结构 实验报告

2013 ～2014 学年 第 一 学期 级 计算机科学与技术专业

班级： 学号： 姓名：

实验三：哈夫曼编/译码器

一． 实验目的

掌握哈夫曼树编码原理

二．实验内容

根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码。 基本要求：

（1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树。对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码。

（2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈夫曼编码（写入文件）。 （3）计算压缩比（选作） （4）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串。（选作）

测试数据：对字符串{casbcatbsatbat}进行编码；对电文“1101000”译码。字符集D={ ？},出现频率为w={？}

三． 程序源代码

#include #include #include

华北水利水电大学 数据结构 实验报告

2013 ～2014 学年 第 一 学期 级 计算机科学与技术专业

班级： 学号： 姓名：

实验三：哈夫曼编/译码器

一． 实验目的

掌握哈夫曼树编码原理

二．实验内容

根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码。 基本要求：

（1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树。对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码。

（2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈夫曼编码（写入文件）。 （3）计算压缩比（选作） （4）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串。（选作）

测试数据：对字符串{casbcatbsatbat}进行编码；对电文“1101000”译码。字符集D={ ？},出现频率为w={？}

三． 程序源代码

#include #include #include

问题解析与解题方法

问题分析：

设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。 （1） 从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）；

（2） 统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）； （3） 根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；

（4） 将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf） （5） 用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率； （6） 进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。

根据上述过程可以知道该编码译码器的关键在于字符统计和哈夫曼树的创建以及解码。

哈夫曼树的理论创建过程如下： 一、构成初始集合

对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合

F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 二、选取左右子树

在F中选取两棵根结点权值

人生充满着期待，梦想连接着未来。 一、需求分析 目前

进行快速远距离通信的主要手段是电报

即将需传送的文字转化成由二级制的字符组成的字符串 例如

假设需传送的电文为\它只有4种字符 只需两个字符的串 便可以分辨

假设A、B、C、D、的编码分别为00 01

10和11

则上述7个字符的电文便为\总长14位 对方接受时

可按二位一分进行译码

当然 在传送电文时

希望总长尽可能地短

如果对每个字符设计长度不等的编码

且让电文中出现次数较多的字符采用尽可能短的编码 则传送电文的总长便可减少

如果设计A、B、C、D的编码分别为0 00 1 01

则上述7个字符的电文可转换成总长为9的字符串\但是

这样的电文无法翻译

例如传送过去的字符串中前4个字符的字串\就可以有很多种译法 或是\或者\或者\等 因此

若要设计长短不等的编码

则必须是任一字符的编码都不是另一个字符的编码的前缀 这种编码称作前缀编码

然而

如何进行前缀编码就是利用哈夫曼树来做 也就有了现在的哈夫曼编码和译码

二、概要设计

利用哈夫曼树编/译码 （一）、建立哈夫曼树 （二）、对哈夫曼树进行编码 （三）、输出对应字符的编码 （四）、译码过程

主要代码实现：

struct

实验五 哈夫曼编码与译码的设计与实现

一、问题描述

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。

基本要求：

（1）接收原始数据：从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件nodedata.dat中。

（2）编码：利用已建好的哈夫曼树（如不在内存，则从文件nodedata.dat中读入），对文件中的正文进行编码，然后将结果存入文件code.dat中。

（3）译码：利用已建好的哈夫曼树将文件code.dat中的代码进行译码，结果存入文件textfile.txt中。

（4）打印编码规则：即字符与编码的一一对应关系。 （5）打印哈夫曼树：将已在内存中的哈夫曼树以直观的方式显示在终端上。

二、数据结构设计 1、

构造哈夫曼树时，使用静态链表作为哈夫曼树的存储。

在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可

实验名称 实验日期 实验六 哈夫曼编码和译码的算法设计与实现

实验方案 实验操作 实验成绩 2012-04-22 实 验 信息系统设计与仿室 真室I 实验台号 34号 班级姓信工11-1BF 李煌名 峰

实验结果

一、实验目的

1、根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法； 2、编程实现哈夫曼编译码器； 3、掌握贪心算法的一般设计方法。

二、预习与参考

1、认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理; 2、设计和编制哈夫曼编译码器。 [参考数据类型或变量] typedef ElemType char； typedef struct node{ int w; int flag; ElemType c;

struct node *plink,*llink,*rlink;

char code[m]; }Node;

Node *num[n], *root; [参考子程序接口与功能描述]

void SetTree( NODE *root )

功能: 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树 void En

安徽大学

本科毕业论文（设计、创作）

题 目： 哈夫曼编码与算术编码压缩效率比较 学生姓名： 李伟 学号： E20714134 院（系）： 计算机科学与技术 专业： 软件工程 入学时间： 2007 年 9 月 导师姓名： 韩莉 职称/学位： 讲师/硕士 导师所在单位： 安徽大学计算机科学与技术学院 完成时间： 2011 年 5 月

哈夫曼编码与算术编码压缩效率比较

摘要

算术编码和哈夫曼编码都利用信源符号的概率分布特性进行编码，使平均码长逼近信息 熵是压缩编码算法的第一要求，算术编码比哈夫曼编码逼近信息熵的能力要强，但是编码效率和实现往往是一对矛盾，编码效率的提高，往往要在实现上付出代价，所以，选择压缩算 要权衡这两点。本论文开篇先引入了信息论的一些概念，因为编码理论发源于信息论，是各 种编码算法的数学基础。然后在第2章分析了算术编码原理，并从无限精度的算术编码原理 过渡到在计算机上能够实现的二进制编码原理。在第3章紧接着介绍了哈夫曼编码原理，并 讨论了怎样