第3课：精选最优方案—搜索模式            
■ 讲师：湖北 黄迎
在第2课中，我们挑拣出所有重复的单词并把它们放入字典中。对我们而言，这是最明显的编写词典的方法。但是，压缩程序实现起来却十分困难：它没有任何单个单词的概念。为了尽可能地减少文件大小，压缩程序将会非常谨慎地选择搜索模式。
如果我们利用这种观点来处理该短语，那么将得到一个截然不同的词典。
如果压缩程序扫描肯尼迪的演说词，它遇到的第一个冗余只有两个字母长。在“ask not what your,”中，有一种重复模式，即字母“t”后面总是跟一空格—在“not”和“what”中。如果压缩程序将其写入词典，它将在每个出现“t”和空格的位置写一个“1”。但是，本短语中，这个模式并不值得写入字典，因为重复次数不多，所以最终程序将会改写它。
程序遇到的第二种模式是出现在“your”和“county”中的“ou”。如果是一个长文档，那么将该模式写到字典中可以节约很多空间——“ou”在英语中是一个相当普遍的组合。但是当压缩程序处理本句子时，它会立刻发现一个更好的选择：不仅“ou”重复，而且整个单词“your”和“country”都重复，并且这两个单词一起以“your country”的形式重复。既然这样，压缩程序就把字典条目“ou”改写为“your country”。
短语“can do for”也是重复的，一次后面跟着“your”，另一次后面跟着“you”，这样就得到重复模式“can do for”。我们可以用一个编号值来代替15个字符（包括空格），而“your country”仅仅是用一个编号值代替13个字符（包括空格），因此程序将把“your country”条目改写为“r country”，然后写入一个单独的条目“can do for you”。程序用这种方法进行处理，挑拣出所有重复的信息位，然后计算应该把哪种模式写入词典。改写词典的能力是基于词典的LZ自适应式算法的“适应”部分。
压缩软件真正使用的方法是相当复杂的，不论你使用什么特别的方法，这种深度搜索系统都比你依靠挑选单词来压缩文件更为有效。使用上述挑选的模式，添加“_”代替空格，即可得到这个更大的词典：
1. ask__
2. what__
3. you
4. r__country
5. __can__do__for__you
于是，我们得到了更短的句子：
"1not__2345__--__12354"
句子现在占18个存储单元，我们的词典占41个单元。因此我们已经将整个文件大小从79单元压缩到59单元！这仅仅是一种压缩短语的方法，并不一定是最有效的方法。

Just Do It
发现规律，利用规律，这可是考验你智商的好时机！看到这里，你可以试验一些专门测试智商的题目（如http://tech.sina.com.cn/other/2004-04-16/1313350012.shtml），先锻炼一下你的观察能力，然后-继续研究这段短语，能不能找到一种压缩率更高的方法？如果有更好的答案，请寄给Cornel！

 第4课:压缩类型的两大类—有损和无损 
■ 讲师：福建 柳坚
我们在前面几课中一直列举的那个总统就职演说的例子，由于它允许你准确地重建原始文件，所以把它叫做无损压缩。所有无损压缩都基于一种思想，就是将一个文件分割成一个更小的、便于传输和存储的形式，然后在另一端把它们组装在一起，以便使用。无损压缩这种方法广泛用于文本数据、软件程序和特殊应用场合的图像数据(如指纹图像、医学图像等)的压缩，因为此类数据如果压缩后一旦无法还原将造成文件无法使用的情况。

无损数据压缩按照采用模型的不同，还可分为统计模型与字典模型这两类技术。统计模型所采用的方式是先将要被编码的数据整体所采用的符号做个统计，然后将重复性大的符号重新以短的码来编排，而重复性愈小的符号则以愈长的码来编排。应用于UNIX和早期DOS中的Huffman算法就是一种统计型技术。字典模型的编码原理则是以较长的字符串或经常出现的字母组合构成字典中的数据项，并用相应较短的数字或符号做为代码表示。当从源数据流中读入的数据能与字典中的数据项相匹配，则输出其对应的代码。字典型技术是由两个以色列人最先提出的，最初为LZ77、LZ78算法，后来经过改良为LZSS和LZW，LZSS后来被ARJ等格式广泛采用，而LZW在ZIP、GIF，UNIX下的compress程序中得到应用。

与无损压缩相比，有损压缩则是简单地去除“不必要”的信息位，裁剪文件使其更小，这种类型的压缩多用于减少位图图形文件的大小。位图文件一般比较大，这一方法利用了人类视觉中对图像中的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息。它虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响较小，却换来了大得多的压缩比，因此还是被广泛应用于语音、图像和视频数据的压缩。
实例：Windows的“蓝天白云”是如何压缩的
为了弄明白有损压缩如何工作，我们先看看你的电脑如何压缩一张扫描照片（见图2）。首先，当图片的大部分看上去一样时——例如，整个天空是蓝色的——大多数单个像素只是稍许不同。为了在不降低清晰度的情况下压缩图片大小，你必须改变某些像素的颜色值。如果图片有大片蓝色天空，程序将拾取一种能用于每个像素的蓝色。然后，改写文件，使每个天空像素的值引用该信息。其次，压缩图片时还可以将其中对人类的视觉不敏感（比如去掉人眼感觉最暗的低频带光）的信息剔除掉。如果压缩方案工作正常，你将看不出作出的改变，但文件体积显著减小。

第5课:文件能被压成多小取决于哪些因素？
   ■ 讲师：旺旺
为什么有的文件经过压缩后，压缩文件的大小并没有多大的变化呢？怎样预知某个文件在经过压缩软件压缩后的大小呢？实际上，文件压缩比率取决于很多因素，包括文件类型、文件大小和压缩方案。
世界上的大多数语言中，某些字母和单词经常一起出现在相同的模式中。由于这种冗余的高出现率，所以能很好地压缩文本文件。对一个相当大的文本文件来说，50%甚至更高的压缩比颇为常见。大多数编程语言也是极其冗余的，因为它们使用一个相对小的命令集，这些命令经常以一套模式一起出现。对于那些包含很多独特信息的文件，比如图形或者MP3文件，该系统无法将它们压缩很多，因为它们没有重复很多模式。

Just Do It
用“记事本”建立一个文本文件，用复制粘贴的方法输入100个“压缩”，保存文件后用WinRAR压缩该文件，看一下压缩文件占用的空间大小，应该是4096字节。同样方法，如果是包含1000个“压缩”的文件，压缩后占用空间仍然是4096字节。为什么都是4096字节？如果是包含5000个“压缩”的文件，压缩后占用的空间还是4096字节吗？不试验，你能想出答案吗？答案在本课末尾揭晓。

如果一个文件有很多重复模式，压缩比率通常会随着文件大小的增加而增大。通过前面几课中的实例，你就可以明白这一点——如果我们处理更多的肯尼迪的演讲，就能更频繁地引用字典中的模式，从而得到更多文件空间。在更长的工作中可能出现更普遍的模式，它允许我们创建更有效的词典。这种有效性也依赖于压缩程序所用的特定算法，有关常用软件采用的压缩算法，大家可以参考附表。一些程序特别适合于在某种文件类型中挑拣模式，从而更简便地压缩。另一些程序有字典嵌套，这可能对大文件的压缩更有效。虽然该类型的所有压缩程序均基于相同的基本思想，但是实际执行的方式却有很大差异，程序员总是试图建立一种更好的系统。
算法讲解：
1.f：每种压缩软件使用的独有的词典和文件预加工过程，这部分不同软件各不相同。
2.LZ77：前面我们已经提到过该算法了，LZ77、LZ78这两个经典算法是当今几乎所有流行压缩软件的算法核心。
3.LZW：LZW由LZ77算法演化而来，该压缩技术比其他大多数压缩技术都复杂，压缩效率也较高。
4.Huff编码压缩：这也是一种常用的压缩方法，是1952年为文本文件建立的。其基本原理是将频繁使用的数据用较短的代码代替，很少使用的数据用较长的代码代替，每个数据的代码各不相同。产生霍夫曼编码需要对原始数据扫描两遍，第一遍扫描要统计每个值出现的频率，第二遍是建立霍夫曼树并进行编码，因此数据压缩和还原速度都较慢，但简单有效。上面介绍的大多数压缩软件都用到了这种技术。
实例：如何在WinRAR中获得最高的压缩比？
WinRAR是大家经常使用的压缩软件，下面的技巧可以让WinRAR在压缩文件时获得最大的压缩比率。不过值得一提的是，在文件相同的情况下，要提高压缩比，那么往往在文件压缩速度上会慢不少，到底是要压缩比还是要压缩速度，大家需要权衡一下。
1.使用“最好”压缩方式：在WinRAR中运行“选项→设置→压缩选项→创建默认压缩配置”打开“设置默认压缩选项”窗口，在“常规”选项卡的“压缩方式”栏中选择“最好”。
2.对压缩大量小文件或同一类型文件：比如，如果你要压缩大量的图片文件、DOC文件，那么可以在“存档选项”栏中勾选“创建固实压缩文件”（见图3)。