无损数据压缩分析

无损数据压缩分析

在网上看到的，不知道作者，觉得不错，就转了过来。


无损数据压缩是一件奇妙的事情，想一想，一串任意的数据能够根据一定的规则转换成只有原来 1/2 - 1/5 长度的数据，并且能够按照相应的规则还原到原来的样子，听起来真是很酷。
半年前，苦熬过初学 vc 时那段艰难的学习曲线的我，对 MFC、SDK 开始失望和不满，这些虽然不算易学，但和 DHTML 没有实质上的区别，都是调用微软提供的各种各样的函数，不需要你自己去创建一个窗口，多线程编程时，也不需要你自己去分配 CPU 时间。我也做过驱动，同样，有DDK（微软驱动开发包），当然，也有 DDK 的“参考手册”，连一个最简单的数据结构都不需要你自己做，一切都是函数、函数……
微软的高级程序员编写了函数让我们这些搞应用的去调用，我不想在这里贬低搞应用的人，正是这些应用工程师连接起了科学和社会之间的桥梁，将来可以做销售，做管理，用自己逐渐积累起来的智慧和经验在社会上打拼。
但是，在技术上来说，诚实地说，这并不高深，不是吗？第一流的公司如微软、Sybase、Oracle 等总是面向社会大众的，这样才能有巨大的市场。但是他们往往也是站在社会的最顶层的：操作系统、编译器、数据库都值得一代代的专家去不断研究。这些帝国般的企业之所以伟大，恐怕不是“有经验”、“能吃苦”这些中国特色的概念所能涵盖的，艰深的技术体系、现代的管理哲学、强大的市场能力都是缺一不可的吧。我们既然有志于技术，并且正在起步阶段，何必急不可耐地要转去做“管理”，做“青年才俊”，那些所谓的“成功人士”的根底能有几何，这样子浮躁，胸中的规模和格局能有多大？

在我发现vc只是一个用途广泛的编程工具，并不能代表“知识”、“技术”的时候，我有些失落，无所不能的不是我，而是 MFC、SDK、DDK，是微软的工程师，他们做的，正是我想做的，或者说，我也想成为那种层次的人，现在我知道了，他们是专家，但这不会是一个梦，有一天我会做到的，为什么不能说出我的想法呢。
那时公司做的系统里有一个压缩模块，领导找了一个 zlib 库，不让我自己做压缩算法，站在公司的立场上，我很理解，真的很理解，
自己做算法要多久啊。但那时自己心中隐藏的一份倔强驱使我去寻找压缩原理的资料，我完全没有意识到，我即将打开一扇大门，进入一个神奇的“数据结构”的世界。“计算机艺术”的第一线阳光，居然也照到了我这样一个平凡的人的身上。

上面说到“计算机艺术”，或者进一步细化说“计算机编程艺术”，听起来

无损数据压缩分析

很深奥，很高雅，但是在将要进入专业的压缩算法的研究时，我要请大家做的第一件事情是：忘掉自己的年龄、学历，忘掉自己的社会身份，忘掉编程语言，忘掉“面向对象”、“三层架构”等一切术语。把自己当作一个小孩，有一双求知的眼睛，对世界充满不倦的、单纯的好奇，唯一的前提是一个正常的具有人类理性思维能力的大脑。
下面就让我们开始一段神奇的压缩算法之旅吧：


1. 原理部分：
　　有两种形式的重复存在于计算机数据中，zip 就是对这两种重复进行了压缩。
　　一种是短语形式的重复，即三个字节以上的重复，对于这种重复，zip用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩，这很容易理解。
　　一个字节有 0 - 255 共 256 种可能的取值，三个字节有 256 * 256 * 256 共一千六百多万种可能的情况，更长的短语取值的可能情况以指数方式增长，出现重复的概率似乎极低，实则不然，各种类型的数据都有出现重复的倾向，一篇论文中，为数不多的术语倾向于重复出现；一篇小说，人名和地名会重复出现；一张上下渐变的背景图片，水平方向上的像素会重复出现；程序的源文件中，语法关键字会重复出现（我们写程序时，多少次前后copy、paste？），以几十 K 为单位的非压缩格式的数据中，倾向于大量出现短语式的重复。经过上面提到的方式进行压缩后，短语式重复的倾向被完全破坏，所以在压缩的结果上进行第二次短语式压缩一般是没有效果的。
　　第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。其中，某些字节出现次数可能较多，另一些则较少，在统计上有分布不均匀的倾向，这是容易理解的，比如一个 ASCII 文本文件中，某些符号可能很少用到，而字母和数字则使用较多，各字母的使用频率也是不一样的，据说字母 e 的使用概率最高；许多图片呈现深色调或浅色调，深色（或浅色）的像素使用较多（这里顺便提一下：png 图片格式是一种无损压缩，其核心算法就是 zip 算法，它和 zip 格式的文件的主要区别在于：作为一种图片格式，它在文件头处存放了图片的大小、使用的颜
色数等信息）；上面提到的短语式压缩的结果也有这种倾向：重复倾向于出现在离当前压缩位置较近的地方，重复长度倾向于比较短（20字节以内）。这样，就有了压缩的可能：给 …… 此处隐藏：14996字，全部文档内容请下载后查看。喜欢就下载吧 ……