zip是什么格式(微信zip文件怎么做)

众所周知，通过网络上传或下载每一个字节的数据都是要耗费流量的，也就是要花钱的。虽然现有的压缩算法有几十种或几百种，但最流行的可能是zip。虽然gzip压缩算法与zip有相似的名称，但它是一种不同的算法。Gzip算法也被广泛使用，它被HTTP的三个标准压缩规范之一所采用。虽然各种压缩算法适用于不同的场景，但是它们的底层都是基于DEFLATE的。DEFLATE是一种无损数据压缩算法，同时使用LZ77算法和霍夫曼编码。

LZ77

DEFLATE基于LZ77算法——一种用于文本压缩的无损压缩技术。

压缩

LZ77算法通过用已经出现在编码器或解码器中的相应匹配数据信息替换当前数据来实现压缩功能。

此算法不会同时在整个文本中搜索重复的字母。一般会先设置一个固定大小的搜索缓冲区，比如20(在真实场景中，这个缓冲区的大小通常是几十kB)。然后，在对文本中的字母进行逐个编码时，我们会先判断当前字母是否出现在前一个缓冲区的20个字母中。如果可以找到匹配的字母，则记录当前字母和找到的字母之间的偏移量D，从而完成字母编码的第一阶段。接下来，与当前编码字母相邻的下一个字母与缓冲器中与匹配的前一个字母相邻的下一个字母匹配。如果匹配，则继续下一个字母的匹配，直到缓冲器中的20个字母匹配或者相邻字母不匹配为止，匹配过程结束。上述过程完成后，当前位置匹配上的连续字母由缓冲字母的偏移量和连续字母的个数L代替。这样，字母编码的第二阶段就完成了。

让我们用这个例子来看看它是如何工作的:

ERTOORTORR一开始能想到的最简单的办法就是直接用指向O第一次出现的标记替换O的第二次出现，或者用RTO的第一次出现替换RTO的第二次出现。

让我们在下面更详细地描述这个过程。假设我们设置的缓冲区大小是4。把这些4长度的缓冲区想象成一个沿着正文向右滑动的滑动窗口:

1) [....E]RTOORTORR2) [...呃]toortor 3)[..奥尔特。ERTOO奥托·托托-& gt；ERTO(1，1)RTOOR 6)E[RTOOR]TORR->ERTO(1，1)(4，3)RR7)ERTO R-& gt；ERTO(1，1)(4，3)(3，1)R8)；ERTO(1，1)(4，3)(3，1)(1，1)滑动窗口随着编码的迭代逐步向右移动，前四步滑动窗口中的字母没有发现重复。在步骤5，滑动窗口中的字母O已经被复制。然后通过查看字母O右侧的R，发现滑动窗口中匹配字母O右侧的相邻字母不是R，于是停止右侧的匹配，将第二个字母O替换为(1，1)(意思是滑动窗口中匹配字母与当前字母的偏移距离为1，匹配上连续字母的长度为1)。在步骤6中，滑动窗口中的字母R匹配左边的第四个字母。继续检查下一个字母T的匹配情况，然后发现滑动窗口中的r T也匹配。然后继续下一个字母o，在滑动窗口中，匹配的RTO也匹配，就这样，因为下一个字母匹配。在滑动窗口中，匹配的字母与当前字母的偏移距离为4，匹配了三个连续的字母，所以在这里，三个匹配的字母被替换为(4，3)。然后，在步骤7中，字母R匹配偏移距离为3的字母，但是后面的r R不匹配。在步骤8中，发现R在最近匹配上的偏移距离是1。最终的整个文本编码如下:

ERTO(1，1)(4，3)(3，1)(1，1)解压压缩后的文本实际上是由一系列这样的(d，1)标记对和字母组成的，直接从标记对中找不到匹配的字母。在解压缩的过程中，字母保持不变，这个标签对被转换成它所指向的字母。看下面一个解压的例子:

Abc(3，2)(1，1)字母Abc不变，标记对(3，2)表示从当前位置向左移动3个单位，然后取出2个字母，因此转换为ab。现在原文变成了这样的abcab(1，1)，最后一个标记对表示它从当前位置向左移动1个单位，然后取出1个字母，于是转换成b，最后解压缩后的文本是abcab。

哈夫曼编码

LZ77消除文本中的重复字母后，使用霍夫曼编码进行第二次压缩。这种方法用较短的代码代替常用的字母，用较长的代码代替不常用的字母，从而减少了文本的总长度。

让我们使用一个简单的示例文本来看看它是如何工作的。

压缩

在这个例子中，我们希望无损压缩这个文本。通常一个字母占用8个字节，所以这个文本的总长度是200个字节。在这篇文章中，我们发现字母F只出现了一次，而字母E出现了七次。霍夫曼编码利用了这一特性，通过减少高频字母的字节长度来减少整个文本的总长度。

用霍夫曼编码压缩一篇文章，首先要统计每个文本中每个字母的出现频率。上例中的字母频率如下:

频率:E: 7，R: 5，T: 4，U: 3，O: 3，P: 2，F: 1我们需要把文本中的字母作为叶节点建立一棵二叉树，通过这棵二叉树对文本中的每个字母进行编码。从出现频率最低的字母:P和F开始，设它们为底层叶节点，取其频率相加的值为父节点，得到如下二叉树:

(3)/\ P(2) F(1)重复上述步骤，依次使用频率最低的字母:U和O和R和t，最后，频率最高的字母E先不动。

(6) (9) E(7)/\/\ U(3) O(3) R(5) T(4)接下来，以上述四棵二叉树为其子树，创建一棵更大的二叉树，对上述二叉树的根节点频率值进行升序排序，优先使用根节点频率值较小的二叉树作为其新的子树。这里，两组二叉树，U和O，R和T，用于形成如下的二叉树:

(9)/\/\ (6) (3)/\/\ U O P F此时有3棵二叉树，根节点分别是:9、9、7(前9棵是上一步创建的二叉树)。类似地，创建一个新的二叉树，将根节点的两个最低频率值作为子节点，如下所示:

(16)/\ 16)/\(9)E/\/\(6)(3)/\/\ U O P F复制代码现在有一棵根节点值为16的大二叉树和一棵根节点值为9的左叶节点为R和T的二叉树。创建一个新的二叉树作为子节点，如下所示:

(25)/\/\(16)(9)/\/\(9)E R T/\/\(6)(3)/\/U O P F现在我们要做的就是根据这个二叉树对文本进行编码。从下面的节点依次访问每个字母，左分支视为0，右分支视为1。这些0和1根据沿着二叉树访问路径的字母顺序连接。例如，从根节点到字母E需要一个左分支和一个右分支，因此字母E的代码是10。字母U需要经过左支4次，其代码为1111；f需要经过两个左分支和两个右分支，它的代码是1100。可以发现，在这里的例子中，以非常高的频率编码字母E之后的位数少于以较低的频率编码字母F之后的位数。在这样的编码之后，最终的压缩文本如下:

1011000011111101110101010110111011011011011010111100111001111001110011000011000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

解压

如果我们收到这样的压缩文本，我们希望将其解压缩，使其可以理解。我们都知道，未压缩文本中的一个字符占用8位。上面说了霍夫曼编码压缩后一个字符的位数不是固定的8位，所以一段数据(例如:011)代表1个字符、2个字符还是3个字符并不清楚。那么这个压缩后的文本将如何解压呢？

这一步没有奇迹，需要上面代码中构建的二叉树来准确提取数据。有两种方案可以得到用于编码的二叉树。第一种是把它和压缩文本放在一起作为原文的压缩结果，可能会造成压缩文本比原文大；第二种方案是使用预定义的二叉树。知道了英语中每个字母出现的频率，我们就可以根据这个频率来构造上面的二叉树。使用这种预先定义的常用字母频率二叉树压缩部分文本的结果可能比根据文本内容使用字母频率二叉树的结果差，但不再需要将字母频率二叉树保存到压缩文件中。总而言之，这两种方案各有利弊。

虽然本文没有深入分析各种压缩算法的细节和相应的实现，但是经过以上的讲解，你应该对文本是如何压缩成zip和gzip格式有个大概的了解了。希望这篇文章能满足你对压缩算法奥秘的好奇心:)

* 从技术上来说，zip 压缩格式是支持使用其他的压缩算法的，但是 DEFLATE 是其中最常用的一种。