陈凯
某一天，意大利艺术家Nazarino Crea脑中忽然灵光一闪，按照现如今以瘦为美的标准，他用画笔给名画里的胖美人们来了一次速效减肥，这个举动引来一片喧哗。本期要讲的，同样也是为名画瘦身，不过，瘦下来的是文件容量，而不是图片里的身材和脸型——无损压缩，具体来说，是以字典法编码为基础的无损压缩，为充分揭示其原理，下面实验中使用的并不是压缩软件，而是充满智慧的头脑。
首先，找一幅尺寸小一些的《蒙娜丽莎》图，将其保存为单色位图（如图1），用图像编辑软件（如XnView）将其转换为XPM格式的图像文件，如果用写字板打开这个图像文件，就可以很明显看出编码文件中的二维点阵（如图2）。
接着，观察并记录这个图像文件的大小，着手对该文件进行无损压缩。所谓的字典法，通俗来说，就是将长的符号串，映射成某个短的符号串。
在《蒙娜丽莎》单色位图中，反引号“`”代表黑色，小数点“.”代表白色，设计字典的方式有很多。例如，把两个反引号变成一个“！”，把两个小数点变成一个“@”，之所以选择“！”和“@”符号，是因为原文件中并没有出现过这两个符号，这样才不会在之后的解压缩过程中产生混淆。
为了减少人工压缩器的劳动量，可以借助写字板中的“全部替换”功能批量替换字符，替换后就可以看到严重变形的二维点阵。文件大小变成原来的一半多一些，压缩效果显著。如果有时间的话，还可以设定更多的映射规则。由于可以直接看到压缩过程，所以实验过程本身就很具有观赏性（如图3）。由于是用“人工压缩器”压缩的，所以还需要将字典的映射规则也写到图像文件中去，以便解压缩时参考，这当然会额外增加一些文件容量。
然而，这个被人工压缩的文件是无法用图像浏览器直接打开观看的，必须要用“人工解压器”将文件解压缩，才能正常浏览。方法也很简单，将先前的替换过程反过来就可以了。如果解压缩后，图像浏览器能正常打开图像文件，并且图像的模样与原来一模一样，就证明无损压缩和解压缩都获得了成功。
然而，真正在对数据进行压缩时，遇到的问题远没有上面所说的那么简单，假设某个文件完全由“0”和“1”两个符号构成，若规定在压缩时不能引入其他符号，那怎么对这个文件进行压缩呢？考虑到实际上计算机中存储的都是二进制文件，这个问题就显得更有意义。显然，不能简单地在压缩时将“00”替换成“0”，在解压缩时将“0”换回“00”，因为如果遇见“000”这样的符号串，经过这番折腾后，字符串就变成了“0000”，这样的话，文件就无法恢复到原来的样子了。
仍然以《蒙娜丽莎》为例子，因为下面的实验完全要靠人工实现，为了简便起见，这里只抽出《蒙娜丽莎》图像文件点阵中的某一行来说明问题：“`````````````````................``````..```.....````````````````````````````............................”。
这个符号串中只有两个符号，反引号和小数点符号。为了压缩数据，可以将符号按同等数量编成小组，例如，每四个符号一组，于是就得到了以下五组不同的符号串：
“````”“`...”“ ....”“.```”“```.”。
接着，就可以给这五组符号串编号，不过因为只能使用反引号和小数点符号，所以编出的号码也是只能由这两个符号构成：“````→ ```”“`... → ``.”“.... → `.`”
“.``` → `..”“```. → .``”。
可以看出，之所以能够将四个符号压缩成三个符号，是因为在实际数据中，反引号和小数点符号的排列组合所出现的种类的数量，要远远少于理论上全部排列组合种类的数量。
按以上规则替换后，原始的符号串就变成了“``````````````.`.``.``.``...```..`.``..````````````````````.`.``.``.``.``.``.`.”。
长度明显缩短了，只占原来的四分之三，对这串数据作解压缩，只需要反过来使用规则，把三个符号还原成四个符号就可以了。
然而，还可以将符号串变得更短，这时候需要一种特殊的字典，因为“````”“`...”“....”“.```”“```.”这四组符号串，出现的频率是不同的，所以对出现频率高的符号串，可以映射成短一些的符号串，而对于出现频率低的符号串，则映射成长一些的符号串。例如，“`````”“.... → .`”“`... → ..`”“.``` →...`”“```. → ....”。
替换之后，初始的符号串就变成了“````..`.`.`.`...`.......`.`...```````..`.`.`.`.`.`.`.”。
符号串又显著缩短了，大概只有原来的一半长，人们可能会怀疑，这样的符号串能否恢复成原来的样子呢？实际上，字典的设计并不是随心所欲的，试一下就知道了，如果从左往右按顺序匹配最短的符号串，恢复数据就不会有任何问题，这种编码的方法实际上正是哈夫曼编码，有兴趣的朋友也可以自己查阅相关资料，设定出自己的映射规则。
然而，作为设定规则的字典，本身就占用了存储空间，于是，令人惊叹的LZ编码方案横空出世，该方案能够用等待被压缩的数据本身作为字典，此中机巧，实在让人佩服得五体投地，限于篇幅，这里就不专门展开论述了。
