劉炯朗博士文章

我爱秋香 — 劉炯朗

站在效率的观点,我们要采取一套规则和方法,以便尽量压缩要传递的资料。

随着电脑科技、通讯科技的发展,当我们要传递资料时,必须选用适当的规则方法和格式,来代表并呈现这些资料,然后据此将资料传出去。在电脑里,任何资料都可以用一连串的“0”和“1”来代表,但是不同的资料怎样选择不同的“0”和“1”,就是所谓“编码”的问题。

编码有三个重要的技术上的考量,第一是效率,那就是在选码时,以简短为原则,让我们在最短时间内将资料传递过去。第二个是可靠,就是在选码时,即使在传递过程中发生一些错误,也不会影响接收资料的正确性。第三是保密,就是在选码时,即使有第三者窃听到传递码,也无法知道传递码代表的真正资料是什么。

接着,让我们从技术观点,来谈编码的问题。

编码的第一个考量是效率。以英文的26个字母为例,每个英文字母都可以用一连串的“0”和“1”来代表。如果只用4个“0”和“1”是不够的,因为只有16个不同的排列,例如“0000”、“0001”、“0010”、“0011”,等等。所以,纯粹以效率的观点,我们会用一连串的5个“0”和“1”,来代表英文的26个字母。

资料的压缩与还原
有人会问,难道没有进步空间了吗?请听我细细道来。如果我们用5个“0”和“1”来代表一个英文字母,一封有一千个英文字母的信,就得用5千个“0”和“1”。按照统计结果,英文文件中最常出现的字母是“E”、“T”、“A”、“O”、“I”等,最不常出现的是“J”、“X”、“Q”、“Z”等。那么,假如我们用比较少的“0”和“1”代表最常出现的字母,例如一连串三个或者四个“0”和“1”;用比较多的“0”和“1”代表不常出现的字母,例如一连串7个或8个“0”和“1”;那么平均下来,也许我们会赚到了。换句话说,一封有一千个英文字母的信,因为信里“E”、“T”、“A”、“O”、“I”比较多,“J”、“X”、“Q”、“Z”比较少,平均下来可能不必用到5千个“0”和“1”。

其实,按照英文字母出现的频率,用长度不同的连串的“0”和“1”代表26个不同的英文字母的观念,在计算机发明前已经有人想到,就是用在电报里的摩斯码。电报是在19世纪发明的,在摩斯码里,用短和长两个讯号组合起来代表26个不同的英文字母,例如英文字母“E”用“.”代表;“I”用“..”代表;“A”用“.-”代表,“Z”用“--..”代表;“Q”用“--.-”代表等等。

和前面讲的基本观念完全一致,在资料科学里,这个观念可以用哈夫曼树的技术准确地表示呈现出来。在大学里学过资料结构的读者都会记得。讲到这里,相信大家对传递的效率这个观念,已经有了基本的了解,还有没有可以讲的东西呢?当然有,还多得很呢。差不多每一个人都有一个MP3用来听音乐。什么是MP3呢?除了数字、文字的资料外,我们还有声音、图片、动画的资料,这些资料都可以全部用“0”和“1”代表,这些“0”和“1”的资料可以用不同的规则和方式代表,以效率的观点而言,我们要采取一套规则和方法,希望能够尽量压缩这些资料。

为什么这些资料可以压缩呢?让我们用两个简单的例子来说明:第一个例子,在声音里有一小部分的频率,即使我们把这些频率拿掉,我们的耳朵是分辨不出来的,所以为了效率的缘故,当我们传送声音时,我们就把这小部分的频率拿掉。第二个例子,当我们要传送一连串的图片时,我们可能把这些图片一张一张地单独送,但是,例如在电影里,一连两张的图片可能很相似,只有一点点的差别,那么在传送了第一张后,我们只要把第一张和第二张之间的差别传出去,收到的人就可以把第一张和第二张还原了。
      
差不多三十年以前,大家就开始设计一套共同的规则和方法代表多媒体之资料,其中一个重要的考量,就是像前面两个简单的例子所讲的资料的压缩和还原。这些共同的规则和方法,就是大家常常听到的MPEG-1,2,3,4,7,21等等,MPEG就是MovingPictureExpertsGroup,它是一个国际组织,大家一起制定共同的方法和规则。MPEG-1是第一套图像和声音压缩的标准,其中有关声音压缩的那一部分是这个标准的第三层,所以叫做MP3。MP3是最常用的声音压缩的标准,大家按照这个标准来压缩存储、传递、播放音乐,所以就可以互通了。

七言可以变五言
让我们回过头来说说在语言文字里,有没有相似的压缩的观念呢?当然有,杜牧有一首很有名的七言绝句:
清明时节雨纷纷,
路上行人欲断魂,
借问酒家何处有,
牧童遥指杏花村。

有人说这首诗可以被压缩一下:
“清明时节雨纷纷”,只是讲下雨,是不是清明没有关系,所以“清明”两个字可以删掉。“路上行人欲断魂”,行人当然是在路上,难道在家不成?所以“路上”两个字可以删掉。“借问酒家何处有”,明明是问一个问题,“借问”两个字是多余的,也可以删掉。“牧童遥指杏花村”,这个问题的答案是杏花村,谁告诉你这个答案,无关重要,所以“牧童”两个字也可以删掉。

这首诗的压缩版,就变成一首五言绝句:
时节雨纷纷,
行人欲断魂,
酒家何处有,
遥指杏花村。

至于前面讲过,假如一连两张图片,相差不多的话,一个压缩的办法是只传送第一张,然后传送第一张和第二张之间的差别。假如我们有两个招标购买冷气机的公文,第一个公文把招标的条例、规格、数量、时间、地点都讲清楚了,那么第二个公文就可以说“和第一个公文一样,只是购买数量改为300台,交货地点改为高雄,交货日期为5月23日”,那么一切就都很清楚了。

编码的第二个考量是可靠。当我们用一连串的“0”和“1”代表一项讯息时,如果在传递的过程中,“0”变成“1”,或者“1”变成“0”,那么接收的人,不是收到了错误的讯息了吗?尤其是在太空通讯里,因为讯号从遥远的太空传送回来,杂音相当多,错误发生的机率也比较高,所以我们在编码时,要考量怎样面对传递时可能发生的错误。第一个要求是知道错误的发生,那就是能够侦测错误的码;第二个更高的要求是要知道错误发生在哪里,那样我们就可以把错误改过来,也就是能够改正错误的码,正如《左传》里说:“过而能改,善莫大焉。”

其实,设计能够侦测错误和改正错误的码,基本观念是很简单的。假如我们要传递一项讯息,“0”代表赞成,“1”代表反对,若是在传递的过程中,错误发生,“0”变成“1”,或者“1”变成“0”,那就糟糕了。如果我传送“00”代表赞成,“11”代表反对,在传递的过程中,如果错误发生了,我们收到“01”或者“10”,虽然我们无法知道原来要传递的是“00”或者是“11”,但是我们会知道发生了错误,可以要求再传送一次;当然如果我们传送的是“00”,收到的是“11”,那么我们是无法知道原本传送的是“00”,是因为传送的错误而变成“11”,还是原来传的就是“11”,没有传递错误。但是,我们可以可以假设两个错误同时发生的几率是比较低的,所以如果我们收到“00”,我们就相信原来要传递的是“00”,如果我们收到“11”,我们就相信原来要传递的是“11”。这就是侦测错误的最基本观念。

延伸下去,如果我们用“000”代表赞成,“111”代表反对,如果我们收到“000”也好,“001”、“010”、“100”也好,我们都假设原来要传递的讯息是“000”,因为传递的三个“0”里,顶多只有一个出了错,如果我们收到的是“111”或“110”,“101”、“011”我们都假设原来要传送的讯息是“111”,这就是改正错误的最基本观念。

为了可靠性而重复传送一项讯息号,这么简单的观念,可以推广到非常有趣和重要的数学研究,那就是所谓代数编码理论,有兴趣的读者可以去探讨一下。

编码、解码学问大
编码的第三个考量是保密、安全,这就是所谓密码的观念。发讯的人用一个方法把要传递的讯息改头换面、隐藏起来,那就是编码;收讯的人有一个方法能够把隐藏起来的讯息还原,那就是解码。但是窃听的第三者却不知道还原的方法,如果他能够把还原的方法猜出来,那就是破码。按照历史的记载,罗马时代的凯撒大帝就已经想出一套密码。密码的应用,以前大部分限于军事,近五十年来,通讯科技迅速发展,除了军事之外,商业的应用,公家和私人资料的储存都是非常重要的问题。

让我们举几个有关密码的简单的例子:一个编密码的办法是“代替”,例如英文的26个字母,A被D来代替,B被E来代替,E被F来代替,X被A来代替,Y被B来代替,那么收讯的人,只要倒过来代替就可以知道原来的讯息了,这就是凯撒大帝当年用的密码。另外一个编密码的办法是“换位置”,例如你要传递一连串的英文字母,你把第一个和第二个,第三个和第四个等等交换位置,就像《达芬奇密码》这本小说或是这部电影,里面就有好几个例子,提到如何将文字原来的次序打乱,变成密码。另外一个编密码的办法是加入杂音,例如你要传递一连串的英文字母,你在每两个字母之间,随便放入一个完全无关的字母。这些都是最简单、最原始的观念。

不过推而广之,怎样设计不容易被破的码?怎样去破解别人的码?都是很有趣,也是相当深奥的一门学问。我要特别提的是,虽然密码学有上千年的历史,但是在30年以前,有人提出公开编码这个观念,它的最基本的想法是,即使我告诉你怎样编码,你也不容易找出解码的方法。这是可能的吗?有兴趣的读者可以去探讨一下。

让我讲一个在二次大战时,美国军方使用的一个秘密通讯办法,他们找到美国原住民印第安人的一个族群,很少人听得懂他们的语言,假如军方要传递一段用英文写的讯息,例如第一个要用的字母是“a”,在英文里,用“a”开头的词很多,例如“apple”(苹果)、“ant”(蚂蚁)、“air”(空气),负责通讯的印第安人在这些英文字里,随便找一个词,例如说“ant(蚂蚁),他就用他的母语把“蚂蚁”这个词说出来;在收讯的地方,另外一个印第安人听到用母语说出来的蚂蚁,就倒过来把英文“ant”写出来,再抽出其中的“a”字,诸位可以想象得到要破解这个密码是相当不容易的。

最后,我要跟大家讲唐伯虎为秋香卖身为奴的故事,老夫人为了考验唐伯虎的文才,要他在一幅山水画上题一首诗,他题了:
我画蓝江水悠悠,
爱晚亭上枫叶愁。
秋月溶溶照佛寺,
香烟袅袅绕经楼。

这是一首藏头诗,也就是一个密码,每一句的第一个字连起来就是唐伯虎要说的:“我爱秋香”这句话。 ……