00:00
各位,我们继续来看赫夫曼编码的下一步,大家看到了,我们已经完成了将这一个字符串。对应的赫夫曼树创建起来了,对不对,但是大家要知道,你光有这一棵赫夫曼,光有这一棵赫夫曼树没有用,你还得拿到什么呀,你还会拿到对应的赫夫曼编码。因为你只有拿到后编码,你才能够对这一个字符串进行编码,得到它编码过后的数据对不对,所以说大家看我的思路呢,继续往下走,我们已经生成的赫夫曼数,下面我们继续往成任务,生成的赫夫曼数对应的这个赫夫曼编码表我没拿到,比如说空格,它会生成01A,生成100啊啊,我再说一遍啊,这个这些。各个字符对应的这个,呃,赫夫曼编码呢,跟你生成的赫夫曼数是有关系的,所以说它不一定完全相,不一定完全相同,但是我讲过,不管你是否相同,最终生最终用赫夫曼编码得到的这个编码后的这个数据的程度是一样就可以了,也就是说只要是133就可以明白我的意思吧,好,现在呢,我们这样子,我们先完成第一步,将生成的赫夫曼数对应的赫夫曼。
01:22
编码表先给大家拿下来。大家记住啊,我们生成这个赫夫曼数的时候呢,我们规定好了这个数的向左边它的这个路径为零,向右边它的这一个路径的值为一,这点大家要非常清晰,好了,现在我们来完成这样一个任务,就是将生成的赫夫曼数对应的赫夫曼编码表给生成起来。好,打开我们的这一个eclipse,我们开始编写这个代码,在哪编呢?咱们在这里边吧。
02:00
好,生成的赫夫曼数,对啊,生成赫夫曼数对应的赫夫曼,赫夫曼编码表,首先我要做一个思路分析,第一步呢,同学们想一想。我们将来把这个赫夫曼编码表放在一个什么样的数据里面去呢?显然我们放在map里面是比较合适的,是吧?我们先写一个纯将将什么呢?注意听江赫夫曼编码表。编码表放在哪里呢?存放在存存放,存放在哪里比较合适呢?放在一个map中比较合适,好,那这个map。这个它的类型呢,我们就直接写下来了,就是俊。啊,史俊,那就说将来这个赫夫曼编码表里面放的东西就是我们的,呃,这个map就是我们放的这个赫夫曼编码表。啊形式大概是什么样的呢?我写的写的对啊形式呢,大概是这样子的,就是说啊比比如说。
03:06
呃,你这比如说是这样子的。就这样子。将来这个形式如这样子。那当然这个地方空格肯定就是对应的32了。32对应个零零啊,像这样子啊,32对应它呢,当然是97 97呢,对应它DA对吧,ABCDD是多少呀,DA是97嘛。呃,加上四个应该是101。Abcd加,加上100加上三个就行了啊,加三个那就是100对应这个值,以此类推啊,以此类推等等,这个后面我就不写了等等。但。等等,好,但这地方我还要说一遍,我还要说一下啊,就是你将来这个赫夫曼编码表不一定跟我写的这个一样,不一定啊,因为我说了跟这个科曼数有关系啊,就说形式是这样子的,但不一定完全跟我这儿一样啊,再说一遍形式,我再想着啊,形式是这样子的。
04:09
好,那第二步同学们想,你在把这个甚至这个赫夫曼编码的时候呢,你肯定是要去便利各位同同学,听我说你是不是会去从这个根节点往下一个的找啊,那找的过程中是不是要把这个0000保存起来,是不是应该用一个字符串保存。是不是字符上保存,那么我们在便利过程中呢,我还得有一个值,就是在。在生成生成这一个夫曼赫夫曼编码表时,需要不停的,需要干什么呢?需要去拼接,去拼接这个路径。是不是要拼接这个路径呢?所以我们创建一个什么呢?String builder,好,我现在干什么呢?我要这样啊,定义一个string builder。
05:04
BU builder怎么写啊?Bubu DR是这个builder干什么呢?存储,呃,就是呃,干什么呢,存储。存储某个叶子节点,叶子点的这个路径我说清楚了啊,那现在我们把它也建起来,这样先把这这两个建起来了,那第一步首先呢,我建一个static。String builder b builder builder。Builder啊,写错了,Builder。那它是什么呢?咱们就叫string build吧,String build等于六一个string build,这个没问题啊,那上面这一个客分编码放到这呢,我们也创建起来叫sta。首先第一个什么呢?嗯,Map map,它里面放的K是bit,它的值是string。
06:01
啊,也就将来这个地方对应的,比如说三十二一对应个0001 97对应个一百幺零零对应个11000,对是这样子的,那我这直接写个什么名字叫哈弗曼编码哈曼cos,诶这些啊叫cos跟上我的思路,Cos等于什么呢?我六一个哈希map。是这样子吧,同学们,我留一个哈希map好,里面呢,我们也可以把它写上去啊,叫bit。Bit,然后OK。好,同学们,这两个就创建好了,创建好过呢,我们就来写这个方法,那这个方法怎么写呢?同学们你们觉得怎么写啊,是不是这样写就可以了,来写一个private private static,注意听啊,这个稍微有一点绕。Get扣子是不是得到这个客曼编码,我叫get扣子,然后呢,首先你把这个节点给我no,好,你再给我一个,这个节点对应的这个路径的值就是扣的。
07:03
啊,然后呢,我把这个string builder传进去,并拼接string builder。好,那这个string builder,你就给我传一个string builder呗,啊,那是什么就什么了啊。好,同学们,我先对这个方法呢做一个简单的说明,不然待会大家不知道我要干什么,这个漏啊,就是它的功能先说一下。但是我写的这个功能是干什么呢?就是将。这个方法是将。将什么呢?呃,传入的传入的注意听no的,这个节点的注意听啊节点的。的所有所有叶子节点,叶子节点。的赫夫曼编码,编码干什么呢?干什么呢?就是存放到,就是相当于你,相当于是将传入node节点的所有叶子节点的编码得到。
08:03
并并放入到并,诶放入到哪里呢?放入到我们这一个哈哈曼扣这个集合中。他要完成的就是这个事情,先理解啊,先理解好,那么这个load呢,当然就是你传入的这个节点了。啊,界定了,默认肯定是从根节点传,是不是因为你便利,肯定是从根节点把它。跑跑一把嘛,是这样子吧,同学们好,传入的这个节点,那么Q的代表什么呢?各位同学,Q的代表它的一个路径,比如说打个比方,你要是从左边呢,如果是连左边就是零,如果是填填这个右边就是一,就是它的路径这个值,好吧,就路径这个值。就是他的一个路径。那么路径呢,是左边的左子节点,注意听啊左。左子节点。左此节点。
09:03
好,这个很很讨厌啊,他每次都是找那个指着着止节点。嗯,左指接点啊表示什么呢?是零好右呢。右右指节点看,又又是一个节点,讨厌指。节点。好,右子节点是一。又是接好这个string builder是用来干什么呢?是用来拼接这个路径的,是用于用于拼接啊,是用于拼接路径。拼接这个路径的,好了,嗯,那这几个字拿到功了,下面我就开始写代码,大家看看能不能首跟上啊,首先我用你这个string build传递的build构建一个是新的string builder。String。String啊,有点卡啊,String builder。对吧,String build,你你给我传进来,然后呢,我把你传进来string builder用一下。
10:05
呃,用一下用一下过了,我产生一个BUILD2。那这个二有什么用呢?待会要拼接,我用一拼接将什么呢?将传入的code啊,加入到加入到十寸BUILD2,因为你每次来了过后就不就要加一次嘛,对不对,所以说死尊BUILD2。时间,Build2.2.end谁呢code?来一次加一次,呃,那么加一次过后呢,我们现在来判断,如果漏注听啊,如果漏不等于空,我们才去处理。因为你在不停的往下,这个变递归的时候,总有一种可能性,它漏等于空了,因为它一直往下走,对不对,如果漏等于空,我们就不要去处理了,就是如果load等于空,不处理。为什么不处理呢?因为现在已经是空节点了。那这个漏不等于空,你下面应该怎么做?同学们是不是要去判断当前?
11:06
当前这个node。是叶子,节点是叶子。节点还是什么呀,还是非叶子节点,非叶子节点。是这样子的吧,好,现在什么情况下它是一个,它是一个非叶子节点呢?就是如果node.data。他。等于空说明什么问题?说明它是个什么节点?它是一个非叶子节点。飞。非叶叶子子节点。是吧,你看又是这个解,真讨厌这个。啊。非叶子节点,它是非叶子节点,如果它是一个非叶子节点,我应该怎么办?同学们是不是要递归递归?递归处理,因为你还没到头啊。
12:01
那现在如果向左递归,注意听啊,向左,如果向左的话,是不是应该这样写get扣子。然后把这个漏传进去。向左吗?那是left吗?向左的话,我们知道这个扣的应该是零,大家理解吧。好,把这个实训二呢往下传,因为他还要。拼接嘛,它下传到这又产生一个又拼接,最后不就是一个呃一一个串了吗,向左递归。左递归好,如果向左递归处理过后,你是不是还得向右递归啊,你向右递归别忘了啊,向右递归。向右递归,如果向右递归的话呢,同学们。那这个漏的这边这个扣就应该等于一,这个大家看能不能理解是吧,一个向左一个向右,那这边我们少了一个right。好,那我问大家一个,问同学们一个问题,假如node它的这个data不等于空,说明它是一个什么节点,各位同学请说,说明是一个叶子节点。
13:08
这个大家能理解吧,如果是叶子节点是不是就应该停止,就相当于说你你在找这个找在便利这个过程中,其实他已经这个这个就可以结束了。是不是这次就可以结束了,如果是个叶子节点,各位同学,各位同学,那这个时候呢,就表示表示找到找到了某个啊,某个叶子节点的最后是这意思吧,最后那整个把这个路径放进去就可以了。放入,那就是half man code.put。Put什么呢?Put就是你这个点,对,然后值是什么,同学们,值就是我们最build。但是这个这个地方放着,人家要求是字符串,你是build,这是不可以的,是不是把build转成一个string就完事了,代码就写完了。
14:04
大家看这这段代码就写完了。这段代码呢,如果我们这个漏传的是一个。就是哈弗曼数的根据点,那么你会发现你在打出这个map的时候就已经把这些哈弗曼编码已经拿到了,我来试一下。来测试一把啊,同学们。测试一把是否生成了对应的哈夫曼编码。注意啊,哈弗曼编码是跟你的这个哈弗曼数是有关系的,理解吧,你不同的哈弗曼数生成的哈弗曼编码是不一样的,理解好,我写一下吧,那现在呢,我们就叫get code。Get code,然后把什么穿进去呢?就是我们哈曼的这个跟节点,那大家想一想,你如果传跟据点的话。你节点的上边,你根节点上面的有有有这个左右吗?有没有先说是不是没有啊没有,其实这个地方作为根据点传的时候呢,其实应该传个空。
15:08
好,然然后再把build传进去,你build是不是在这已经已经创建好了。是不创建好了,也就是说你通过这个方法呢,是build我们也用到了,因为他们是在在不停的使使用这个东西嘛,那下面这一个呢,我们主要看的是哈曼扣这个map是否是否生成呢?来我们看一看。我们生成一下啊,同学们就说它生成的。呃,生成的哈夫曼编码表是什么呢?来捋一捋,我就直接在后面打就完了啊,加上我们这一个halfman扣扣子没问题吧,各位同学。是不是哈曼扣纸,那它打印出来这个样子,形式应该大致是这样子,32对应一个什么零一九十七对应一个什么字,但是我说了啊,不不一定完全跟我这说的一样,有可能是不一样的,因为你生成的赫曼数呢,呃,不一定跟我那个图画的一样,来走一个,我们运行一把。
16:14
各位同学可以看到,诶,第一个三十二零一。就是空格呢,呃,这个好,好像跟我们一样,三十二零一,也就是说你看这32。打开啊,就说你这上哪去了,再再运行一下再预习啊,同学们三十二零一九十七是AA呢,是100,好,这个就跟我不一样了,看到没有。我在10100好像一样的哈。是一样的吧。看看啊。诶,往下拉。97是100,九十七九十七是100,我看看我这边写的是不是100。好,就是幺零对的啊,对的对的好,大致就这样子,这个意思我就说完了,也就是说现在我们已然拿到了这个赫夫曼编码,现在对于我们来说呢,我们生成的赫夫曼编码其实就是长这个样子的。
17:07
对我这种运行的这个情况啊,我们生成的后面编码呢,现在就可以把它放到这了。是吧,长得是这个样子的,长得这样子的好,那现在大家再来看,目前我们这样写呢。我们这样生成一个赫夫曼编码呢,这个方法呀,我想再做一个包装,大家看你现在。在哪去了?在这是吧,盖着扣子,那么现在呢,我想我想这样子,你这这传了太麻烦了,咱们能不能这样处理,就是你把一个根节点给我,你把一个根节点我,我就给你返回一个赫夫曼编码,是不是更好一点啊。所以说现在呢,我准备把这个方法进行一个简单的处理,简单处理把它重重载一下,让我们调用更简单,好,我现在重载一下同学们这里为了为了调用方便,调用方便我们重载重载。
18:06
这一个get扣子,好吧,Get扣子,那我现在重载一把,比较简单的一种方式,好调用它private。Private,然后呢,这个方法我们取一个名字叫什么呢。哦,我们就叫static。Static,然后返回这个map,这个map呢,K是bit,对string,然后呢就写一个get cold。Get一个扣子,你把什么传给我呢?好的,你给我传入哈弗曼编码,哈夫曼数的。跟节点。就可以,那我怎么调呢?我就调啊,如果你传的这个root它等于空好,那这个事情我们就不玩了,直接return一个no就完事了,相当于说你没没没办法处理好,如果说这个不等于空,我就干什么呢,处理root的左指数。
19:05
是不是这个更简单啊,左指数,左指数怎么处理,是不是get我们这个code。Code,然后呢,把route route点它的左指数传进去,左指数这边呢,传的是零没问题吧,好,然后把这个string builder传进去就可以了。那么再接着处理什么呢?处理我们root的什么呀?右子数一样的道理的的右子数没问题吧,那也是get一个扣。干什么呢?Low就是root点我们的right,那向right向右边呢,它的这个code码就是它的路径值,我们用一表示的就处理完,处理完了过后是不是我们直接return我们最后的这个half man code就完事了。那也就是说以后我们在调用的时候呢,就没有这么麻烦,怎么调呢,大家看啊,原先是我们这样调用的不太方便,我就直接。
20:07
把这个去掉就可以了。看起来比较简洁嘛,说你把一个赫夫曼树的根节点给我,我就给你返回一个赫夫曼编码,诶这样不是挺好吗?对不对,好的,我这呢生成一个变量。这边我们就叫哈夫曼。Halfs就完事了。就完事了,当然我再说一遍啊,就是如果你你不接收,如果你不接收,其实你这一个哈弗曼扣也也已经生成了,只是我为了方便呢,就是让他返回。让他返回这个,这个就是为了调用方便而做的,好,我们再来看看目前这种形式能不能使用,为了以示区别,我在前面打一个波浪号,就看到确实有变化好不好?看看有没有有没有生成走一个。好,同学们看,呃,还是一样的,还是一样的,没有任何问题,没有任何任何问题,好了,同学们,那关于我们。
21:05
就是是这个知识点哪个这里呢,就是数据压缩的第二步,生成我们的赫夫曼编码,就先给大家讲到这,大家看看能不能理解,代码也不多是吧,就是生定义了两个属性,然后呢写了两个方法,而且第二这个方法其实主要是重载,没有实质性的东西,真正干活的呢是我们。盖扣子这个方法大家理解一下好吧?好,这讲先给同学们聊到这里。
我来说两句