专栏首页职场亮哥从哈夫曼编码再出发:原理和现实

从哈夫曼编码再出发:原理和现实

对于计算机科班出身的人来说,在大学阶段几乎都学过信息论和算法这两门课,信息论都会讲到香农三大定理以及哈夫曼编码,算法课上会学习二叉树,甚至哈弗曼树。在介绍哈夫曼编码之前,先介绍一下什么是有效编码,以及香农第一定理的内容。

一个好的有效编码需要遵循两个基本原则:

  • 易辨识
  • 有效性

那么怎样才能做到有效编码呢?下面有一个问题:

用10根手指头,能表达多少个数字?

常见的回答有以下两种:

  1. 能表达10个数字,因为小孩子数数的时候就是掰着指头数的。
  2. 能表达100个数字,因为我们平时能用一只手就能做出10个形状,也就是能数10个数,将两只手组合起来,一个表示十位,一个表示个位,就能表示从0到99共100个数字

第一个回答最直观,第二个回答其实就利用了编码的知识。

但是这依然不是最有效的编码,如果我们考虑采用二进制,而不是十进制进行编码,则能表示1024个不同的数字。

具体的做法是这样的,把10个手指并排在一起,从左到右依次给手指编号,编码为0~9。每一个手指头都有伸出和收起两种状态。每一种状态对应于一位二进制,十个手指头就能表示10位二进制,也就是2的10次方,也就是1024种数字。

当然也有人觉得可以让每个手指具有伸开、半伸开、收缩三个状态,表示3的10次方也就是59049中数字。虽然这种想法也是正确的,但是过分强调有效性,而忽视了易辨识这个原则,凡事过犹不及。

常见的比较有效的编码有阿拉伯数字,莫尔斯电码以及计算机中根据电路状态演化的二进制编码。

一个有效的编码是否就是最优编码呢,答案当然是不一定。香农第一定理告诉我们编码长度是有理论最小值的,摘录信息论这本书中的公式如下:

编码长度 ≥ 信息熵(信息量) / 每一个码的信息量

香农对此做出了严格的数学证明,同时还证明,只要编码系统设计得足够巧妙,上面的等号是成立的。

我们以二进制编码为例来说明这个公式,为了预测世界杯冠军,我们先对世界杯的32只球队编码,那如何编码才能使得编码长度最短呢?对于这样的n选1的问题,根据香农第一定理,32选1的信息熵为log32=5比特(以2为底的对数),每个编码的信息量为1比特,根据公式最短编码长度为5。如果编码长度小于5,那么传递出去的信息就一定包含不确定性,也就是有损信息、失真信息。

至于信息熵的计算为什么是以2为底的对数,可以参考分治思想。

如果我们对经常出现的字母采用较短的编码,对不常见的字母采用较长的编码,根据常识,这样是能够降低编码的整体长度的。在莫尔斯电码中,我们会发现26个英文字母中的5个元音字母aeiou的编码长度是最短的。如果对英文26个字母采用等长度的编码,比如进行二进制编码,需要log26,就是5比特信息。而采用莫尔斯的编码方式,平均只需要3比特,这样效率就提升了很多。

在中国,北京和上海等重要城市的长途电话区位码就是两位,小城市就使用3位,比如北京是010,上海是021,而江苏常州是0519(所有都忽略掉前面的0),这样做的目的就是为了减少平均的编码长度。

那怎样才能找到最有效的二进制编码呢?哈夫曼在*《A Method for the Construction of Minimum-Redundancy Codes》*这篇论文中发表了基于自底向上的有序频率二叉树的编码方法,并很快证明了这个方法是最有效的。

关于哈夫曼树的构建过程可以参加文末的参考中的Wikipedia链接,此处只做一个简单描述:

假设我们要给一个英文单字**“F O R G E T”**进行哈夫曼编码,而每个英文字母出现的频率分别列在下图中。

进行霍夫曼编码前,我们先创建一个霍夫曼树。

  1. 将每个英文字母依照出现频率由小排到大,最小在左,如上图。
  2. 每个字母都代表一个终端节点(叶节点),比较F.O.R.G.E.T六个字母中每个字母的出现频率,将最小的两个字母频率相加合成一个新的节点。
  3. 比较5.R.G.E.T,发现RG的频率最小,故相加4+4=8。
  4. 比较5.8.E.T,发现5E的频率最小,故相加5+5=10。
  5. 比较8.10.T,发现8T的频率最小,故相加8+7=15。
  6. 最后剩10.15,没有可以比较的对象,相加10+15=25。

最后产生的树状图就是霍夫曼树,如下图。

给霍夫曼树的所有左节点'0’与右节点'1’,从树根至树叶依序记录所有字母的编码,如下图。

哈夫曼编码从本质上讲,是将最宝贵的资源(最短的编码)给出现概率最大的信息。我们可以在任何需要分配资源的工作中利用哈夫曼编码的思想。

在风险投资领域,利用哈夫曼编码原理投资就是一套比较有效的系统方法。假定你有一大笔钱可以用于风险投资,怎样投资效果最好?下面有三种做法:

  1. 平均的投入到100个初创公司
  2. 利用自己的眼光投入到一家最可能的公司中
  3. 利用哈夫曼编码进行投资

第一种方法,过于平均,基本上只能得到一个市场的平均回报。第二种方法,只投一家,其实这就是赌博,我的一些朋友购买股票时,会只买单只股票并且重仓,这种情况如果碰到了会有几倍收入,但是大多数情况下都是血本无归,这是极为糟糕的投资方式。第三种方法是利用哈夫曼编码的原理,可以先把钱逐级投下去,每一次投资的公司呈指数减少,而金额倍增,这样通常不会错失上市的那家。大部分资金都集中到了最后的上市或被收购的企业中,这种投资回报要远远高于前两种。

对于个人而言,利用哈夫曼编码进行投资也是适用的。美国有名的私立学校哈克学校的前校长尼克诺夫博士说过,在孩子小时候,要让他们尝试各种不同的爱好,但是最终他们要在一个点上实现突破。他将这比作圆规画圆,一方面有一个扎得很深的中心,另一方面有足够广的很浅的覆盖面。

在工作中,一方面需要成为某个方面的专家,做到足够的深入,比如在DevOps方面,另一方面也需要有足够的覆盖面,了解各个细分领域的设计思想,基本原理和简单实用。

对于我而言,我会尝试很多新的事情,不会去排斥,是因为不想失去机会,虽然结果是绝大部分失败了,但是至少也尝试过了,毕竟谋事在人成事在天。另一方面对于我花了一些精力,但是看样子也成不了的事情,我是坚决做减法退场止损。这条同样也适用于感情。

参考:

  1. wiki:https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
  2. dahuffman:https://github.com/soxofaan/dahuffman
  3. 哈夫曼树的调整:https://blog.csdn.net/fx677588/article/details/70767446

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [数据结构] 使用最小堆思想实现哈夫曼编解码

    假设有n个权值,构造有n个叶子结点的二叉树,每个叶子结点的权值是n个权值之一,这样的二叉树可以构造很多棵,其中必有一棵是带权路径长度最小的,这棵二叉树就称为最优...

    泰坦HW
  • 原以为哈夫曼树、哈夫曼编码很难,结果……

    哈夫曼树、哈夫曼编码很多人可能听过,但是可能并没有认真学习了解,今天这篇就比较详细的讲一下哈夫曼树。

    main方法
  • Android 中图片压缩分析(上)

    在 Android 中进行图片压缩是非常常见的开发场景,主要的压缩方法有两种:其一是质量压缩,其二是下采样压缩。

    QQ音乐技术团队
  • JNI方法实现图片压缩(压缩率极高)

    直接使用项目或直接复制libs中的so库到项目中即可(当前只构建了armeabi),需要其他ABI可检下项目另外使用CMake构建即可。

    砸漏
  • C++实现哈夫曼编码压缩软件

    一个简单的压缩软件,利用哈夫曼思想,构造哈夫曼编码,实现对文件的二进制压缩,以及解压,再利用MFC制作可视化操作界面,美化软件又简化文件操作。(各个步骤有解释可...

    HcodeBlogger
  • 从节省Redis内存空间说开去

    上周部门会议上讨论的一个议题是如何节省Redis内存空间,其中有个小伙伴提到可以从压缩字符串入手,我觉得这是一个可以尝试的思路。因为有时候我们存在Redis中的...

    Bug开发工程师
  • 数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现

    Tencent JCoder
  • 数据结构(十三)——树的具体应用(一)

      我们用两篇文章介绍了树的相关概念,分别介绍了树的概述,将树与数组和链式的存储结构做了相应的对比;然后又介绍了二叉树的相关概念,包括满二叉树和完全二叉树的相关...

    一计之长
  • 图解哈夫曼(Huffman)编码树

    哈夫曼(Huffman)编码算法是基于二叉树构建编码压缩结构的,它是数据压缩中经典的一种算法。算法根据文本字符出现的频率,重新对字符进行编码。因为为了缩短编码的...

    JavaEdge
  • 看懂哈夫曼编码

    在计算机学科中,编码方式有很多种,对于Java开发而言,其中ASCII码和RFC3986(URL中非ASCII字符的编码)应该是我们最熟悉的了, 在ASCII编...

    每天学Java
  • 哈夫曼编码原理与Python实现代码(附手动推导过程原稿真迹)

    哈夫曼编码依据字符出现概率来构造异字头(任何一个字符的编码都不是其他字符的前缀)的平均长度最短的码字,通过构造二叉树来实现,出现频次越多的字符编码越短,出现频次...

    Python小屋屋主
  • 当Kotlin遇见数据结构丨使用哈夫曼编码压缩文件

    哈夫曼编码是一种编码格式,属于可变字长编码的一种,该方法依照字符出现的概率来构建异字头的平均长度最短的码字,最终实现根据使用频率来最大化节省码字(字符)的存储空...

    码脑
  • 数据压缩的元老——哈夫曼树精解

    数据结构从逻辑结构上可以分为:集合、线性表、树、图 集合中常用的数据结构是背包等。 线性表包括栈、链表、队列等。 树包括堆、二叉树、哈夫曼树等。 图包括有...

    文彬
  • 程序员需要了解的硬核知识之压缩算法

    我们想必都有过压缩和 解压缩文件的经历,当文件太大时,我们会使用文件压缩来降低文件的占用空间。比如微信上传文件的限制是100 MB,我这里有个文件夹无法上传,但...

    cxuan
  • 当Kotlin遇见数据结构丨哈夫曼编码

    哈夫曼编码是一种编码格式,属于可变字长编码的一种,该方法依照字符出现的概率来构建异字头的平均长度最短的码字,最终实现根据使用频率来最大化节省码字(字符)的存储空...

    码脑
  • 经典算法之最优二叉树

    我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的“最优二叉树”,为了纪念他呢,我们称之为“哈夫曼树”。哈夫曼树可以用于哈夫曼编码,编码的话学问...

    用户3467126
  • 哈夫曼编码

    1.哈夫曼编码是一种可以被唯一解读的二进制编码 2.前缀编码保证了解码时不会有多种可能 3.哈夫曼编码有不等长和等长两种编码,为了保证不等长编码的唯一性,使...

    大忽悠爱学习
  • 当Kotlin遇见数据结构丨哈夫曼解码

    哈夫曼编码是一种编码格式,属于可变字长编码的一种,该方法依照字符出现的概率来构建异字头的平均长度最短的码字,最终实现根据使用频率来最大化节省码字(字符)的存储空...

    码脑
  • 数据结构 哈夫曼编码/译码器

    题目8:哈夫曼编码/译码器 实验类型(验证/设计/创新):设计 学时:16 课程设计内容: 设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编...

    川川菜鸟

扫码关注云+社区

领取腾讯云代金券