浅谈赫夫曼树及其应用(文件压缩)

日常生活中经常会使用到文件压缩,但是基本很少有人会问到压缩是如何实现的。所谓的,就是把文本重新进行编码,减少不必要的空间。目前最新技术在编码上已经很强大,但是笔者不打算说那些很高深的压缩技术(其实那些高深的压缩技术,其实笔者也不懂)。虽然有很多高深的压缩技术,但是目前经常使用到的压缩和解压缩技术都是基于赫夫曼的研究基础上发展而来。所以今天就简单介绍一个最基本的压缩编码方法-----赫夫曼编码。

一、实例开篇

        if a < 60 {
            b = "不及格"
        }else if a < 70{
            b = "及格"
        }else if a < 80 {
            b = "中等"
        }else if a < 90{
            b = "良好"
        }else {
            b = "优秀"
        }

如上代码是百分制考试的评分标准。粗略看上面的代码,貌似没有什么问题。但是通常情况来说一个班级的学生成绩分布在及格、中等、良好的相对较多,分布在优秀和不及格的相对较少。但是上面的代码,最开始的逻辑是先判断是否及格,再逐渐向上得到结果。当输入量很大的时候,算法在效率方面是存在一定问题的。

假设实际中学生在5个等级上成绩分布的概率如下表所示。如果按照上述的代码逻辑执行,70分以上的成绩占总概率的80%,但是想判断出一个70分以上的成绩至少需要执行3次以上的判断才能得到结果,显然是十分不合理的。


成绩分布规律

如果能依照成绩概率分布的规律,如下图,更改成绩等级判断逻辑,那么程序判断的次数将大大较少。

更改后的逻辑判断

二、赫夫曼定义

按照上面的两种逻辑,可以把上述的逻辑分别简化成下图的二叉树结构。其中A表示不及格、B及格、C中等、D良好、E优秀。分支线上的数字表示成绩所占比例数。

屏幕快照 2017-09-11 下午11.37.15.png
在说赫夫曼之前先说明另个概念:
  • 路径长度: 从树中的一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称作路径长度。
  • 树的路径长度 : 树的路径长度就是从树根到每一个结点的路径长度之和。
说完了上述的两个概念,看一下赫夫曼树的定义。
若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径WPL长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径WPL长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。

关于赫夫曼树的定义出现了权。如果考虑到带权的节点,节点的带权路径长度为从该节点到树根之间的路径长度与节点上权的乘积。
按照上述所讲,则上图中二叉树a的WPL = 5 * 1 + 15 * 2 + 40 * 3 + 30 * 4 + 10 * 4 = 315。二叉树b的WPL = 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 * 2 = 220。315和220这两个结果分别意味着,如果用二叉树 a 的判断方法,10000个学生的成绩需要做31500次比较,而二叉树 b 的判断方法只要做22000次比较。很显然,二叉树b的效率比a高了很多。

三、赫夫曼构造原理

看了上述两个二叉树的对比,但是想二叉树 b 这样的高效的二叉树又是如何得到的?

总共分为四个步骤。
  • 1、构成初始集合

对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算法,一般还要求以Ti的权值Wi的升序排列。)

  • 2、选取左右子树

在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。

  • 3、删除左右子树

从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。

  • 4、重复二和三两步,

重复二和三两步,直到集合F中只有一棵二叉树为止。

结合上述的步骤,看看如何将二叉树 a 转为二叉树 b。
  • 第一步,先把有权值得叶子结点按照从小到大的顺序排列成一个有序序列,即为A5,D10,B15,C70。

  • 第二步,取头两个最小权值的结点作为一个新结点N1的两个子结点,注意相对较小的的孩子是左孩子,这里A就是N1的左孩子,D为N1的右孩子, 新结点的权值为两个叶子结点的权值之和 5 + 10 = 15;

第二步
  • 第三步,将N1替换A与E,插入有序序列中,保持从小到大的排序,即 N1 15,B15,C70;

  • 第四步,重复步骤2,将N1与B作为一个新结点N2的两个子结点, N2的权值 = 15 + 15 = 30;

第四步
  • 第五步,将N2替换N1与B,插入有序序列中,保持从小到大的排序,即 N2 ,D30,C40;

  • 第六步,重复步骤2,将N2和D作为一个新结点N3的两个子结点。N3的权值为30+30 = 60

屏幕快照 2017-09-12 下午10.17.20.png
  • 第七步,将N3替换N2和D,排序得到C40,N3为40。
  • 第八步,重复步骤二,将C于N3作为一个新节点T的两个子节点。即完成赫夫曼树的构造。


    赫夫曼树构造完成

四、赫夫曼编码

赫夫曼树最大的成绩是在当前远距离通讯过程中,解决了数据传输最优化问题。比如有ABCDEF六个字母,通过0和1编码用二进制字符发送。编码后的数据为000001010011100101,解码的时候可以按照3位一份来解码。是上上,不管是任何文字语言,字母或汉字在某一话题或其他方面出现的频率是不一样的。如汉字中的“的”、“了”、“你”等等,都是频率极高的汉字。所以因为频频的不同,可以按照赫夫曼树的规律来规划。
假设ABCDEF出现的概率分别为27%、8%、15%、15%、30%、5%。则形成的赫夫曼树如下图。此外我们可以将左右分支分别改为0和1,然后用0和1来编码字母。则编码结果为A=01、B=1001、C=101、D=00、E=11、F=1000。

按照赫夫曼树编码
原本的编码结果为:000001010011100101
现在的编码结果为:0110011010011100

现在的编码结果明显要比之前的少了一些,短短是几个字母编码后,少的量不是很大,如果是通篇的文章或更多,那么编码量将会节省很多,这就是文件压缩的原理。并且随着字符的增多,按照权重优先级编码,这种压缩会进一步提升很多。
既然有编码,就必然有解码。简单说说解码,按照赫夫曼树这种编码方法,非0即1,且每个字符编码长短不等很容易混淆。所以若要设计出长短不等的编码,则必须是任意字符的编码都不是另一个字符编码的前缀(这种编码通常称为前缀编码)。自己观察A=01、B=1001、C=101、D=00、E=11、F=1000根本就不存在容易和 1001 、1000混淆的10和100编码,这一点从上面的0和1的左右分支图也能轻易的总结出,因为ABCDEF这几个字符都在输的最末端,所以不会出现这种容易混淆的问题。另外一点,当然是编码和解码都要规定好同样的赫夫曼编码规则。

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

推荐阅读更多精彩内容