Java知识分享网 - 轻松学习从此开始!    

Java知识分享网

Java1234官方群25:java1234官方群17
Java1234官方群25:838462530
        
SpringBoot+SpringSecurity+Vue+ElementPlus权限系统实战课程 震撼发布        

最新Java全栈就业实战课程(免费)

springcloud分布式电商秒杀实战课程

IDEA永久激活

66套java实战课程无套路领取

锋哥开始收Java学员啦!

锋哥开始收Java学员啦!
当前位置: 主页 > Java文档 > Java基础相关 >

LZ77压缩算法详解 PDF 下载


分享到:
时间:2020-11-29 15:45来源:http://www.java1234.com 作者:小锋  侵权举报
LZ77压缩算法详解 PDF 下载
失效链接处理
LZ77压缩算法详解 PDF 下载

本站整理下载:
 
相关截图:


主要内容:

gzip 、zlib以及图形格式png,使用的压缩算法都是deflate算法。从gzip的源码中,我们了解到了defalte算法的原理和实现。我阅读的gzip版本为 gzip-1.2.4。下面我们将要对deflate算法做一个分析和说明。首先简单介绍一下基本原理,然后详细的介绍实现。
 
1 gzip 所使用压缩算法的基本原理
 
gzip 对于要压缩的文件,首先使用LZ77算法的一个变种进行压缩,对得到的结果再使用Huffman编码的方法(实际上gzip根据情况,选择使用静态Huffman编码或者动态Huffman编码,详细内容在实现中说明)进行压缩。所以明白了LZ77算法和Huffman编码的压缩原理,也就明白了gzip的压缩原理。我们来对LZ77算法和Huffman编码做一个简单介绍。
 
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个字节的话,那么用“(之间的距离,匹配长度)对”进行替换的话,不但没有压缩,反而会增大,所以需要一个最小匹配长度。
 
压缩:
从文件的开始到文件结束,一个字节一个字节的向后进行处理。用当前处理字节开始的串,和滑动窗口中的每个串进行匹配,寻找最长的匹配串。如果当前处理字节开始的串在窗口中有匹配串,就先输出一个标志位,表明下面是一个(之间的距离,匹配长度) 对,然后输出(之间的距离,匹配长度) 对,然后从刚才处理完的串之后的下一个字节,继续处理。如果当前处理字节开始的串在窗口中没有匹配串,就先输出一个标志位,表明下面是一个没有改动的字节,然后不做改动的输出当前处理字节,然后继续处理当前处理字节的下一个字节。
 
解压缩:
从文件开始到文件结束,每次先读一位标志位,通过这个标志位来判断下面是一个(之间的距离,匹配长度) 对,还是一个没有改动的字节。如果是一个(之间的距离,匹配长度)对,就读出固定位数的(之间的距离,匹配长度)对,然后根据对中的信息,将匹配串输出到当前位置。如果是一个没有改动的字节,就读出一个字节,然后输出这个字节。
 

------分隔线----------------------------

锋哥公众号


锋哥微信


关注公众号
【Java资料站】
回复 666
获取 
66套java
从菜鸡到大神
项目实战课程

锋哥推荐