00:00
各位同学,我们来学习一下赫夫曼编码,赫夫曼编码呢,它其实是利用我们赫夫曼数的特性来构建或者是来形成的一种编码。那么我们先对赫夫曼编码呢做一些基本的介绍,赫夫曼编码呢,也翻译为哈夫曼编码。叫哈曼coding,也翻译成这种,呃,这种赫元甲的赫,这这也可以,它是一种编码方式,属于一种程序的算法,也也就是说赫夫曼编码了,已经不再是数据结构了,它是一种算法,能理解。那么赫夫曼编码,它是我们哈夫曼数,也就是说赫夫曼数在电讯通讯上的一个经典应用之一,也就是说我们赫夫曼编码呢,是利用了赫夫曼数的一些特性,就是赫夫曼数不是WPL,它是。它是一个最小的吗?利用这个特性,然后呢,来构建的一种编码。
01:01
那么赫夫曼编码呢?广泛用于数据文件的压缩,当然它也可以解压。它压缩率呢,通常在20%~90%之间。尤其是文本,如果你重复数据越多,那么它的压缩率呢就越高。赫曼,它是一种可变至长的编码,就是什么叫可变至长呢?后面我们会看到。看到它的这个特性啊,赫夫曼是这个赫夫曼编码是赫曼这个人,哈夫曼这个人在1952年提出的一种编码方式,也称之为最佳编码。好,这是它的一个基本介绍,那现在呢,呃,有了对客户们编码一个基本认识呢,我们先来看一看。就是对客户编码做一个原理性的剖析。那既然我们要讲赫夫曼编码它的好处,或者说赫夫曼编码的它的一个优越性,我们首先得给大家看,在不使用赫夫曼编码的时候,它是一种什么样的形式来进行这个电信处理的,或者是进行这个通讯的,那么在大家看这里在通讯领域领域的这个信息处理方式,第一第一种就是定层编码,定层编码就是我们所说的。
02:17
最笨的这种编码方式就是说完完全全的按照他的这一个原始的数据来进行编码的,比比如说同学们看我这里有一个字符串,这个字符串是这么一句话,I like like like Java do you like Java。那么同学们看这一个字符串,它一共有40个字符,注意啊,我包括空格了,大家可以去数一下,一共有40个。那么如果这40克我们按照阿斯克玛来处理的话,那么它会变成什么呢?大家应该知道阿斯克玛这个东西吧?就是如果记不起来的同学呢,可以打开我给大家分享的。分享的这个文件,同学们看,在我们资料里边有一个阿玛对照表。
03:06
那同学们可以看到这里啊,比如说。大家看。比如比如说我这里写的这个I like,这个I,这个I呢,它是一个英文字母,英文字母对应的它的阿斯克玛是哪一个呢?我们可以往下找一找。好的,同学们看这I。这个I啊,各位同学看这个I呢,它对应的十进制就是1105。对,105,也就是说我们在传递的时候呢,其实它是以数字形式来传递的,那这样子的话呢,它就会把它变成这样一个东西,105。空格32 32就是哪一个呢?同学们大家知道32是哪个吗?32我们来看对照是哪一个啊,32走32大家发现没有,就是空格。也就是说在他传递的时候呢,它会把空格翻译成32。这个数字。明白我的意思吧。OK,那其他我就不一个推了啊,我就不一个推了,那就108呢,就是L。
04:05
对不对,那么105呢,又是I,好,以此类推,最后这上面这个字符呢,如果用数字来表示的话,就是这一段数字。但是实际上大家都知道,这段数字呢,在计算机里面它都会翻译成二进制,也就是说我们计算机在处理的时候呢,它会把这个十进制转成二进制来进行进行这个传递,那同学们看,那么105翻译成这个二进八位的这个二进制呢,它就变成了这样一个字。就幺幺,用一个字节来表示的话,那就是1101001,我们看可以打开一个计算器算一算。好,我打开一个计算器,用程序员,好同学们看一下,比如说105。是个十进制,我转成二进制,大家看是不是1101001看这看啊。
05:01
1101001,那么前面为什么一个零呢?这个是它的高位,高位代表一个符号位,好,其他一样的道理我就不去讲了啊,比如说你是按一个字节来传来,来传递一个字节八位吗?一个自己八位好,那整个这边传递过去呢,就是这么一个。长度,那这个一个长度是多长呢?有多少个长度呢?长度是359包括空格。就空格这地方都算进去了啊,算进去就是359,大家可以看我给他统计一下。统计呢,同学们看我打开。我打开一个,呃,记事本,大家可以看是不是359个。好,同学们看。那如果说我把这个选中,这边有个叫做字符统计是不是300,诶这个怎么回事啊,多了一个啊,我看看。该359啊哦,不好意思,这边应该是打的。这样一个东西,我们再看一下。
06:02
应该是359,后面这个是,诶对多了一个哦,刚才这进去过有个有个空格。好,再来看一下统计。是不是359啊。359没问题吧,那也就是说如果我们按照这个定长的方式来走的话呢,那么诶各位同学,他就是359。长,总的长度就是359。OK,那实际上我们往往不会这么做,因为这样做呢。太不划算了,太长了,所以说信息领域在通信领域呢,它往往会进行一个变,变成编码,那变成编码他会怎么做呢,注意听。变成编码,他会这样做,他先统计你这个字符串里面出现的字母的。字母的这个个数,比如说D这个字母出现了一次。Y出现了一次好。这个U出现了一次,节出现了两次,V出现了两次,O出现了两次,以此类推,最后呢,空格出现了九次。
07:06
这个地方就是写的各个字符对应的个数,那按照这个来说的话呢,它就可以这样计算说。用零表示空格。用一表示A,用幺零,幺零是不是就二啊,二表示I挨在这。幺幺是一三表示我们的这个一,大家有没有发现它这样进行一个变成编码过后呢?因为为什么是变成啊,有些是一位,有些是两位对不对。那么说明按照各个字符出现的次数编码,原则是出现的次数越多编码越小,比如说空格出现的九次,我们就用零,你看它编码是反过来编的,这样呢有有助于我们进行一个这个节省我们的这个长度。那这个就是他一个。变成编码,那如果说按照上面给出的各个字符规定的编码呢,我们在传输这个字符串的时候,这个编码就变成这样子了。
08:02
我们看这个I。这个I进行一个编码是幺零,那么这个就是I,我用蓝色的表示的。零是谁呢?零是一个空格,大家看啊,I后面是个空格,那么我就用一个零表示空格,1011是谁呢?1011大家看,11011是D1011啊。1011。啊不不不是1011啊,是101,因为后面这个是蓝色的,101是谁啊,101我们查一查,101是L。就是这个L好,依此类推,Ii是不是又是幺零呢?然后呢,这个I呢,I是幺零,K呢,是100 K是不是100,查一下果然是100,好,那也就是说,如果我用上面的这个变成编码来处理的话呢,我这个地方就变成这个样子了,大家想这样子肯定会节省。
09:00
这个长度是吧,长度肯定会减少。长度可能会减少,但是呢,这现在这个编码是有一个问题的,大家有没有发现这个编码呢,它不是不是这个前缀编码。什么叫前缀编码呢?大家看我这里做个解释啊,大家不要着急,大家有没有发现。首先,我们先说什么叫前缀编码,字符的编码都不能是其他字符编码的前缀,符合此要求的编码我们就称之为前缀编码,即不能匹配到重复的编码。也就是说不要这个编码不要有二意性,但是现在我们这种编码呢,会有二意性,怎么理解呢?大家看啊,我给大家讲一下,你们就其其实一下就明白了,大家看,如果我把按照这个编码把这个10010110100这个串发给了。通过这个我们的这个通讯方式,或者是通过网络传输发给了一个程序,或者是一个接收接收器,那接收器是不是要对它进行解码。
10:03
你不解码我我不知道原先是什么呀,这个肯定人是看不懂的嘛,那你要解码你是不是就匹配好,现在麻烦事来了。假如他扫描到一哦,吼,麻烦了,你看他扫描到一,他发现这个一呢,诶是个A,他很有可能把这个一呢就翻译成A,后来他发现有个零,诶他发现可能是个空格。那这样子就麻烦了,他本身传的是I空格,现在你翻译成A空格了,是不是这是这个出现的原因,就是因为你这个零。这个零,这个一,它呢是别的编码的前缀,你看啊零。他是谁的前缀呢?你看啊,我找我找这个这个零还不是啊,零不是,但是一是看到没有一一你看一。你看这个一,它可以表示A,但是一零又表示I,当我们在进行解码的时候,现在这个一我就不知道了,这个一到底是A的第一个字符还是I的。
11:04
I的编码的第一个字符,第一个第一位我不知道,所以说这个就会造成匹配的多义性。多异性。明白,所以说这个编码呢,上面我们这个编程编码它是存在问题的。啊,存在问题的,他不是前缀编码,而我们后面讲的霍夫曼编码呢,它就是真正的前缀编码。好,那大家讲到这呢,反正大家知道有一种变成编码的概念就可以了。OK,那前面我们讲到了定场编码,我们又说到电场编码,那现在我们要来讲通讯领域的第三种处理方式,什么编码呢?赫夫曼编码。那么我们把后部编码呢,放在下一个视频为大家讲解,这块你们先理解一下,就是这个编程编码的特点,OK。
我来说两句