00:00
各位同学,我们来介绍一下赫夫曼编码,也就是我们通讯领域中处理信息的第三种方式,赫夫曼编码还是以刚才这个字符串为例好,那这个时候呢,可能我要一边讲呢,一边把这一个图示给大家画一画,OK,注意听啊,这个讲的是赫夫曼编码的一个原理剖析赫夫曼编码的。对编码的一个原理,原理剖析。剖析好,同学们跟上我的思路啊,跟上我的思路,那同样我们还是以这个字符串为例好,第一步我们假如呢,在这个通讯领域,我们需要传递这么一个轴串。我们要传递这么一个字符串,看清楚了,要传递的,要传输的吧。传输的这个字符串是什么样子呢?是这个样子的。就是这样一个串,这样一个串,那这样一个串拿到以后,同学们,诶,我我把这个稍微放大一点吧,看看它这个后面能不能都变大啊。
01:05
好,这个都变大可以了,那么我拿到一个字符串过后,我先怎么办呢?同学们看我第二步,我先统计他们各个字符出现的个数。这个很简单,这个跟刚才呢很像。对不对,很像吧。那这个怎么又变小了,这个很讨厌,好,那么我统计出来过呢,D是一,Y是一,U是一,好,最后空格是九,我就不说那么清晰了啊,这是第一步。我们拿到字符串,第二步呢,我们统计各个字符出现的次数。好,第二步我们就完事了。第三步,同学们,第三步大家知道我要做什么事情吗?第三步我呢,按照上面字符出现的次数构建一棵赫夫曼树。构建一棵赫夫曼树,那同学们想一想啊,你这棵赫夫曼树的话,构建的时候我们把次数作为这个全职。把次数作为全职构建,大家是不是还记不记得我们刚才已经演示过怎么去构建一棵赫夫曼树,理解了吧?
02:09
赫尔曼数怎么构建的?还还记记得吧,好,现在呢,我们假定有。有这样一个数组,这个数组呢是111222444559,同学们,你把这一个。这个。这个按照刚才老师讲的这个步骤,哪个步骤就是刚才我们讲的这个步骤,是不是刚才这个步骤讲的已经很很细致了。这个步骤呢,仍然按照刚才的AK步骤,我们这个构建的步骤跟我们刚才讲的。就是前面讲的构建赫夫曼树的步骤一样。一样,好,我把这个步骤写到这里来,这个步骤仍然是第一步,先排序。因为我们前面讲的这个二套数后,方曼数的构建本身它就是有用的第四步。
03:06
好,那也就是说此时此刻你把第一个它的全值当成一,那你可以构建成个load节点嘛,这个load节点的那个全是一,它的另外一个域,比如说他另外一个域记录它的字符是什么。但是我比较的时候呢,我在比较的时候,我仍然以他的这个value比较,也就是说你可以这样写,你再加一个叉。呃,差,比如这是它的一个char char,这是它的一个字符。能理解我的意思吧,这是它的字字符,这就完事了吗?当我进行这个load比较的时候,我仍然以这个VALUE6来比较,这个value就是。同学们说的这个次数。次数,而它的这个D呢,D Yu就是它的什么呢?就是它的差,能理解我的意思吧。不难理解吧,好,那你根据这个value仍然可以进行我们的这一个。
04:02
赫夫曼树的构建,那赫夫曼数构建完了以后呢,各位同学注意听啊,这个构建过程,呃,我就不去构建了,这一共有这么多字符,太累了啊,一共一二三四五六七八九十十一十二,太累了,那没关系,因为我在讲课之前呢,已经把这棵树已经给他构建好了,肯定我讲课肯定要有一个准备嘛,好这棵这棵树。同学们看到的。啊,刚才看错了啊,同学们看到的这一棵树。这棵树就是我们按照赫夫曼树构建的流程形成的一棵,呃,形成的111棵这个赫夫曼树大家有发现,如果你仔细观察的话呢,你会发现。这个DY你看DY是最小,它放在了我们这个后伏函数最下面,最最下面这一层是不是,那么你没有发现,有没有发现空格,这个空格它的全值是九,你们有没有发现它是放在上面的,看这。
05:08
是不是其实这个构建流程跟我们一样,我只是这个时间关系,我没有去画了,我相信同学们应该都能。应该都能画出来。呃,流程是一样好,那也就是说我们通过这个,呃,构建步骤呢,我们就把。就把这个赫赫夫曼数做完了,那第四一步该干什么事情呢?各位同学跟上我的思路,第四一步啊,这个没有完,你现在仅仅是把这个赫夫曼数构建起来了而已。那下面第四步该干什么事情,同学们看啊,第四一步数就是刚才我们是。这个流程第四一步,根据赫夫曼数给各个字符规定编码。那么我们规定向左它的这个路径为零,向右这个路径为一,那么根据这个路径呢,我们就可以得到一个编码,好,这是我们的D。
06:03
是一部。好,待会后面我们要写代码的啊,同学们,我们仍然用代码来实现赫夫曼编码,所以说大家要认真看这个流程好吧。根据赫夫曼数给各个字符编码,那么这个编码的时候呢,同学们要注意,我们现在编码的时候要采取另外一个方案,我把这个还是放大一点,怎么编呢?诶,这个地方没没有改过来是吧,没有改过来怎么编呢?同学们看清楚了,我规定向左的这个路径是零,向右这个40的,向右的这个节点路径为一,哎,你没有发现零一刚好又是我们的二进制了。对吧,那这样编码过后,我们得到的编码呢,应该是长这个样子的啊。应该是长这个样子的,大家有没有发现就变成这个样子了?怎么样子呢?就变成这个德行。变成这样子的,大家注意观察。当我们编完了以后,我我我照几个例子啊看。
07:02
O。O就是100 u就是100,幺零,我们找几个例子来看一下。呃,我找一个E吧,这个E大家容易看啊E。一按照我们这这个赫夫曼树构建起来过后,它的路径应该是什么呢?这这是11111,就是1111好,这个呢,就是E对应的。霍夫曼编码是不是这样子的正确,我们再找一个节点O。O这个节点,我们看一下它的编码应该什么呢?是1000,好,那么O对应的这个赫夫曼编码就是一。1000好,我们再找一个结节,这个后部分编码,按这个路径来算啊,就是0000好四个零,那节呢,就应该是0000。是不是零呢?结对的,我们再找一个长一点的YY这个很长哈,因为Y这个为什么很长呢?因为它的这一个圈子其实是比较小的,所以它放在这个最下边的,那这样算的话就是。
08:09
100111看到没有,负Y就是什么呢?Y就是刚才我们所说的100111,看清楚了没有?是不是Y?Y10011号,大家有没有发现这个编码有个特别牛逼的地方,什么牛逼呢?他就这个编码,它是一个前缀编码。也就是说,这个编码是个前缀编码。那为什么它是前缀编码?你们来看一下,他们每一个字符的编码都不会是另外一个字符编码的前缀。大家知道我在说什么吗?你比如说吧。比如说我我们看零一。这是空格的编码,空格的编码是其他编码的前缀吗?你找不到,你有没有发现找不到很神奇,说他是一个很神奇的编码啊,当然你要肯定是研究过的啦,对不对,你们看。
09:07
你们看这里,这个是空格的编码的,你你你把前面整个编码都走一圈,你会发现没有任何一个字符,编码的前缀是零一。你看这个它的前缀是幺零,不是应该以零打头的啊。以零打头是他,但是以零打头,这个是零零。这个是零一,肯定肯定不是这个什么呢?这个也是零零。显然呃,这个零一,呃跟他不是再来001,这个这个是两个零,我是零一也不是对不对,所以说你会发现呢,这就是我们所说的前缀编码,这个前缀编码在匹配的时候就不会出现多一性。好,这是第四步,我们就讲完了,那第五步呢,大家看按照前面这个编码,我们这一个注意听我们这个赫夫曼编码,对这个。字符编码就变成这个德行了。来,我们再看一下第五一步。
10:01
第五一步好,我稍微慢一点啊,第五一步按照上面的赫夫曼编码,我们会将这个,我把这个放大一点。我们会干什么呢?我们会将I like like like Java do you like Java字符串编码变成了这样的东西。我是写写全了的哦。也就是说你们来看。I是几呢?I是。注意听I41101说说。这个就代表I,我画一个颜色。红色这个就是I。好,我们继续往下匹配。零没有零一,我们发现有一个看到没有零一,它不会出现一个二一性,因为零一它一定是个空格,说老师为什么会,为什么是因为零看啊,零是匹配不到的,再一匹配零一只有一个是零一。为什么呢?因为没有哪一个字符的前缀是零一,所以说一定是空格。
11:00
再说一遍啊,没有哪一个的字符前缀是零一,所以说它只只有一个。能够马上匹配,就是说空格它的它的它这个401,其他字符的前缀都不是零一,因此呢,我们可以肯定的说,这个零一,它匹配的就是我们的空格。其他依此类推,再看我们再匹配零没有零零有吗?啊零零。也没有,因为这个是000对吧,零零好,再往下走,再往下走。再往下走,因为0001个都匹配到,没有哪个是零零嘛,没有哪个是零零,再往下走,诶001。001有吗?果然有了,看001就匹配上了。001是谁啊?001就是L,所以说第一个就是啊,这个I空格like的第一个字母L,好,其他我就不一个个去找了啊。其他我就不一个去找了,那么同学们有没有发现这个长度它是多大呢?来,我们把这个统计一下。
12:07
同学们有注意观察,我保存一版。同学们看,我统计这个字数算,你会发现它的长度呢,变成了133。133,也就是说此时此刻我们这个长度呢,就变成了幺。长度啊,通过这个相当于说通过我们。通过赫夫曼编码。赫夫曼编码。处理,那么长度为多少呢?我们要发出这个长度为133,诶,这个写怎么粘了这个度呢?133,好,那么还记不记得我们不使用编码,它原先长度是359。好,这样子我们就可以算出来,它的一个压缩率,原先是359,现在呢,我们变成133,它的压缩率是多大呢?是159减去133除以359,变成压缩率是62.9%。
13:01
2%,所以说我在这里说了,此编码满足前缀编码及字符的编码都不能是其他字符的前缀,不会造成匹配的多性,好,到此为止,各位同学。我们这一个要讲解的赫夫曼编码的一个特性就给大家说完了。大家看看,现在大致理解我们这个赫夫曼编码的,呃,一个过程了没有。后门编码,我们再简单的总结一下啊,它其实是这样子的。第一步,首先统计。我们。每个这个要发送的这这一段文章,或者是一个字符串的各个字符出现的次数。那么把这个次数作为作为一个全职,当然你你这个全职做完了之后,这个字母也也也你也得也也得记录啊,你不记录到时间没法编码的对不对,也没法恢复回去嘛,对不对,好呃,然后呢,根据这个全值,我们来构建这个赫夫曼数,构建赫夫曼数跟刚才前面讲的。
14:07
构建赫夫曼数的步骤完全一样。就形成了这颗。这这一棵赫夫曼树,赫夫曼纯建纯,呃,做好了以后呢,我们把赫夫曼树的向左的这个方向标为零,向右的方向标为一。这样呢,我们就可以给通过这个路径,就是我们常说的路径,这个通路给每个字符。编一个码,这个码就称之为赫夫曼编码。而这个码呢,同时也满足是个前缀编码,刚才我已经讲过这个东西了,然后呢,我们再根据这个赫夫曼编码,对你要发送的字符串。进行变长编码处理,就得到了这个串串得到一个串,这是这个就是我们真实要发送给对方的。一个呃,一个内容,当然你你编的时候啊,说老师那发的时候怎么发呢,他仍然是要把它组合成一个字节来发送的啊,这后面还要具体说,你也也说这个地方,他每八个一位。
15:07
每八呃,每八每八个bit,一个bit,然后发送过去,以自解码的形式发送过去的啊,后面还要解决解码问题。好,反正说他发送的这个串呢,就是这样一个串。这个串呢,就变成133这么长度,那么我们根据刚才的统计。133原因是现在是133,你现在是359,那么压缩率呢,就是62.9%,而且要提示大家,我们这个赫夫曼编码是无损压缩。无水压缩,就是它在恢复的时候呢,不会出现问题。不会出现问题啊,就是说你你原先这个呃,文件是什么样子,我恢复回来过,就是原原本本的样子,而不会造成精度或者是呃,如果是图片不会也不会造成这个图片清晰度的损失,不会,因为它是无损压缩,我们再说一句话啊,就说后风曼编码是无损压缩后。
16:02
夫曼。编码是无损。就是无损的。无损的一种处理处理方案。好,这点呢,请同学们注意一下,好,各位同学,那么这个关于赫夫曼数的一个讲解,说到这最后我还有一点特别要把他说清楚,对于我们初学者呢,容易在你们搞晕的地方,我一定要再点一下啊,哪一点呢特别重要。就是注意这个赫夫曼数呢,根据你排序方法不同,有可能不太一样。这句话怎么理解呢?这句话怎么理解呢?就是说我们在进行,大家还记不记得我们在进行这个构建赫尔曼数的时候,有可能造成。注意听,有可能造成我们在排序过程中,它的两个全职,甚至三个,四个,五个,他们的全职都是。一样大的。大家理解我在说什么吗?就说呃,就是说我们在构建,这在上面老师在构建,构建这个二条树的,假如说你这有个事,那很不幸,我们这个地方后面还有好几个节点也是四。
17:12
有没有这种可能性,还是四个五个很多。都是四,那这样就出现一个问题了。你你出现的时候,到时间你你排完序,你你排完序过后。如果说你排完序过后,你你这棵树是位于它的最前面,还是位于它的。还还是位于这个最市的最后面还是位于这。吃的中间不知道。因为你排序完了过后,完全有可能你这个这颗新建的二叉树,有可能是在所有四的最前面,也可以在四的最后面,也有可能是在中间,因为他都满足从小到大排序嘛。那这样子你的顺序不稳定,你的顺序不稳定就有可能造成你将来形成的这棵赫夫曼树长得不一样,明白我在说什么吗?
18:05
啊,这这点一般的老师就说你自己不去想,很难想到这儿,一般老师也没在这点出来。也就是说,假如我们这有四个市,那有可能我们我们这颗刚刚新建的,它是排在这个这个市的后面的。这个式的后面,但是他也可能是排在这个所有十的最前面的,但是他也可能是排在第二个式后面,第三个式的后面,不知道。好,那如果这样的话呢,就完全有可能造成什么呢,造成你最终形成的这颗。夫曼树长得不一样,如果你这个赫夫曼数长得不一样,那么你对应的赫夫曼编码也会也会不完全一样,就有可能相同,也可能不相同了,大家理解这意思吧,但是有一点大家不用担心,老师,那这样的话就麻烦了嘞。那就话就麻烦了,不,不要担心啊,我说了,但是不管你怎么排,只要你满足赫夫曼数的WPL小,因为我不管你是那样排还是这样排。
19:09
你都按照霍夫曼数构建的形成,那么WPL是一样的。WP2就说你就按照这个流程来,不管你你新建的这这个二条书到底排在这四个事例市的哪个哪个市的后面,他最终的这个WPR一定是一样的。都是最小的,那所以说最后你形成的这个赫夫曼编码呢,它的大小也都是一样的,换言之就是说。最后你形成的这个赫夫曼的这这个串,就是同学们看到前面这个串。都会是133。都会是133,我这点是需要给大家提提醒出来的啊,提醒出来的,所以说你看假如我这我这有个视,我这有个视频啊,呃,我我这有另外一种剑法。比如说现在呢,如果我们每次让生成的新的二叉树总是排在全职相同的二叉树的最后,我们原先是按排在全职相同的。
20:10
这个二叉树的前面是吧,现在我如果排在全是相同的二叉树的后面,它生成的二叉树就是长这个德行。而不是刚才我们看的这个这个这个二叉树。不是我们刚才看的,呃嗯,这个霍弗曼数,那么数不一样,肯定编码霍夫曼编码不一样。对不对,编码不一样,那你肯定这个也不一样。这个不但是我试过啊,但是我是我刚才讲过,只要你满足盘数,虽然它的编码不一样,但是它的总的长度是一样的。理解我在说什么吧,那个无所谓嘛,因为你这个后面编码主要是为了压缩,至于你这个编码是这样长还是那样长无所谓,只要我能做到无损压缩,而且保证你的长度不要不要说诶这种编码是133,另外一种编码就变成156了,是不是它不会?
21:00
好,所以说这个赫曼苏呢,有可能长这样子,它也有可能长这样子。这样子的,这个跟你的算法是跟你这个后面这个排序呢,到底用哪个方法去排序是有关系的啊是有关系的,好这两个呢,最终形成的都是一样的,好这个图我也我就不画这了,容易引起大家误会好不好。容易引起大家误会,但是我这点出来,这个这个点大家一定要非常清晰的知道。清晰的知道好了,同学们,那关于赫夫曼编码的原理,我们就给大家讲到这儿,大家看看理解没有,好现在呢,我把呃原理剖析完了,过后一会呢,我们就代码实现,用代码来实现这个数据的压缩,然后来解压,好现在我先把刚才讲的内容给各位朋友板书一把好不好?先板书一把刚才我们讲的。好,我们捋捋刚才讲的内容哈。呃,刚才我们讲的是什么内容呢,各位朋友。各位朋友,我们讲的是赫夫曼编码,是这意思吧?
22:03
我们讲的是赫夫曼编码,那赫夫曼编码我们首先给各位同学讲了它的基本介绍,就是什么是赫夫曼编码?是不是这个道理,那后面编码呢,我先做了一些介绍。是这个流程,哈赫夫曼编码介绍完了以后,对我们就给同学们说了什么呢?说了。原理剖析就是赫夫曼编码是什么来着呢?我们先说了,呃,他的原理剖析呢,就是在通讯领域第一种我们最笨的处理方式,就是不去进行这个处理,就定场处理就完了。是这样子的吧,好,这里我就快速的写到这里来,原理剖析。对原理剖析,他的第一种方案就是我们所说的。定长编码,定长编码呢,就是按照原先是什么样子,咱就怎么怎么形式去发送。
23:00
这样的这个长度我们统计了是359。如果根据我们这设置的一个案例来说,它就是359这么一个程度。好,那紧接着呢,我们发现这个长度呢,太长了,不不太好,于是我们就提出了什么呀,第二种方案就是变成编码。对不对,是不是说的编程编码。OK,那么这种编程编码呢,我们也做了一个分析,也做了分析,它其实呢,编程编码确实在一定程度上,它是可以减小我们这一个。长度的传送,传送数据的长度,但是呢,它有一个问题,这种方式呢,它会造成匹配的多一性,因为它不是前缀编码,所以说这个方案呢,也被呃很多地方他是他是不去使用啊,就是我们。相当于说过渡一下使用,呃,提出这个变长,那最后呢,由这个我们就引出我们真正要讲的这个通讯领域的赫夫曼编码,对赫夫曼编码,那赫夫曼编码它是怎么玩的呢?好老师呢,就在这个Excel文件里面,把它整个流程给大家讲一下,第一步,第二步第三步对不对,好我把这个给它整理一下。
24:11
后半编码的一个。步骤啊,步骤如下。步骤录像,那现在呢,为了方便,我直接写一个小的表格,对不对,这样待会我放的比较方便,我把整个这个包下来。好吧,同学们看看大家能不能理解对不对,就是刚才我整个这个分析就直接放在我们这个表格里面就完事了。好,这个有个图片我带过来。上面有个图片,我看看图片来了没有啊。这儿不是有个图片吗?诶,这个图片是我们画的,这一棵赫夫曼树好看,看来了没有?诶,这个地方有点慢哈,好看看在没在上面。好,这个图没有整过来啊,图没整过来那不行,我得把这个图给大家拿过来,好吧,不着急,我把这个图给他拷贝过来就行了,在哪呢,就这个图。
25:04
这样便于大家的复习嘛。以后。好,放这就可以了,把它放小一点。好,各位同学,那关于我们这一个讲解的就是我们所说的赫夫曼。你看这个字有没有变小啊。好,呃,那这块我们讲解的关于就是后曼编码的一个说明就说了,最后呢,我这还有一点对,忘了还还得把这个提一提,就是原理剖析的一个注意事项。对,我也给他拿过来啊,因为这块呢,也是我们一个整理嘛,就是原理剖析的一个注意事项,就注意事项,好把注意事项给他板述一下就可以了,那这个注意事项呢,是我们初学者容易忽略的,而且呢,你可能想到这你会突然想不明白对吧?说这个夫曼根据夫曼数呢,根据排序的不一样,就当你有相同权值的时候,你在前面,在后面,这个最终生成的赫夫曼数长得就不一样了。
26:05
那这样不一样,不一样呢,就会造造成我们后方编码也不太,也不完全一样。但是不用着急,因为他最终WPL还是一样的,所以说你用WP2相同的情况下编的这个后曼数呢,它的长度仍然是一样的哦,长度一样就说WPS是一样的,最后我就写啊,写到这句话最后。最后呢,最后生成的,注意听这句话啊,最后生成的这个赫夫曼编码赫。和夫曼。编码的这个长度啊,是一样的。是一样的。好,这边我举了一个例子,就是哪个例呢?就这个例子对不对。好,同学们关于赫夫曼编码的一个原理剖析,我们就给大家讲到这儿,那下面呢,下一个视频就给大家讲如何实现赫夫曼编码对文件的。或者是字符串的,待会儿我们会讲文件的压缩。
27:03
会讲文件的解压。我们后面用代码给大家实现前面的思路很重要啊,后面我写的时候其实就是按这个思路来完成的,好的这一讲我们就到这里。
我来说两句