数据流压缩原理和数据压缩Zlib的实现

压缩的本质就是去冗余，去除信息冗余，使用最短的编码保存最完整的数据信息。所以对于不同的场景，压缩采用的算法也因时制宜，比如视频和图片可以采用有损压缩，而文本数据采用无损压缩。压缩率又取决于信息的冗余度，也就是内容中重复的比例。那些均匀分布的随机字符串，压缩率会降到最低，即香农限

deflate是zip文件的默认算法。它更是一种数据流压缩算法。

LZ77压缩算法采用字典的方式进行压缩，是一种简单但是很高效的数据压缩算法。其方式就是把数据中一些可以组织成短语的字符加入字典。维护三个概念： 短语字典、滑动窗口、向前缓冲区

压缩的逆过程，通过解码标记和保持滑动窗口中的符号来更新解压数据。当解码字符被标记:将标记编码成字符拷贝到滑动窗口中，一步一步直到全部翻译完成

在流式传输中，不定长编码数据的解码想要保持唯一性，必须满足唯答码一可以码的条件。而异前缀码就是一种唯一可译码的候选，当然这样会增加编码的长度，却可以简化解码。

huffman编码是一种基于概率分布的贪心策略最优前缀码。huffman编码可以有效的压缩数据，压缩率取决于数据本身的信息冗余度

计算数据中各符号出现的概率，根据概率从小到大，从下往上反向构建构造码树，这样最终得到的编码的平均长度是最短的。同时也是唯一可译的

解读：咐滑在一开始，每一个字符已经按照出现概率的大小排好顺序，在后续的步骤衡举腊中，每一次将概率最低的两棵树合并，然后用合并后的结果再次排序（为了找出最小的两棵树）。在gzip源码中并没有专门去排序，而是使用专门的数据结构（比如最小堆或者红黑树）。

使用优先队列实现huffman树，最后基于Huffman树最终实现文件压缩。

具体步骤：

gzip = gzip 头 + deflate 编码的实际内容 + gzip 尾

zlib = zlib 头 + deflate 编码的实际内容 + zlib 尾

压缩之前：初始化各种输入输出缓冲区；

压缩：我们可以不断往这些缓冲区中填充内容，然后由deflate函数进行压缩或者indeflate函数进行解压

总结：在调用deflate函数之前，应用程序必须保证至少一个动作被执行（avail_in或者avail_out被设置），用提供更多数据或者消耗更多的数据的方式。avail_out在函数调用之前千万不能为零。应用程序可以随时消耗被压缩的输出数据

下面是使用zlib库的压缩和解压缩演示代码：

#include <stdlib.h>

#include <stdio.h>

#include <zlib.h>

int main(int argc, char* argv[])

{

FILE* file

uLong flen

unsigned char* fbuf = NULL

uLong clen

unsigned char* cbuf = NULL

/* 通过命令行参数将srcfile文件的数据压缩后存放到dstfile文件中 */裂圆

if(argc < 3)

{

printf("Usage: zcdemo srcfile dstfile\n")

return -1

}

if((file = fopen(argv[1], "rb")) == NULL)

{

printf("Can\'t open %s!\n", argv[1])

return -1

}

/* 装载源文件数据到缓冲区 */

fseek(file, 0L, SEEK_END)    /* 跳到文件末尾 */

flen = ftell(file)        /* 获取文件长谈液度 */

fseek(file, 0L, SEEK_SET)

if((fbuf = (unsigned char*)malloc(sizeof(unsigned char) * flen)) == NULL)

{

printf("No enough memory!\n")

fclose(file)

return -1

}

fread(fbuf, sizeof(unsigned char), flen, file)

/* 压缩数据 */

clen = compressBound(flen)

if((cbuf = (unsigned char*)malloc(sizeof(unsigned char) 含源物* clen)) == NULL)

{

printf("No enough memory!\n")

fclose(file)

return -1

}

if(compress(cbuf, &clen, fbuf, flen) != Z_OK)

{

printf("Compress %s failed!\n", argv[1])

return -1

}

fclose(file)

if((file = fopen(argv[2], "wb")) == NULL)

{

printf("Can\'t create %s!\n", argv[2])

return -1

}

/* 保存压缩后的数据到目标文件 */

fwrite(&flen, sizeof(uLong), 1, file)    /* 写入源文件长度 */

fwrite(&clen, sizeof(uLong), 1, file)    /* 写入目标数据长度 */

fwrite(cbuf, sizeof(unsigned char), clen, file)

fclose(file)

free(fbuf)

free(cbuf)

return 0

}

    Zip文件格式是通用的文档压缩标准。自1.6版本起，Python中zipfile模块能够直接处理zip文件里的数据，例如需要将对应目录或多个文件打包或压缩成zip格式，或者需要查看一个zip格式的归档文件中部分或者所有文件同时避免讲这些文件展开到磁盘上。使用ZipFile类来 *** 作zip文件。

创建一个ZipFile对象，表示一个zip文件。

     参数file：文件的路径或者类似文件对象

     参数mode：读"r",写入"w",添加"a"

     参数compression: ZIP_STORED(无压缩),ZIP_DEFLATED(压缩，需要zlib支持)

     参数allowZip64:默认情况下报错，将其设为True，ZipFile将用ZIP64扩展进行创建文件。

下面示例演示了读取一个zip文档，将文档里所有文件解压到名为"work"的文野察慎件里。

import zipfile

if __name__ == "__main__":

    zFile = zipfile.ZipFile("F:\\txt.zip","r")

    #ZipFile.namelist():获取ZIP文档内所有文件的名称列表

    for fileM in zFile.namelist():

        zFile.extract(fileM,"F:\\work")

        zFile.close()

read(self,name,pwd=None)获取ZIP文档内文件的二进制数据

下面例子演示了使用read方法获取ZIP文档中mango.txt文件的数据，并写到copy.txt文件中

import zipfile 

if __name__ == "__main__":

    zipFile = zipfile.ZipFile('F:\\test.zip','r')

    data = zipFile.read("mango.txt")

    (lambda f,d:(f.write(d),f.close()))(open("F:\\copy.txt,'w"),data)

    zipFile.close()

write(self, filename, arcname=None, compress_type=None)将指定文件写入ZIP文档中

     参数filename:需要写入文件的路径

     参数arcname:文件写入ZIP文档后保存的文件名

     参数compress_type:压缩方法(ZIP_STORED或ZIP_DEFAULED)

下面离子演示了创建一个zip文档，将test.docx文件写入压缩文档里面。

import zipfile

if __name__ == "__main__":

    zipFile = zipfile.ZipFile("F:\\test.zip","w")

    zipFile.write("F:\\test.docx","ok.docx",zipfile.ZIP_DEFLATED)

    zipFile.close()

getinfo(name)返回一个ZipInfo类的对象。

import zipfile

if __name__ == "__main__":

    zipInfo = zipFile.getinfo(ok.docx)

    print("filename:",zipInfo.filename)

    print("date_time:",zipInfo.date_time)

常用函数

关闭归档文件，你必须在退出程序之前调用close()否则将不会写入关键记录数据。

返回一个ZipInfo对象，其中包含有关归档成员name的信息。针对一个目前并不包含于归档中的名称调用getinfo()将会引发KeyError。

   返回一个列表，其中包含每个归档成员的ZipInfo对象。如果是打开一个现有归档则这些对象的排列顺序与他们对于条目在磁盘上的实际ZIP文件中的顺序一致。

返回按名称排列的归档成员列表。

以二进制文件类对颂敬象的形式访一个归档成员。没改name可以是归档内某个文件的名称也可以是某个ZipInfo对象。如果包含了mode形参，则它必须为"r"(默认值)或"w"。pwd为用于解密已加密Zip文件的密码。

open()也是一个上下文 管理器，因此支持with语句：

with ZipFile('spam.zip') as myzip:

    with myzip.open('eggs.txt') as myfile:

    print(myfile.read())

如果mode为“r”则文件类对象(ZipExtFile)将只读并且提供下列方法：read(),readline(),readlines(),seek(),tell(),__iter__(),__next__()。这些对象可独立于ZipFile进行 *** 作。

如果mode='w'则返回一个可写入的文件句柄，它将支持write()方法。当一个可写入的文件句柄被打开时，尝试读写ZIP文件中的其他文件将会引发ValueError。

当写入一个文件时，如果文件大小不能预先确定但是可能超过2GiB，可传入force_zip64=True以确保标头格式能够支持超大文件。如果文件大小可以预先确定，则在构造ZipInfo对象时应设置file_size,并将其作name形参。

从归档中提取一个成员放入当前工作目录；member必须为成员的完整名称或ZipInfo对象。成员的文件信息会尽可能精确地被提取。path指定一个要提取到的不同目录。member可以是一个文件名或ZipInfo对象。pwd是用于解密文件的密码。返回所创建的经正规化的路径(对应于目录或新文件)。

从归档中提取出所有成员放入当前工作目录。path指定一个要提取到的不同的目录。members为可选项且必须为namelist()所返回列表的一个子集。pwd是用于解密文件的密码。

警告：绝不要未经预先检验就从不可靠的源中提取归档文件。 这样有可能在  path  之外创建文件，例如某些成员具有以 "/" 开始的文件名或带有两个点号 ".." 的文件名。 此模块会尝试防止这种情况。 参见  extract()  的注释。

将归档是目录表打印到sys.stdout.

设置pwd为用于提取已加密文件的默认密码。

返回归档中文件name的字节数据。name是归档中文件的名称，或是一个ZipInfo对象。归档必须以读取或追加方式打开。pwd为用于已加密文件的密码，并且如果指定该参数则它将覆盖通过setpassword()设置的默认密码。 on a ZipFile that uses a compression method 在使用  ZIP_STORED  ,  ZIP_DEFLATED ,  ZIP_BZIP2  或  ZIP_LZMA  以外的压缩方法的 ZipFile 上调用  read()  将引发  NotImplementedError 。 如果相应的压缩模块不可用也会引发错误。

读取归档中的所有文件并检查他们的CRC和文件头。返回第一个已损坏文件的名称，在其他情况下则返回None。

将名为filename的文件写入归档，给予的归档名为arcname(默认情况下将与filename一致，但是不带驱动器盘符并会移除开头的路径分隔符)。compress_type如果给出，它将覆盖作为构造器compression形参对于新条目所给出的值。类似地，compresslevel如果给出也将覆盖构造器。归档必须使用"w","x“或"a"模式打开。

将一个文件写入归档。 内容为  data ，它可以是一个  str  或  bytes  的实例；如果是  str ，则会先使用 UTF-8 进行编码。  zinfo_or_arcname  可以是它在归档中将被给予的名称，或者是  ZipInfo  的实例。 如果它是一个实例，则至少必须给定文件名、日期和时间。 如果它是一个名称，则日期和时间会被设为当前日期和时间。 归档必须以 'w', 'x' 或 'a' 模式打开。

ZIP文件的名称

---