共有回帖数 0 个
-
Huffman 编码简介
在一般的数据结构的书中树的那章后面著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码哈夫曼编码是哈夫曼树的一个应用哈夫曼编码应用广泛如JPEG 中就应用了哈夫曼编码
为什么是二叉树
为什么压缩领域中的编码方法总和二叉树联系在一起呢原因非常简单回忆一下我们介绍过的前缀编码为了使用不固定的码长表示单个字符编码必须符合前缀编码的要求即较短的编码决不能是较长编码的前缀要构造符合这一要求的二进制编码体系二叉树是最理想的选择考察下面这棵二叉树
根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a | d e
0 | 1
+-----+-----+
| |
b c
要编码的字符总是出现在树叶上假定从根向树叶行走的过程中左转为0 右转为1,则一个字符的编码就是从根走到该字符所在树叶的路径正因为字符只能出现在树叶上任何一个字符的路径都不会是另一字符路径的前缀路径符合要求的前缀编码也就构造成功了
a - 00 b - 010 c - 011 d - 10 e - 11
Shannon-Fano 编码
进入Huffman 先生构造的神奇二叉树之前我们先来看一下它的前身由Claude Shannon和R.M.Fano 两人提出的Shannon-Fano 编码讨论之前我们假定要编码字符的出现概率已经由某一模型统计出来例如对下面这串出现了五种字符的信息( 40 个字符长):
cabcedeacacdeddaaabaababaaabbacdebaceada
五种字符的出现次数分别a - 16 b - 7 c - 6 d - 6 e - 5
Shannon-Fano 编码的核心仍然是构造二叉树构造的方式非常简单
1) 将给定符号按照其频率从大到小排序对上面的例子应该得到
a - 16
b - 7
c - 6
d - 6
e - 5
2) 将序列分成上下两部分使得上部频率总和尽可能接近下部频率总和我们有
a - 16
b - 7
-----------------
c - 6
d - 6
e - 5
3) 我们把第二步中划分出的上部作为二叉树的左子树记0 下部作为二叉树的右子树记
1
4) 分别对左右子树重复2 3 两步直到所有的符号都成为二叉树的树叶为止现在我们有如下
的二叉树
根(root)
0 | 1
+------+------+
0 | 1 0 | 1
+-----+-----+ +---+----+
| | | |
a b c |
0 | 1
+-----+-----+
| |
d e
于是我们得到了此信息的编码表
a - 00 b - 01 c - 10 d - 110 e - 111
可以将例子中的信息编码为
cabcedeacacdeddaaabaababaaabbacdebaceada
10 00 01 10 111 110 111 00 10 00 10 ......
码长共91 位考虑用ASCII 码表示上述信息需要8 * 40 = 240 位我们确实实现了数据压缩
哈夫曼树:
首先介绍什么是哈夫曼树哈夫曼树又称最优二叉树是一种带权路径长度最短的二叉树所谓树的带权路径长度就是树中所有的叶结点的权值乘上其到根结点的路径长度若根结点为0 层叶结点到根结点的路径长度为叶结点的层数树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln) N 个权值Wi(i=1,2,...n)构成一棵有N 个叶结点的二叉树相应的叶结点的路径长度为Li(i=1,2,...n) 可以证明哈夫曼树的WPL 是最小的哈夫曼在上世纪五十年代初就提出这种编码时根据字符出现的概率来构造平均长度最短的编码它是一种变长的编码在编码中若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列则编码的平均长度是最小的注码字即为符号经哈夫曼编码后得到的编码其长度是因符号出现的概率而不同所以说哈夫曼编码是变长的编码
Huffman 编码
Huffman 编码构造二叉树的方法和Shannon-Fano 正好相反不是自上而下而是从树叶到树根生成二叉树现在我们仍然使用上面的例子来学习Huffman 编码方法
1) 将各个符号及其出现频率分别作为不同的小二叉树目前每棵树只有根节点
a(16) b(7) c(6) d(6) e(5)
2) 在1 中得到的树林里找出频率值最小的两棵树将他们分别作为左右子树连成一棵大一些的二叉树该二叉树的频率值为两棵子树频率值之和对上面的例子我们得到一个新的树林
| (11)
a(16) b(7) c(6) +---+---+
| |
d e
3) 对上面得到的树林重复2 的做法直到所有符号都连入树中为止这一步完成后我们有这样的二叉树
根(root)
0 | 1
+------+----------------+
| 0 | 1
| +---------+-----------+
| 0 | 1 0 | 1
a +-------+------+ +-------+-------+
| | | |
b c d e
由此我们可以建立和Shannon-Fano 编码略微不同的编码表
a - 0 b - 100 c - 101 d - 110 e - 111
对例子中信息的编码为
cabcedeacacdeddaaabaababaaabbacdebaceada
101 0 100 101 111 110 111 0 101 0 101 ......
码长共88 位这比使用Shannon-Fano 编码要更短一点
让我们回顾一下熵的知识使用我们在第二章学到的计算方法上面的例子中每个字符的熵
为
Ea = - log2(16 / 40) = 1.322
Eb = - log2( 7 / 40) = 2.515
Ec = - log2( 6 / 40) = 2.737
Ed = - log2( 6 / 40) = 2.737
Ee = - log2( 5 / 40) = 3.000
信息的熵为
E = Ea * 16 + Eb * 7 + Ec * 6 + Ed * 6 + Ee * 5 = 86.601
也就是说表示该条信息最少需要86.601 位我们看到Shannon-Fano 编码和Huffman 编码都已经比较接近该信息的熵值了同时我们也看出无论是Shannon-Fano 还是Huffman 都只能用近似的整数位来表示单个符号而不是理想的小数位我们可以将它们做一个对比符号理想位数S-F 编码Huffman 编码
( 熵) 需要位数需要位数
----------------------------------------------------
a 1.322 2 1
b 2.515 2 3
c 2.737 2 3
d 2.737 3 3
e 3.000 3 3
----------------------------------------------------
总计86 601 91 88
这就是象Huffman 这样的整数位编码方式无法达到最理想的压缩效果的原因
哈夫曼算法
然而怎样构造一棵哈夫曼树呢最具有一般规律的构造方法就是哈夫曼算法一般的数据结构的书中
都可以找到其描述
一对给定的n 个权值{W1,W2,W3,...,Wi,...,Wn}构成n 棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn} 其中每棵二叉树Ti 中只有一个权值为Wi 的根结点它的左右子树均为空为方便在计算机上实现算法一般还要求以Ti 的权值Wi 的升序排列二在F 中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树新二叉树的根结点的权值为其左右子树的根结点的权值之和三从F 中删除这两棵树并把这棵新的二叉树同样以升序排列加入到集合F 中四重复二和三两步直到集合F 中只有一棵二叉树为止用C 语言实现上述算法可用静态的二叉树或动态的二叉树若用动态的二叉树可用以下数据结构
struct tree
{
float weight; /*权值*/
union
{
char leaf; /*叶结点信息字符*/
struct tree *left; /*树的左结点*/
};
struct tree *right; /*树的右结点*/
};
struct forest
{ /*F 集合以链表形式表示*/
struct tree *ti; /* F 中的树*/
struct forest *next; /* 下一个结点*/
};
例若字母A B Z C 出现的概率为0.71,0.54,0.28,0.43 则相应的权值为75 54 28 43构造好哈夫曼树后就可根据哈夫曼树进行编码例如上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后经哈夫曼编码得到的对应的码值只要使用同一棵哈夫曼树就可把编码还原成原来那组字符显然哈夫曼编码是前缀编码即任一个字符的编码都不是另一个字符的编码的前缀否则编码就不能进行翻译例如a,b,c,d 的编码为0 10 101 11 对于编码串1010 就可翻译为bb 或ca 因为b 的编码是c 的编码的前缀刚才进行哈夫曼编码的规则是从根结点到叶结点包含原信息的路径向左孩子前进编码为0 向右孩子前进编码为1 当然你也可以反过来规定这种编码方法是静态的哈夫曼编码它对需要编码的数据进行两遍扫描第一遍统计原数据中各字符出现的频率利用得到的频率值创建哈夫曼树并必须把树的信息保存起来即把字符0-255(2^8=256)的频率值以2-4BYTES 的长度顺序存储起来用4Bytes 的长度存储频率值频率值的表示范围为0--2^32-1 这已足够表示大文件中字符出现的频率了以便解压时创建同样的哈夫曼树进行解压第二遍则根据第一遍扫描得到的哈夫曼树进行编码并把编码后得到的码字存储起来Huffman 编码模型最简单最容易被Huffman 编码利用的模型是静态统计模型也就是说在编码前统计要编码的信息中所有字符的出现频率让后根据统计出的信息建立编码树进行编码这种模型的缺点是显而易见的首先对数据量较大的信息静态统计要消耗大量的时间其次必须保存统计出的结果以便解码时构造相同的编码树或者直接保存编码树本身而且对于每次静态统计都有不同的结果必须分别予以保存这要消耗大量的空间这意味着压缩效率的下降再次事实上即使不将编码树计算在内对通常含有0 - 255 字符集的计算机文件来说静态统计模型统计出的频率是字符在整个文件中的出现频率往往反映不出字符在文件中不同局部出现频率的变化情况使用这一频率进行压缩大多数情况下得不到太好压缩效果文件有时甚至在压缩后反而增大了所以静态统计模型一般仅作为复杂算法的某一部分出现在信息的某一局部完成压缩功能我们很难将其用于独立的压缩系统有一种有效的静态统计模型的替代方案如果我们要压缩的所有信息具有某些共同的特性也即在分布上存在着共同的特征比如我们要压缩的是普通的英文文本那么字母a 或者字母e 的出现频率应当是大致稳定的使用语言学家事先已经建立好的字母频率表来进行压缩和解压缩不但不用保存多份统计信息而且一般说来对该类文件有着较好的压缩效果这种方案除了适应性不太强以外偶尔还会有一些尴尬的时候读一遍下面这段话
If Youth throughout all history had had a champion to stand up for it to show a
doubting world that a child can think and possibly do it practically you
wouldn't constantly run across folks today who claim that "a child don't know
anything." - Gadsby by E.V.Wright, 1939.
发现什么问题了吗哦整段话中竟没有出现一次英文中出现频率最高的字母e 真让人惊讶但没有办法事先拟定的频率分布总有意外的时候
对英文或中文文本有一种比较实用的静态模型不是把字符而是把英文单词或中文词语作为统计频率和编码的单位进行压缩也就是说每次编码的不再是a b c 这样的单个符号而是the look flower 这样的单词这种压缩方式可以达到相当不错的压缩效果并被广泛地用于全文检索系统对基于词的编码方式需要解决几个技术难点首先是分词的问题英文单词可以由词间空格分隔但中文怎么办呢其实有很多中文分词算法可以解决这个问题本书就不再详细介绍了王笨笨就曾开发过一个不错的分词模块但希望通过收取一定报酬的方式提供该模块如有需要请和王笨笨E-Mail 联系一旦我们将词语分离出来我们就可以对每个词进行频率统计然后建立Huffman 编码树输出编码时一个编码将代替一个词语但要注意英文和汉语的单词数量都在几万到十几万左右也就是说我们的Huffman 编码树将拥有十几万个叶子节点这对于一棵树来说太大太大了系统将无力承担所需要的资源这怎么办呢我们可以暂时抛开树结构采用另一种构造Huffman 编码的方式范式Huffman 编码范式Huffman 编码(Canonical Huffman Code)的基本思路是并非只有使用二叉树建立的前缀编码才是Huffman 编码只要符合(1)是前缀编码(2)某一字符编码长度和使用二叉树建立的该字符的编码长度相同这两个条件的编码都可以叫做Huffman 编码考虑对下面六个单词的编码
符号出现次数传统Huffman 编码范式Huffman 编码
------------------------------------------------------------
单词1 10 000 000
单词2 11 001 001
单词3 12 100 010
单词4 13 101 011
单词5 22 01 10
单词6 23 11 11
注意到范式Huffman 编码的独特之处了吗你无法使用二叉树来建立这组编码但这组编码确实能起到和Huffman 编码相同的作用而且范式Huffman 编码具有一个明显的特点当我们把要编码的符号按照其频率从小到大排列时如果把范式Huffman 编码本身作为单词的话也呈现出从小到大的字典顺序
构造范式Huffman 编码的方法大致是
1) 统计每个要编码符号的频率
2) 根据这些频率信息求出该符号在传统Huffman 编码树中的深度也就是表示该符号所需要的位数- 编码长度因为我们关心的仅仅是该符号在树中的深度我们完全没有必要构造二叉树仅用一个数组就可以模拟二叉树的创建过程并得到符号的深度具体方法这里就不详述了3) 分别统计从最大编码长度maxlength 到1 的每个长度对应了多少个符号根据这一信息从maxlength 个0 开始以递增顺序为每个符号分配编码例如编码长度为5 的符号有4 个长度为3 的有1 个长度为2 的有3 个则分配的编码依次为00000 00001 00010 00011001 01 10 11
4) 编码输出压缩信息并保存按照频率顺序排列的符号表然后保存每组同样长度编码中的最前一个编码以及该组中的编码个数,现在完全可以不依赖任何树结构进行高速解压缩了而且在整个压缩解压缩过程中需要的空间比传统Huffman 编码少得多,最后要提到的是Huffman 编码可以采用自适应模型根据已经编码的符号频率决定下一个符号的编码这时我们无需为解压缩预先保存任何信息整个编码是在压缩和解压缩过程中动态创建的而且自适应编码由于其符号频率是根据信息内容的变化动态得到的更符合符号的局部分布规律因此在压缩效果上比静态模型好许多但是采用自适应模型必须考虑编码表的动态特性即编码表必须可以随时更新以适应符号频率的变化对于Huffman 编码来说我们很难建立能够随时更新的二叉树使用范式Huffman 编码是个不错的选择但依然存在不少技术上的难题幸好如果愿意的话我们可以暂时不考虑自适应模型的Huffman 编码因为对于自适应模型我们还有许多更好的选择下面几章将要谈到的算术编码字典编码等更为适合采用自适应模型我们将在其中深入探讨自适应模型的各种实现方法
静态哈夫曼编码方法有一些缺点
一对于过短的文件进行编码的意义不大因为光以4BYTES 的长度存储哈夫曼树的信息就需1024Bytes 的存储空间二进行哈夫曼编码存储编码信息时若用与通讯网络就会引起较大的延时三对较大的文件进行编码时频繁的磁盘读写访问会降低数据编码的速度,因此后来有人提出了一种动态的哈夫曼编码方法动态哈夫曼编码使用一棵动态变化的哈夫曼树对第t+1 个字符的编码是根据原始数据中前t 个字符得到的哈夫曼树来进行的编码和解码使用相同的初始哈夫曼树每处理完一个字符编码和解码使用相同的方法修改哈夫曼树所以没有必要为解码而保存哈夫曼树的信息编码和解码一个字符所需的时间与该字符的编码长度成正比所以动态哈夫曼编码可实时进行动态哈夫曼编码比静态哈夫曼编码复杂的多有兴趣的读者可参考有关数据结构与算法的书籍前面提到的JPEG 中用到了哈夫曼编码并不是说JPEG 就只用哈夫曼编码就可以了而是一幅图片经过多个步骤后得到它的一列数值对这些数值进行哈夫曼编码以便存储或传输哈夫曼编码方法比较易懂大家可以根据它的编码方法自己编写哈夫曼编码和解码的程序
用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构：
struct tree{
float weight; /*权值*/
union{
char leaf; /*叶结点信息字符*/
struct tree *left; /*树的左结点*/
};
struct tree *right; /*树的右结点*/
};
struct forest{ /*F集合，以链表形式表示*/
struct tree *ti; /* F中的树*/
struct forest *next; /* 下一个结点*/
};
例：若字母A，B，Z，C出现的概率为：0.71,0.54,0.28,0.43；则相应的权值为：75，54，28，43。
楼主 2016-02-19 16:27 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
