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

4次阅读

共计 2931 个字符，预计需要花费 8 分钟才能阅读完成。

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…

记得帮我点赞哦！