title: 从哈夫曼编码再登程：原理和事实
tags:
- 哈夫曼
- 编码
- 投资
categories:
- 总结感悟
对于计算机科班出身的人来说，在大学阶段简直都学过信息论和算法这两门课，信息论都会讲到香农三大定理以及哈夫曼编码，算法课上会学习二叉树，甚至哈弗曼树。在介绍哈夫曼编码之前，先介绍一下什么是无效编码，以及香农第一定理的内容。
一个好的无效编码须要遵循两个根本准则：
- 易辨识
- 有效性
那么怎样才能做到无效编码呢？上面有一个问题：
用 10 根手指头，能表白多少个数字？
<!–more–>
常见的答复有以下两种：
- 能表白 10 个数字，因为小孩子数数的时候就是掰着指头数的。
- 能表白 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” 进行哈夫曼编码，而每个英文字母呈现的频率别离列在下图中。
进行霍夫曼编码前，咱们先创立一个霍夫曼树。
- 将每个英文字母按照呈现频率由小排到大，最小在左，如上图。
- 每个字母都代表一个终端节点（叶节点），比拟 F.O.R.G.E.T 六个字母中每个字母的呈现频率，将最小的两个字母频率相加合成一个新的节点。
- 比拟 5.R.G.E.T，发现R 与G的频率最小，故相加 4 +4=8。
- 比拟 5.8.E.T，发现5 与E的频率最小，故相加 5 +5=10。
- 比拟 8.10.T，发现8 与T的频率最小，故相加 8 +7=15。
- 最初剩10.15，没有能够比拟的对象，相加 10+15=25。
最初产生的树状图就是霍夫曼树，如下图。
给霍夫曼树的所有左节点 ’0’ 与右节点 ’1’，从树根至树叶依序记录所有字母的编码，如下图。
哈夫曼编码从实质上讲，是将最贵重的资源（最短的编码）给呈现概率最大的信息。咱们能够在任何须要分配资源的工作中利用哈夫曼编码的思维。
在风险投资畛域，利用哈夫曼编码原理投资就是一套比拟无效的零碎办法。假设你有一大笔钱能够用于风险投资，怎么投资成果最好？上面有三种做法：
- 均匀的投入到 100 个初创公司
- 利用本人的眼光投入到一家最可能的公司中
- 利用哈夫曼编码进行投资
第一种办法，过于均匀，基本上只能失去一个市场的均匀回报。第二种办法，只投一家，其实这就是赌博，我的一些敌人购买股票时，会只买单只股票并且重仓，这种状况如果碰到了会有几倍支出，然而大多数状况下都是血本无归，这是极为蹩脚的投资形式。第三种办法是利用哈夫曼编码的原理，能够先把钱逐级投下去，每一次投资的公司呈指数缩小，而金额倍增，这样通常不会错失上市的那家。大部分资金都集中到了最初的上市或被收买的企业中，这种投资回报要远远高于前两种。
对于集体而言，利用哈夫曼编码进行投资也是实用的。美国有名的私立学校哈克学校的前校长尼克诺夫博士说过，在孩子小时候，要让他们尝试各种不同的喜好，然而最终他们要在一个点上实现冲破。他将这比作圆规画圆，一方面有一个扎得很深的核心，另一方面有足够广的很浅的覆盖面。
在工作中，一方面须要成为某个方面的专家，做到足够的深刻，比方在 DevOps 方面，另一方面也须要有足够的覆盖面，理解各个细分畛域的设计思维，基本原理和简略实用。
对于我而言，我会尝试很多新的事件，不会去排挤，是因为不想失去机会，尽管后果是绝大部分失败了，然而至多也尝试过了，毕竟谋事在人成事在天。另一方面对于我花了一些精力，然而看样子也成不了的事件，我是坚定做减法登场止损。这条同样也实用于感情。
参考：
- wiki：https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
- dahuffman：https://github.com/soxofaan/d…
- 哈夫曼树的调整：https://blog.csdn.net/fx67758…
记得帮我点赞哦！
精心整顿了计算机各个方向的从入门、进阶、实战的视频课程和电子书，依照目录正当分类，总能找到你须要的学习材料，还在等什么？快去关注下载吧！！！
朝思暮想，必有回响，小伙伴们帮我点个赞吧，非常感谢。
我是职场亮哥，YY 高级软件工程师、四年工作教训，回绝咸鱼争当龙头的斜杠程序员。
听我说，提高多，程序人生一把梭
如果有幸能帮到你，请帮我点个【赞】，给个关注，如果能顺带评论给个激励，将不胜感激。
职场亮哥文章列表：更多文章
自己所有文章、答复都与版权保护平台有单干，著作权归职场亮哥所有，未经受权，转载必究！