00:00
各位同学,我们来完成使用我们刚刚生成的这个赫夫曼编码来生成赫夫曼编码过后的这个数据,也就是说我们假如这有一个字符串,那么最终我们生成了,生成的就是赫夫曼。编码。嗯,处理过后的这个数据明白意思吧,好,现在呢,我们把这个代码给大家一边写一边做,呃分析,还把这段代码写到哪里呢,咱们写在上边。咱们写在这个位置,好吧,来,同学们跟上我的思路。跟上我的思路。那现在干什么呢?我们编写一个方法。对,我们。编写一个。一个方法。编写一个方法干什么呢?将。将一个字符串。对应的这个bit数组。
01:00
数组干什么呢?压缩成跟呃,通过通过生成的这个赫夫曼编码,编码表干什么呢?呃,就是先给我传一个字符串生成的这个BA数组,然后通过生成的赫夫曼编码表呢,返回返回一个,呃。赫夫曼编码编码表处理过后的这么一个字符,字符数组,呃,字节数组,字节数组返回字符曼编码处理后或者压缩后的压缩后的一个BAT数组。好,这就是待会我们要做的事情,那么明白这个东西道理过后呢,我们来开始写东西。三我们返回的是一个bit数组Z。好,呃,那首先你把一个数组传给我,这是一个。没有处理过的数组,对吧,然后你把什么传给我们呢?把这赫夫曼编码表传给我,这不赫夫曼编码表实际上是一个map。
02:07
这样子吧,所以说我这直接写helpman halfman什么呢。Cause。好,这是这个方法,好,我在这里呢,先做一个注释,这个是什么啊,说明这是原始的,原始的字符串对应的这个BY的数组。好,这个就是我们生存的。生成的赫尔夫曼编码。赫尔夫曼编码它是一个map。OK,这个是返回什么返回?呃,就是赫夫曼编码处理后的一个bit数组。那我再举,呃举例说明一下,举例比如说你待会儿传的是。
03:00
这个。待会传的是这个字符串,注意听啊,这个字符串它对应的一个bit数组。这个拜的数组就是同学们说的这个玩意儿。明白意思吧。啊,就是他。也就待会传的是content by,然后我们返回的是什么呢?同学们注意听,因为你要知道这个,你待会知道老师在写什么,返回的是这样一个东西。呃。返回的是什么呢?返回的是。呃,如果说按照我们刚才分析的,返回的就是它。返回的是他。返回的是这个。对,这个对应的什么呢?不不不不是这个字符串啊,是这个返回的是这个字符串。这个字,这个字符串。干什么呢?对应的对应的一个bit数组。
04:05
BAT数组,那因为你你这个地方是个字符数倒数,以你是八位一个嘛。八位一个,也就是到时我们返回的直接输入,假设我是写了一个这个东西啊halfman。哈们这个编码hold code code hold,一个bit数组,那么它其实是八位一个。因为你这个支付算,那肯定是我要,如果说我不处理的话,它它还比以前还长了呢,你原先才40个40个长度,那你按支不算处理的话,那更长是不是实际上我是要八位一组。对什么呢?呃,是及及注意听啊及八位八个八位。对应。对应一个什么呢?一个bit。然后放入到哪里呢?放入到我们这个BY的数组中,就是这个BY数组中。
05:00
那就再说的再直接一点,就相当于说到时间这个这个啊,比如说我说的再直接一点,到时间这里面的第一个,他的这个数组里面的第一个元素,其实就是谁呢?其实就是这个对应的数就是幺。嗯,我我我我先弄八位啊,12345678,就是这个八位。它对应的一个bite。那这个BY到底是多少呢?说的再直接一点,就是要把它转成一个bad,这个到底是多少呢,同学们。大家知道这个是多少吗?这个呀是一,你如果把它看成一个BY的话,它是一个复数。大家知道吗?它是一个负数,它到底是多少呢?各位同学,它实际上是这个,这个其实是一个补码。他如果做的话,它是一个补码,他如果是补码的话呢,你你你要把就是相当于说这个东西,它对应的真正的BA应该这样推导。将推导呢,注意听啊,这个稍微有一点点难,有一点点难,就是它是一个补码,你先把它把这个补码推成他的反码,它的砝码是呃符号位不变,然后呢,呃,这个补码怎么样呢?是减一啊补码减一也就是这个,这样的话,12345678好减一。
06:25
那如果这个减一的话。好,如果这个减一的话,它就变成多少了呢?如果它减啊减一,那它就应该等于符号位不变,减一就是这个借一位。啊,其他都是000,那就是这样写的啊呃,我给同学们写一下。减一嘛,那就是这个符号位不变,这个地方也不变,这个地方变成了零,后面呢,变成了。三个一对一位两位,三位四位,五位,六位,七位八位,好这个这个就是。
07:02
刚才那个补码对应的反码。斑马。好,那么这个反码它对应的源码是多少呢?源码就是呃,符号为不变,其他再取反。就是它的源码了,那就是一这个地方就变成,那我把这个拿过来啊。那这个地方就是一变,符号位不变,这个一零变一,这个变零,这个变一,这个变一,这个变零,这个变零,这个变零,也就是说到时间,如果你把这个东西转成一个bit,它其实是这个数。带符号的,带符号它到底是多少呢?说的再直接一点,如果翻成这个,翻译成我们真正的数的话,它应该是这个数,好我我用这个计算器算一下哈。呃,我先来一个二进制粘过来。就这个这个是多少呢?转成十进制是88,那88前面有个一一代表负数,也就是说是负的88。
08:03
说的再直接明白一点,就是将来你这个哈夫曼。就是你处理完了过后,这个哈夫曼的它的它对应的这个字节数组的第一个元素就是什么呢?就是负的88。大家明白这意思吧,也就是说。也就是说将来呢,你翻译过来过后,这个地方的一第一位其实就是负的。88。负的88是不是这样子的呢?我们可以试一下啊,试一下呃,我这用一个方法来给大家测一下,我这有个test类,我该玩一把,比如说我这里有一个字符串。注意听啊,使得字符串的bit是什么呢?就是刚才同学们看的。呃,看到给大家分析的。这这个八个八位的一个字符串。OK。那么如果我把它转成大家看我用integer,这个integer呢,它有个方法叫pass in,后面大家看到没有,这有个red,就是指定是按什么进制来做的,那如果说我在这里把string better放进去,我把这个放大一点。
09:16
Better。放进去,然后呢,这边我写上二。写上二功能,我把它转成一个BY,因为你不把它转成BY的话,它第一位就不是符号位了,这个地方如果没有什么问题的话,它应该返回一个负的88。明白我在说什么吧,好,我们运行一下,我们可以。哦,这边应该代码有问题,他不让我执行,好先把它注销一下,OK,走一个。走一个我们可以看到他的确是负的,88看到没有说,那那有些有些同学说老师这个这个地方我有点听不懂了啊,听不懂那就那就对了啊,那有可能是因为你曾经欠缺一些知识,而且这些知识点是特别重要,同时又是特别基本的关于二进制的东西。
10:00
那我我再把我刚才那个概念说一下啊,待会我这个这个方法是要把你这一个字符串对应的BA数组转成我们。呃,通过哈夫曼编码过后的这一个字符串对应的那一个BAT数组。因为你原先只有40个嘛,四四十四十个字符,那这样子如果你不把它再重新每八位放置,放到一个BAT里面去,那变得更长了,对不对,那更不划算了嘛,所以说我是要八位处理,所以我先把这个说清楚,那你想这个东西你要除以八肯定就不会有,呃,40个这么大了,其实待会你可以算一下,其实它只有17个啊,17个BAT。啊,还是省了很大的空间。好,那关于刚才老师讲的这个东西,为什么推导出来是负的88,其实就是刚才我的这个推导过程,那有些同学在这块如果你欠缺关于二进制的源码、反码、补码的知识点怎么办呢?第一个方法你就是在网上自己去找一下,第二个方法呢,我这里有点资料,但这个资料呢,我不知道大家能不能看得到啊,你们可以到网上去看,我在讲。
11:13
Java基础的时候讲了二十二天的一个课程,其中在第三天我专门给同学们讲了二进制的内容,包括这里面其他进制转十进制,其他进制转二进制,二进制转八进制,16进制,其他进制转二进制,未运算。计算机的源码反码补码和位移,位移运算和移位运算在这个地方,其实诶对。说到这儿啊。哎,这我又把它删掉了是吧,不好意思啊。在在这个课程里面,就是第三天这里面呢,我把就是我把这个内容讲的是比较清晰和透彻的。那如果说你缺这点知识呢,你就在网上找一点,把二进制块稍微看一看,因为你作为一个学计算机的人,连二进制的源码反码、补码搞不清楚,那是出问题的,而且正数负数它不一样,对不对,所以这块呢,我就聊到这里啊好,现在我接着往下面写代码,大家不着急。
12:11
好,记着起来吧。好,呃,那现在明白这个道理过后呢,我们接着往下继续学,首先呢,同学们都知道我们。我们在整个处理过程过程中,实际是要得到一个这样的,先得到这个字符串,然后把这个字符串呢,经过这个处理,再得到我们这个字节的,所以说它整个过程是这样子的。呃,是先得先用,那应该是第一步干什么啊,听我说先使用先利用啊,利用我们这个赫夫曼编码表。啊将什么呢?注意听啊,将我们这个传进来的这个BYT数组,这个BAT数组,就是原始的BAT数组,转成什么呢?先转成。先转成同学们看到的这个玩意儿。
13:00
也就是转成什么呢?呃,赫夫曼编码后的那个那个赫夫曼编码的字符串转成赫夫曼。和夫曼编码。编赫夫曼编码对应的字符串,好,这个其实特别简单,那为了得到这个字符串呢,我首先要拿到一个build,这个大家能理解吧,因为你你要要进行这个拼接嘛,所以说我先念一个,先溜一个string builder,很简单的啊,String builder。好,Stream builder,那我先分配一个stream builder。好,这个时间build呢,咱们就不要叫二了,咱们直接就就就就一就行了啊,这个是一个局部变量,好拿到它。那拿到它以后呢,下一步该干什么呢?好,我们便利,我们便利哪一个呀,我们便利这个BY的数组。是不是因为这个数组是不是已经把这个I空格L一个一个给你拆开了呀。那呃,然后我们就开始写这句话啊,For循环bit b。
14:05
Bit大家看清楚了,这个BY词就是在便利它,那遍利的时候我怎么做呢?各位同学streambu,看这句话点end看清楚了怎么写?就是我们哈方编码表点get我们的B看懂了吗?好,如果说同学们有兴趣,你如果同学们有兴趣,你输出这个build,其实它就是这个圈了。是不是这样子呢,我们我们可以试一下。好,我们可以简单测试一下啊,测试一把,我们测试string builder等于多少呢?好,我们给大家看一下。Build连to string就完了,那为了能够测试,我先把这个地方改成贸易的啊,后面肯定不是返回贸易的,好,我现在来测一把。测试好,测试的时候呢,也非常简单,就用刚才的zip。
15:01
那这这个bit bit词就是我们的哪个呀,是不是就是我们刚才得到这个content bit。然后哈弗曼比哈弗曼编码表还是这个好,我们运行一下,大家看一下效果。同学们可以看到呢,你看视频B是不是就这个圈。而且大家有没有发现这个串串呀,其实就是133大一,一共是133个,呃,它的长度是133,我们可以给大家算一下。看一下啊,同学们注意听,我把这个打开给大给大家搂一下好保存,保存过后呢,我用一个统计工具给大家看一下,我刚才讲过,不管你的这一棵赫夫曼编赫夫曼树长什么样子,或者说你对应的那个赫夫赫夫曼编码是不是完全一样,但是它最终编码过后的这个长度呢?这个应该是133,我们统计一下。好,同学们看,的确是133。对不对,的确是133,是不是,呃,跟我们刚才最先分析的这个是一样的133,但是你看这个按照我们这颗赫夫曼树,嗯,推断出来的,呃,按照这个赫夫曼树推的一个赫夫曼编码,在推出这个赫夫曼编码对应的这个字符串是133,但是你发现他跟我的现在这个不一定完全一样,你看啊,我随便找一个。
16:26
呃,同学们看我在这输出已经输出来了。说出来了,你们你们看一下。你看这个是这样子的。我就截前面一部分哦,我就截前面一部分,那太多了,我也截不了那么多,大家比较一下,你们看并不完全一样看。你看1010。10011。你看这后面这这几位就不一样不一样了,你看这。你看这儿。10101,这个没问题,10101没问题,后面是001,后面你看这个不一样理解。对不对,不一样,那说明就是这两种方式,它生成的这个赫夫曼书并不一样,但是你会发现很神奇,你这按照这个赫夫曼生成的赫夫曼自符串是133,按照我这种方式也是133,看到没有,这就是我前面一直在强调这个问题,说大家呢,不用特别担心,说诶你这个在排序的时候,呃,不一样会造成赫福曼数不一样,这个没有关系,因为你最终生成的。
17:26
你最终生成的这个赫夫曼编码过后的字符串长度是一样的,因此它的压缩率是一样的。明白我的意思吧,好,现在呢,我们接着往下继续写。那你拿到这个东西呢?下一步该干什么了,同学们?下步该干什么?你们不要忘了一件事情,拿到这个没有用。因为这个东西如果你真的按照这个来传递,说说老师,那我要已经已经搞定了,那如果你一定已经搞定,你把这个string标转成支上发送的话,那反而不但没有,不但没有压缩,反而变大了,因为原先人家这个字长度才多少,才40。
18:02
是不是原先原先你你这个支付串的长度才40个,结果你整那个支付串你变成133了。不但没有变大啊,不但没有变,不但没有变小,反而变大了,肯定不行,因此呢,我们现在要有一个任务干什么呢?将。将这个字符串简单写啊,将你这个对应的这个字符串转成什么呢。转成一个败的数组。你这个拜登数组才能发送嘛,好拜色数组好,这个呢,稍微有点麻烦,大家认真听讲啊,认真听讲好。好,首先呢,我们先去计算,就是统计统计这个返回的。统计统计这个返回的。这这个。这个哈夫曼编码对应的字符串的长度有多大,就是它的它的认识长度。那么怎么怎么来统计呢?大家看啊,我先写个NS,注意听这句话,稍微稍微大家注意一下啊,首先呢,我我用这个build点它的这个嫩识好,如果他磨八。
19:09
如果它磨上八就等于零,说明什么?它刚好是八的整数,整数倍,如果是整数倍,那认识呢,就应该等于十,String点认怎么样除以一个八就搞定了。是不是我这个数组的哈弗曼编码过后对应的这一个字节数组啊,字节数组它就是这么长,否则否否则它说明它不能被八整除,不能被不能被八整除的话呢,我们是不是在这个基础上怎么样加个一就可以了。是不是这样就就把这个嫩子算出来了,但这样写呢,稍微有点麻烦,你也可以一句话搞定,你也可以这样写一句搞定啊,注意听,如果说用一句话。一句话搞定的话呢,这个代码就应该可以这样去写,怎么写呢,就是啊论等于各位,那就是。Jim有点嫩死。
20:01
怎么样啊,加上一个七。除以一个八就完事了。能理解吧,就你一句话也也可以搞定,你写成两句话呢,也可以搞定,无所谓啊,无所谓,因为上面下面这个衣服钥匙,它等价于上面这个写法,那我就还用下面这个比较好阅读好吧。好,那这个地方做完了过后,是不是长度就创建起来,现在呢,我们创建我们就可以创建这一个halfman code BAS了,这个能理解吧,那我就溜一个啊。啊,这个地方还不能不能用它,因为刚开始还要用一个临时的,先不要创建啊,我们先创建一个存储这样写啊,创建一个存储压缩后的这个bit数组。注意听啊拜的数组。也不是很难,也不很也不是很难,各位同学跟上我的思路,那这个BY的数组,我们刚才呢,已然统计到它的大小了,是不是?
21:02
BY吗?BY,诶,这个bit数组应该是这样写吧?BYT,走,把嫩S放进去不就完了吗?OK。啊,先做一个临时存储的,那临时存储现在你现在是不是要去便利我们这一个build。然后呢,根据实际情况,八位把的八位八位的放好,所所以说我现在开始做了啊,For循环n ti n ti等于零,I只要小于什么string lengths string build,点它的NS,我就可以说I干什么,这个时候是八位放一个,所以说I加八不长呢,就变成了八,这点大家一定要注意。这点同学们一定要注意,就是不长尾巴。因为小,这里因为是每八位。注意听啊,每八位。八位对应一个。所以。所以是不是,所以我们的不长,所以不长应该是加八。
22:04
这个同学们理解吗?约八位嘛,好,那如果这样做的话呢,我们就每八位,我们就把它放在一个string。使string by里面去好初始化一下,大家在我开始写了啊,如果我们这个啊,应该怎么写呢?哎,这样写就可以了啊这样写那怎么写呢,String bit。等于string build,注意看啊,开始截了,点string build里面是不是有个键sub string,那么就从I开始截多少呢?截I加八就完事了。是不是这样子,就说我每循环一次。我每循环一次,我就从这个I开始去取八位放到这个string be里面去,拿到这个string be以后,我们下面应该干怎么办呢?同学们,是不是我们就把这个string by转成,就按这样子转成一个BY,把它放进放到这个数组里面去就可以了,好下一步将什么呢?将string bit。
23:05
转成一个bit数。放入到放入到哪里去呢?各位同学,放入到我们这个BY就可以了。BY就可以了,那这个这个呃,这个地方我们取个名字叫。哈曼的bed也可以是吧?其实也是可以的,取这个名字也可以。啊,这样应该更更好,更形象一点,对不对,是不是更形象一点啊,就是啊,Half man code bits嘛,可以的啊,就那我就就写这个名字好的,呃,那么放到哪里呢?放到这个数字里面去,那就很简单了,咱们就这样写走,是不是这边有个变量啊。你现在不能是I,因为I是八位,所以说我现在要定一个计数器。你看,又要回头去写这个代码了。所以说写代码的时候,有时候你写着写着,你发现有个变量,你回头写进去就了,这个是记录什么呢?记录是第几个bed。
24:03
是不是第几个。好,那现在第一个呢,我们是末尾为零,那就是inex把谁放进去,同学们是不是把这个十寸转成一个bed放进去,刚才是不是刚刚讲过怎么写的in t。Inr,注意听哦,点purse。Int,然后呢,把这个寸bitt寸bitt放进去,按二位,注意前面一定要把它转成bit,否则类型不匹配。好,放进去,放进去过后,同学不要忘了,你在for循环的过程中,下一次,下一次同学们你是不是应该还要做一个处理,把这个呃应该怎么处理啊,把这个index怎么样。佳佳。代码就行了,但是我这样写大家有没有发现是有是有一个问题的,大家发现问题在什么地方。大家看啊,你上来过后每一次都是ii加八。我问大家一个问题,你敢保证我们这一个string builder的长度一定是八的倍数吗?
25:05
你无法保证。有,你这个Java有可能会出问题,会出什么问题呢,越界。比如说我上来过后,我我我上来过后,我的我的字符就是110,好,你存吧,你说你要从零取到八位,这哪有八位啊,一共才三位呢。所以这个代码呢,就是有一个问题,我们要把它补一下,怎么补呢?如果I加八看啊,如果I加八它大于注意听。Build了。点认识说明什么问题?各位同学,如果这个条件成立,说明其实你最后这一位不够,不够八位了,是不是说不够了。就是不够八位,就说不够不够八位。不够八位,那不够八位,你这个时候就不能这样去取,应该怎么取呢?非常的简单,把这句话呢,后面这个去掉就行,大家都知道,如果我这样string,呃,Sub string就是代表从这个位置取到最后有多少位取多少位不就完了,Else才是按照这个逻辑走。
26:11
好代码,这样子就比较完善。好,那通过这个for循环的,呃,一系列的处理,大家都知道,当这个for循环结束以后,各位朋友,是不是此时此刻我们就真正的拿到了赫夫曼编码。呃,赫夫曼编码。变成了这一个字符串所对应的这个字节数组。是不是同学们好,现在呢,我们就可以将其返回,把谁返回去呢?把half man code返回就代码就写完了。诶,有问题啊,我看看哦,对,我前面是不是把它变成VO了,现在应该返回BA code。BYBY的一个数组写完了,那我们来看一看是不是这样子的啊,我们看看是不是这样子的,我们来验一下。验一下,呃,现在应该返回的是一个BY数组啊,几个bit,那我就用这个接收,我们就叫halfman。
27:07
Harman编码过后的BI词没问题吧,同学们。接收了,接收过后呢,我把这个打出来给大家搂好不好来看一下。呃。我们把它lawyer等于什么呢?加上我们哈。Code好,我们看看对对不对,走一个。我们可以看到呢,诶这个不行,这样打出来打不了啊呃,那怎么打呢。用A吧。Aris。点我们的to string把谁转一下呀?把这个BY,把这个half man。哈曼编码过后的这个字节打一下,好,我们再运行一下。好,同学们大致能够看到了吧,看也就是说其实你你你有没有发现。我们原先生成的字符串,那么那么长的一个字符串,现在就变成了这么几个数,哪几个数,你数一数,一个两个,三个,四个,五个,六个,七个,八个,九个,十,11 12 13 14 15 16 17,是不是才17个呀?
28:12
诶,你们有没有发现他的认识实际上才是17个,而原先你最早的是40个。是不是在一定程度上,我们就已然?对它进行了一个压缩,压缩率大概是多少呢?可以算一下,就是40减去17,再除以40,算一下大概是多大。OK啊,相当于说40减掉一个13。再除以一个40,好压缩力呢,诶,它这个地方不行,我得。换一个这个写法啊,就是40减去。13 17 17,这是我,呃,压缩掉了少了20 23个,再除以我们的43。对吧,大概是53.4%的样子是吧,还是有效果的,还是有效果,因为我这句话很少嘛,那如果是我把它放大一点,是不是这个节省的空间就比较可观了。
29:12
好,同学们,那这样子的,我们终于达到了一个一样的效果了,我们终于经过一番处理,终于经过一番处理,我们拿到了什么呀,拿到了我们这一个。就是赫夫曼编码处理过后的这个字节数组,这个时候我们就可以把这个字节数组发出去了。因为你原先发40个字节,现在我仅需要发17个字节,是不是这个效果就明显了,现在就可以发送了。发送谁呢?赫夫曼编码过后的这个自己数组。对不对,输出完事了。这就是我们所说的赫曼编码,但是大家有没有发现,我这样写太麻烦了?你看我,其实我最终不就是要拿到一个赫夫曼编码过后的字节数组吗?你每次这样分布写,是不是太啰嗦了呀?
30:09
太啰嗦了,你看你get的一个no,然后呢,创建二叉树,再创建这个赫夫曼编码,然后再返回,其实你完全可以把它封装起来,写一个方法。这是不是就异常简单了,那么把这个代码封装成一个方法呢?我们在下一个视频给大家讲解这块,这个这一定要好好理解啊。怎么压缩,怎么就实现压缩的,好好理解一会儿呢,我们把它封装成一个。方法就看起来比较简洁了。好,这一讲先给同学们聊到这里。
我来说两句