搜索
当前位置: 秒秒彩官网 > 读入原语 >

DEFLATE 压缩算法

gecimao 发表于 2019-05-26 00:22 | 查看: | 回复:

  是同时使用了LZ77算法与哈夫曼编码(Huffman Coding)的一个。它最初是由Phil Katz为他的PKZIP归档工具第二版所定义的,后来定义在RFC 1951规范中。

  人们普遍认为DEFLATE不受任何专利所制约,并且在LZWGIF文件格式使用)相关的专利失效之前,这种格式除了在ZIP文件格式中得到应用之外也在gzip压缩文件以及PNG图像文件中得到了应用。

  DEFLATE压缩与解压的源代码可以在自由、通用的压缩库zlib上找到。

  更高压缩率的DEFLATE是7-zip所实现的。AdvanceCOMP也使用这种实现,它可以对gzipPNGMNG以及ZIP文件进行压缩从而得到比zlib更小的文件大小。在Ken Silverman的KZIP与PNGOUT中使用了一种更加高效同时要求更多用户输入的DEFLATE程序。

  gzip,zlib,以及图形格式png,使用的是同一个压缩算法deflate。我们通过对gzip源码的分析来对deflate压缩算法做一个详细的说明。我阅读的gzip版本为 gzip-1.2.4。我们对算法做三种程度的说明。第一种程度,对gzip所使用压缩算法基本原理的说明。第二种程度,对gzip压缩算法实现方法的说明。第三种程度,对gzip实现源码级的说明。

  如果你有时间的话,我建议你先不要看下面的内容,自己尝试通过读gzip源码,来了解它的压缩解压缩是如何实现的,这将会是一个非常有趣的智力游戏,千万不要错过。当一个又一个的谜被解开时,那感觉就像唐伯虎同志所说的,“慷慨然诺杯酒中”。(小唐的诗,除了另一个倒霉蛋曹雪芹外,好像不太被人提。)

  gzip 对于要压缩的文件,首先使用lz77算法进行压缩,对得到的结果再使用huffman编码的方法进行压缩。所以我们分别对lz77和huffman编码的原理进行说明。

  首先,gzip 从要压缩的文件中读入64KB的内容到一个叫window的缓冲区中。为了简单起见,我们以32KB以下文件的压缩为例做说明。对于我们这里使用32KB以下文件,gzip将整个文件读入到window缓冲区中。然后使用一个叫strstart的变量在window数组中,从0开始一直向后移动。strstart在每一个位置上,都在它之前的区域中,寻找和当前strstart开始的串的头3个字节匹配的串,并试图从这些匹配串中找到最长的匹配串。

  如果当前的strstart开始的串,可以找到最少为3个字节的匹配串的话,当前的strstart开始的匹配长度那么长的串,将会被一个匹配长度,到匹配串开头的距离对替换。

  如果当前的strstart开始的串,找不到任何的最少为3个字节的匹配串的话,那么当前strstart的所在字节将不作改动。

  为了区分是一个匹配长度,到匹配串开头的距离对,还是一个没有被改动的字节,还需要为每一个没有被改动的字节或者匹配长度,到匹配串开头的距离对,另外再占用一

  位,来进行区分。这位如果为1,表示是一个匹配长度,到匹配串开头的距离对,这位如果为0,表示是一个没有被改动的字节。

  现在来说明一下,为什么最小匹配为3个字节。这是由于,gzip 中,匹配长度,到匹配串开头的距离对中,匹配长度的范围为3-258,也就是256种可能值,需要8bit来保存。到匹配串开头的距离的范围为0-32K,需要15bit来保存。所以一个匹配长度,到匹配串开头的距离对需要23位,差一位3个字节。如果匹配串小于3个字节的话,使用匹配长度,到匹配串开头的距离对进行替换,不但没有压缩,反而还会增大。所以保存匹配长度,到匹配串开头的距离对所需要的位数,决定了最小匹配长度至少要为3个字节。

  下面我们就来介绍gzip如何实现寻找当前strstart开始的串的最长匹配串。

  如果每次为当前串寻找匹配串时,都要和之前的每个串的至少3个字节进行比较的话,那么比较量将是非常非常大的。为了提高比较速度,gzip使用了哈希表。这是gzip实现LZ77的关键。这个哈希表是一个叫head的数组(后面我们将看到为什么这个缓冲区叫head)。gzip对windows中的每个串,使用串的头三个字节,也就是strstart,strstart+1,strstart+2,用一个设计好的哈希函数来进行计算,得到一个插入位置ins_h。也就是用串的头三个字节来确定一个插入位置。然后把串的位置,也就是 strstart的值,保存在head数组的第ins_h项中。我们马上就可以看到为什么要这样做。head数组在没有插入任何值时,全部为0。

  当某处的当前串的三个字节确定了一个ins_h,并把当时当前串的位置也就是当时的strstart保存在了head[ins_h]中。之后另一处,当另一处的当前串的头三个字节,再为那三个字节时,再使用那个哈希函数来计算,由于是同样的三个字节,同样的哈希函数,得到的ins_h必然和前面得到的ins_h是相同的。于是就会发现head[ins_h]不为0。这就说明了,有一个头三个字节和自己相同的串把自己的位置保存在了这里,现在head[ins_h]中保存的值,也就是那个串的开始位置,我们就可以找到那个串,那个串至少前3个字节和当前串的前3个字节相同(稍后我们就可以看到这种说法不准确,这里是为了说明方便),我们可以找到那个串,做进一步比较,看到底能有多长的匹配。

  我们现在来说明一下,相同的三个字节,通过哈希函数得到的ins_h必然是相同的。而不同的三个字节,通过哈希函数有没有可能得到同一个ins_h,我没有对这个哈希函数做研究,并不清楚,不过一般的哈希函数都是这样的,所以极大可能这里的也会是这种情况,即不同的三个字节,通过哈希函数有可能得到同一个ins_h,不过这并不要紧,我们发现有可能是匹配串之后,还会进行串的比较。

  一个文件中,可能有很多个串的头三个字节都是相同的,也就是说他们计算得到的ins_h都是相同的,如何能保证找到他们中的每一个串呢?gzip使用一个链把他们链在一起。gzip每次把当前串的位置插入head的当前串头三个字节算出的ins_h处时,都会首先把原来的head[ins_h]的值,保存到一个叫prev的数组中,保存的位置就在现在的strstart处。这样当以后某处的当前串计算出ins_h,发现head[ins_h]不空时,就可以到prev[ head[ins_h] ]中找到更前一个的头三个字节相同的串的位置。对此我们举例说明。

  我们看到所有头三个字母为abc的串,被链在了一起,从head可以一直找下去,直到找到0。

  现在我们也就知道了,三个字节通过哈希函数计算得到同一ins_h的所有的串被链在了一起,head[ins_h]为链头,prev数组中放着的更早的串。这也就是head和prev名称的由

  gzip寻找匹配串的另外一个值得注意的实现是,延迟匹配。会进行两次尝试。比如当前串为str,那么str发生匹配以后,并不发生压缩,还会对str+1串进行匹配,然后看哪种

  从这个例子中我们就看到了做另外一次尝试的原因。如果碰到的一个匹配就使用了的话,可能错过更长匹配的机会。现在做两次会有所改善。

  我在这里对gzip压缩算法做出了一些说明,是希望可以和对gzip或者压缩解压缩感兴趣的朋友进行交流。

  我对gzip的了解要比这里说的更多一些,也有更多的例子。如果哪位朋友愿意对下面的问题进行研究,以及其他压缩解压缩的问题进行研究,来这里和我交流的话,我也愿意就我知道的内容进行更多的说明。

  这种匹配算法,即用3个字节(最小匹配)来计算一个整数,是否比用串比较来得高效,高效到什么程度。

  哈希函数的讨论。不同的三个字节,是否可能得到同一个ins_h。ins_h和计算它的三个字节的关系。

  treat_file() 中打开文件,调用函数 zip()。注意这里的 work 的用法,这是一个函数指针。

  由于计算strstart=0时的ins_h,需要0,1,2这三个字节和哈希函数发生关系,所以在lm_init中,预读0,1两个字节,并和哈希函数发生关系。

  在第一次使用uncompress函数的时候,就把我弄得很老火,最后错误的原因现在具体是什么也没有弄明白,特别无语。compress函数与uncompress函数可以跨平台。在Linux上编译链接时别忘...博文来自:u012654882的专栏

  地址:因为最近需要像web上报些数据,对接的web是统一的接口,需要我这边对数据进行gzip压缩以及bas...博文来自:danis_wang的博客

  官网:功能:压缩一段字节流,但是不包含任何文件信息。所以如果要编写压缩数据,还要自定义头部信息之类的,自己生成对应的文件结构设计:CMake编译工具(用于在wi...博文来自:u013674509的专栏

  gzip是一种数据格式,默认且目前仅使用deflate算法压缩data部分;deflate是一种压缩算法,是huffman编码的一种加强。deflate与gzip解压的代码几乎相同,可以合成一块代码。...博文来自:飘在上海的北方人

  一、LZ77算法基本概念LZ77算法的说明网上很多,本文为个人见解,仅供参考。本人认为LZ77算法其实是字典压缩的一个变种,与字典压缩不同的是,它的字典是动态生成的并且只有一个,一般选取一定数量的最近...博文来自:自由理想的足迹

  以下内容包含我对RFC1951部分内容的翻译与总结,不足之处还请大家指出,小弟感激不尽。 在压缩中,哈夫曼编码有两种方式,分别是静态哈夫曼编码(CompressionwithfixedHuffmanc...博文来自:jison_r_wang的专栏

  不少网友读完zlib库compress和uncompress函数的使用方法这篇文章之后,仍然无法独立完成简单的文件压缩和解压缩功能,为此作者在这里追加这样的演示代码。问题的根源在于这些网友对于字符串和...博文来自:图灵狗的专栏

  今天在获取HTTP报文头的Accept-Encoding时,在控制台蹦出个gzip和deflate,有些陌生,只是知道这是两种压缩算法。那么它们到底有什么不同呢?这里转载一位技术人员的文章,做一下详解...博文来自:红石丶的博客

  经过大量学习和研究参考,整理除了ZlibDeflate算法解压缩侧的具体实现,详见下文图片,便于各位读者理解。...博文来自:ADC_ZZZ的博客

  gzip 、zlib以及图形格式png,使用的压缩算法都是deflate算法。从gzip的源码中,我们了解到了defalte算法的原理和实现。我阅读的gzip版本为 gzip-1.2.4。下面我们将要...博文来自:幻听

  本文会使用Fiddler来查看HTTPrequest和Response,如果不熟悉这个工具,可以先参考[Fiddler教程]HTTP压缩是指:Web服务器和浏览器之间压缩传输的”文本内容“的方法。HT...博文来自:SAN_YUN的专栏

  压缩的过程使用了“窗口”这一概念。压缩时,将需要处理的数据拷贝到窗口中,然后直接在窗口中分析并处理这些数据。这个窗口就好比一张工作台,每次把要处理的东西放到这张工作台上,人们站在工作台旁边收拾这些数据...博文来自:jison_r_wang的专栏

  LZ4是一个快速的无损压缩算法,单核的压缩速度超过400MB/s,单核的解压速度超过1GB/s。LZ4也适用于多核的情况,压缩速度能成倍的提高,解压速度几乎达到RAM的速度限制。文本主要分析LZ4的原...博文来自:zhangskd的专栏

  其实ZIP压缩算法详细分析及解压实例解释篇文章讲的已经是比较清楚了,但因为讲到许多细节,内容还是偏长,我尽量简略总结和补充下。...博文来自:aircattle的专栏

  LZ4是一种无损压缩算法,压缩速度为每核心400MB/s(0.16字节/周期)。它拥有速度极快的解码器,速度为每核心多GB/s(0.71字节/周期)。此外,一种称为LZ4_HC的高压缩率衍生产品可用于...博文来自:lucklytom的博客

  据本人了解,使用deflate算法进行解压缩时,需要提前知道压缩前数据大小,然后根据压缩前数据大小申请动态内存,用以存放解压缩后的数据。 这样问题就来了,若一个数据流压缩前为100M以上,那么我就需要论坛

  本节内容,是整个该系列文章的灵魂所在,后面的源码分析不过是肉体罢了。所有使用deflate算法的压缩格式,gzip、PKzip等等,也许他们互相之间的头和尾不同,但是这部分,属于瓤的这部分,是基本相同...博文来自:jison_r_wang的专栏

  我们在配置网站GZip压缩的时候,会发现有两个模块可以设置的,一个是GZip模块的参数配置,另一个是Deflate模块的参数配置,他们的设置方法是一样的。刚开始时我不太明白,这两地方有什么不同?网站开...博文来自:小洋人最happy的专栏

  本文将会对常用的几个压缩算法的性能作一下比较。结果表明,某些算法在极端苛刻的CPU限制下仍能正常工作。文中进行比较的算有:JDKGZIP——这是一个压缩比高的慢速算法,压缩后的数据适合长期使用。JDK...博文来自:cnm_csdn_wt的博客

  转自:做项目就伴随着一个问题--数据来源。在网络数据获取的过程,考虑到数据的动态下载需要爬虫。这也是必经之路吧。我在运用url...博文来自:一起长大的约定

  原文地址:引言有两种主要的压缩算法:有损和无损。有损压缩算法通过移除在保真情形下需要大量的...博文来自:holly的专栏

  内容丰富,闲暇时可以细品引言有两种主要的压缩算法:有损和无损。有损压缩算法通过移除在保真情形下需要大量的数据去存储的小细节,从而使文件变小。在有损压缩里,因某些必要数据的移除,恢复原文件是不可能的。有...博文来自:Beatman的专栏

  引言有两种主要的压缩算法:有损和无损。有损压缩算法通过移除在保真情形下需要大量的数据去存储的小细节,从而使文件变小。在有损压缩里,因某些必要数据的移除,恢复原文件是不可能的。有损压缩主要用来存储图像和...博文来自:永无止境,上下求索

  1压缩原理要清楚USI的压缩原理,首先需要对图像的存储方式有一个基本的了解。USI压缩是建立在索引色的基础上进行的。1.1索引图与RGB图对于PNG图像,可以分为索引(Index)图和RGB图两种,索...博文来自:程序猿有一天也会成为工程狮!

  由于在工作中有用到数据压缩的功能,我便查找了一些压缩函数库,对这些函数库进行了简单的实验,简要对比了各自的性能。在这里,我既是对以前工作的总结,也同时希望能给其他人带来一些帮助。首先,因为我工作中使用...博文来自:wyw__wyw的博客

  Hive的后端存储是HDFS,它对大文件的处理是非常高效的,如果合理配置文件系统的块大小,NameNode可以支持很大的数据量。但是在数据仓库中,越是上层的表其汇总程度就越高,数据量也就越小。而且这些...博文来自:yycdaizi的专栏

  查看本博客前,请先参考博客:有时候,激活的时候不成功,比如我的是myeclips...博文来自:Miss_kun的专栏

  1、错误:                 键盘遮挡输入框最常见的可能就是在登录界面了,无论有多少个textFiled,不论是在VC的任何位置。都有可能造成键盘弹出来时,把输入框挡住了。...博文来自:AppleWiner的博客

  链表是数据结构中最基本常用的,C++语言中单链表是利用指针操作实现的,python作为面向对象编程的,可以使用创建一个Node类来实现链表,利用类的属性引用来代替指针操作。 下面我们创建了一个...博文来自:令狐公子的博客

  最近比较有空,大四出来实习几个月了,作为实习狗的我,被叫去研究Docker了,汗汗! Docker的三大核心概念:镜像、容器、仓库 镜像:类似虚拟机的镜像、用俗话说就是安装文件。 容器:类似一个轻量...博文来自:我走小路的博客

  一、概述 二、7个设计原则 三、创建型模式(5种) 四、结构型模式(7种) 五、行为型模式(11种) 六、总结 前言:熟练地掌握设计模式,并能在实际编程开发中灵活运用它们,不仅能使代码更规范,重用性...博文来自:csdn_aiyang的博客

  帐号相关流程注册范围 企业 政府 媒体 其他组织换句话讲就是不让个人开发者注册。 :)填写企业信息不能使用和之前的公众号账户相同的邮箱,也就是说小程序是和微信公众号一个层级的。填写公司机构信息,对公账...博文来自:小雨同学的技术博客

  tensorflow在ubuntu系统上按照官方文档安装起来相对容易,在centos上由于没有apt-get( yum)相对困难一些,本文会提到一些安装过程中遇到的一些坑及解放方案。...博文来自:zhangweijiqn的专栏

  在网上所搜索很多操作Word的都是用VC,VS2010做了一些修改,添加操作的方式和用法都有所变化。 要操作Word必须先添加对应的类,如下图在工程中添加操作类(TypeLib中的 MFC类): ...博文来自:xiangjianbo127的专栏

  python中要使用pychartdir的绘图的话需要安装pychartdir模块,其安装方法不同于其他python模块的安装。 1.先下载pychartdir,可从官网博文来自:走在测试的路上

  若函数的返回值是指针,且用const修饰,则函数返回值指向的内容是常数,不可被修改,此返回值仅能赋值给const修饰的相同类型的指针。如: 1  const int * f1(){ 2      ...博文来自:教学 & 技术专栏

  前段时间看了一些关于LSTM方面的论文,一直准备记录一下学习过程的,因为其他事儿,一直拖到了现在,记忆又快模糊了。现在赶紧补上,本文的组织安排是这样的:先介绍rnn的BPTT所存在的问题,然后介绍最初...博文来自:天道酬勤,做一个务实的理想主义者

  强连通分量: 简言之 就是找环(每条边只走一次,两两可达) 孤立的一个点也是一个连通分量   使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点)   定义: int Ti...博文来自:九野的博客

  jquery/js实现一个网页同时调用多个倒计时(最新的) 最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦! //js ...博文来自:Websites

  阅读内容为:FX系列微型可编程控制器用户手册(通讯篇)中计算机链接功能章节。 采用本方法通信,pc端的实现,其实就是,把操作按照协议(2种)翻译成相应的字符串,通过串口发送给plc。 编写一应用程...博文来自:pengjc2001的博客

  最近在学热更新,涉及到资源热更,所以就了解了XML,JSON相关的东西。这方面网上资料还是比较多的,所以这里主要是总结一下基本使用方法和一些应用的Demo。 1.先介绍一下 XML 和 JSON ...博文来自:YzlCoder的记事本

  数据库 UPDATE多条记录不同值,同时UPDATE多个字段。博文来自:小单的博客专栏

  测试环境莫名其妙有几条重要数据被删除了,由于在binlog里面只看到是公用账号删除的,无法查询是那个谁在那个时间段登录的,就考虑怎么记录每一个MYSQL账号的登录信息,在MYSQL中,每个连接都会先执...博文来自:路在脚下

  1. 规则引擎面临的问题:业务规则的实现大部分是由开发人员来实现的 业务规则需要业务分析人员能够阅读和理解 业务规则的可读性和用户的友好性都不太好2. DSL领域特殊语言DSL == Domain...博文来自:哎幽的成长

  显示CSDN通知。本身没有非法功能,不得用于非法用途。博文来自:jdgdf566的专栏

本文链接:http://k-mood.com/duruyuanyu/378.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部