Huffman编码算法的数学模型依赖于Huffman Tree
Huffman Tree的定义?
假设有n个权值{w1,w2,w3......wn},试构造一棵有n个叶子节点的二叉树(节点总数为m=2*n-1),每个叶子带权值为wi,其中WPL(树带权路径)最小的二叉树成为Huffman树或者最优二叉树。在一些判断性问题中,可以利用Huffman树得到最佳的判断算法,比如编制一个将百分制转换为五分制问题(参见《数据结构》清华版p144)。如有10000个输入数据,一般二叉树的判断过程需要31500次判断操作,而最优二叉树只需22000次。
如何构造Huffman Tree?
(1)根据给点的n个权值{w1,w2,w3.....wn}构成n棵二叉树的集合F={T1,T2,T3......Tn},其中每棵二叉树只有个带有权值Wi的根节点,其左右子树为空。
(2)在F中选取两棵根结点的权值最小的树作为左右子树构造一个新二叉树,新根权值为左右子树权值之和。
(3)在F中delete掉这两棵树,插入新二叉树到F中。
(4)重复(2)和(3),直到F中只含一棵树,此数位Huffman Tree。
Huffman编码?
广泛运用在电报中,电报传送将文字转换为由二进制字符组成的字符串。如电文为 ” A B A C C D A" 4个字母只需2个字符可以分别,A B C D 分别为 00 01 10 11,则电文编码成 ”00010010101100“ 。但我们总喜欢编码尽可能的短,则可以采用不等长的编码进行表示,但必须保证任一个字符的编码不是另一个字符编码的前缀,否则无法译码。我可以用二叉树达到这个目的。让A B C D作为二叉树的节点,约定左分支为”0“,右分支为”1“,从根节点到叶子节点的路径上分支组成的字符串为叶子节点字符的编码。如此得到的编码并无前缀问题。同时在电文中,将每个字符出现的次数作为叶子节点的权值,优化该二叉树为最优二叉树使得其WPL值最小,则可以使电文编码最短。
Huffman编码实现:
字符序列为 A B C D,对应的权值为 1,3,6,9,设计Huffman树,并输出对应的Huffman编码。
此算法中Huffman树的存储结构为一个n行4列的二维数组,定义如下:
定义一个HuffmanTree变量HT,初始化HT。将每一个叶子结点的双亲结点,左孩子,右孩子初始化为0。假如有n个叶子结点,则总结点数为m=2*n-1,则还有n-1个非叶结点,也将其双亲结点初始化为0。
初始化后的HT数组状态:
初始化后就可以构造huffman树了,依次选择2个权值最小的叶子结点,分别作为左子树结点和右子树结点,修改它们的双亲结点域,使它们指向同一个非叶子节点,同时其他此结点的权值为左右权值之和。重复操作n-1次,就可以得到一个huffman树。
- 大小: 8 KB
- 大小: 20.4 KB
- 大小: 15.3 KB
- 大小: 27.1 KB
- 大小: 14.9 KB
分享到:
相关推荐
基于C语言的自适应Huffman编码算法分析及实现研究.pdf
基于C语言实现Haffman编码 实现文件加密,解密。用01代码来表示不同字符,从来实现加密,解密
huffman编码 c语言实现过程 c语言
实验目的:熟练掌握二叉树应用(Huffman编码)的基本算法实现。 实现功能:对输入的一串电文字符实现Huffman编码,再对Huffman编码生成的代码串进行译码,输出电文字符串。实现功能如下: • Huffman树的建立 ...
包括文件的导入,huffman树的建立,打印,编码与解码。有算法的详细分析,流程图,原代吗,运行结果。
这是利用huffman算法 对一个tmp图像进行编码 然后再解码
用c语言来实现多元的霍夫曼编码,元数n任意输入,概率个数任意输入。霍夫曼编码(Huffman Coding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。
利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的...
通过二进制流读入文件,然后以字节计算统计的方式进行文件的压缩,压缩算法使用huffman,
用C语言实现了Huffman编码,并对同一个文本文件进行压缩和解压缩,文本文件仅限于英文文件。解压缩后的文件跟原文件一样。压缩较大的文件效果明显,但是仅压缩1个字节或者非常少的字节文件会增大文件。
本文是关于信息论中哈夫曼编码的c语言和matlab实现,注意文档不能编辑,需逐行输入,不能复制。对于c实现注意需建立两个文件*.h和*.c文件。
实现了Huffman编码算法: 1、使用链表结构。 2、使用《数据结构》(严蔚敏,C语言版)中给出的算法; 3、增加预先排序的功能的算法
代码实现huffman图像压缩的过程:从内存中读出图像数据,...形成huffman编码;对图像数据就行huffman编码压缩;将压缩后的数据存入内存;再将该数据进行解码解压。可将解压后的数据与原数据进行对比,是完全一致的。
C语言实现赫夫曼树的构建及赫夫曼编码的源代码,配合我的CSDN博客:http://blog.csdn.net/ns_code/article/details/19174553中的讲解,帮助你掌握Huffman编码的算法实现
赫夫曼编码, 时间空间复杂度很合理,我大二时编写的
c语言数据结构中经典算法,Huffman编码c的实现!!!!!
编程语言:C语言 Huffman树的建立方法 Huffman编码的方法 Huffman译码算法 注:包含C语言源程序、运行结果
huffman编码,ajax读取文件二进制,对读取的数据进行huffman编码 压缩、解压
自适应Huffman的编码和解码算法,在VS环境下可运行。