本文主要介绍一下霍夫曼编码,
Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码
先说一下背景,编码的含义:
给出定义:
待编码字符集S:待编码的字符的集合
待编码序列s:一个字符序列,其中每个字符来自带编码字符集
编码字符集S':用于编码的字符的集合
编码方法:对S中的每个字符,给定一个唯一对应的序列,其中序列中每个字符来自S'
举例来说:
S={a,b,c,d,f} 可以是一个 待编码字符集
abbcdaf 是一个待编码序列
S'={0,1} 是一个编码字符集
编码可以理解为一个映射关系,比如
a -> 0
b -> 1
c-> 01
d-> 10
f->001
那么编码方法可以看成一个函数,实际上的编码过程,就是
把序列s中的字符,依次按照编码方法映射为编码字符序列的过程;
比如 abbcdaf 经过上述编码方法编码后变为:
01101100001
如果编码字符集S' ={0,1} ,则称为2进制编码;
编码长度:对于待编码序列s;其中每个字符经过编码方法编码后,所得到的的最终序列的总长度
其中因为可能是相同字符,它们对应的l也相等;
进一步,可以求出相对长度,其实就是 , 表示编码序列的总长度;因此,如果某个字符在中出现的频率为
则编码相对长度公式如下:
i遍历所有不同的字符集合,后文中不加说明都是指相对长度
以上就是编码定义;
下面介绍两种编码方式,
定长编码,不定长编码;
定长编码很好理解:每个字符经过编码方法之后的映射字符序列都是固定长度的;不定长就是长度不固定;
上述范例中的是不定长编码;
下面说说定长和不定长的区别:
首先,编码就意味着要解码,对于定长来说,只要编码方法和固定长度的大小,解码相当容易,隔固定间隔读取,再做逆向映射就ok了;
但对于不定长编码,可能出现冲突;
比如 a编码为 0
b编码为1
c编码为01
此时如果我收到一个编码后的序列为 01,
那么有两种可能,原序列为ab 或者原序列为c,这两种都合理,将无法正确解码;
不定长既然有这种缺陷,为何实际编码还是用不定长,原因就是不定长编码能够节省空间;
举例来说,如果有8个不同字符,用定长编码,每个字符的编码长度至少为3;()
但如果不定长编码,可以少一些,后文中将会给出一个例子;
那么不定长编码的缺陷怎么解决,我们发现之所以出现上述缺陷,一个主要原因在于,某些编码恰好是另外一个编码的前缀;
比如0是 01的前缀,如果不定长编码可以保证编码后的字符序列中没有一个是另外一的前缀,则这个问题就可以解决了;
满足这种条件的编码叫做前缀编码;
当然即使不是前缀编码,有没有办法让它可以正确解码,也是有的,但是这里为了简化先不讨论这种情况;
下面给出最优编码的定义;
就是给定一个序列,设计一种不定长编码方法,使得这个序列按照这个编码方法编码后的长度最小;(前提当然是要可以正确解码)
可以证明(略)最优编码方式可以在前缀编码中取到,因此我们可以只考虑前缀编码中的最优方式;
那么具体的最优编码是什么,就是本文主题,霍夫曼编码,就是最优前缀编码(也是最优编码)
在讲解霍夫曼编码之前,先说一下编码树的概念:
我们只考虑2进制编码,
显然大家都知道2叉树,
那么如果我给定一个完全无穷极2叉树,根节点不放值,左节点存0,右节点存1,
则任何一种2进制编码比如 0100101,我们可以把它在该树中的路径画出来;经历过的节点标上记号;
对于所有字符的所有编码,我们把这些路径上的节点全部标上记号(已经有的不用重复标记)
之后把这个无穷2叉树剪裁,只保留那些标记颜色的节点,得到一个2叉树,这个树,就是该编码的编码树;
比如我们上面的demo,这个树长这样:
(0) (1)
0 (1) (0)
(1)
我们有些节点打上了括号,表示这个节点对应的路径对应着一个编码,从图中可以看出,显然前缀编码意味着所有打括号的节点都是叶子节点,(这是因为叶子节点一定有括号,这一点是显然的,如果有不是叶子节点的节点右括号,它下面的叶子节点也有括号,便和前缀编码相矛盾了)
这样每一种编码,尤其是前缀编码,都可以用一个编码树来描述,前缀编码的编码树连括号都不需要用,因为默认都在叶子节点,则一个编码树(无括号)可以完全对应一种前缀编码
有了以上基础,我们来描述,霍夫曼编码,显然只需要把它的编码树结构描述清楚,霍夫曼编码也就描述清楚了,霍夫曼编码的编码树构造方法如下:
1,输入序列s,
首先计算s中出现的每个字符出现的频率,并且按照从小到大排序;
2,找到最小的两个,分别赋值0,1作为左右2个节点,并生成其父节点,其值取为两者的和,(这一次操作称为合并)
3,从S中去掉这两个字符,把这个父节点看成一个新字符加入到S中,其对应频率为两者的合,再重复上述过程,
4,如果在生成节点的过程中发现某个字符是新生成的,则直接拿这个字符对应的节点来用并保留其子节点
下面举个例子:
a:10 b:3 , c: 5 d:1
这是出现频率
先取 b,d 标记为0,1
合并频率为 4(新字符记录为bd),变为
a:10 bd:4 c:5
再去bd 和 c 合并,新字符可记为c',频率为9,最后和a合并;
对应树如下:
root
0(c') 1(a)
0(bd) 1(c)
0(b) 1(d)
这个树对应的就是霍夫曼编码,除了叶子节点是原字符集中的,其余的是新生成的中间字符不用考虑;
编码如下:
a :1
b:000
c:01
d:001
长度计算公式为:
那么这个编码方式的编码长度为何最短?
终于可以说的全文最关键的部分,下面给出一个简明的证明:
首先,给出几个引理:
1,最优编码下,频率越小的字符编码必然越长
证明:如果不是这样,比如字符x的频率fx < 字符y的频率fy
并且它们在树中的路径长度(编码长度)lx<ly
显然,我们可以交换这两个字符在树中的位置(也就是交换它们的编码方式)得到一个新的前缀编码方式,
由于其他的不变,考虑这两者的编码长度差:就是
fxlx+fyly-(fxly+fylx) = (lx-ly)(fx-fy) >0,说明后者的编码长度更小
矛盾;
2,最优编码下,频率最小的那两个字符的编码长度相等
证明:根据1,如果不是这样,则频率最小那个字符将有一个独一无二的最长的编码路径l,那么我们可以调整编码方式,把字符编码(对应某个叶子节点)的父节点作为其编码,并去掉该节点,那么这个新的叶子节点对应的路径必然不是其他字符编码的前缀,这是因为其他的长度l'<=l-1,如果新叶子节点是其他字符编码的前缀,则只有一种可能l'=l-1,这意味着这个其他字符的编码就是该编码,那它就是原来的最优编码的那个节点的前缀,矛盾;
同时其他编码不是它的前缀是显然的;
现在我们看霍夫曼编码方式:
首先从构造方式可以看出满足引理2,之后,那么意味着求最优编码长度的公式:不妨设就是频率最小的两个,则它们长度一定相等
公式变为:
从公式即可看出,该式子对应一个新的霍夫曼编码问题,也就是上文中去掉 1,2号字符,引入一个新的频率对应的字符的编码问题;原来的最小值一定在新的和取最小值时取到;
这是因为:
新字符的频率为,因此实际上最优编码对应方程为:
也就是求满足条件的编码使得上式最小;
显然如果找到了这个编码,
对于原编码来说:
显然也取到最小值,因为两个式子完全相等(是大前提)
并且一旦新编码是前缀码,1,2号生成的节点增加两个孩子,再去掉该节点编码这一操作,不会影响前缀码的正确性;
这样就证明了霍夫曼编码是最优编码;
实际上本文不单证明了霍夫曼编码是最优编码,实际上是给出了构造最优编码的思路,顺着该思路设计编码方式就自然而然的导出霍夫曼编码,