《你没听过的逻辑课》书摘──科技时代的压缩逻辑

欢迎大家来到IT世界,在知识的湖畔探索吧!


欢迎大家来到IT世界,在知识的湖畔探索吧!

生活中隐藏许多逻辑，例如蛋糕怎么分？俊男美女怎么挑？数学怎么学？MLB 怎么看？魔术怎么学？乐透彩怎么买？当我们要回答这些问题时，必须跳脱惯性思惟，才能激活成功教程这些花招。中研院士刘炯朗以亲切的语法，引领思考的阶梯，以深入浅出的方式，带领读者逐步激活成功教程各类日常迷思。以下是由《时报出版》授权，摘自该书的部份内容。

从远古时代开始，文字的发明让我们可以储存语言的资料；照相机发明于 1820 年左右，让我们可以储存图像的资料；爱迪生于1877 年发明留声机，让我们可以储存声音的资料；电影发明于1895 年，让我们可以储存动画的资料。有了电脑之后，文字、语言、图像、声音、动画的资料都可以用 0 和 1 来表达，也就可以由电脑来处理，用内存来储存，并且透过网络来传送。当用 0 和 1 以某一个形式来表达资料时，资料压缩就是指能否找到另一个形式，以较少的 0 和1 来表达。资料压缩是一项重要的技术，可以减少储存空间和传送的时间。

资料压缩的技术可以分成两大类：无失真压缩（Lossless Compression）与失真压缩（Lossy Compression）。无失真压缩减少使用 0 和 1 的数目，但原来的资料仍保持完整无缺，原因是原始资料的表达形式不见得是最有效率的，因此可以有改进的空间；而失真压缩减少了更多 0 和 1 的数目，并造成一部份原始资料消失了，如果消失的部份不是那么重要的话，为了让资料量变得更小，倒也是一个值得的代价。

先来看几个资料压缩的例子：从十九世纪电报的发明开始，工程师已经订定了一个规格，用由 5 个 0 和 1 的组合来表示英文里的字母 a、b、c、d……。5 个 0 和 1 可以产生 32 个不同的组合，对 26 个英文字母已足够了，但是为了区分大写和小写，再加上标点符号等，所以在 1960 年代订定了至今大家仍相当熟悉的 ASCII 规格（American Standard Code 和 Information Interchange 的缩写），使用由 7 个 0 和 1 的组合来表示英文字母和标点符号。7 个 0 和 1 有 128 个不同的组合，已足够大小写及标点符号的需求了。

因此，一篇有 1,000 个字母和标点符号的文件就要用 7,000 个 0 和 1 来表达，这些 0 和 1 的资料有没有不失真压缩的可能呢？

答案是可能的，语言学家分析过 26 个字母在英文里使用的频率，e 是最常用的字母，频率是 12%，其次是 t 的 9%，a 是 8%，接下来是 o、i、n；在另一个极端，z 用的最少，0.07%、q 是0.09%、x 是 0.1%，如果我们不硬性地用一连串 7 个 0 和 1 来代表每一个字母，可以用比较少的 0 和 1，例如一连串 5 个或者 6 个 0 和 1 来代表比较常用的字母，用比较多的 0 和1，例如一连串 8 个或者 9 个 0 和 1 来代表比较不常用的字母，那么平均下来可能不必用到 7,000 个 0 和1，就能达到压缩的目的了。

如果我们硬性地用一连串 7 个 0 和1 来代表每一个字母，那么当我们接收到转送过来的 0 和 1 的时候，只要把每 7 个 0 和 1 切开来就对了，如果不同的字母用不同数目的 0 和 1 来代表的时候，应该怎样把传送过来的 0 和 1 正确地切开来呢？还有常用的字母用比较少的 0 和 1，不常用的字母用比较多的 0 和 1 来表达，“常用”和“不常用”、“比较多”和“比较少”这些观念都可以精准地量化，在资讯科学里“霍夫曼树”（Huffman Tree）的方法就同时回答了这两个问题。

在十九世纪，电报通讯技术发明的时候，英文字母是用一连串短的点“•（dot）”和长的划“—（dash）”来代表的，例如 e 用点“• ”来代表，i 用点点“• • ”来代表，a 用点划“• —”来代表，g 用划划点划“—— • —”来代表，也符合了常用的字母用比较短的讯号来代表的观念。

这个例子也指出资料压缩里一个重要的观念，那就是压缩的效率和资料的内容有关，当我们传送一份用英文写的文件的时候，上面讲的压缩方法是相当有效的，但是如果传送的是一份闽南语罗马字拼音的文件，那么 a、b、c、d、e……的使用频率可能和英文不同，上面讲的压缩方法，效率可能不会那么高，甚至可能适得其反，增加了一共要使用 0 和 1 的数目了。

第二个我要讲的例子，使用相似的观念，那就是常用的字和词汇用比较精简的形式来表达，以达到资料压缩的目的。用过微软视窗操作系统的读者，都知道 winzip 是常用的资料压缩的工具，winzip 和其他压缩工具的基本观念是，每一个文件都会有用得比较多的字和词汇，譬如说一份有关股票市场的报告，“买超”、“卖超”、“涨停板”、“跌停板”这些词会重复出现，一份有关能源的报告，“节能”、“减碳”、“替代能源”这些词会重复出现，所以如果对每一份文件，先制作一本字典，这本字典有几千个在这份文件里出现得比较多的字和词，这些字和词有一个相对的数字代号，当字典里的一个词在文件里出现的时候，例如“涨停板”，我们不必把“涨停板”三个字传送出去，而且它在字典中的数字代号，譬如说“168”传送出去就可以了，这也是不失真的资料压缩。

第三个资料压缩的方法叫做“连续长度编码法”（Run-Length Encoding），譬如说我们要传送一连串的 0，可以直接把 0 传送出去，也可以传送 0（3 个 1）（4 个 0）1，不直接传送 111 而传送（3 个 1），不直接传送 0000 而传送（4 个 0），可能是多费了力气增加要传送的 0 和 1，但是如果我们要传 0（15 个1）（32 个 0）（89 个 1），那就比直接传送 0……来得有效率了。当我们存送一张图像的时候，会用 0 来代表白色，1 代表黑色，如果图里有一大片白色的空白或者一大片黑色背景的时候，那就是一长串的 0 和一长串的 1，那么连续长度编码就是有效的资料压缩方法了。

第四个压缩方法叫做“差额编码”（Delta Encoding），例如我们要把班上学生考试的成绩记录下来，可以写 97、93、95、86……，但也可以写 97、－4、＋2、－9，表示第一个学生成绩是97，第二个学生的成绩是第一个学生的成绩－4 等于93，第三个学生的成绩是第二个学生的成绩＋2 等于95，因为学生的成绩彼此之间往往相差不大，差额编码可以有助于资料的压缩。

《你没听过的逻辑课》简介

有时直觉会告诉我们正确的答案，但是数学上的计算才是最可靠的！中研院士刘炯朗以亲切的语法，引领思考的阶梯，以深入浅出的方式，让逻辑和数学不再深奥，生活变得更有趣。

（首图来源：Flickr/A Health BlogCC BY 2.0）

[前往原始页面]微信搜索公众号technews 2013（TechNews科技新报）关注我们。