00:00
好,同学们,我们来把刚才的第一个步骤先把它用代码实现,那现在呢,我们新建,我们新建一个包,好吧,这个包呢,我们讲的就是赫夫曼的编码是这样写了,Half full man cold OK。好,现在呢,我们新建一个类,跟上我的思路,好,代码都不难,好。Man什么呢?Cold OK cold。呃,我们就取这个名字吧,然后我们把这个主方法勾上。根据刚才老师讲的这个思路,是不是首先我们先把这个node重新创建一下啊,OK,创建这个node。啊,带全职带什么呢?带它的数据和全值了,能理解好,我把这个放大一点,我们一步步写啊代码呢有点多,大家认真听,Class,首先no,然后我刚才讲过,我们首先用一个bit来存放它的data。
01:07
好,这个就做一个主啊,就是存放。存放数据本身啊,比如这个A啊,当然这个A呢,对应过来,它存的这个data呢,就是97按阿斯克码来存的,如果你存的是空格,OK,那么存的就32,这个我就不讲了,第二个呢,它有一个全值对不对?位置这个代表它的一个什么呢?就是全职。圈子到这就表示我们这个数据,这个圈子说的再具体点,就是在我们这个要传送的字符串里边,你的这一个A或者是空格存有几次表示数据,就或者叫那个字符啊字符。字符这个数据就是就是我们这说的字符。啊,字符出现的。出现的这个次数,这个能理解哈,然后呢,我们再写它的左,这个呢,是指向左边的,我就不写那么多了,No right指向右边的。
02:11
好,那紧接着呢,我们写一个构造器,这个我相信同学们应该知道,左右我们不给。左右我们不给好,这是我们的构造器写完了,紧接着呢,大家都知道我们这个node呢,将来会参与这个比较,大家还记不记得我们在讲哈曼的half man的时候,我们这个node呢,是实现这个接口的。是不是为什么实现这个机构,前面是不是讲过了,我就不再多说,好把这一个compar,把它这个未实验方法写进去,这方应该写是什么呢?各位,这个时候就应该写上this是点位减去o.weight能理解什么意思,这个就是代表将来我在比较的时候是按照从小到大排。这个前面讲过是吧,是从小到到这个排序。
03:04
OK,这点不再多说,然后呢,我们是不是还需要编写一个to string方法,便于我们打印。看这个信息,好,我重写一下图string。没有问题吧,托斯俊。诶,这个地方我们看一下。透视俊,诶,这个地方为什么吊不起来了?呃,我写一下吧,啊two。String。好,那么这个图俊,诶这个为什么不出来哦对,看一下我是快捷键是不是出了问题啊。呃,快捷键出了问题,诶快捷键出了问题了,那那快捷键出了问题,我们先不管它,直接这样写吧,Public。Public,然后这边我们写一个string,写个two string,好,那这个to string里面我们怎么写呢?非常简单。
04:00
啊,我们return return这个no的的一些信息,比如node它的data。对它的data呢,我们加下。加上他的这个数据。好,先写一个小叉,待会再表示,然后呢,它一个全值对吧,为W。EGHD全值是多少?是不是这样子表示就可以了,然后呢,我把这稍微的整理一下,这边传进来是什么呢?好,这边就是我们的data加加。对的。这边这个Z就是我们的全职加加位置。没问题了啊,把它格式化一下就可以了。格式化一下就可以了,好的,这个呢,是我们在处理的时候打印出这个节点的信息,打印出这个节点信息,那紧接着呢,我们还要写一个前序便利。情绪便利大家应该还有印象吧,我们是怎么写出这一个情绪便利的呢?
05:04
是不是这样写的,Public void pre order,先把这些都写好,待会呢,我们要用的哈,首先呢,我先输出这个节点本身this,然后我们就判断,如果this.left,它不等于空。然后呢,我就向左走是吧?This this.ed.pre order好,行完,那么如果,如果this.right它呢?它不等于空,对,我们就向右对不对?this.right.order好,这个这块就写完了,那写完以后我们下一步该写什么呢?同学们打开笔记,好,我们现在呢,应该把这一个字符串先拿到一个bit数组,然后就要构建这个list了。好,现在呢,我们在这儿玩一把。首先呢,我把这个字符串先把它洗出来,比如说这是个字符串string,这个是我们准备。
06:04
传递的字符串。字符串的内容,我们就用这已经设计好的这个串,因为待会儿呢,我们可以进行这个验证,它的长度是不是对对不对,它的长度情况,那大家想我现在怎么去得到它的字字节数组呢?是不是有个get bit就可以了。大家这个能理解啊,我们就叫拜。就叫BY或者叫string的一个BY词。啊,这个叫content,比如说这个我们要传的内容,好吧,Content。将来比较好记content的bit词,OK,好,首先我们看一下此时此刻,当你这样去处理的话呢,我们这个长度目前是多少,我们先输出一下。就是在你还没有压缩的时候,你的这个count bits.get。哦,认识吧,认识认识。
07:02
点认识。好,这个认识呢,我们输出一下同学们看。目前呢,目前它是事实,好记住它是事实。记住了啊,这是事实,好,当我们把这一步做完了之后,下一步呢,根据我的设计,应该去先得到这个字符串。对应的这个list是这意思吧,同学们好,那现在呢,老师开始要写这段代码,这个稍微的麻烦一点,大家跟上我的思路,那现在呢,我们写一个方法private干什么呢?Sta get notes。它返回一个什么呢?各位同学返回的是一个list,这个list里面放的是no OK,那你。给我传一个什么进来呢?你把刚才得到的这个字节数组传给我,我就可以进行一个分析,BY。好,下面我们怎么处理好,我先把这个该引的包给引一下。该印的包给印下。
08:01
好这是包,那现在呢,我们来怎么处理呢?首先第一步对先创建一个,你这个大家知道吧。你不创建,你到时间怎么放啊,我就写了啊,有一个r list里面放的是no。OK,然后呢?这边我们呃,就叫note吧,就是很多节点在里面嘛,我们再把这个包引一下。好的,拿到这个以后,下一步我们该干什么呢?同学们,我们要存储。我们要存注意听啊,存储每个每注意听每个bit出现的次数,那你怎么办呢?这个时候我们用map来处理。这是最巧妙的方法,就是说大家都知道我们在进行便利的时候,我不知道每个里面有多少,那我首先卖,我待会要便利是什么?BY,也就是说我要便利。相当于说我要待会我要遍什么呢?我要遍历这个BY词,就是我们这个字节数组,然后呢,统计,注意听啊,统计每个每个bitt出现的次数。这个是用。
09:12
Map比较好,因为map呢,它有个K,还有一个值,是不是这样子就很好处理了,那同学们开始写了啊,我这就快速的演示一下bits,这是不是便利啊。BAS,那呃BAS拿到以后,我们现在怎么做呢?首先大家看我先呃看看怎么写啊,我先用个integer,我用个inegger来得到当前用这个,呃,我看看用个什么来写哈,那这个map还没创建起来,我先把这个map创起来啊,那大家看我这这个这样写,大家看能不能看懂哈希map。哈希迈普。好。呃,哈希map,然后呢,我们用什么来接收呢?我们用个map,它的K我们用就是败。
10:02
对,它的值就是integer。好,然后呢,这边写一个count。好,大家知道我要干什么哈,这边少了一个这个东西好,同样我们要引包。把包引进去就可以,那这句话的意思就是说,待会我们这个map的K呢,就是。说白了就是你这个数据,而他的in t呢,就是它的次数,能理解哈,好,那现在过后我先尝试着从这个count里面去获取一把。我获取什么呢?我获获取这个币,大家知道我在干什么吧,就是我先尝试着从这个map里面去获取,当然我获取的时候只有两种可能性。两种可能性干什么呢?拿到了或者没拿到,好,如果注意听,如果我们在count,它等于空,说明什么问题?说明你现在一次都没存放。也就是说,现在map里面还没有这个数据是意思吧,Map还没有这个字符数据。
11:04
啊,支付数据那就简单了,我们直接把它放进去,怎么样用put把B放进去是几次呢?第一次,也就是现在是第一次。啊,第一次检索到。第一次,那如果说不是第一次怎么办呢?各位同学很简单,如果不是第一次就是S,那么我们这个count,它就应该put,跟上我的思路,Put什么呀,诶,Count put put,我们这一个B,同时把你刚才取得的count count加一。就完事了。大家看看这段代码有没有问题。能理解啊,这是跟Java有点关系的。跟Java有点关系的好,当我们把这个键整个这个for循环结束以后,请问。是不是我们这个map里边就已经统计了某某。字符数组,呃,字符字符数据它有多少次了。
12:00
但是你还没有把这个load建立构建起来是不是好,现在呢,这是我们要说啊,将把每个。把每个什么呢,键值对。键,诶这样写啊,键值键值对转成一个no的对象。是不是并加入到notes这个集合,能跟上我的思路吗?很简单,那怎么写啊,同学们for循环,这个时候呢,我们要便利我们这个map,便利map大家是不是以前是学过的呀。Map什么样点方法很多,我用其中一个方法int,那首先呢,遍历出来,第一个是bit,第二个是我们的int interger还记得吧,好,然后呢,我用一个接收这个我们叫intry吧。OK,然后怎么取的呢,Counts点。Entry site。这个我就不解释,同学们,这个是便利我们的map。这个是便利map啊,原因我就不再多说了,然后notes.i什么呀,好,加一个节点进去就可以了,那么这个节点现在要构建的时候,是不是要串两个字,一个是data,一个是wait,那么data是什么呢?同学们,Data就是我们的N。
13:16
Entry必须做了啊,Entry点什么呢?Get k。这个K就是它的数据。是不是啊,那么次数呢,就是ENT。点get它的value完事了。好,同学们,经过这番一个便利呢,我们其实就已经完成了这个任务,也就是说现在你这个方法的作用是干什么呢?接收一个字节数组。字节数,但这个字节数组里面每个字节放的是字符啊,放的是一个一个的字符,然后返回的什么呢?返回的就是。啊,就是这个list的,这个list的形式是长得有点像这个样子,就是刚才我们分析的,他最终长的样子呢,是这样子的。
14:06
明白我的意思吧,诶,它长的就是这样子,这样子的一个一个漏啊,一个漏里面有一个有一个值哦,这个刚才为什么写错了,就是七啊。97我看是不是。就这少少写了一个,可能不小心啊,应该是97,大致就是这样子的,对吧,97呃代表A出现了五次,32呃代表空格出现了九次,大致就是这么一个这么一个东西,好最后你这做完了以后,是不是应该返回啊,把谁返回去就可以了,我们的谁notes代码。代码就行了,那么现在是不是有必要我们来测试一把?是不是我们需要测试一把来玩一把,那现在呢,我们就以这个为例来测试看看对不对。那现在呢,我用get notes。放进去我们这个CONTENT100词是不是好,我分配一个变量。
15:01
呃,这个变量应该叫什么呢?漏好就叫漏吧。然后现在我把它输出来,同学们看一下跟我们想的是否一样,等于加上not。OK,我运行一把,同学们可以看,现在呢,我们拿到的跟我们选的应该是一样,看第一个32啊,32有有九次啊,97有五次,97就是A嘛,100是什么呀?呃,不知道100是什么,看一下阿斯克玛啊。看一下阿斯玛,这个我看看。一百一百一百是什么玩意儿呢?好看这100呢是D,就是对应我们字符D啊,D出现了几次,大家看一下,诶看到D出现了几次呢,D出现了一次正确,所以说我们这个这个处理应该是没有问题的。哦,没问题,也就是现在呢,我们已经把这个list拿到了,好看一下录制了多久?好15分钟好好下面呢,我们是不是应该完成下一步工作了呀,同学们是不是通过这个list来创建对应的后数了,这个是不是很简单?
16:04
我们在前面是不是已然给同学们讲过怎么去构建一棵赫夫曼树,讲过没有好讲过,其实我们就那就快速的写一遍就完了啊。好,我们来写这个,就是干什么呢,完成我们的第四一步功能。通过一个list。对,通过一个list的创建对应的后服曼数,那现在开始写代码了,Private static。Sta,那你返回的是什么呢?同学们返回的就是这个赫夫曼数的根节点,还记得吧?那就写了啊,Create什么呢?Hoffman?Halfman,那你给我传一个什么进来呢?没问题,你把这个历史的给我。好,你把这个给我,你给我,我就给你搞定这个事,好,那现在呢,我们应该怎么写啊,上来直接就Y循环了,我这就不啰嗦了啊,跟我们前面已经讲的完全是一样的,我直接只要它大于一。
17:05
设置要大于大于一,我们先要排序,还记得吧。你你必须得先排序啊,不排序不行,那排序的时候用connections connections啊点so谁呀,No写错了so。送稍微慢一点,然后呢,我们把notes放进去,是不是排完序过后。现在这个排序注意啊,是从小到大,别忘了,因为你挑的时候,你如果是从小到大排,你应该是挑,挑出我们这个list里面的前面的第一个和第二个,如果你是从大到小排,你是挑出这个list的最后的倒数第一个和倒数第二个这个这个有区别啊,同学们。好,那拿到这个排序以后呢,我们是不是应该按照这个取出,取出第一颗,第一第一颗。第一颗。
18:00
第一颗最小的。二那个二叉树。好嗯,那这个地方我们就note.get我们的什么呀,零没问题吧,零好分配一个,那这个节点其实就是我们的nap的节点do na的一个node没问题啊,那现在呢,我们再取出第二颗。取,取出第二颗最小的,呃,这个二叉树是不是第二颗?诶,这个怎么又忘了啊呃,起初第二颗应该是loads.get1。对不对,GET1。那GET1这边呢,这个变量咱们就叫right。Write note,好,没问题吧,同学们把这两颗拿到以后,下面我们该干什么吧,是不是创建创建。一棵新的二叉树它的全,那么大家想啊,创建一棵新的二叉树,它这个地方要必须知道这颗星的二叉树它的根节点。
19:05
它的这个根节点就是这个新的二叉树的根节点。根节点它有有那个data吗?注意听啊,没有。没有,只有什么呢?只有全职,这点大家一定要分析出来。对,就说他他有他没有data,因为你你所有的这个字符呢,最终都是放在叶子节点的。对不对,他没有对的,只有犬子,犬子仍然是下面的这两棵树的。下面这两个数的那个它的全全值的和啊,能明白的意思啊,那我就开始写了,那开始怎么写呢?No。Parent。Parent parent parent别写错了啊,Parent等于什么呢?好,六一个no。
20:02
那这边穿什么呢?第一个因为data没有了,所以说穿空,那么它全值应该是等于left not.weight加上它的right no。点wait,这个大家要看清楚啊,好,拿到这个过后是不是把它挂起挂上去parent,点它的ne呢?就等于na的这个no parent点它的right呢,就等于right.load好,这这点大家看看能否理解好,这个做完了以后不要忘了一件事情啊,下面应该干什么呢?将。将处理过的这两棵二叉树处理掉,移除啊,将已经已经处理的。两个两棵二叉树移除从哪里呢?从漏子移除或者删除。这个工作不要忘了啊,怎么删除呢?非常简单,就not remove谁呀?
21:02
啊,一个是我们的left。呃,Left node是不是还有一个not.remove我们的哪个呢?Right node,好,这个移除,移除完了,不要忘了一件事情,还要把我们这个新的二叉树加进去,对不对,加入到将。将这个新的二叉树加入到哪里呢?加入到这个notes,这个大家应该清晰对不对?not.i的谁呀?Parent搞定。搞定好,通过你这个Y2循环不停的去处理,最终是不是这个节点,这个漏里面最终只只有一个元素了。这个就是我们的什么呀,赫夫曼数的根节点,好,最后返回到这个节点,节点最后相当于这个note里面最后这个节点啊,这个note里面应该这样写notes。Nose。最后的。
22:02
最后的这个节点,节点就是哈哈夫man哈夫曼树的根节点。这个大家能理解更几点好,太简单了,直接return,谁要not.get我们的零代码写完。来玩一把呗,到底行不行不知道,我们试一把,来测试一下。测试一把啊,测试一把,创建的二叉树能理解啊,跟着我的思路好输出一下。好,也就是说这个字符串。他嗯,他对应的这嗯,把这个全职考虑进去过后,它对应的这个赫夫曼树长什么样子呢?赫夫曼树。怎么怎么整呢?呃,先调一下,先调一下那就是。先用我们刚才写的create。好曼,把谁放进去?把肉放进去,把肉齿放进去过后。
23:05
他其实返的返回的就是我们这个哈哈弗曼数的。数的这个root节点。是不是好,我们先来看代码有没有抛什么异常什么的,好没没有,没有抛异常,没有抛异常,现在呢,我们把它前序遍历一下。因为你前序便利就能看到大概的一个情况了嘛,前序。情绪便利,OK,那情绪便利我们这有方法吗?OK,还没有啊,这只是在里面写了,我们外面还没有写这个方法,各位同学是不是好,我先写一个前序遍历。情绪。OK,情绪便利的一个方法很简单,Public,我们叫private吧,Private什么呢?呃,Static void,没有什么返回值,直接是pre order,好,那你给我传一个什么呢?没问题,你给我传一个跟据点过来就可以了,我们是no root,我判断一把,如果root它不等于空怎么办?
24:09
我们就可以去遍历,如点我们的pre order,否则我们提示一句话说怎么样和慢速为空和夫曼数为。为空啊,不能变利好,同学们玩一把,来,走一个,嗯,怎么走呢,好,慢竖。点它的一个pre order,好,我我跟大家讲一下啊,当我们便利的时候呢,他应该打印出一个大概打印出一个什么情况呢,就是我们生成的这个哈弗曼数的。信息。但是我在前面讲过了,我讲过一点,就是哈夫曼数呢,根据排序方法不一样,也有可能不太一样,因为刚才讲过,就是在你有相同码值的时候,相同权值的时候呢,可能微有微微有些差别,好吧,但是呢,我我讲过不管你是雷生成的是什么样子的。
25:06
这个赫夫曼数只要你满足WPL一样,那么你最终生成的编利生成的这这个压缩过后的这个字符串呢,都是133就行。腰三形我们简单验证一下啊呃,我们看一下。如果前序变异的话呢,应该第一个输出的是40,第二个十七八,这个应该是四,那也就说应该是四十十七八四,但是这个40呢,它是没有带的。事实它是一个什么?它是一个,嗯,它不是一个叶子节点,因此它这边应该显示个空。事实这个也不是,应该说也是一个空。然后十七八也不是空八四就是了,四是什么呢?四应该是个L。L应该是个L对应的阿斯柯玛。L对应的阿斯玛好简单验证一下啊,这个大家知道就行,来跑一个运行。
26:05
好,运行过呢,我们看到它这边打印的跟我们大致分析的差不多,第一个空,第二个空,第三空分别是40 17和八,还有一个全值为四的是108,我们来看看108对应的是不是L。幺零哦,这边这这边还有我们看一下108啊108。108在哪儿去了?好,往下走啊。108啊,108它的权重的确是四,那么108对应哪一个字符呢?打开我们的阿斯克曼表,我们捋一捋108,看一下各位朋友,108108他。L,那么L到底是不是应该有四个呢?根据刚才我们这个阿斯玛表,呃,我们分析的这个呢,的确它就应该是四个,刚才我们看到这个图也也是这样子啊,的确是四个,从这我们分析出来呢,L也应该有四个。
27:04
来了,应该有几个。L。啊,看看前面这个才行啊。前面这个LL是这。是不是这个呀,同学们四个。我们再来验证一个其他的空格是不是九个,我们看一下空格,空格应该是32,打开看一下32。我们随便找啊,32找找32在。32在这好九个正确,好同学们,那关于我们的就是关于把通过这个赫夫曼编码压缩数据的第一个步骤什么呢?将这一个准备发送的字符串转成对应的赫夫曼数,这个步骤咱们就写完了。大家看看能不能理解啊,能不理解代码,代码呢,其实你看起来好像比较多,但并不是特别的难,因为前面咱们都讲过,好,那第一个步骤我们就先给大家讲解到这里,大家消化一下。
我来说两句