没有合适的资源?快使用搜索试试~ 我知道了~
zlib 源码分析 对Huffman tree, lz77基础进行了深入讲解 对zlib的实现思路有深度的分析
资源推荐
资源详情
资源评论
gzip 、zlib 以及图形格式 png,使用的压缩算法都是 deate 算法。从 gzip 的源码中,我们了解到了
defalte 算法的原理和实现。我阅读的 gzip 版本为 gzip-1.2.4。下面我们将要对 deate 算法做一个分
析和说明。首先简单介绍一下基本原理,然后详细的介绍实现。
1 gzip 所使用压缩算法的基本原理
gzip 对于要压缩的文件,首先使用 LZ77 算法的一个变种进行压缩,对得到的结果再使用 Human 编码
的方法(实际上 gzip 根据情况,选择使用静态 Human 编码或者动态 Human 编码,详细内容在实现
中说明)进行压缩。所以明白了 LZ77 算法和 Human 编码的压缩原理,也就明白了 gzip 的压缩原理。
我们来对 LZ77 算法和 Human 编码做一个简单介绍。
1.1 LZ77 算法简介
这一算法是由 Jacob Ziv 和 Abraham Lempel 于 1977 年提出,所以命名为 LZ77。
1.1.1 LZ77 算法的压缩原理
如果文件中有两块内容相同的话,那么只要知道前一块的位置和大小,我们就可以确定后一块的内容。所
以我们可以用(两者之间的距离,相同内容的长度)这样一对信息,来替换后一块内容。由于(两者之间
的距离,相同内容的长度)这一对信息的大小,小于被替换内容的大小,所以文件得到了压缩。
下面我们来举一个例子。
有一个文件的内容如下
http://jiurl.yeah.net http://jiurl.nease.net
其中有些部分的内容,前面已经出现过了,下面用()括起来的部分就是相同的部分。
http://jiurl.yeah.net (http://jiurl.)nease(.net)
我们使用 (两者之间的距离,相同内容的长度) 这样一对信息,来替换后一块内容。
http://jiurl.yeah.net (22,13)nease(23,4)
(22,13)中,22 为相同内容块与当前位置之间的距离,13 为相同内容的长度。
(23,4)中,23 为相同内容块与当前位置之间的距离,4 为相同内容的长度。
由于(两者之间的距离,相同内容的长度)这一对信息的大小,小于被替换内容的大小,所以文件得到了
压缩。
1.1.2 LZ77 使用滑动窗口寻找匹配串
LZ77 算法使用"滑动窗口"的方法,来寻找文件中的相同部分,也就是匹配串。我们先对这里的串做一个
说明,它是指一个任意字节的序列,而不仅仅是可以在文本文件中显示出来的那些字节的序列。这里的串
强调的是它在文件中的位置,它的长度随着匹配的情况而变化。
LZ77 从文件的开始处开始,一个字节一个字节的向后进行处理。一个固定大小的窗口(在当前处理字节
之前,并且紧挨着当前处理字节),随着处理的字节不断的向后滑动,就象在阳光下,飞机的影子滑过大
地一样。对于文件中的每个字节,用当前处理字节开始的串,和窗口中的每个串进行匹配,寻找最长的匹
配串。窗口中的每个串指,窗口中每个字节开始的串。如果当前处理字节开始的串在窗口中有匹配串,就
用(之间的距离,匹配长度) 这样一对信息,来替换当前串,然后从刚才处理完的串之后的下一个字节,继
续处理。如果当前处理字节开始的串在窗口中没有匹配串,就不做改动的输出当前处理字节。
处理文件中第一个字节的时候,窗口在当前处理字节之前,也就是还没有滑到文件上,这时窗口中没有任
何内容,被处理的字节就会不做改动的输出。随着处理的不断向后,窗口越来越多的滑入文件,最后整个
窗口滑入文件,然后整个窗口在文件上向后滑动,直到整个文件结束。
1.1.3 使用 LZ77 算法进行压缩和解压缩
为了在解压缩时,可以区分“没有匹配的字节”和“(之间的距离,匹配长度)对”,我们还需要在每个“没有
匹配的字节”或者“(之间的距离,匹配长度)对”之前,放上一位,来指明是“没有匹配的字节”,还是“(之
间的距离,匹配长度)对”。我们用 0 表示“没有匹配的字节”,用 1 表示“(之间的距离,匹配长度)对”。
实际中,我们将固定(之间的距离,匹配长度)对中的,“之间的距离”和“匹配长度”所使用的位数。由于
我们要固定“之间的距离”所使用的位数,所以我们才使用了固定大小的窗口,比如窗口的大小为 32KB,
那么用 15 位(2^15=32K)就可以保存 0-32K 范围的任何一个值。实际中,我们还将限定最大的匹配
长度,这样一来,“匹配长度”所使用的位数也就固定了。
实际中,我们还将设定一个最小匹配长度,只有当两个串的匹配长度大于最小匹配长度时,我们才认为是
一个匹配。我们举一个例子来说明这样做的原因。比如,“距离”使用 15 位,“长度”使用 8 位,那么“(之
间的距离,匹配长度)对”将使用 23 位,也就是差 1 位 3 个字节。如果匹配长度小于 3 个字节的话,那么
用“(之间的距离,匹配长度)对”进行替换的话,不但没有压缩,反而会增大,所以需要一个最小匹配长
度。
压缩:
从文件的开始到文件结束,一个字节一个字节的向后进行处理。用当前处理字节开始的串,和滑动窗口中
的每个串进行匹配,寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串,就先输出一个标
志位,表明下面是一个(之间的距离,匹配长度) 对,然后输出(之间的距离,匹配长度) 对,然后从刚才
处理完的串之后的下一个字节,继续处理。如果当前处理字节开始的串在窗口中没有匹配串,就先输出一
个标志位,表明下面是一个没有改动的字节,然后不做改动的输出当前处理字节,然后继续处理当前处理
字节的下一个字节。
解压缩:
从文件开始到文件结束,每次先读一位标志位,通过这个标志位来判断下面是一个(之间的距离,匹配长
度) 对,还是一个没有改动的字节。如果是一个(之间的距离,匹配长度)对,就读出固定位数的(之间
的距离,匹配长度)对,然后根据对中的信息,将匹配串输出到当前位置。如果是一个没有改动的字节,
就读出一个字节,然后输出这个字节。
我们可以看到,LZ77 压缩时需要做大量的匹配工作,而解压缩时需要做的工作很少,也就是说解压缩相
对于压缩将快的多。这对于需要进行一次压缩,多次解压缩的情况,是一个巨大的优点。
1.2 Human 编码简介
1.2.1 Human 编码的压缩原理
我们把文件中一定位长的值看作是符号,比如把 8 位长的 256 种值,也就是字节的 256 种值看作是符号。
我们根据这些符号在文件中出现的频率,对这些符号重新编码。对于出现次数非常多的,我们用较少的位
来表示,对于出现次数非常少的,我们用较多的位来表示。这样一来,文件的一些部分位数变少了,一些
部分位数变多了,由于变小的部分比变大的部分多,所以整个文件的大小还是会减小,所以文件得到了压
缩。
1.2.2 Human 编码使用 Human 树来产生编码
要进行 Human 编码,首先要把整个文件读一遍,在读的过程中,统计每个符号(我们把字节的 256 种
值看作是 256 种符号)的出现次数。然后根据符号的出现次数,建立 Human 树,通过 Human 树得
到每个符号的新的编码。对于文件中出现次数较多的符号,它的 Human 编码的位数比较少。对于文件
中出现次数较少的符号,它的 Human 编码的位数比较多。然后把文件中的每个字节替换成他们新的编
码。
建立 Human 树:
把所有符号看成是一个结点,并且该结点的值为它的出现次数。进一步把这些结点看成是只有一个结点的
树。
每次从所有树中找出值最小的两个树,为这两个树建立一个父结点,然后这两个树和它们的父结点组成一
个新的树,这个新的树的值为它的两个子树的值的和。如此往复,直到最后所有的树变成了一棵树。我们
就得到了一棵 Human 树。
通过 Human 树得到 Human 编码:
这棵 Human 树,是一棵二叉树,它的所有叶子结点就是所有的符号,它的中间结点是在产生
Human 树的过程中不断建立的。我们在 Human 树的所有父结点到它的左子结点的路径上标上 0,右
子结点的路径上标上 1。
现在我们从根节点开始,到所有叶子结点的路径,就是一个 0 和 1 的序列。我们用根结点到一个叶子结点
路径上的 0 和 1 的序列,作为这个叶子结点的 Human 编码。
我们来看一个例子。
有一个文件的内容如下
abbbbccccddde
我们统计一下各个符号的出现次数,
a b c d e
1 4 4 3 1
建立 Human 树的过程如图:
剩余22页未读,继续阅读
资源评论
行走的路人GB90
- 粉丝: 12
- 资源: 61
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 基于SSM写的停车场管理系统,加入了车牌识别和数据分析+源码+文档说明
- stream-response.txt
- Python库d和OpenCV来实现眼部闭合检测,主要用于评估用户是否眨眼
- 使用Python库dlib和OpenCV来实现面部特征点的检测和标注
- 强大好用的人体关键点标注工具
- mmexport1713375197200.png
- LP.mlx
- 17期基础网络笔记.one
- bugreport-venus-TKQ1.220829.002-2024-04-18-00-45-35.zip
- bitnami-redmine-4.1.1-2-linux-x64-installer.run(实测可用)
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功