霍夫曼编码题目_线性四叉树编码的例题有图

用我小时候的淘气故事，给孩子讲讲编码中的组合数学 　　
　　

　　导语 　　清爽宜人的秋天总能吸引人们流连于窗外湛蓝色的天空和清脆的鸟鸣。你望着窗外，思绪穿越回了小学的淘气包时代。想不到吧？那时的你就已经会用组合数学制作编码啦！

　　作者 易全文共4394字，阅读时间约6分钟 　　嗖地一秒钟，你穿越回了小学课堂上。课上的你突发奇想：要不晚上约小伙伴去后山冒险吧！你把这个大胆的想法一五一十转述给了你的发小：他从小就一直住在你家对面，两个人无话不谈，甚至你们隔着街道都能看到对方卧室是什么样子的。“好啊！问题是我们怎么去呢？” 　　这个问题一下子把你们两个都难住了。爸妈是绝对不可能允许你们去山里面乱跑的。这时你的发小想出了一条妙计：不如今晚天黑以后出发！你们每天十点半上床睡觉，所以十点半以后在自己卧室里“秘密行动”父母大多是发现不了的。小伙伴和你约定，等你们都上床睡觉以后，两个人都要把自己卧室的窗帘拉开，用手电筒交流。 　　如果看到对方打开了手电筒说明对面已经准备好下楼出发了。 　　但是如果没有看到对面卧室有手电筒的亮光，就说明今天晚上不是一个好的行动时机，需要下次再议。 　　你对这个计划拍手叫好。两个人一致决定：就这么办！实际上，你们俩都没有意识到，你们在不知不觉中已经构建了一套最简易的信息收发系统。而且在这几分钟时间里，你们已经交换了源编码（source code）表。这个表很简单，记录了你收到的信号和信号背后的含义： 　　可能接收到的信息 　　信息对应的含义 　　对方手电筒亮着 　　准备行动！ 　　对方手电筒没亮   　　不要行动！下次再议！ 　　有了这个表，你和小伙伴非常确定：我们一定可以实现晚上去后山探险的计划！ 　　于是你们两个人兴致勃勃地放学回家，默默等待着夜幕的降临。 　　到了晚上，你躺在床上，仔细地监听着自己周围的动静。等到你确认父母已经睡下了，你蹑手蹑脚地从抽屉中取出手电筒，兴奋地拉开窗帘向窗外望去——对面什么都没有，一片漆黑。你开着手电筒等了五分钟，发现对面还是没有动静。没办法，你只好按照先前约定好的规则，认为今天并不是一个好的行动时间。只好悻悻地拉上窗帘，倒头睡去。 　　第二天，当你俩终于又在学校见面时，你终于有机会问发小昨天到底是怎么回事了。结果小伙伴说：昨天他一躺下就打开了窗帘，按照约定打开了手电，但是并没有看到你的信号。所以他认为你一定是有什么事情耽搁了。就没再继续等。 　　这不是和你的遭遇一样嘛！你们俩合计了半天，最后发现一定是两个人打开窗帘的时间不对。导致彼此都没能看到对方发来的信号。于是你们这次约定，两个人需要从晚上10:30开始等对面的信息，如果等到11:30对面还没有手电的亮光，才能认为对面今天没办法行动。同时，你们为了保险起见，希望能从手电的闪烁规律中提前预判到具体在楼下见面的具体时间，以免类似的差错再次发生。 　　于是你和小伙伴较劲脑汁列出了如下的源编码表： 　　编码信息 　　编码 　　马上在楼下见面 　　· · 　　15分钟后在楼下见面 　　· — 　　30分钟后在楼下见面 　　— · 　　你们发明的这套信息编码方式每一个码字（symbol）包含两个比特（bit），也就是两个基本的信息单。其中“—”表示手电长亮一秒钟，“·”表示手电短亮0.5秒。在这种情况下，你们发明的这中编码实际上能够表示最多A(2,2)*A(2,2)，即2*2一共四种不同的信息。这里A(2,2)代表了2个选项里面选两个的所有排列数量。即如果我有一个0和一个1，我们一共可以排列为“01”和“10”两种有序数列。 　　你和小伙伴对视了一眼，发现除了你们已经设定好的信息以外，还有一个“— —”的编码没有被指定信息。但是如果要等四十分钟的话你们两个又觉得实在没有继续的必要了。所以你决定，不如把最后一个“— —”编码认定成“接收错误”编码，如果你们两个有任何一个人没有收到之前的信息，你们就需要长按两次手电，以让对方重新发送一遍之前的消息。最后，你们更新了你们之间的源编码表： 　　编码信息编码马上在楼下见面· ·15分钟后在楼下见面· —30分钟后在楼下见面— ·error 　　— — 　　至此，虽然你和小伙伴并没有学过通信方面的任何知识，但是你们已经建立起了一套相对完整的，有一定纠错能力的信息交流系统了。在这套系统里，一条信息只包含一个码字，一个码字包含两个比特的信息位。所有的信息编码都有且只有两比特信息位，也就是说，每发送一个确切信息手电必须亮起两次。 　　你和小伙伴对于你们的工作成果非常满意。但你们并不满足于此。如果能够把26个英文字母全都按照相似的方法编码的话，你们不就可以直接放弃手机，随时在晚上通过手电“打字”交流了吗？所以你和小伙伴想，如果需要编码26个字母，我们手电又只能有长亮或者短亮两种变化模式，我们可能需要把每个码字增加到5个比特的长度，也就是一个码字需要能够表示最多A(2,2)^5 = 32 种不同的信息。 　　但是请稍等！我们需要注意到一点，到目前为止，我们选择的编码长度都是一样的。我们能不能通过改变编码长度来缩减我们在实际沟通时的信息长度呢？ 　　实际上，如果我们设定一个编码的长度最高为5比特，那么算上4比特、3比特、2比特、1比特的情况，理论上这种编码最高可以容纳的信息数量为：A(2,2)^5+A(2,2)^4+A(2,2)^3+A(2,2)^2+A(2,2) = 64-2 = 62 个 　　当然，对于26个字母来说，可以容纳62个不同信息的编码实属浪费。在历史上，1837年美国人艾尔菲德·维尔发明的摩尔斯电码正是通过类似的想法发明的一种用于摩尔斯电报机上的通信编码。 　　
　　艾尔菲德·维尔 　　摩尔斯电码 　　下表中，“dash”（横杠）的长度等于三个“dit”（点）的长度。从下表中我们可以看到，摩尔斯电码最的编码长度为五比特。同时尽管是早期的电码也编入了26个英文字母和数字以及一些标点符号。 　　
　　同时还有一点值得注意的是，我们可以发现如果我们从摩尔斯码中随意选取一个编码，它的编码内部从开始到任意一位都不会和摩尔斯码中的任何其它编码重复。我们称这种编码为无前缀编码（prefix-free code）。这样的安排有效避免了无法断定信息具体含义的情况——例如，如果我们定义0代表对，1代表错，01代表不知可否。那么在接收方接收到“01”时就无从判断对面是想说“对错”呢，还是想说“不知可否”。而有了无前缀编码，在实际通信过程中，接收方在收到这种编码时则无需考虑收到的信息是否会有另一种不同的意思。 　　尽管摩尔斯电码有这样或者那样的好处，但是不可否认的是凭当时的技术，维尔并没有能够找到一种真正高效的制作无前缀编码的办法，例如字母O这种使用频率相对较高的字母，就被编码成了三个长键，非常复杂。 　　而更高效的编码办法是在100多年后由戴维·霍夫曼（David Huffman）发明的霍夫曼编码（Huffman Code）。 　　
　　戴维·霍夫曼 　　戴维霍夫曼趣事 　　作为信息论的先驱，戴维从小到大是一个不折不扣的大学霸。出生于美国俄亥俄州的戴维在十七岁时就已经从俄亥俄州立大学取得了电机工程学士学位。但是由于二战的缘故，霍夫曼不得不暂时中止学业并在美国海军服役两年时间。服役归来后，霍夫曼继续在母校攻读了电机工程的硕士学位。在此期间，他第一次萌生了有关霍夫曼编码的相关想法。 　　有趣的是，学霸也有为学业焦头烂额的时候。霍夫曼由于在一节专业课上没能取得更好的平时成绩，因为作业实在做的太差，所以十分焦虑自己如果参加期末考试会直接挂科。走投无路的他只好选择了当时教授给学生们的另一条出路：做一个project。于是，信息论中最基础的一种编码技术就诞生了：霍夫曼编码。 　　后来，霍夫曼又顺着研究生时期的思路继续对他的编码进行了研究。这便是他博士时期的研究项目，也是他一生中最重要的成就之一。当然，最后那门研究生课程肯定是得了A。 　　霍夫曼编码 　　最简单的霍夫曼编码是一种另类的“树状图”，它不仅能够列出所有沟通所需要的编码，还能够帮人们按图索骥，在一一对应信息和编码的同时保证最短的编码长度。我们先来介绍霍夫曼编码方法的核心：编码树状图。 　　编码树状图是对于给定条件下的所有可能的编码的枚举方法。它包含了顶点，中间点和边的概念。每一层都是编码的一个数位。如果拿我们开篇设计的编码作为例子，我们就会得到如下树状图。其中起始点不计算入编码内。 　　
　　我们注意到，在这个例子里，如果我们想做到能够给出无前缀编码，我们必须舍弃在上一层中已经选定作为编码的一支下面的所有后继分支。比如说，由于我们选定01作为其中一个信息的编码，我们下面为了保证其他编码的前缀中不再出现01，我们需要剩下所有的编码必须以00开头。这就给了我们两种不同的选择。下图很好地解释了我们该如何通过树状图构建无前缀编码。 　　
　　在这两种不同的编码方式中，由于最多只能有三种不同的编码，所以两种方法均舍弃了一个纠错码。导致上图呈现的编码不再具有纠错功能。 　　正如上图中的无前缀编码在树状图中的呈现形式，我们可以顺着这个思路不断地累加无限多数量的无前缀编码。并且中间不会出现编码没有使用的情况。在树状图中，这种编码长得是不是有点像蜈蚣。。。。 　　
　　而如果不考虑我们需要编码的信息源（source）的可能分布情况的话，单纯的树状图已经可以解决我们的所有问题了。只要把蜈蚣的每一只脚都指定相应的信息即可。但是，霍夫曼编码的精髓除了可以给出相对来说最短的无前缀编码以外，还有一个厉害之处：它可以使得编码对应的编码长度期望最小。简单来说，就是如果考虑到信号源发出的不同信号的频率，综合下来接收端接收的编码后信息长度最短。 　　霍夫曼编码的步骤如下： 　　1. 将信息源的所有可能信息按照出现概率从大到小顺序排列。2. 选取概率最小的两个信息，分别标上0和1后（自选顺序）将两者的概率相加，由树状图类似的边引出并合并作为新的概率。3. 重复步骤2直到概率最终为1停止。4. 相应信息源的编码即从最终点出发开始直到信源信息停止路径上的0和1组成的一串数字。 　　对于我们文章一开始的例子，霍夫曼编码是这样的： 　　
　　写在最后 　　编码学是一种人们在生产生活中经过长时间总结得出的一套高效远距离交流信息的理论。其中应用到了包括概率论，组合学，因果推断等众多的数学分支。当然，有的时候人们在追求高效交流的同时也会注重隐私。因此，也衍生出了通过牺牲编码的一部分效率来增加保密性的密码学。我们之前也有过相关的介绍文章： 　　滴——您的密码安全系数极低，请立即修改！ 　　随着科技进步，编码学的编码形式也日新月异。有时候找到一个好的编码就能够提升一整代通信产业。（例如4G到5G）因此，编码学作为人类通信的手段之一也是非常重要的哦！而这些先进的技术，其实都离不开组合学的应用。想让孩子从小打好组合学方面的基础？不如来看看combinatorist罗教授北美课程中的Module3组合专题+Workout3A组合拔高训练吧！ 　　🔔🔔🔔