弗里曼编码属于什么数据结构？

嗯，大家好，今天我们来讲一下一个哈弗曼数的一个构造，然后他最后成型是一个这样的一个东西。然后我们就是主要来讲一下这个解题的一个过程，然后我们的主要过程就是第一步啊，第一步就是说一个排序，把这些按递增的一个序列，就是从小到大排序。第二步就是 找到这个序列里面的前两个最小的就是三跟五，这就是八到七八、八十一、十四、二三、二九。然后这里的这里我们就呃 开始继续往下面做呃，七八八七八、八、十一、十四、二三跟二九，我们这是第二次，第二次，因为这是第一次嘛，这是第一次，第二次的话就相当于是七跟八构成的是一个十五， 然后连序列去掉七跟八，把十五插入到其中就是八十一、十四、十五、二三跟二九。然后第三步第三次 我们就把八跟十一取出来，八跟十一取出来就是构成一个十九，这里的八，这里的八跟我们这里的八是对应起来的，这里的八就是对应的是一个三根 啊，然后就是把十九插入到其中八根弦去掉就是十四、十五、五十四、十五、十九、二三跟二九。 第四步第四次就相当于是十四跟十五嘛，十四跟十五就是二十九， 二十九插入到其中，十四、十五去掉十九、二三、二九跟二九。然后第五次就是呃，十九跟二三， 就是一个四十二，然后四十二他就是二九，二九跟四二。然后第六次就是二九跟二九跟一个五十八，对，然后就是 呃多少来着五十八、二九、二九，去掉就是四二跟五八嘛，然后第七次就是四二五、八跟一百， 然后把这些就是这几个，这，这从上面到下面这几个拼起来。什么叫拼起来呢？你看，呃，我们第一， 四呢？三跟五，这第一次，第一次三跟五，我们构成了一个八，然后呢？然后我们把八插回去了，就是说七跟八构成了什么？七跟八构成了十五，七跟八构成了十五，七跟八构成了这个十五， 然后十五放回去，这个八，这个八，这个八呀，这个八跟十一，八跟十一构成了一个十九，然后十九。嗯，看这里啊， 八跟十一构成的一个十九，十九。之后我们插入再插入到其中，其中选选两个最小的十九跟二十三，十九跟二十三， 二十三构成了多少？十九跟二十三构成了 四十二， 然后呢？四十二、四十二、二九跟二九。这里有一个二九。是，呃，这里有一个二九跟二九又构成了一个多少，二九跟二九构成了一个四，呃，构成一个五十八，二九跟二九 构成了一个五十八、五十八，然后二九。 我们这里的二九是十四根十五。呃，等一下，这里的十五应该是移到这边啊，然后十四根，十五嘛，圆圆须还有个十四，十四根十五就构成了一个，这个，这两个构成了一搏。 其实这个这个就，呃，跟我们跟我们这边的，跟我们这边的是一样，跟我们这边是一样。然后整个哈弗曼树的一个构造就到这里完成，然后顺带讲一下哈弗曼边 马上这个这个树画的太丑了。哈佛半边马，哈佛半边马就是记住一个原则，就是左零右一零一零一零一， 你就是把每颗节点的左子左左分支跟右跟那个右分支标成零跟一。然后比如人家问你啊，这个七的哈弗曼编码是多少，我们就可以七，我们就就就举个举个例子啊， 叫七的哈弗曼对应就是，哎，我们一条路数下来看一下，一一一 零啊，那就是一一一零八对应的是多少的幺幺幺幺幺幺幺，然后就以此类推啊，我们就假如啊，我再举个例子，这个五的话，那不就是零零零 一，五的话就是零零零一哈弗曼，哈弗曼编码的就这样去进，就我们去找节点的哈弗曼编码是多少，就这样去找左零右一的原则，左零右一，然后就讲到这里吧。好，谢谢大家。

好，我们理解呢，如何判定哈弗曼书？那么我们通过一个实力，我们说主要去求他的什么值呢？ wpr 值为最小的，那么设计当中里面我们在求的时候呢，我们通过一个实际的案例，比如有这样的一个例子， 有七个带前节点，他的前值分别为这些数值，让我们以他们为叶子节点的前值来构造一颗哈弗曼数 来构造。怎么构造呢？我们一般是要求按照每个节点的左指数的根节点的前指小一或等由右指数根节点的前指的这样的次序来进行构造，并计算他的路径长度，也是 wp 好，那么如何来构建这样的一个哈弗曼术呢？我们一般的思路只从最小 小的根子来进算，刚才我们不是总结了他的规定吗？什么规定？小的要放离根眼还是近呢？离根要远眼就要放到最后面去喽，那么要放到最后面去，我们就先找他最小的， 最终求出来的结果是这样，我先把结果打出来，然后我们再来分析，以后你就要会分析了，那么这一些前职当中里面最小的肯定是哪一个呢？二，我怎么四？那么我就把这两个人构建， 把这两个的构建啊，这两个的构建，那么构成了这个七七的时候呢，再找这里面重新来构建他整个的一个思路，就是像这种思路，依次类推啊，依次类推呀，啊，依次类推好，那么得这个单能理解吗？就是一个一个网的，比如说二跟他 四，他构建一个六，六啊，这个二跟的四跟，呃，二跟的四，这数写错了，二跟到六应该。呃，二跟到四这里应该是几啊？应该是六啊？应该是六。好，六，这里面还有一个是几呢？这个应该是几呢？五，这数写反了，所以这个五又没有了吗？然后这个七还在不在？ 呃，主跟到这里应该是六，哈，六当中里面有一个是什么？有一个是五，那我们就把这个五样拿过来喽， 我要拿过来啊，好，这个五跟到六的构建，然后这个时候五跟到六构建呢，以后呢？得到一个是什么？十一，十一的时候呢？仔细观察，特别要注意这个问题地方，那么要说这个没有了，你就把它画掉，七是不是也没有了？ 五跟到六没有了，哎，这个地方五跟五没有了哈。五，呃，这个六是新增， 五是这里的，那这两个是没有拉到，这三个没有拉的好，那么我得罪了一个。十一，十一的时候你就要注意了，你千万不要说十一再长哪一个呢？哪七也行，哪八也行， 这两个都行，那么这两个都行的时候我们就重新来构建。这个地方应该是七，这里应该是八，我们重新把它构建，你写七八过来，这个图应该是错了，按一个是错了啊，之前改的时候没改到 啊，在以七跟到八，你看这个地方就对了。七跟到八加起来是多少？十五这样来构建呢 啊，所以这个七跟他八，他就没有了，好构建呢？十五，十六，这两个都比我这个职要小，那我就直接把这两个合并起来，合并起来呢，构成了二十六，二十六又跟这里面的小的哪一个呢？十六，那就把十六过来。那么一般左边的是更小，右边的直呢？是要更大， 右边的脚跟大，所以要把石榴放到左边，每一个都是这样啊，你看他的龟裂，这就是我们构建哈弗曼树的一般的龟裂，你一定要记住这个规裂，来 啊，然后再得到四十二，四十二，四十二里面还有个三十，再把三十得出来，这个就是我们构建的什么哈弗曼术。那么有了这个哈弗曼术，这一期求他每一个叶子节点的前职会求吗？这个，这个都是叶子，叶子的，你都按照的规则蕊家进行得到 雷佳竞得的啊，这就是我们所说构建的哈弗曼术，就这样来构建好，那么有了这个哈弗曼术的构建他的思路，我们最终的作用是要来构建他的哈弗曼编码，那么等一下我们再来讲哈弗曼编码。

直观理解哈弗曼数，哈弗曼编码呢，是由哈弗曼在一九五二年发明得到的，然后为了纪念他的成就呢，就把他编码当中用到的这种特殊的二叉数啊，称为哈弗曼数。我们平时用到的这个压缩和解压缩技术呢，都是基于他的研究发展而来的。 让我们来直观理解一下，哈弗曼数到底是什么样子。我们都知道呢，现在推行的是这个素质教育，所以说很多学校啊，都已经不再公布学生的成绩了，转而是用这个不及格，及格良好、优秀啊等等的标签来代替。 但是对于老师来说呢，他首先肯定还是要对这个学生的分数进行一个计算，然后再根据各个的区间呢，对学生进行一个打标签的这样的一个行为，整个的这个流程啊，就可以用这一段简单的代码来表示一下。但是呢，这个流程其实存在一个问题，就是一份 设计的比较合理的试卷呢，他其实是让学生的成绩呈现一个类似正态分布的一个样子，也就是说非常优秀的呢和不及格的学生啊，其实占比都是非常低的，大多数的学生都是处于中间的这个良好的这样一个状态。 但是呢，我们可以看到啊，刚才的这个判断流程里，当我们得到一个试卷，一个分数的时候，首先就是要对他判是不是处于不及格的这个区间，而实际上呢，不及格的这个区间占比是非常小的。举个例子来看一下，假如说我们现在有这样的一个学生成绩的分布的情况， 我们可以看到啊，在七十分以上的这个成绩呢，基本上都要经过三次的判断，但是实际上呢，这一部分的成绩的同学占比是最多的，就可以看到这样的话，这个流程整个的效率是非常低的，所以说呢，其实我们就是应该把 这个占比最高的一部分的成绩作为判断的第一个环节，也就是七十到七十九分的，然后其次呢就是这个八十到八十九分的，这样呢，其实也就是一个哈弗曼术的一个通俗的直观的理解了。好，今天的分享就是这样，这是艾瑞斯，拜拜。

同学们好，今天我们来讲数据结构与算法课程第六章数和二岔数中的哈弗曼编码算法。上节课我们介绍了哈弗曼编码的方法， 在此基础上，今天我们来讨论算法实现。首先回顾一下哈弗曼编码的构造方法。当我们已经根据不同字符的使用频率构造了一颗哈弗曼术，存储于静态三叉链表中的时候， 由哈弗曼树构造哈弗曼编码需要从叶子出发，从下向上走一遍，从叶子到根的路径，每经过一条路径上的分支，就判定求得一位哈弗曼编码值。每个叶子节点的哈弗曼编码 应该是由后向前逐位生成的，当前节点为父亲的左孩子，则当前求取的编码位为零。当前节点为双亲的右孩子，则当前编码位为一。 当由叶子一直走到了根的时候，就逆向完成了一个叶子节点哈弗曼编码的构造。下面我们来看这样的一个例子，这个例子有五个叶子节点哈弗曼数，他的静态三叉链表在左边， 五个叶子的结点分别对应着下标一到五的位置。我们来看全值为七的这个叶子结点，他的下标是一。双亲是七，而七的左孩子是一，因此当前编码位是零。七的双亲是九，而九的左孩子是七， 因此当前编码位还是零。九号节点已经是根了。因此我们知道全职为七的这个叶子节点的哈弗曼编码是零。零。 来看全职为三的叶子节点，其下标是二。二的双亲为六，而六的左孩子是二，因此当前编码位是零。 六的双亲是七，而七的幼孩子是六，因此当前编码位是一， 七的双亲是九而九的左孩子是七。当前编码位是零，九号节点是根，因此全职为三的这个叶子节点的哈弗曼编码是零幺零。再来看全职为五的这个叶子节点，其下标为三，三的双亲为六而 六的幼孩子是三，因此当前编码位是一，六的双亲是七而七的幼孩子是六。当前编码位是一， 七的双亲是九而九的左孩子是七。当前编码妹是零，九号节点是根。因此权之为五的这个叶子节点的哈弗曼编码就是零幺幺， 以此类推，全职为九的叶子节点哈弗满编码是幺零，全职为十二的叶子节点的哈弗特别码是幺幺。至此，我们就求取了每个叶子节点的哈弗满编码。 在认真书里总结上述哈弗万编码求取过程的基础上，我们讨论算法实现的问题。首先讨论 存储结构，算法中求取的每个叶子节点的哈弗曼编码，最后要存储在一种字符数组中。针对每一个叶子节点的哈弗曼编码是由后向前足位求取的这一情况， 在算法中我们另外设置一个自负串，用来暂时存储求取的每一位哈弗曼编码。 当一个叶子节点的哈弗曼编码求取完成之后，我们再把它完整的复制到那个哈弗曼编码字符数组中来看。这个 cd 就是攒存编码的字符串。最后一位设为字符串的结束标志。 在由后向前逐位求取叶子节点的哈弗曼编码时，我们设置一个死大下标指示器，在 求取编码的过程中，时代始终指向的是当前 cd 自负串中已经生成的哈弗曼编码的最前面一位。 当一个叶子节点的哈弗曼编码求取完成，我们就将其复制到下面的这个哈弗曼字符数组中，然后 cd 再去求取下一个叶子节点的哈弗曼编码，求取完一个编码再复制到下面的数组中， 这样就可以完成所有叶子节点的哈弗曼编码的求取。至此，我们给出算法的存储结构定义。由于每个哈弗曼编码的长度不等，因此按编码的实际长度动态申请空间单，要 使用一个指针数组存放每一个编码数组的头指针，所以首先定义这个指针型数组，图中的 hc 就是该指针型数组变量，然后定义 cd 这个自负串。还有四大， 接下来讨论算法。我们来看构造哈弗曼编码的算法函数，其参数传递的是静态三叉链表存储的哈弗曼数以及刚才定义的字福串。指针数组 还有叶子节点的个数 n。 算法开始，首先根据叶子节点个数 n 定义 cd 自负串的长度，这个长度足够用。然后给 cd 自负串的最后 后一位设为自护串结束标志。接下来进入循环，逐个求取叶子节点的哈弗满编码。循环控制变量 i 从一到 n 变化， 对应的是在静态三帕链表中下标为一到 n 的这 n 个叶子节点循环体内。首先给 stha 至出值 n 减一指示的是 cd 自负串的最后一位， 因为前面已经讲到，斯大在整个算法过程中始终指向的是当前 cd 中已经生成的哈弗曼编码的最前面那一位。 c 指针用于指向当前叶子节点， p 指针始终指向 c 的双亲。下面进入循环 求取当前叶子节点的每一位哈弗满编码。当 p 不为零的时候，表示还没有走到根节点，此时要来判定 p 和 c 的关系。 如果 c 是 p 的左孩子，则求取的当前编码位是零，放入 cd 数组中，此大减一所指的这个位置，也就是当前已经生成的哈弗曼编码位的在前面一位。 若 c 不是屁的左孩子，则屁的右孩子求取的当前编码位是一 同样放入 cd 宿主中四大减一所指的位置。当前编码妹求得之后，要把 c 移动到 p， p 再次指向 c 的双， 以便循环求取下一位哈弗曼编码，这个循环一直到 p 等于零，即 c 已经走到了根结点为止。当前叶子结点的哈弗曼编码求取完成。 接下来来申请存放哈弗曼编码的字符数组空间，空间大小由 n 减死大决定， 这是当前叶子也点哈弗万编码的实际长度，申请的空间由 hci 指针指示。 然后我们把 cd 字符串中以四大为开始位置的哈弗曼编码复制拷费到 hci 指针所指的新申请的字符数组空间内。此时一个叶子节点的哈弗曼编码 求取完成。算法进入下一次循环。循环变量爱增值一，继续求取下一个叶子节点的哈弗曼编码。待整个循环结束， n 个叶子节点的哈弗曼编码求取完成之后，我们把 cd 数组释放掉，算法结束。这就是我们要学习的哈弗曼编码算法。 好，关于哈弗曼编码算法今天就介绍到这里，同学们回去可以自己设计一颗哈弗曼术， 走一下这个程序，看看 cd 自付串的求取变化过程，以及最终存放叶子节点哈弗曼编码的自付串数组的申请，以及复制拷贝编码的结果。好，今天的课程就讲到这里，谢谢大家。

同学们好，今天我们来讲数据结构与算法课程第六章数和二岔数中哈弗曼编意码的相关内容。在当今的信息社会中， 信息传输与数据压缩等有着广泛的应用。在信息传输等实际应用中，需要将信息文本中出现的字符进行二进制编码传输后又要将二进制编码译为原先的信息文本， 这就是典型的编码与依码问题。在编码与依码问题中，编码的设计非常重要，他关乎信息传输的质量与效率。 为此，在编码设计中需要遵循两个原则，第一要保证编码能够唯一的被溢码。第二要保证编码长度要尽可能的短。而利用上节课所讲的哈弗曼数，就可以设计平均长度最短的编码。 在讨论哈弗曼编码之前，先介绍一些相关的基本概念。首先介绍的是等长编码和不等长编码，等长编码是每个字符的编码长度相同， 不等长编码是根据字符的使用频率设计编码，使用频率高的字符编码短，使用频率低的字符编码长。事实上，平均长度最短的编码一般为不等长编码。下面来看一个例子， 给定带编码的字符集是 a、 b、 c 等长编码，每个字符需要两位二进制编码，设计为 a 是零零， b 是零一， c 是一零。而不等长编码可设计为 a 是零， b 是一一， c 是一零。 现要进行编码的文本是 a、 a、 ab、 ac。 等长编码对应的结果为零零零零零零零一零零一零， 总长度是十二位二进制，而不等长编码对应的结果为零零零一一零一一，总长度只有八位二进制，可见不等长编码效率更高。然而，一般的不整长编码有一个致命的问题，就是不能有效 进行 e 码。来看这个例子，现有带编码的字符级是 a、 b、 c、 d。 设计的不等长编码为 a 是零， b 是 e、 c 是零、零、 d 是零一。如果要进行编码的文本是 a、 b、 a、 c、 a、 d， 编码，结果则是零一、零零零零零一共八位二进制。而对这八位二进制，在一码的时候可能出现一码结果不唯一的严重问题来看一码的结果，至少有这三种可能， 可以译为原来的文本， a、 b、 a、 c、 a、 d 也可以两位一亿码，结果就是 d、 c、 c、 d。 还可以一位二级 定制一亿码，结果就是 ab、 aa、 aaab。 这显然是一个不能容忍的严重错误。 此问题产生的原因就在于不等长编码的不等长性质一码的时候可以一位一码，也可以两位一码，造成了如此混乱的结果。 怎样解决这个问题呢？通过研究，人们发现，对于不等长编码，若想在各编码间不加分界符，就可以正确的、有效的识别其编码，必须是前缀编码。 那么什么是前缀编码呢？前缀编码的定义是这样的，任何一个字符的编码都不能是同一字符集中另一个字符编码的前缀。来看刚才的例子， 我们设计的编码为 a 是零， c 是零零， d 是零一。 a 的编码零既是 c 的编码，零零的前缀也是 d 的编码，零一的前缀不符合前缀编码的规则，所以不能正确的一码。 那如何设计平均长度最短而又能够有效识别的前缀编码呢？答案是利用上节课所讲的哈弗曼数来进行编码设计，就可以得到平均长度最短且能够有效识别的前缀编码。 下面我们就来介绍如何利用哈弗曼树设计编码。上节课我们介绍过，哈弗曼树是树的带全路径长度为最小的最优二岔树，其特点就是叶子结点的全值 越大，离跟越近。而构造不等长编码的原则是自符使用频率越高，编码越短。结合这两点，我们就有了利用哈弗曼数设计不等长编码的基本构想， 那就是每个带编码的字符对应一个叶子节点，每个字符的使用频率对应叶子的全值，每个字符的编码对应跟到叶子的路径。 这样就可保证使用频率越高的字符对应的叶子全值越大，梨根 就越近，编码就越短，满足了构造不等长编码的原则。下面来看这个例子。现有带编码字符集为 abcde 个字符使用的频率为五 五三二七八，以字符的使用频率为叶子的全值构造的哈弗曼数。如图所示，用哈弗曼数构造编码，要对数的分支进行标记，左分支标记为零，右分支标记为一。 标记之后从跟到叶子的路径上的零一序列就构成了该叶子相应字符的编码。来看， a 字符对应全值为五的叶子 根到该叶子路径上的标记为零零，所以 a 字符的编码就是零零。 b 对应全值为三的叶子，其编码是零幺零。 内推可知， c 的编码是零幺幺， d 的编码是幺零， e 的编码是幺幺。好，这 就是利用哈弗曼数设计的编码，称为哈弗曼编码。有了设计编码的方法，我们还应确保编码的有效性。既要确保哈弗曼编码是前缀码，并且是平均长度最短的前缀码，经过分析可以确认 哈弗马编码是前缀码。因为不同字符所对应的叶子结点不同，从跟到叶子的路径也不同， 即使有相同的前半段，到了后面对应不同叶子的路径一定会分开， 因此一个字符的编码就不可能是另一个字符编码的前缀，所以哈弗曼编码是前缀编码。经过分析还可以确认哈弗婉编码是最 u 前缀码，也就是平均长度为最短的前缀码。因为哈弗曼数是 wpl 值为最小的最优二差数，而 wpl 由公式 c 个码 w i 成 l i i 由一到 n 变化计算， 所以依据字符使用频率 pi 为叶子的全职 wi 构造哈弗曼数 eg 根到叶子的路径长度 l i 构造自负的编码长度 l i。 所得到的编码的平均长度应该是由公式 c 个码 p i 乘以 l i i 由一到 n 变化计算， 其与 wpl 一致，必定最小，故哈弗万编码为平均长度最短 的最优前缀码。现在有同学可能就会进一步的提出问题了，当我们已经根据不同字符的使用频率构造了一颗哈弗曼数，存储于静态三踏链表中，我们如何能够求得各个字符的哈弗曼编码呢？ 好，这就是下面要介绍的内容，哈弗曼编码的构造。当哈弗曼术存储于静态三叉链表中，我们由哈弗曼术构造哈弗曼编码需要从叶子出发， 从下向上走一遍，从叶子到根的路径，每经过一条路径上的分支，就判定求取一位哈弗曼编码值。每个叶子节点的哈弗曼编码 是由后向前逐位生成的，当前节点为双亲的左孩子，则当前求取的编码位为零，否则当前编码位为一。 当由叶子一直走到根的时候，就逆向的完成了一个叶子节点哈弗曼编码的构造。 下面通过一个实力具体介绍哈弗曼编码的构造方法。这是一颗哈弗曼树及其静态三叉链表，共有五个叶子，从下边唯一的叶子开始求取编码， 该叶子的双亲下标是七，七号的左孩子是一，所以当前编码位就是零。再看七号的双亲是九，九号的左孩子是七，当前的编码位还是零，这样 就求取了一号叶子节点的编码零零。再来看下标为二的叶子，他的双亲是八，八号的左孩子是二，当前编码位是零。再看八号的双亲是九，九号的右孩子是八，所以当前编码位是一， 这样就求得了二号叶子节点的编码是一零。如此类推，其他三个叶子节点的编码也可以求得，分别是三号叶子编码是零幺零，四号叶子编码是零幺幺五号叶子编码是幺幺。 好，这就是哈弗曼编码的构造方法。学会了编码的构造方法，我们接下来来介绍如何根据哈弗曼数进行溢码。与构造编码的过程相反，根据哈弗曼数进行溢码， 需要走一条自上而下，从根到叶子的路径来完成一个字符的一码，当前带一码的直为零，走向左孩子当前带一码的直为一走向右，孩子这样从根走到叶子就完成了一个字符的一码。 下面来看一个实力，这是一颗有五个叶子的哈弗曼树，各叶子对应的字符和边码，如右边的图所示，献给出代意码的零幺信息串为零零一零零一零零一一一零一一。 一码的过程如下，从左至右逐位的扫描读取代一码的信息串，同时从树根开始，根据读 取得信息位进行一码。首先是零走向左孩子还是零走向左孩子到达页子一码 a。 从根开始，信息位是一走向右孩子，信息位是零走向左孩子到达页子一码 d。 从树根开始，信息位是零走向左孩子，信息位是一走向右孩子，信息位是零走向左孩子到达叶子一码 b。 如此类催，最终的一码结果是 a， d， b， c， d， e 这一一码方法非常的简单，并且效率很高。这就是今天所要讲的哈弗曼编译码的内容，下次课将要继续讨论哈弗曼编码的算法。好，今天的课程就讲到这里，谢谢大家。

压缩文件在我们日常生活中用途十分广泛，几乎随处可见， 他为我们节省了大量的网络传输资源和存储空间。这期视频我们就来聊一聊最简单也是使用最广泛的一种压缩算法，哈弗曼编码。首先我们通过一个简单的例子来看一看信息在计算机中的存储，这里有一串字符， 而计算机只能存储二进之数，所以我们要先把这串字符转化为二进之码来保存。最简单的方法，我们可以使用定长编码来一一存储， 比如我们每三位二进制码对应一个字符，就像这样，那么解码的时候呢，只需要按照表中的编码规则，每三位二进制码解码为一个对应字符 即可。比如说在编码后的串，我们一次读取三个字符，前三个是零零零，查表可知零零零对应的是 a， 我们就把这三个字符解码为 a。 这种定长编码存储方式最简单，效率也比较高，但是占用空间比较大。那么有没有一种实现简单同时又能减少占用空间的编码方式呢？答案是肯定的，哈弗曼编码就是其中之一。下面呢，我们就来尝试使用哈弗曼编码来压缩这段字符。 哈弗曼编码是通过构造哈弗曼数得到的，所以要了解这种编码，首先我们需要知道一点数和二差数的知识。数是一种非线性的数据结构，右图就是一颗数。图中的 abc 也叫做节点，节点不仅包含数据，还包含指向 其他节点的分支。 a 又叫根节点，节点的度就代表节点拥有的分支个数，比如说节点 a 的度是三， c 的度是零，叶子节点就是度为零的节点。一 hci 都是叶子节点 路径和路径长度。路径呢，就是指竖中一个节点到另一个节点分支所构成的路线，路径长度呢，就是这个路线上分支的个数。比如说 a 到 h 路径长度为三， 那么二叉数，顾名思义就是节点的度小于等于二的数，并且他的子数有左右之分，顺序不能颠倒。右图就是一颗二叉数。 带旋路径长度是指如果一个节点具有全值，那么从该节点到根之间的路径长度乘以节点的全值，就是该节点的带 带全路径长度。比如说 a 结点的带全路径长度就是六乘三等于十八。竖的带全路径长度就是竖中所有叶子结点的带全路径长度之和。右图二差数的带竖的带全路径长度就是四十九。 那么有了这些知识，我们就可以尝试构造哈弗曼编码了。这里我们多说一句。哈弗曼数一般来说是二查数，虽然哈弗曼本人的论文和实际应用中都出现过哈弗曼恩查数， 但是呢，二叉的哈弗曼数是使用最多也是最简单的一种，所以这里我们就以哈弗曼二叉数为例来向大家介绍哈弗曼编码。要构造一颗哈弗曼二叉数，首先我们需要确定节点的全值，对于一串字符来说，我们把出现次数作为某一个字符的全值。 首先将 abcde 看作是只有根节点的数，任意选出全值最小的两个根 bd， 将他们作为左右子数，构造一颗新的二叉数，新的二叉数根节点的全值为 bd 两个节点全值之和， 并且把新生成的二叉数加入集合，这个时候呢，原来的集合中除了剩下的 ace， 还有新加入的由 bd 组成的二叉数。注意， bd 组成的二叉数，我们只考虑他们跟节点的全职，而不考虑 bd 本身。 然后呢，我们在剩下的四个节点中再选出全值最小的两个节点组成二差数，反复循环，直到最后全部节点都并入二差数。这种生成算法是一种典型的贪心算法。然后根据这个生成的哈弗曼数，我们再进行 编码，从根节点出发，遇到左分支编码为零，遇到右分支编码为一。比如说我们以 a 为例，从根节点出发，直接走一次左分支就能到达 a， 所以 a 的哈弗曼编码是零。 我们根据这个哈弗曼编码规则对原字符串进行编码，最后生成的串长度是二十九，相比于刚刚的定长编码三十九确实短了很多，有效压缩了数据。 解码的话呢，我们只需要从哈弗曼数的根节点开始，顺着编码后的字符串走，遇到临走左分枝，遇到一走右分枝，直到最后走到叶子节点。 比如说我们这里编码后的串，第一个是零，我们就走左分之，直接遇到了 a， 那么零就翻译为 a， 前三个零就是三个 a， 然后呢，后面 是一，我们就走右分之一，后面又是零，再走左边零，后面又是一，再走右边，这个时候遇到了 b， 所以幺零幺就翻译为 b， 以此类推。 并且对同一数据来说，哈弗曼编码不为一，因为可能有多个节点全职相同，而我们又是任意选择的两个全职最小的节点有多种不同的选法， 所以对于同一组数据可能会出现不同的编码。但是无论是使用哪一个哈弗曼数，数的代权路径长度都是相同的，在实际应用中都是等价的。哈弗曼编码跟之前说到的定长编码不同， 它是一种变长编码，全职越高的字符编码越短。这个时候可能会有同学问，既然不定长，有没有可能一个字符的编码是另一个字符的一部分呢？比如说，如果 a 的编码是一， b 的编码是一一，那么如果遇到四个一，是解码为四个 a 还是两个 b 呢？这里我们就扯到了另一个概念，前缀码。在前缀码中，任意字符的编码串都不是另一字符编码串的前缀，因此不会产生奇异。 观察哈弗曼数，我们可以发现，哈弗曼数的根节点到任意叶子节点的路径都不可能是通往其余叶子节点的路径，也就是说，哈弗曼编码恰好是前缀码，所以哈弗曼编码也不会产生奇异。 这个时候可能又会有同学问，任意构造一棵二叉树，同样能构造出前缀马，为什么非得是哈弗曼树呢？这是因为在所有的情况中，对于哈弗曼树来说，树的带权路径长度是最小的。哈弗曼边马产生的不仅是前缀马， 而且是最短前缀码。哈弗曼编码是一种非常重要的无损编码方法，在很多压缩算法中都使用到了它。 关于压缩算法还有很多丰富的内容，限于时间关系，我们不再展开，有兴趣的观众可以自己搜索了解一下。