Archive | beauty of mathematics RSS feed for this section

【转】数学之美系列 二十三 :输入一个汉字需要敲多少个键 — 谈谈香农第一定律

今天各种汉字输入法已经很成熟了,随便挑出一种主要的输入法比十几年前最好的输入法都要快、要准。现在抛开具体的输入法,从理论上分析一下,输入汉字到底能有多快。

我们假定常用的汉字在二级国标里面,一共有 6700 个作用的汉字。如果不考虑汉字频率的分布,用键盘上的 26 个字母对汉字编码,两个字母的组合只能对 676 个汉字编码,对 6700 个汉字编码需要用三个字母的组合,即编码长度为三。当然,聪明的读者马上发现了我们可以对常见的字用较短的编码对不常见的字用较长的编码,这样平均起来每个汉字的编码长度可以缩短。我们假定每一个汉字的频率是

它们编码的长度是

那么,平均编码长度是

?香农[......]

阅读全文

Tags: , ,

Comments { 0 }

【转】数学之美系列二十二:由电视剧《暗算》所想到的 — 谈谈密码学的数学原理

前一阵子看了电视剧《暗算》,蛮喜欢它的构思和里面的表演。其中有一个故事提到了密码学,故事本身不错,但是有点故弄玄虚。不过有一点是对的,就是当今的密码学是以数学为基础的。(没有看过暗算的读者可以看一下介绍,http://ent.sina.com.cn/v/2005-10-17/ba866985.shtml
因为我们后面要多次提到这部电视剧。)

密码学的历史大致可以推早到两千年前,相传名将凯撒为了防止敌方截获情报,用密码传送情报。凯撒的做法很简单,就是对二十几个罗马字母建立一张对应表,比如说

cryptography-1

 

这样,如果不知道密码本,即使截获一段信息也看不懂,比如收到一个的消息是 EBKTBP,那么在敌人看来是毫无意义的字,通过密码本解破出来就是 CAESAR 一词,即凯撒的名字。这种编码方法史称凯撒大帝。当然,学过信息论的人都知道,只要多截获一些情报,统计一下字母的频[......]

阅读全文

Tags: ,

Comments { 0 }

【转】数学之美系列二十一:布隆过滤器(Bloom Filter)

在日常生活中,包括在设计计算机软件时,我们经常要判断一个元素是否在一个集合中。比如在字处理软件中,需要检查一个英语单词是否拼写正确(也就是要判断它是否在已知的字典中);在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上;在网络爬虫里,一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中,遇到一个新元素时,将它和集合中的元素直接比较即可。一般来讲,计算机中的集合是用哈希表(hash table)来存储的。它的好处是快速准确,缺点是费存储空间。当集合比较小时,这个问题不显著,但是当集合巨大时,哈希表存储效率低的问题就显现出来了。比如说,一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址,全世[......]

阅读全文

Tags: ,

Comments { 0 }

【转】数学之美系列二十:自然语言处理的教父 马库斯

我们在前面的系列中介绍和提到了一些年轻有为的科学家,迈克尔·柯林斯,艾里克·布莱尔,大卫·雅让斯基,拉纳帕提等等,他们都出自宾夕法尼亚计算机系米奇·马库斯(Mitch Marcus)名下。就像许多武侠小说中描写的,弟子都成了各派的掌门,师傅一定了不得。的确,马库斯虽然作为第一作者发表的论文并不多,但是从很多角度上讲,他可以说是自然语言处理领域的教父。

马库斯教授长期当任宾夕法尼亚大学计算机系主任,直到他在几年前从 AT&T 找到皮耶尔替代他为止。作为一个管理者,马库斯显示出在自然处理和计算机科学方面的卓识的远见。在指导博士生时,马库斯发现语料库在自然语言处理中的重要性。马库斯呕心沥血,花了十几年工夫建立了一系列标准的语料库,提供给全世界的学者使用。这套被称为 LDC 的语料库,是当今全世界自然语言处理的所有学者都使用的工具。我们在以前的系列中讲到,当今的自然语言处理几乎都是使[......]

阅读全文

Tags: ,

Comments { 0 }

【转】数学之美系列十九:马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks)

我们在前面的系列中多次提到马尔可夫链 (Markov Chain),它描述了一种状态序列,其每个状态值取决于前面有限个状态。这种模型,对很多实际问题来讲是一种很粗略的简化。在现实生活中,很多事物相互的关系并不能用一条链来串起来。它们之间的关系可能是交叉的、错综复杂的。比如在下图中可以看到,心血管疾病和它的成因之间的关系是错综复杂的。显然无法用一个链来表示。

bayesian-networks

我们可以把上述的有向图看成一个网络,它就是贝叶斯网络。其中每个圆圈表示一个状态。状态之间的连线表示它们的因果关系。比如从心血管疾病出发到吸烟的弧线表示心血管疾病可能和吸烟有关。当然,这些关系可以有一个量化的可信度 (belief),用一个概率描述。我们可以通过这样一张网络估计出一个人的心血管疾病的可能性。在网络中每个节点概率的计算,可以用贝叶斯公式来进行,贝叶斯网络因此而得名。由于网络的每个弧有一个可信度,贝叶斯网络也被称[......]

阅读全文

Tags: , ,

Comments { 0 }