Huffman算法是一种用来构造最优前缀码(Huffman编码)的贪心算法。Huffman编码是一种被广泛应用而且有效的数据压缩技术,它主要针对字符文件的压缩。
Huffman算法可能产生具有不同编码的最优前缀码,这句话需要这么理解:最优前缀码之所以称为最优是因为它的代价是最小的,但是具有最小代价的编码可能不止一种,而Huffman算法恰恰可以产生多种形式的最优前缀码(代价是相同的)。
Huffman(C)
/* C是待编码的字符集合,|C|=n,对于任意c∈C,c在文件中的出现频度为f(c)。Q是一个最小优先级队列。Q在具体实现时可以考虑采用最小二叉堆。
该算法自底向上地构造一棵最优前缀码所对应的树T*/
n ← |C|
Q ← C
for i ← 1 to n-1
do
allocate a new node z
left[z] ← x ← Extract-Min(Q)
right[z] ← y ← Extract-Min(Q)
f[z] ← f[x] + f[y]
Insert(Q, z)
return Extract-Min(Q) // return the root of the tree
上面过程所产生的树称为Huffman树,它是一棵满树(树中的每个非叶结点都有两个子结点),满树也是最优编码的充分条件。非叶结点的左枝上编码0,右枝编码1,每个叶子结点的编码是从根结点到该叶子结点的枝上的0、1串构成。
新节点z以x和y分别作为其左右子结点,由于左右的次序是任意的,因而Huffman算法得到的最优前缀码不唯一。Huffman算法的时间复杂度为O(n)。
Huffman算法为什么属于贪心算法?
Huffman树的构建过程实际上是对最小频度的字符的贪心选择上进行的,具有|C|个字符的字符集需要执行|C-1|次合并得到Huffman树,每次合并的时候选择最小频度的两个叶结点(包括合并后新产生的结点),而若用频度表示代价,则在每一步所有可能的合并中,Huffman总是选择一个代价最小的合并,此即为贪心。
分享到:
相关推荐
具体实现Huffman算法的源程序,比较适合新学数据结构的人学习。
Huffman算法的分析与改进
huffman进行编码,解码根据Huffman算法编写一个对文件进行压缩和解压缩的程序。该程序可以对所有的文件类型进行压缩,压缩之后的文件后缀名为huff。
一种应用广泛是算法,虽然简单;但是比较重要
用huffman算法实现的压缩代码 TXT文档
huffman算法 huffman生成和编码演示 这个也是一个不错的例子 可以参考参考
编写基于 Huffman 算法的压缩和解压缩程序。你的程序应该能够压缩任意文件,并能无损解压。 实验内容 压缩文件:根据 ASCII 码文件中各 ASCII 字符出现的频率情况创建 Huffman 树,再将各字符对应的哈夫曼编码写入...
java实现huffman算法 ~可以在控制台输入字符串编码~
简单的算法实现,可以实现任意的最优二叉树的生成(生成的二叉树不唯一)
许多按照高性能思想设计出的DSP 处理器, 其性能却在应用中得不到很好的发挥。深入分析DSP 处理器的指令编码就会发现, ...在分别讨论、比较了两种方式后, 提出了一种基于Huffman 算法的能够提高编码效率的指令编码方法。
基于LZ77算法和Huffman算法的GZIP压缩C++源码+文档说明 前言 文件压缩概念 数据压缩是指在不丢失有用信息的前提下,缩减数据量以减少存储空间,提高其传输、存储和处理效率,或按照一定的算法对数据进行重新组织,...
这是利用huffman算法 对一个tmp图像进行编码 然后再解码
基于C++、文件操作和Huffman算法实现图片压缩源码+使用说明+详细注释+sln解决方案.zip ——使用C++、文件操作和Huffman算法实现“图片压缩程序”。 ## 1. 核心知识 (1) 树的存储结构 (2) 二叉树的三种遍历方法...
huffman算法实现.doc
Huffman算法的压缩程序(C#实现),含有详尽代码以及注释
Huffman算法的优势就在于对于权值的处理,因此,如果被压缩的字符出现的次数差别很小的时候,它的效率会大打折扣。 此文件压缩主要分为以下两个部分: 压缩: 统计字 - 不懂运行,下载完可以私聊问,可远程教学 该...
很快,很好!压缩用, C++源码!用于文件压缩的huffman算法.rar
第8章贪心算法-Huffman算法,java考试参考资料,大家踊跃下载。
c++版的字符串加解密程序,huffman算法