霍夫曼编码实现方法（共3篇）
霍夫曼编码实现方法 篇1
1 概述
数据压缩是信息科学中的一项重要的技术, 有着广泛的应用。它可以使存储的文件变小, 也可以提高模块之间数据交换的速度等。通常, 文件是由字符构成的, 而字符在计算机中是由二进制串表示的。这就是说, 如果字符集包含C个字符, 则在标准的等长编码中, 每个字符由┌log2c┐位的二进制串表示。但在实际应用的一些大文件中, 字符被使用的比率不是平均的, 有时甚至相差很悬殊。因此, 如果所有字符都由等长的二进制码表示, 那么将造成一定的空间浪费。为了尽量减少这种不必要的空间浪费, 解决的方法之一就是采用不等长的二进制码, 令文件中出现频率高的字符的编码尽可能短。
采用不等长编码, 又可能会产生多义性。例如:如果用“01”表示字符a, “10”表示字符b, “100”表示字符c, 那么对于编码“1001”, 无法明确指出它究竟表示字符c, 还是表示字符串“ba”, 其原因是b的编码与c的编码的前缀部分相同。为了避免出现多义性, 就必须要求字符集中任何字符的编码都不是其它字符编码的前缀, 即要求字符编码必须是前缀码。设组成文件的字符集C={c1, c2, -, cn}其中ci的编码长度为l i, ci出现的次数 (或频率) 为pi.要使文件总编码长度最短, 就必须要确定l i, 使WPL=∑ni=1pi×l i最小。WPL表示树的带权路径长度, 定义为树中的所有叶子结点的权值与叶结点的路径长乘积之和。为了设计出使WPL最小的前缀码, Huffman于1952年提出了Huffman算法。
哈夫曼 (Huffman) 编码是一种常用的压缩编码方法。它的基本原理是频繁使用的数据用较短的代码代替, 较少使用的数据用较长的代码代替, 每个数据的代码各不相同。这些代码都是二进制码, 且码的长度是可变的。
2 Huffman编解码原理
哈夫曼 (Huffman) 编码是一种常用的压缩编码方法。它的基本原理是频繁使用的数据用较短的代码代替, 较少使用的数据用较长的代码代替, 每个数据的代码各不相同。这些代码都是二进制码, 且码的长度是可变的。
哈夫曼树又称最优树 (二叉树) , 是一类带权路径最短的树, 构造这种树的算法最早是由哈夫曼1952年提出, 这种树在信息检索中很有用。哈夫曼编码是哈夫曼树的一个应用, 数据压缩过程称为编码, 即将文件中的每个字符均转换为一个惟一的二进制位串。数据解压过程称为解码, 即将二进制位串转换为对应的字符。所谓树的带权路径长度, 就是树中所有的叶结点的权值乘上其到根结点的路径长度 (若根结点为0层, 叶结点到根结点的路径长度为叶结点的层数) 。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln) , N个权值Wi (i=1, 2, ...n) 构成一棵有N个叶结点的二叉树, 相应的叶结点的路径长度为Li (i=1, 2, ...n) 。此时, 可以证明哈夫曼树的WPL是最小的。
哈夫曼编码法的特点在于其经过编码得出的档案是具有唯一码性质的实时编码。即各个不同字符编码得出的位串并不相同, 因此, 译码时能立即解出。也就是说, 哈夫曼编码法的译码过程是实时的并且是唯一的解码。
3 Huffman编码软件实现部分
3.1 软件运行环境
操作系统:Microsoft Windows XP Professional版本2002 Service Pack 2
开发软件:
EDK7.1i sp2:嵌入式集成开发环境
ISE7.1i sp4 IMPACT:将配置文件下载到FPGA的工具
串口调试工具:调试串口数据的软件工具
3.2 FPGA端Huffman数据结构定义
3.2.1 定义Huffman编码表构造的每个树结点的信息
3.2.2 记录每个符号的编码
3.2.3 保存树节点的权值和序号, 用于建树时找权值最小的两个点用
3.3 构造Huffman树
进行Huffman树构造函数, 其中还包括一个每次选择最小、次小权值接点选择的定义函数。
3.4 Huffman编码
计算机存储数据使用定长编码 (如ASCII码) , 其字符使用的频率不同, 为在计算机实现数据的压缩, 只需将全部数据的ASCII码频率做权进行Huffman编码, 使用数据前再利用Huffman树译码, 就可获得原数据, 从而大大节约存储空间。
4 Huffman编码硬件实现部分
4.1 硬件运行环境
PC机
FPGA开发板:Xilinx Virtex 2p xc2vp7
4.2 FPGA开发板
本实验使用的是Virtex-ⅡPro开发板, Power PC处理器。Power PC处理器是32位的RISC处理器, 具有嵌入式环境结构, 使用IP核嵌入技术集成到Virtex-ⅡPro开发板上。
4.3 PC机端串口配置
为了确保PC机与FPGA开发板之间能够通过串口正常通信, 正确传输数据, 则必须在PC机端对RS232串口进行配置, 使其与FPGA开发板的串口通信格式保持一致。否则, 会造成数据的丢失, 致使通信失败。
5 系统集成和测试
本实验在VirtexⅡPro开发板上完成, 借助串口进行输入、输出以测试程序的正确性, 所以在该程序中还有一些串口的操作函数。
可以根据输入的字符及权值, 画出Huffman树.然后对其编码, 再与串口的输出编码进行比较, 即可测试程序的正确性。对于解码程序的设计, 则可以是在同一棵树上对输入的串进行解码看是否正确则可测试出程序的正确性。
6 软件执行结果
编码文件输入:27.2KB的文章
压缩后为15.3KB, 压缩率为56.3%
7 结论
通过该实验, 可以进一步熟悉Xilinx开发板的功能以及如何利用Xilinx提供的集成开发环境对开发板进行编程、编译、下载、测试与调试等功能。也可以进一步了解哈夫曼编码解码的思想, 并且了解了在嵌入式开发板上进行开发的基本流程及其开发环境的配置、调试等等, 对整个流程有了一个基本的认识。
摘要：介绍了Huffman编码原理, 描述了如何利用VⅡPro开发板完成基于Huffman编码的数据压缩模块, 通过串口使PC机与开发板通信, 从而实现将给定的文件压缩成二进制文件的功能。
关键词：哈夫曼 (Huffman) 编码,VirtexⅡPro开发板,串口配置
参考文献
[1]严蔚敏.数据结构[M].北京:清华大学出版社, 1997.
[2]杨恒.FPGA/CPLD最新实用技术指南[M].北京:清华大学出版社, 2005.
霍夫曼编码实现方法 篇2
这篇文章主要介绍了go语言实现字符串base64编码的方法,实例分析了Go语言操作字符串的技巧及base64编码的使用技巧,需要的朋友可以参考下
本文实例讲述了go语言实现字符串base64编码的方法，分享给大家供大家参考。具体实现方法如下：
代码如下:
package main
import (
“fmt”
“encoding/base64”
)
func main {
var b bytes.Buffer
w := base64.NewEncoder(base64.URLEncoding, &b)
w.Write(data)
w.Close()
data := b.Bytes()
}
哈夫曼编码方法的方案选择研究 篇3
一、哈夫曼编码方法简介
最佳编码定理指出:在编码过程中, 对于信源符号, 如果出现概率大的符号分配短字长的码字, 出现概率小的符号分配长码字, 编码编码结束后, 得到的码字长度严格按照符号概率的大小的相反顺序, 那么这种编码方式得到的平均码字长度一定小于任何其他排列方式得到的码字长度。哈夫曼编码法就是利用了这个原理, 是一种典型的无失真的编码方法, 且是熵编码中的最佳编码方法。
哈夫曼编码法的过程:首先将信源按概率递减排列, 然后将最小两个概率相加, 得到的新概率再放入原概率序列中重新排列, 如此反复, 不断的缩减信源, 直至信源个数只剩一个为止。最后从最后一级缩减信源开始, 依编码路径向前返回, 并分配码字, 得到哈夫曼码。
二、哈夫曼编码方案分析与选择
根据哈夫曼编码的方法可得:哈夫曼编码法编码结果一定不唯一。首先, 缩减信源结束后, 对最小概率分配“0”和“1”是任意的;其次, 当将概率序列中的两个最小概率相加时, 得到的概率和可能与原序列中的概率相等, 此时, 概率相等的几个符号及可以任意排列, 也将导致最终的编码不唯一。那编码中究竟哪种方案更好呢?用以下这个例来分析说明。
若已知信源空间为:
编码方案一:相加后的概率排在其他相同概率符号的后面, 其编码过程如图1所示。
编码方案二:相加后的概率排在其他相同概率符号的前面, 其编码过程如图2所示。
由此看出:不同的编码方法的到的码字长度li也不尽相同, 但最终平均码长相同, 编码效率也相同, 此时如果仅靠平均码长来判断哪种方案较好是不行的, 我们可以用码长li偏离平均码长的方差来判断。
由此可见, 编码二的方差较小, 说明其码字的变化较小, 此方案较好。
三、总结
哈夫曼编码方法主要是依据最佳编码定理, 通过以上例子的分析, 我们得出结论:在编码的过程中, 对缩减信源符号按概率由大到小得顺序重新排列时, 应将相加后的新概率尽可能的排在其他相同概率之前, 这样就可以使相加后的新符号概率重复编码的次数减少, 使得短码得到充分利用。
摘要：本文首先分析了哈夫曼编码的理论根据, 介绍了哈夫曼编码的编码过程, 通过举例详细分析了不同编码方案的编码结果, 最后对不同方案的编码方法进行了总结。
关键词：哈夫曼编码,无失真编码,编码方案
参考文献
[1]陈运.信息论与编码.北京:电子工业出版社.2009
[2]姜丹.信息论与编码.合肥:中国科技技术大学出版社.2001
[3]傅祖芸.信息论与基础.北京:电子工业出版社.2006
[4]钟家恺.通信原理教程.北京:科学出版社.2003