00:00
各位同学,我们来看一下赫夫曼编码,那前面呢,我们给大家讲解了赫夫曼树的一个创建,那现在呢,我们利用赫夫曼树的特性,我们来。使用一下赫夫曼编码。嗯,那首先我们来看一下各位同学。那后换编码的原理我们已经比较清晰了,对不对,就是它是怎么。呃,怎么得到这个赫夫曼编码的,那现在呢,我们实际的操作一下。那么我们做一个什么样的案例呢?大家看我们做一个数据压缩的这么一个案例,比如说我给大家一段文本,这段文本呢,就是前面我们分析的这段文本。好,就这么一段文本,那么这段文本呢?根据前面讲的赫曼编码的原理呢?我们想把它压缩过后再传递,明白我的意思吧,好,那么我们的目标很简单,就是需要把这个字符串压缩成什么样子呢?压缩成这个样子。
01:05
大家理解我的意思吧。就是压缩成。形势如,哎形势如这个样子的。一一那个这个数据把它发过去,但是我要说啊,刚才我讲过,就是因为你在创建这个赫夫曼数的时候,因为排序的规则就是在相同全职的时候呢,谁在前面谁在后面会对这个赫夫曼编码有影响,因此呢。它产生的这一个压缩过后的数据呢,不一定完全相同,但是它的长度应该一样。明白我的意思吧,也也就是说它压缩出来过后,只要能够保保证它的长度是133就可以了,就133就可以了,明白我的意思吧,就是形式如,所以说我这写的是形式如,明白好,那现在呢,我们就来开始分析怎么做这个事情,我们要完成把这个字符串转成这么一个。
02:03
转成这么一个数据的数据的话呢,我们首先第一步是不是首先要创建这颗赫夫曼树啊。如果你不创建这棵赫夫曼树,那你肯定就不能得到赫夫曼编码,你得不到赫夫曼编码,你就得不到这个赫夫曼编码过后的这么一个数据,是这样子吧,同学们。好,所以说我们第一步根据赫夫曼编码压缩数据的原理,首先我们要创建这个字符串对应的赫夫曼数,那么我现在把这个思路呢给各位同学,呃,画一下,前面我们已经分析过了,对不对?前面我们已经分析过了这个流程,那么我们再来把这个和伙伴数的一个创,创建具体的代码的一个思路,再给同学们分析一把来。那么我们来看看。我们这个事情的步骤来吧,首先呢,我们要完成的功能。我们把它拆解一下啊,我们先说这个功能。
03:02
功能是干什么呢?注意听讲哈,我们要把这个字符串。我们要把这个字符串。这个字符串对应的。这个对应的赫夫曼数创建起来,来说,说白了就这个事情啊,应该应该应该把这个功能写成这句话就简单了,对不对,也就是说。我要嗯,这个怎么这么小哈,把放大一点嘛,这样大家看看的清晰一点,好根据后面编码呢,把它串成后盘数,我的我的思路,我的思路这样子的同学们听我讲啊思路。第一点呢,首先我们需要构建一个新的节点。我们要审一个新的节点,这是肯定的,这个节点里面包含的属性呢,我简写一下啊,肯定有个data。这个这个就是存放我们数据的。这个属性就是存放数据的。
04:01
明白我的意思吧,就是说比如说你是I,你是L,第二个呢,同学们,我们是不是还要存放它的权重,Wi wait wi权重。这个是它的权重,什么叫权重,还记得吗?就是全值吧,就说你你这个字符串里面有多少个I。比如说你这存的是I,那么这个全值呢,就代表一共有几个I。同时应该还有一个na。Left和right,这个大家应该很清晰,清晰的知道,好,这是第一步,我们要创建第二步,第二步我们是不是要把这个字符串对应的这个字节。它的字节字符串字节,呃,字数组,拿到第二步,我们要得到,得到什么呢?就是你的这个字符串,注意听啊,这个字符串对应的。对应的一个什么呢?Bit数组。
05:02
败的数组。呃,为什么要拿到这个数组呢?因为大家也看到你这里面的每一个字,这个字母呢,其实都可以用一个bit来表示,OK,第三一步我们要做什么呢?各位同学这个关键的啊,第三第三一步呢,我们要编写一个方法。我们要。编写一个方法将什么呢?将。将这个准备。准备构建,构建赫夫曼,赫夫曼树的这些节点,就漏的这个节点,漏的这个节点。节点啊,节点放到哪里去呢?放到一个历史中,大家还记不记得我们在前面创建这个哈夫曼树的时候,大家还记不记得我们实际上第一步是不是先把这些节点放在一个历史的终点,还记得吧?那这个时候这个节点长什么样子呢?这个形式大致是这样子的,我说一下啊,它的形式大大致这样子的,一个node,注意听一个node,这个note里面呢,有个data域,这个data域就是它的一个值,比比如说。
06:12
大家看我们我们这个A,我们这个A1共有几个呀,假设放到A啊,A是不是一共有五个A啊,看一个A。两个A3个A啊,我看有几个A啊。哦,这是这是一个A。两个A好。好,两两两个A。三个A4个A5个A,好,那到时间这里面呢,有一个A对应的阿斯克玛,A对应的阿斯克玛是不是97啊。然后它的权重。IGWGT等于几呢?就等于五啊,就这就这个意思明白吧,那如果说呃,再放一个节点的话呢,呃,比如说我们还有一个节点。还有一个节点,他记得是空格no啊啊,当这个地方肯定是个list的了,叫no。
07:05
No,好,这个node放的是什么呢?好,假设我们又有一个数据node。是什么呢?Data,注意听啊,这个data等于什么呢?32 32是不是空格呀,那32的权重有多?呃权值是多大呢?EGT好,这个就应该等于九好,类似于这样一种,呃,一个结构好,那里面肯定还有很多,那最终呃这个形成的节点,它就应该把哪个拿到呢?说白了就是把前面。前面这个拿到就是刚才我们统计的。这个数据拿到,诶就这个。明白我的意思吧,诶也就是最终呢,就把这个体现出来了,体现什么呢?体现这个性格,也就说你将来这个D有多少个,Y有多少个,整个就放在list里面去了,好第三一步,当我们呃把list拿到过呢,我们下一步就应该干什么呢,下一步就可以。
08:03
可以通过通过这个历史的创建,创建对应的这个赫夫曼数。好,同学们,这个就是我的一个思路,好吧,待会我首先写node,这个node我要改造,呃,不仅是存放数据,还要存放我们全职这个数据就是说的再具体一点就是我们的字,每一个字符,当然了,呃,你不用,呃如果有重复的A你不用,你不用存五次,就说一个A后面带一个全值就可以了,你理解我意思吧,然后呃,嗯,然后根据这个这个返回来的bad数组呢,把这些节点重构放在一个。呃,List中,而一个list的里面放的就是load,这个load记录的就是某某某某字符对应有几个,那么为什么这写的不是这样子写的呢?同学们,可能有同学,诶,老师你写的不对啊,你应该写成A呀,其实写成写A也是一个意思,因为我们的字字母呢,在底层它其实都是用数字来表示的,所以说我们我们到时间构建这个no的节点的时候,这个data呢,写成一个int也是可以的,明白吧,好,所以说我在这呢给他说清楚,因为你A字母它对应到S克码不就是一个数字吗?是这样子吧,同学们,呃,以前老师都讲过,好同学们关于这块的思路,我们就聊到这儿,下面呢,我们准备代码实现思路,就先给大家写到这里啊。
我来说两句