文档介绍：... ... 无损数据压缩算法的历史引言有两种主要的压缩算法:有损和无损。有损压缩算法通过移除在保真情形下需要大量的数据去存储的小细节,从而使文件变小。在有损压缩里,因某些必要数据的移除,恢复原文件是不可能的。有损压缩主要用来存储图像和音频文件,同时通过移除数据可以达到一个比较高的压缩率,不过本文不讨论有损压缩。无损压缩,也使文件变小,但对应的解压缩功能可以精确的恢复原文件,不丢失任何数据。无损数据压缩被广泛的应用在计算机领域,从节省你个人电脑的空间,到通过web 发送数据。使用 Secure Shell 交流,查看 PNG 或GIF 图片。无损压缩算法可行的基本原理是,任意一个非随机文件都含有重复数据,这些重复数据可以通过用来确定字符或短语出现概率的统计建模技术来压缩。统计模型可以用来为特定的字符或者短语生成代码,基于它们出现的频率,配置最短的代码给最常用的数据。这些技术包括熵编码(entropy encoding) 、游程编码(run-length encoding) 以及字典压缩。运用这些技术以及其它技术,一个 8-bi t 长度的字符或者字符串可以用很少的 bit 来表示,从而大量的重复数据被移除。历史... ... 直到 20世纪 70年代,数据压缩才在计算机领域开始扮演重要角色,那时互联网变得更加流行, Lempel-Ziv 算法被发明出来,但压缩算法在计算机领域之外有着更悠久的历史。发明于 1838 年的 Morse code ,是最早的数据压缩实例,为英语中最常用的字母比如”e”和”t”分配更短的 Morse code 。之后,随着大型机的兴起, Claude Shannon 和Robert Fano 发明了 Shannon-Fano 编码算法。他们的算法基于符号(symbol) 出现的概率来给符号分配编码(code) 。一个符号出现的概率大小与对应的编码成反比,从而用更短的方式来表示符号。两年后,David Huffman 在MIT 学****信息理论并上了一门 Robert Fano 老师的课, Fano 给班级的同学两个选项,写一篇学期论文或者参加期末考试。Huffman 选择的是写学期论文,题目是寻找二叉编码的最优算法。经过几个月的努力后依然没有任何成果,Huffman 决定放弃所有论文相关的工作,开始学****为参加期末考试做准备。正在那时,灵感爆发, Huffman 找到一个与 Shannon-Fano 编码相类似... ... 但是更有效的编码算法。 Shannon-Fano 编码和 Huffman 编码的主要区别是构建概率树的过程不同,前者是自下而上,得到一个次优结果,而后者是自上而下。早期的Shannon-Fan o编码和Huffma n编码算法实现是使用硬件和硬编码完成的。直到 20世纪 70年代互联网以及在线存储的出现,软件压缩才被实现为 Huffma n 编码依据输入数据动态产生。随后, 1977 年Abraham Lempel 和Jacob Ziv 发表了他们独创性的 LZ77 算法,第一个使用字典来压缩数据的算法。特别的,LZ7 7 使用了一个叫做 slidingwindow 的动态字典。 1978 年,这对搭档发表了同样使用字典的 LZ78 算法。与 LZ77 不同, LZ78 解析输入数据,生成一个静态字典, 不像 LZ77 动态产生。法律问题 LZ77 和LZ78 都快速的流行开来,衍生出多个下图中所示的压缩算法。其中的大多数已经沉寂了,只有那么几个现在被大范围的使用,包括 DEFLATE ,LZMA 以及 LZX 。绝大多数常用的压缩算法都衍生于 LZ77 ,这不是因为 LZ77 技术更好,只是由于 Sperry 在1984 年申请了 LZ78 衍生算法 LZW 的专利,从而发展受到了专利的阻碍, Sperry 开始因专利侵权而起诉软件提供商,服务器管理员,甚至是使用 GIF 格式但没有 License 的终端用户。同时, UNIX 压缩工具使用了一个叫 LZC 的LZW 算法微调整版本,之后由于专利问题而被弃用。其他的 UNIX 开发者也开始放弃使用 LZW 。这导致 UNIX 社区采用基于 DEFLATE 的gzip 和基于 Burrows-Wheeler Transform 的bzip2 算法。长远来说,对于 UNIX 社区这是有好处的,因为 gzip 和bzip2 格式几乎总是比 LZW 有更好的压缩比。围绕 LZW 的专利问题已经结束,因为 LZW 的专利 2003 年就到期了。尽管这样,LZW 算法已经很大程度上被替代掉了,仅仅被使用于 GIF 压缩中。自那以后,也有一些 LZW 的衍生算法,不过都没有流行开来, LZ77 算法仍然是主流。另外一场法律官司发生于 1993