数据结构从逻辑结构上可以分为:集合、线性表、树、图
集合中常用的数据结构是背包等。
线性表包括栈、链表、队列等。
树包括堆、二叉树、哈夫曼树等。
图包括有向图、无向图、最小生成树、最短路径等(就职于高德地图的算法工程师,图的知识必须完全掌握(ง •̀_•́)ง)。
下面我们分别从数据压缩的简介,数据(位、字节、字符)的简介,到哈夫曼树,哈夫曼编码来详细分析。
现代IT产业经常提及“大数据”,实际上伴随着计算机行业兴起,数据就占据着最重要的地位,近年来,数据的增长量也是越来越大。
数据压缩可以节省数据存储的空间,以及节省数据传输的时间,在如此巨大的数据量面前,效果显著。
计算机内部数据类型最小单元为bit,也叫位、比特。但是一般编程语言处理的最小单位为byte,也叫字节、8位元组。通过定义也能知道,1个byte等于8个bit。Java 中,8位的char编码为1个字节,16位的short编码为2个字节,32位的int编码为4个字节。
《爸爸去哪儿5》10月底一期,山上展示了一串数字是“52088”,现在要把这些数字存进来。下面展示几种方式:
最终第五种方式占用空间最小,这是最粗糙的一种数据压缩的方式。
我们知道计算机中所有类型的数据最终都是用二进制(0和1,计算机用高电平和低电平分别表示0和1)表示。网络传输过程中,数据往往是通过比特流或者字节流的方式在网络中通信。比特流就是我们熟知的种子下载,p2p,免费、自由。字节流就是我们传统并常见的数据传输方式。程序员在调试过程中,是如何查看比特流和字节流的呢?我们如果直接打开一个二进制文件,看到的将是一团乱码,乱码的内容随着你操作系统的不同而不同,转储(dump)就是将这些乱码转换成我们看得懂的方式。例如可以转为二进制,以0和1表示,也可以转为8位的字节,甚至可以转为图片文件,0为白色像素,1为黑色像素。前两天我们公司系统出bug,就是采用的TCP dump的工具进行调试,很快发现了网络通信中的问题根源。代码中,我们一般会用管道方式将二进制文件传给这些dump编解码工具,或者直接重定向到另一个文件。
单字节编码系统,世界上语言众多,直接拿比特数据给别人看,谁也看不懂,因此诞生了单字节编码对照系统,它规定了哪些二进制数代表哪些字符。第一版的ASCII编码采用7位二进制数共计代表了128个字符,包括数字0-9,大小写字母a-z、A-Z,以及标点符号、运算符号和一些控制命令符号。英语用这128个字符就够了,但是其他语言不行,后来在它的基础上增加一位,也就是8位,可表示256个字符,前128个字符仍旧与第一版保持一致,而后128个字符被称作“扩展字符编码”,扩展字符集,每个地区国家都有自己的一个版本,所以无法达到世界通用的目的。这就造成了很大问题,当你拿到一个文件,如果不按照当初的编码打开,就会得到一堆乱码。这时出现了Unicode编码,它将全世界所有的字符编码集合到了一起。Unicode也有问题,因为某些语言或者符号要用大于一个字节来表示,这就与基础的ASCII出现了冲突,计算机如何知道这一个字节是代表ASCII中的字符还是Unicode中某个字符的一部分呢?随着互联网出现,UTF系列编码出现了,当前最流行的就是UTF-8编码格式,它加长了编码,设立了标志位,可以有效区分出英语和其他语言的字符。
带权路径长度最小的二叉树叫哈夫曼树。
如图:
A占5%,B为15%,C为40%,D为30%,E为10%。对应的每个结点的权就是他们所占的百分比。
二叉树a的WPL值为:1*5+2*15+3*40+4*30+4*10=315
二叉树b的WPL值为:3*5+15*3+40*2+30*2+10*2=220
由此可见,二叉树b的带权路径长度要小于二叉树a,我们的目的就是让权值大的结点尽量路径长度小一些,这样可以保证总效率提高。
如图:
此时该二叉树的WPL值为:4*5+10*4+15*3+30*2+40*1=205
该二叉树的WPL值比上面的二叉树b还少了15,此时构建的二叉树才是WPL最小的,才是标准的哈夫曼树,也叫最优二叉树。
接着使用上面的例子,我们按照他们的权值要传输1个A,2个E,3个B,6个D,8个C。连起来就是:
AEEBBBDDDDDDCCCCCCCC
共20个字符,按约定转为二进制数:
A | B | C | D | E |
---|---|---|---|---|
000 | 001 | 010 | 011 | 100 |
取数据的时候仍旧按照这个约定再将他们取出即可。
那么存储时就是一串二进制数:
000100100001001001011011011011011010010010010010010010010
三位一组表示一个字母,共60个数。
现在我们要使用哈夫曼编码,利用上面已经构建出来的哈夫曼树,将所有左子路径的权都改为0,右子的权都改为1,如图:
从根节点开始拼凑,我们用这些0和1来编码,得出结果为:
A | B | C | D | E |
---|---|---|---|---|
1000 | 101 | 0 | 11 | 1001 |
那么,现在的二进制数串为:
10001001100110110110111111111111100000000
共40个数。
也就是说我们的数据被压缩到67%,节约了33%的空间,随着原字符的增加和权重的变化,这种压缩效率会更高。
以上就是哈夫曼编码的内容,那么我们该如何解码呢?
在上面第一种原始的方式中,我们可以直接按照三位一截取,然后对比我们的约定表格,还原源字符串。然而我们利用哈夫曼编码以后,发现每个字符换成的二进制数的长度不同了,二进制数中非0即1,如果长度不同,很容易混淆。
若要设计长短不等的编码,则必须任意字符的编码都不是另一字符的前缀,这种编码称作前缀编码。
我们仔细观察编码后的二进制串,发现按照约定表格,从第一个字符1000换成A以后,第二个是1001,换成E,后面的并没有出错。