zip是什么意思

2021.10.25 -

我们平时经常使用zip压缩软件,压缩后的文件大小,能够达到几十分之一甚至几百分之一。

他是怎么做到的?压缩的原理又是什么,视频的开始,我们还是要先从他的作者菲尔卡斯的传奇讲起。上世纪八十年代末,互联网刚刚开始有了出钱。在当时最流行的上网方式是使用电话线拨号上网,但是由于电话线的接入速度慢的可怜,导致通过b b i s 传输文件变成一件非常痛苦的事情。所以文件压缩在那个年代变得尤为重要。当时的美国b b s 上流行的一种压缩技术叫a r c,它是一家商业公司开发的压缩技术,使用a r c 压缩是需要付费的。当时的菲尔卡茨还是一个刚从大学毕业不久的毛头小伙,由于时常混迹在b b i 词上,他对a r c 的收费模式非常不满,于是自己开发了一款软件叫p k l c。

这个程序a r c 完全兼容,可以压缩和解压a r c 文件,并且免费提供给大家使用。由于用户减少,a r c 公司一怒之下把菲尔卡茨告上法庭。控告菲尔卡茨侵犯a r c 公司的知识产权,法院判决侵权属实。菲尔卡茨狼刚入狱,但是这种判决并没有埋没掉菲尔卡茨的斗志。他在监狱中冥思苦想,决定开发一款超越a r c 的压缩算法出来,不鸣则已,一鸣惊人。仅仅用了两周时间,p k zip算法就横空出世。压缩比压缩速度都超过a l c 十二。卡茨不仅免费提供软件,并且直接公开源码,于是z i p 流行起来。从而当时internet 传输标准z i p 压缩格式也成为压缩文档的事实标准。
但菲尔卡茨并没有从zip 中赚到一分钱,最终穷困潦倒的他于二零零四年四月十四日死在了美国威斯康星州密尔沃基的一家汽车旅馆里。

此时手里还紧握着一个烈性酒的酒瓶。到底菲尔卡茨在狱中思考了什么?p k zip 算法又是什么原理呢?我们先来举一个简单的例子,大家看下面这段话,黑化肥发黑灰化肥发黑,黑化肥挥发会发黑,灰化肥挥发会发灰。这段话总共二十六个字符,加上标点符号是三十个字符。如果用普通的unicode 表示,一共是三十乘以二,等于六十个字节。可不可以压缩呢?所有人都可以一眼看出这段话中出现了很多重复字符,比如化肥挥发,化肥发挥发挥发等等。我们能不能这样操作?第一次出现的时候,用普通的unicode 编码。第二次出现的时候就换成距离加长度来表示距离的意思就是距离前面重复的字符间隔的字节数。

长度就是后面多少字节是重复的,所以这段话可以变成这样,黑化肥发黑灰十二六灰二十四六,灰发灰三十二六三十六。十八六三十六六编码完之后,我们来计算一下这里面汉字和标点符号还有十二个,数字有十二个。如果一个数字占一个字节,则编码或者大小就是十二乘以二加十二等于三十六之间。比之前的六十次减少了很多。但是大家有没有发现一个问题,就是解码的时候,解码到这个十二六,我怎么知道这个十二六代表的是普通字符还是距离加长度。显然,我们还需要增加一个标记位,这个标记位的要求是能够表示每一个字符是普通字符还是距离加长度。还有一个专有名词叫leader roll。至于如何表示的,我们稍后会讲解。还有一个问题就是如果出现多次重复的字符,在第三次出现的时候,应该用距离近的表示,还是距离远表示。

关于这个问题,菲尔卡茨认为,距离越近,重复概率越高。就比如我们平时聊天的时候,你重复说的话,最有可能是刚说完不久的话,你很少去重复五个小时之前的话。所以我们在压缩的时候,如果有多次重复的句子,我们一定要用距离我们最近的那个距离长度数值越小,这些数字出现的概率就越高。出现概率越高意味着什么?意味着这些重复的数字又能进一次压缩,重复次数越多,压缩率就越高。请记住这个思想,这个思想贯穿了z i p 的始终。我认为这个思想就是菲尔卡茨在狱中思考的精髓。往往伟大的思想就是这么简单。继续回答我们的问题,这些重复字符如何二次压缩的,我们先保留一下这个疑问,后面会给你解答。因为距离越大,重复概率就越低。所以菲尔卡斯还规定。距离最大值为三二七六八,也就是最多向前找三二七六八个字节,超过了即使是有重复字节也不再处理。所以这个窗口是不断向前滑动的。称之为滑动窗口。我们之前提到短字符压缩还不如不压,所以长度最小为三,超过三的才会压缩呢。

看到这里,大家明白了一个句子,经过以上的编码之后,变成了包含普通字符标几位距离长度的字符串。我们先来看一下普通字符在计算机中。字符是以字节为单位表示的一个字节,八个比特位能表示零到二百五十五的数字。也就是说我们抛开这个字符所表达的含义,把它当做数字来处理的话。他一定是零到二百五十五中的一个。那我如何用一个数字,就既能表示普通字符,又表示压缩字符呢?菲尔卡斯设计了这么一个编码方式,就是将零到二百五十五向后扩展出来一部分字。前面的零到二百五十五还是继续表示普通字符。如果大于二百五十五,就表示压缩字符的长度,多出来多少就表示长度为多少。

其中,二百五十六是结束标记leader,从二百五十七开始,二百五十七表示length 等于三,二百五十八表示length 等于四,以此类推。塞尔卡斯认为,重复区间不可能无。二百五十八个字间已经构成了,所以论词的长度被限定为最大二百五十八。那这个数字的长度应该是二百五十六加二百五十五等于五百一十一。这样我们就实现了只用一个数字就把普通字符让几位长度合三为一。但是菲尔卡茨认为,五百一十一也太长了,还可以缩小。由于我们之前提到嫩子越小,出现的概率就越大,恁子越大,出现的概率就越小。所以菲尔卡茨并不是累加棱子大小的。而是设计了一个编码表links 小于等于十的书,编码是依次递增,一links 越大,一个编码表示的区间就越多。如果出现了超过十的数,再附加一个扩展编码来表示。扩展码是什么意思?比如十五和十六的code 都是二百六十七,二百六十七的二进制数为一零零零一零一一。再扩展一个比特的扩展码。后面加零就是十五,后面加一就是十六,所以认识越长,需要的扩展比特越多。

这个思想的意思就是用较少的比特来表示出现概率高的数,用较大的比特来表示出现概率较低的数,可以使整体最小的概率最大。这是菲尔卡斯第二次运用到这个思想。解码时如果是零到二百五十五,则认为是普通编码,不做处理。如果是大于二百五十六,则根据code 加扩展编码得到length,再往后取一个distance。得到distance challenge 往前找到普通编码替换。

以上的这个编码过程有一个专有名词叫l z 七七编码。看到这里,不知道大家有没有一个疑问,上面说了一个字节是八个集成位,最高表示到二百五十五。那上面经过leader 处理后,最高要达到二百八十五。而且再加上length 的扩展编码,导致一个数字需要超过一个字节才能表示。不管是编码还是解码,不再按照字节为单位,而是按照比特位作为单位。解码时如何在一段连续的二进制数中找出来每个数字占多少位。大家别着急,这里请大家跳出对飞马比特位的纠结,纠正为编码后变成了一堆数字的组合。

菲尔卡茨最神奇的设计是对这一堆数字进行的二次压缩。他将大名鼎鼎的哈夫曼编码运用到了如虎纯青的地步。

- END -

24
0

已关闭回复!

《抖音直播运营地图》直播4大节点,100+知识点

《抖音直播运营地图》直播4大节点,100+知识点 图片下载到本地观看才是高清图片,在线观看受网络影响会不清晰 […]