数学算法——识别文章

Python与开源GIS

数学算法——识别文章

2016-11-09 作者: xuzhiping 浏览: 2723 次

摘要: 我们想在硬盘里储存的数据,其数据量增长的速度远高于储存设备容量快速增长的速度,因此我们需要能够把磁盘数据塞得更密的软件,才能克服硬件的限制。压缩技术的发展,使我们有了意 料之外的应用。 要了解何谓数据压缩,必须先了解熵这个概念,物理学中的熵是系统(例如气体)的...

我们想在硬盘里储存的数据,其数据量增长的速度远高于储存设备容量快速增长的速度,因此我们需要能够把磁盘数据塞得更密的软件,才能克服硬件的限制。压缩技术的发展,使我们有了意 料之外的应用。

要了解何谓数据压缩,必须先了解熵这个概念,物理学中的熵是系统(例如气体)的无序程度的量度。在电子通信中,熵是信息中信息量的度量。举例来说,由1000重复的0所组成的信息,含有的信息量极少,熵值也极低,它可以被压缩为简短的形式:“1000乘以0”。另一方面,由1与0组成的安全随机数列,其熵很高,根本无法压缩,储存这种字符串的唯一方式就是重复每一个字符。

相对熵代表在以一个字符列的最佳压缩方式来压缩另一个字符列时,有多少储存空间被浪费掉了。最适用于英文的莫尔斯电码就是一个例子。英文中极其频繁出现的字母“e”分配到最短的码:一个点;而鲜少出现的字母则被分配到较长的码,例如“q”的码是“-----”。对英文以外的语言来说,莫尔斯码不是非常理想,因为码的长度与字母出现的频率没有相互对应关系。相对熵测量的是需要多少额外的圆点与横线,才能以最适用于英文的码,来传递一篇例如意大利文的文章。

大多数数据压缩程序都是依据1970年代末以色列海法理工学院的两位科学家所提出的算法。计算机科学家伦佩尔及电子工程师齐夫所发明的方法,源于一个文件中常常重复出现相同的字符串。一个字符串首次出现时,会进入一个“字典”,当同一个字符串再度出现时,就会有一个指针指向字典中的合适位置,由于指针所占的空间较序列本身小,因此文章被压缩了。不仅如此,准备一个列出所有字符串的表格并不按照标准字典的编辑规则,而要依照待压缩的文件做自我调整。算法能够 “学习”那些极常见的字符串,然后视情况调整压缩方式,随着文件容量的增大,所需的储存空间就会按照文件的熵值逐渐降低。

计算机在科学上的运用总是让人拥有无尽的想象空间,而压缩算法同样可以应用在节省计算机文件储存空间以外的领域。意大利罗马拉萨皮恩扎大学的两位数学家和一位物理学家一贝内代托、卡糜蒂和洛雷托一决定将伦佩尔一齐夫算法运用在工作中。他们的目标是辨识一些文学作品的作者,素材源自11位意大利作家写出的90篇文章(包括但丁和皮兰德类)。先选出特定作者的文章,文末分别附上两段长度相同的短文:一段来自同一作者,另一段则来自另一个作者。两个文件都放入压缩程序里,例如已经被大众广泛使用的WinZip程序, 接下来科学家检查两者各需多大的储存空间。他们预测这种复合文章的相对熵,可以作为辨认佚名文章作者的指标: 如果两篇文章是同一位作者写的,算法需要的储存空间较小;若附加的短文是来自不同作者,则需要的空间较大。后者的相对熵会较高,因为算法必须考虑两个作者的不同风格与不同词汇要使用较多空间来储存文件。复合文章压缩后的文件愈小,原文与附加文章愈可能是同一位作家的作品。

实验结果简直令人震惊。在将近95%的事例中,压缩程序能正确辨认作品的作者。

当这3位科学家为他们的新发现雀跃不已时,却没有注意到,或至少是忘了在他们的参考文献目录中提到的,他们的方法并不像他们曾想象的那般新奇。事实上,他们并不是第一个想到用数学方法来辨认文学作品作者的人。哈佛语言学教授齐普夫1932年就研究过类似的单字频率问题;而苏格兰人尤尔也在1944年的论文《文学词汇的 统计研究》中阐明,自己如何确认出手稿《遵主圣范》的作者是15世纪住在荷兰的著名神秘主义者肯皮斯。当然还必须一提的有18世纪的《联邦主义者文集》,直到1964年,美国统计学家莫斯特勒及华莱士才确认了该书的作者是汉密尔顿、麦迪逊和杰伊。

由于进展十分顺利,贝内代托、卡廖蒂及洛雷托决定再进行另一项实验。他们分析了不同语言间的相似程度,属于同一语系的两种语言应该有较低的相对熵,因此压缩两篇相同语系文字组合而构成的复合文章,会比压缩两种不同语系文字组成的文章有更高的效率。这几位科学家分析了52种不同的欧洲语言,再度获得了成功。他们利用压缩程序,将每种语言归到正确的语系。举例来说,法文和意大利文的相对熵很低,因此属于相同的语系;另一方面,瑞典文与克罗地亚文的相对熵较高,因此一定是来自不同的语系。Win Zip甚至可以确认马耳他文、巴斯克文及匈牙利文是独立的语言,不属于任何已知的语系。

实验的成功让3位科学家乐观地认为,利用压缩软件测量相对熵,或许也可以运用于其他数据串,如DNA序列或股市的变动。

坐而言不如起而行

前述方法激起了我做测试的念头。我所使用的文字模板是我为瑞士大报《新苏黎世报》撰写的短篇新闻报道,18篇文章中涵盖了以色列发生的种种事件,共有14000多个单词、105000个字符。 删除标题及副标题后,我将文章储存为Ascii文件(一种字符编码),并用WinZip压缩。

当我看了结果后,吓了一大跳,这些我费时整整一个月呕心沥血写出的原文,经过压缩之后,缩小了2/3。于是得到一个无可避免的结论,原文中只有33%是重要信息,而其余2/3只是单纯的熵。换言之,有2/3全是多余的。

我试图自我安慰,说服自己一定是高超的文字排列提供了有意义的信息,而不是单词本身。为了证明这个攸关面子的理论,我依字母顺序排列这14000个单词,然后再压缩一次。瞧!依字母排序 的单词序列可以被压缩掉超过80%,只提供了20%的信息(这当然不令人意外,因为“以色列”或“以色列人”这些字出现大约231次,而“巴勒斯坦人”和它衍生出的相关单词总共出现了195次)。

这表示用有意义的次序来排列单词(只有杰出的新闻记者才能胜任这个工作),会比字典多提供13%左右的信息。虽然自我安慰的效果不算太好,但好歹让我松了一口气。不过随后又受到了重重一击,随机收集的14000个单词只能被压缩60%。与绝妙好文的66%压缩率相较,完全随机收集的单词集合包含的信息比真正的文章还多,这给我留下了深刻印象。

在以下实验中,我用了3篇文字模板:其中两篇是各1000字的长文,分别是我和报纸编辑史蒂芬(Stefan)写的;另外一篇则是我写的50词短文。我把这篇短文接在两篇较长文章的后面,然后再压缩这两篇文章。

结果与意大利科学家的发现相符:当我那篇由462个字母组成的短文加到我的文章中时,WinZip需要159个额外的字母;若是接在史蒂芬的文章中,压缩程序需要再加209字母。因此,这证明短文 不是史蒂芬写的,而是在下的手笔。

关注“开源集思”公众号
获取免费资源

随机推荐


Copyright © from 2014. 开源地理空间基金会中文分会 吉ICP备05002032号

Powered by TorCMS

OSGeo 中国中心 邮件列表

问题讨论 : 要订阅或者退订列表,请点击 订阅

发言 : 请写信给: osgeo-china@lists.osgeo.org