2021-01-04 霍夫曼编码最优性的一个简单证明概述

本文主要介绍一下霍夫曼编码,

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 =s1*l(s1)+s2*l(s2)+...
其中因为si 和sj可能是相同字符,它们对应的l也相等;
进一步,可以求出相对长度,其实就是l/NN表示编码序列的总长度;因此,如果某个字符在s中出现的频率为f(s)
则编码相对长度公式如下:
l = si*f(si) i遍历所有不同的字符集合,后文中不加说明都是指相对长度

以上就是编码定义;

下面介绍两种编码方式,
定长编码,不定长编码;
定长编码很好理解:每个字符经过编码方法之后的映射字符序列都是固定长度的;不定长就是长度不固定;
上述范例中的是不定长编码;

下面说说定长和不定长的区别:
首先,编码就意味着要解码,对于定长来说,只要编码方法和固定长度的大小,解码相当容易,隔固定间隔读取,再做逆向映射就ok了;

但对于不定长编码,可能出现冲突;

比如 a编码为 0
b编码为1
c编码为01

此时如果我收到一个编码后的序列为 01,
那么有两种可能,原序列为ab 或者原序列为c,这两种都合理,将无法正确解码;

不定长既然有这种缺陷,为何实际编码还是用不定长,原因就是不定长编码能够节省空间;
举例来说,如果有8个不同字符,用定长编码,每个字符的编码长度至少为3;(2^3=8)
但如果不定长编码,可以少一些,后文中将会给出一个例子;

那么不定长编码的缺陷怎么解决,我们发现之所以出现上述缺陷,一个主要原因在于,某些编码恰好是另外一个编码的前缀;
比如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
长度计算公式为: l1*f1+l2*f2+...+

那么这个编码方式的编码长度为何最短?

终于可以说的全文最关键的部分,下面给出一个简明的证明:
首先,给出几个引理:
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,之后,那么意味着求最优编码长度的公式:l1*f1+l2*f2+...不妨设f1,f2就是频率最小的两个,则它们长度一定相等l1=l2=l
公式变为:(f1+f2)*l+f3*l3+...
从公式即可看出,该式子对应一个新的霍夫曼编码问题,也就是上文中去掉 1,2号字符,引入一个新的频率对应f1+f2的字符的编码问题;原来的最小值一定在新的和取最小值时取到;
这是因为:
新字符的频率为f1+f2,因此实际上最优编码对应方程为:
(f1+f2)* l+f3*l3+...
也就是求满足条件的编码使得上式最小;
显然如果找到了这个编码,
对于原编码来说:
l1*f1+l2*f2+... 显然也取到最小值,因为两个式子完全相等(l1==l2是大前提)

并且一旦新编码是前缀码,1,2号生成的节点增加两个孩子,再去掉该节点编码这一操作,不会影响前缀码的正确性;

这样就证明了霍夫曼编码是最优编码;
实际上本文不单证明了霍夫曼编码是最优编码,实际上是给出了构造最优编码的思路,顺着该思路设计编码方式就自然而然的导出霍夫曼编码,

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,723评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,080评论 2 379
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,604评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,440评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,431评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,499评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,893评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,541评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,751评论 1 296
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,547评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,619评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,320评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,890评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,896评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,137评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,796评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,335评论 2 342

推荐阅读更多精彩内容