general0100量产工具-()

general0100量产工具

()

最近实现了一个ZIP压缩数据的解压程序认为有必要ZIP详细总结压缩格式。数据压缩是一门涉及通信原理和计算机科学的学科。在通信原理中，它通常被称为信源编码。在计算机科学中，它通常被称为数据压缩，两者本质上没有区别，在数学家眼里都是映射。一方面，在通信过程中，有必要压缩待传输的数据，以减少带宽需求；另一方面，当计算机存储数据时，为了减少磁盘容量需求，也会压缩文件，虽然网络带宽越来越高，压缩不像90年代初那么紧迫，但在许多情况下仍然需要，原因之一是压缩数据容量减少，磁盘访问IO时间也缩短，虽然压缩和解压过程会消耗CPU资源，但是CPU计算资源增长迅速，但磁盘IO但资源变化缓慢，如当前主流SATA如果磁盘仍然是7200转，硬盘仍然是7200转IO压力转化到CPU一般来说，系统运行速度可以提高。压缩作为一种非常典型的技术，会应用到很多很多场合下，比如文件系统、数据库、消息传输、网页传输等等各类场合。压缩作为一种非常典型的技术，将应用于文件系统、数据库、信息传输、网页传输等多种场合。虽然压缩涉及到许多术语和技术，但不用担心，博客试图描述它。此外，本文所涉及的压缩算法非常主流和精致。ZIP压缩过程应该更容易理解其他相关的压缩算法。

压缩可分为无损压缩和有损压缩。有损是指压缩后原始信息无法完全恢复，但压缩率可以很高，主要用于视频、语音等数据的压缩。由于少量信息丢失，人们很难检测到，或者没有必要这么清楚地阅读和听；无损压缩用于文件等必须完全恢复信息的场合，ZIP自然是一种无损压缩压缩。在通信原理中介绍数据压缩时，往往从信息理论的角度引出香农定义的熵概念。这方面的介绍太多了。在这里，从最原始的想法出发，如何设计算法以达到压缩的目的。而ZIP为我们提供了相当好的案例。而ZIP为我们提供了相当好的案例。

虽然我们不讨论信息论中复杂的概念，但我们应该从两位信息论大牛开始。因为他们奠定了今天大部分无损数据压缩的核心，包括ZIP、RAR、GZIP、GIF、PNG等等大多数无损压缩格式。这两头牛的名字分别是Jacob Ziv和Abraham Lempel，1977年，两位以色列人发表了一篇论文《A Universal Algorithm for Sequential Data Compression》，从名称上看，这是一种所谓的通用压缩算法，这意味着这种压缩算法对数据类型没有限制。不过我觉得不用仔细看论文，因为博主是通信专业的。PHD，它看起来也很焦虑，但我们可以看到它的想法仍然很简单，主要是因为它看起来很复杂IEEE有些杂志就是这个特点，需要从数学上证明这种压缩算法有多优秀，比如一个各种状态的随机序列(不需要调查什么是各种状态的随机序列)。在这种压缩算法之后，你是否能接近信息论的极限（即熵的概念）等等，但在理解它的想法之前，我认为除非你想发表论文，否则没有必要深入研究这些东西。这两位大牛提出的算法被称为LZ一年后，两头大牛又提出了一种类似的算法，叫做LZ78.思想相似，ZIP这个算法是基于的LZ77的思想演变过来的，但ZIP对LZ77编码后的结果继续压缩，直到难以压缩。除了LZ77、LZ78.还有很多变种算法，基本都是以LZ开头，如LZW、LZO、LZMA、LZSS、LZR、LZB、LZH、LZC、LZT、LZMW、LZJ、LZFG等等，很多，LZW也比较流行，GIF记得用动画格式。LZW。我也写过解码程序，以后有时间可以再写一篇，但是感觉和LZ77这些类似，写作不必要。我也写过解码程序，以后有时间可以再写一篇，但是感觉和LZ77这些类似，写作不必要。

ZIP作者是一个名字Phil Katz这个人是开源界的悲剧传奇人物。虽然二三十年前，开源这个词并没有现在这么风起云涌，但无论他在哪个时代，总有一些有黑客精神的牛人心中充满了自由。Phil Katz这个人是个牛逼程序员，成名于DOS我个人没有经历过那个时代。Windows98开始接触电脑的人只是从书中得知，当时网速很慢，拨号只用了几十个Kb(比特不是字节)猫，56Kb其实是这种猫的最高速度，在ADSL该技术出现后迅速被淘汰。当时硬盘也是记录文件的，但是软盘是在电脑之间复制文件的。我大一的时候用过这个东西。记得最高容量是1.44MB，这还是200X年的软盘，以前的软盘容量具体多大就不知道了，Phil Katz上网还不到1990年，WWW事实上，它没有出现。当然，没有浏览器。当时为什么要上网？基本上类似于网网络管理部门敲击各种命令，所以你实际上可以聊天，去论坛，不是吗件，你必须慢慢死去，所以压缩在那个时代非常重要。当时，一家商业公司提供了一个名称ARC在那个时代，压缩软件可以让你聊得更快，当然要付费，Phil Katz感觉不舒服，就写了一个PKARC，免费，看名字知道是兼容的ARC所以网友都用PKARC了，ARC公司自然不开心，把哥们告上法庭，说涉及知识产权等等，结果Phil Katz坐牢了。。。。牛人是牛人， 在监狱里冥想，决定超越整个人ARC牛逼算法出来了，牢里适合思考，用了两周就整理出来了，叫PKZIP，不仅免费，这次还开源，直接发布源代码，因为算法不同，不涉及知识产权，所以ZIP流行，但是Phil Katz这个人没有从里面赚到一分钱，还是很穷，由于饮酒过多等诸多原因，2000年死在一家汽车酒店。英雄逝去，精神永存。现在我们用它UE打开ZIP文件，我们可以看到开头的两个字节是PK两个字符的ASCII码。英雄逝去，精神永存。现在我们用它UE打开ZIP文件，我们可以看到开头的两个字节是PK两个字符的ASCII码。

好了，Phil Katz牢里到底想到了什么？压缩数据的算法是什么？我们想一个简单的例子：

生，容易。活，容易。生活，不容易。

如果上述句子没有压缩，如果使用Unicode编码，每个字用两个字节表示。为什么是两个字节？Unicode这是一个国际标准。制定了英文字符、日文字符、韩文字符、中文字符、拉丁字符等常见字符的标准。显然，最多可以用两个字节表示2^16=65536字符，那么65536就够了吗？其实生僻字很多，比如光康熙字典里有几万个汉字，其实是不够的，那么扩展到四个字节吗？也可以，空间变大了，可以包含更多的字符，但一方面，扩展到四个字节必须保证足够吗？另一方面，四个字节是不是太浪费空间，只是为了那些一般情况下不会出现的生僻字？因此，在正常情况下，使用两个字节表示，当出现的单词时，使用四个字节表示。事实上，这反映了信息理论中数据压缩的基本思想。频繁出现的字符表示较短；稀有的可以表示较长（一般不会），从而减少整体长度。除了Unicode，ASCII编码是针对英文字符的编码方案，可以用一个字节。除了这两种编码方案，还有很多区域编码方案，比如GB2312可以编码中文简体字，Big5可编码中文繁体字。如果两个文件都使用编码方案，那就没问题了，但考虑到国际化，尽量使用Unicode这个国际标准。不过这个跟ZIP没关系，纯属背景介绍。

好了，回到我们前面提到的例子，如果用普通的话，总共有17个字符(包括标点符号)。Unicode总共是17*2=34字节。能压缩吗？大家一眼就能看出里面有很多重复的字符，比如里面有很多容易的词(其实很容易加句号三个字)，第一次出现的时候用普通的字符。Unicode，容易第二次出现。它可以用（距离和长度）来表示。距离意味着下一个字符与前面重复的字符分开，长度意味着有几个重复的字符。上面的第二个例子很容易。意思是(5,3)，距离为5个字符，长度为3。解压缩时，解决这个地方时，向前跳5个字符，复制这个位置的连续3个字符，完成解压缩。这其实不是指针的概念吗？没错，和指针很像，但是在数据压缩领域，一般叫字典编码。为什么叫字典？我们去查一个字的时候，总是先去目录找字在哪一页，然后翻到那一页。指针不一样。指针不是内存的地址。为了操作一个内存，我们先得到指针，然后去那个内存。所谓的指针、字典、索引、目录等术语，不同的背景可能有不同的名称，但我们必须理解它们的本质。若使用(5、3)这种表示方法，原本需要用6个字节表示，现在只需记录5、3即可。那5和3怎么记录呢？一种方法自然还是可以用Unicode，所以这相当于节省了两个字节，但有两个问题，第一个问题是如何知道这两个字符是正常的5和3，还是这只是一个特殊的标志？所以前面要加前面添加一个标志来区分下一个标志Unicode代码是指普通字符，还是指距离和长度Unicode，则直接查Unicode代码表，如果是距离和长度，则向前移动一段距离并复制。第二个问题是压缩程度不好不好，所以，感觉压缩不多，如果重复字符更长，更划算，因为距离 长度就够了，但比如这个例子，如果在5和3之前加一个特殊的字节，不就是3个字节，最好不要压缩。咋办呢？能否再次压缩(5，3)这个整数？以下是我们前面提到的一个基本原则:少出现整数多编比特，多出现整数少编比特。那么，3、4、5、6、7、8、9这些距离谁出现得多呢？谁出现的少？谁知道？

压缩之前当然不知道，不过扫描一遍不就知道了？比如后面重复的字符串容易。按照前面的规则，可以说是(7、3)，即与前面重复的字符串距离为7，长度为3。(7，3)指着前面和自己一样的字符串。那为什么不指第一个容易呢？指着第二个容易。”呢？若指第一个，则不是(7、3)，即(12、3)。当然，表示(12、3)也可以减压，但有一个问题，就是12这个值比7大，大了怎么了？我们在生活中会发现一些常见的规律，重复现象往往是局部的。例如，当你和一个人说话时，你经常很快重复一句话，但你不会每五个小时重复一次。这个特征也存在于文件中。到处都是这样的例子。例如，当你编程时，你定义了一个变量int nCount，这个nCount一般来说，你很快就会使用它，不会离得很远。我们前面提到的距离代表你说这句话需要多长时间。这个距离一般不大。在这种情况下，应以最接近当前字符串的字符串为记录依据（即最接近自己的重复字符串）。在这种情况下，所有标记都是短距离的，如3、4、5、6、7，而不是3、5、78、965等，如果大部分是短距离，所以这些短距离可以用较短的比特来表示，较长的距离不是很常见，而是用较长的比特来表示。这样， 整体表示长度会减少。这样， 整体表示长度会降低。好了，我们之前已经得到了(5、3)、(7、3)的重复记录，距离有两种:5、7；长度只有1:3。咋编码？越短越好。

既然比特越短越好，3是0，5是10，7是11，好吗？这样(5，3)，(7，3)只需要表示为100，110，不是很短吗？好像可以，好像很高效。

但解压缩遇到10这两个比特的时候，怎么知道10表示5呢？这种表示方法是一种叫做代码表的映射表。上述例子的代码表如下：

3-->0

5-->10

7-->11

这个代码表也必须传输或记录在压缩文件中，否则压缩无法解决，但在记录代码表后，整体空间会变大，不会发挥压缩的作用吗？如何记录代码表？代码表记录也是一堆数据，也需要编码吗？码表能继续压缩吗？不需要新的码表吗？压缩是一个永无止境的过程吗？作为一名入门级学生，我可能会想到这一点 儿就