哈夫曼添加虚节点公式

同学们好，今天介绍哈弗曼树的定义和构成方法。先看几个基本概念， 路径和路径长度。在一棵树中，从一个节点往下可以达到的子节点之间的通路称为路径，通路中分支的树木称为路径长度。若规定根节点的层数为一，则从根节点到第 l 层节点的路径长度为 l。 减一 看下面这棵树，节点 a 的路径长度为一，节点 b 的路径长度为二，节点 c 和节点 d 路径长度都是三。 下一个概念，节点的全以及代全路径长度。如果给数中的节点赋予一个有着某种含义的数值，则这个数值称为该点的全节点 a、 b、 c、 d 的全分别为七、五、二和四。节点 的代全路径长度定义为从根节点到该节点之间的路径长度与该节点的全的乘积。在这棵树中，节点 a 的路径长度为一，全为七，他的代全路径长度等于一乘以七， 节点 b 代全路径长度等于二乘以五，节点 c 等于三乘以二，节点 d 等于三乘以四。最后介绍一下竖的代全路径长度。竖的代全路径长度是所有叶子节点的代全路径长度之和。 在下图中，这棵树的代全路径长度等于节点 a 的代全路径长度七乘以一，加上节点 b 的代全路径长度五乘以二，再加上节点 c 的二乘以三，再加上节点 d 的四乘以三。由此可以得到 哈弗曼树的概念。给出 n 个叶子节点，每个节点都对应着一个全植，构建一棵二叉树，如果该树的带全路径长度最小，这样的二叉树成为最优二叉树，也叫做哈弗曼树。来看一下哈弗曼树的构成。 有六个节点，他们的全职分别是一、七、三、四、九和八。首先选择两个全职最小的节点 a 和 c。 全职是一和三，将他们删除，组成一个新的二茬数。用树枝连起来 计算他们的核作为他们的根，再将根加入到节点对列。如果这个数恰好是下一步两个最小数其中之一，那么这个数直接往上生长。如果计算出的全值 比较大，不是下一步两个最小数其中之一，那么就并列生长。继续从五个数中选择两个较小的，选择了四和四向上生长，用树枝连起来他们的和是八。 将八加入对列，再选择两个最小的数，七和八，包括刚才的八向上生长， 用数值连起来计算他们的和十五。将十五加入对列，选择两个最小的数九和八。注意，刚刚生成的十五不再是最小的两个数之一。并列生长， 将九和八用数值连起来计算他们的和十七，将十七加入对列，最后还剩两个数，十五和十七别无选择。 用树枝连起来计算他们的和三十二。到现在为止，哈佛曼术构建完毕。哈佛曼术有以下几个特点， 第一， n 个叶子结点生成的哈佛曼树有二 n 减一个结点。这是因为每次将两颗全枝最小的二叉树合并成一颗新的二叉树时，需要增加一个结点作为新二叉树的根结点。 第二，全职大的节点离根近，全职小的节点离根远。第三，生成的二叉数不为 一，两棵全植最小。倒插树哪棵作为左子树，哪棵作为右子树？哈弗曼算法并没有要求，但是最小的代全路径长度是唯一的。 第四，没有度，唯一的节点。由于每次都是将两颗全枝最小的二茬树合并成一棵新二茬树，所以没有度唯一的节点。好了，哈弗曼树我们就讲到这里，谢谢大家。

通往 a g i 的 路， skilling law 只能走完百分之五十。说这句话的人是诺贝尔奖得主，也是 jimmy 三背后的男人，谷歌 deepmind 的 创始人 damis haasabis。 就在谷歌凭借 g m i 三刚刚反超 openai 的 高光时刻，哈萨比斯却在最新的一场访谈里给全球狂热的算力竞赛泼了盆冷水。他直言，百分之五十确实靠堆算力，但剩下的百分之五十如果找不到，我们永远造不出真正的 agi。 这缺失的另一半拼图到底是什么？我把这场一个小时的访谈提炼成了接下来几分钟的硬核干货。这篇内容可能会颠覆你对 ai 下半场的认知。 首先，哈萨比斯用一个词精准概括了现在 ai 的 尴尬状态，锯齿状智能。 现在的 ai 更像是一个全知全能的图书管理员，但他有一个致命缺陷，永远无法走出图书馆。他并不理解文字背后的真实逻辑，他只是在做高概率的预测下一个词。 哈萨比斯指出，现在的大模型本质上是被困在了人类互联网的存量数据里。他能把已知的学到极致，却无法创造出人类都还不知道的新定律。 怎么解决？哈萨比斯给出的解法是，摆脱人类数据，自我进化。还记得当年的 alpha zero 吗？他抛弃了人类棋谱，完全靠左右互搏就吊打了全世界，未来的 agi 也是如此。 deepmind 正在构建一个 ai 版的黑客帝国，也就是日内所说的世界模型。 谷歌最近发布的 jenny 模型，能让 ai 生成一个符合物理规律的虚拟世界，数据不再依赖人类互联网，而是由 ai 在 仿真中无限生成。 当 ai 在 这个虚拟世界里把现实世界的运行规律演练了一亿遍之后，再把它放回现实世界，那就是对现有语言模型的降维打击。 那么费这么大劲造出真正的 agi， 到底是为了什么？仅仅是为了让我们写代码更快，或者工作效率翻倍吗？ 不，在哈萨比斯眼里， ai 的 终极使命是解决根节点问题。什么叫根节点？就是那些一旦被解开，下游所有问题都会迎刃而解的总开关。 比如帮他拿下诺奖的 alpha fold， 它破解了蛋白质折叠的谜题，这就是生物学的根节点。再比如可控核聚变，这是能源的根节点，一旦 ai 帮我们控制了磁场，人类将拥有无限清洁能源。 正如哈萨比斯所说，我想做的就是用 ai 去寻找那个最终的极限。 甚至他还抛出了一个极具哲学意味的猜想，也许信息才是宇宙最基础的单元。 在他看来，物理世界的一切光热、触觉本质上都是信息流。如果宇宙本质上就是一台巨大的图灵机，那么理论上 ai 终将能计算一切 回到开头的问题，那缺失的百分之五十到底是什么？就是这套能让 ai 理解并模拟宇宙运行的科学方法。只有找到了这把钥匙，再加上足够的算力，宇宙对我们来说才将不再有秘密。 最后，这一切会来的有多快？哈萨比斯的关键词是压缩工业革命，用了一百年才完成的社会改革，我们可能要在五到十年内全部消化。 在这种急速狂飙下，人类将来不及审核每一个决策，这就引出了最大的风险，自主智能体。 当数百万个拥有超人智商的智能体在网络上自主行动，而我们又跟不上他们的速度时，该如何确保他们的目标和人类一致？这将是未来两三年我们面临的最大考验。 帕萨比斯的这番话其实是在给当下的浮躁降温，但它只是 scaling law 的 胜利。真正的 agi 需要的是另外百分之五十的突破， 去跳出预测下一个词的局限，去构建那些能真正模拟真实世界的自我进化路径。这已不再是简单的推算力游戏，而是人类对宇宙本质的终极解码。