数学之美 系列一 -- 统计语言模型

翔子

在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。

今天，我们介绍一种称作布隆过滤器的数学工具，它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。

假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。（见下图）



现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。

布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万分之一以下。

布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

来自：[url=http://googlechinablog.com/2007/07/bloom-filter.html]http://googlechinablog.com/2007/07/bloom-filter.html

翔子

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

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


这样，如果不知道密码本，即使截获一段信息也看不懂，比如收到一个的消息是 EBKTBP，那么在敌人看来是毫无意义的字，通过密码本解破出来就是 CAESAR 一词，即凯撒的名字。这种编码方法史称凯撒大帝。当然，学过信息论的人都知道，只要多截获一些情报，统计一下字母的频率，就可以解破出这种密码。柯蓝道尔在他的“福尔摩斯探案集”中“跳舞的小人”的故事里已经介绍了这种小技巧。在很长时间里，人们试图找到一些好的编码方法使得解密者无法从密码中统计出明码的统计信息，但是，基本上靠经验。有经验的编码者会把常用的词对应成多个密码， 使得破译者很难统计出任何规律。比如，如果将汉语中的“是”一词对应于唯一一个编码 0543，那么破译者就会发现 0543 出现的特别多。但如果将它对应成十个密码 0543，3737，2947 等等，每次随机的挑一个使用，每个密码出现的次数就不会太多，而且破译者也无从知道这些密码其实对应一个字。这里面虽然包含着朴素的概率论的原理，但是并不科学化。另外，好的密码必须做到不能根据已知的明文和密文的对应推断出新的密文的内容。历史上有很多在这方面设计得不周到的密码的例子。在第二次世界大战中，日本军方的密码设计就很成问题。美军破获了日本很多密码。在中途岛海战前，美军截获的日军密电经常出现 AF 这样一个地名，应该是太平洋的某个岛屿，但是美军无从知道是哪个。于是，美军就逐个发表自己控制的每个岛屿上的假新闻。当美军发出“中途岛供水系统坏了”这条假新闻后，从截获的日军情报中又看到 AF 供水出来问题的电文，美军就断定中途岛就是 AF。事实证明判断正确，美军在那里成功地伏击了日本主力舰队。

事实上，在第二次世界大战中，很多顶尖的科学家包括提出信息论的香农都在为美军情报部门工作，而信息论实际上就是情报学的直接产物。香农提出信息论后，为密码学的发展带来了新气象。根据信息论，密码的最高境界是使得敌人在截获密码后，对我方的所知没有任何增加，用信息论的专业术语讲，就是信息量没有增加。一般来讲，当密码之间分布均匀并且统计独立时，提供的信息最少。均匀分布使得敌人无从统计，而统计独立能保证敌人即使看到一段密码和明码后，不能破译另一段密码。这也是《暗算》里传统的破译员老陈破译的一份密报后，但无法推广的原因，而数学家黄依依预见到了这个结果，因为她知道敌人新的密码系统编出的密文是统计独立的。有了信息论后，密码的设计就有了理论基础，现在通用的公开密钥的方法，包括《暗算》里的“光复一号”密码，就是基于这个理论。

公开密钥的原理其实很简单，我们以给上面的单词 Caesar 加解密来说明它的原理。我们先把它变成一组数，比如它的 Ascii 代码 X=099097101115097114（每三位代表一个字母）做明码。现在我们来设计一个密码系统，对这个明码加密。

1，找两个很大的素数（质数）P 和 Q，越大越好，比如 100 位长的, 然后计算它们的乘积 N=P×Q，M=（P-1）×（Q-1）。

2，找一个和 M 互素的整数 E，也就是说 M 和 E 除了 1 以外没有公约数。

3，找一个整数 D，使得 E×D 除以 M 余 1，即 E×D mod M = 1。

现在，世界上先进的、最常用的密码系统就设计好了，其中 E 是公钥谁都可以用来加密，D 是私钥用于解密，一定要自己保存好。乘积 N 是公开的，即使敌人知道了也没关系。

现在，我们用下面的公式对 X 加密，得到密码 Y。
   


好了，现在没有密钥 D，神仙也无法从 Y 中恢复 X。如果知道 D，根据费尔马小定理，则只要按下面的公式就可以轻而易举地从 Y 中得到 X。
   


这个过程大致可以概况如下：
    [url=http://www.kuqin.com/upimg/allimg/071204/2235033.jpg]

公开密钥的好处有：

1.简单。

2.可靠。公开密钥方法保证产生的密文是统计独立而分布均匀的。也就是说，不论给出多少份明文和对应的密文，也无法根据已知的明文和密文的对应来破译下一份密文。更重要的是 N,E 可以公开给任何人加密用，但是只有掌握密钥 D 的人才可以解密, 即使加密者自己也是无法解密的。这样，即使加密者被抓住叛变了，整套密码系统仍然是安全的。（而凯撒大帝的加密方法有一个知道密码本的人泄密，整个密码系统就公开了。）

3.灵活，可以产生很多的公开密钥E和私钥D的组合给不同的加密者。

最后让我们看看破解这种密码的难度。首先，要声明，世界上没有永远破不了的密码，关键是它能有多长时间的有效期。要破公开密钥的加密方式，至今的研究结果表明最好的办法还是对大字 N 进行因数分解，即通过 N 反过来找到 P 和 Q，这样密码就被破了。而找 P 和 Q 目前只有用计算机把所有的数字试一遍这种笨办法。这实际上是在拼计算机的速度，这也就是为什么 P 和 Q 都需要非常大。一种加密方法只有保证 50 年计算机破不了也就可以满意了。前几年破解的 RSA-158 密码是这样因数分解的

395058745832651445264197678006144819960207764603049364541393760515793556265294
50683609727842468219535093544305870490251995655335710209799226484977949442955603
= 3388495837466721394368393204672181522815830368604993048084925840555281177 ×11658823406671259903148376558383270818131012258146392600439520994131344334162924536139

现在，让我们回到《暗算》中，黄依依第一次找的结果经过一系列计算发现无法归零，也就是说除不尽，我猜她可能试图将一个大数 N 做分解，没成功。第二次计算的结果是归零了，说明她找到的 N=P×Q 的分解方法。当然，这件事能不能用算盘完成，我就不知道了，但我觉得比较夸张。另外我对该电视剧还有一个搞不懂的问题就是里面提到的“光复一号”密码的误差问题。一个密码是不能有误差的，否则就是有的密钥也无法解码了。我想可能是指在构造密码时，P 和 Q 之一没找对，其中一个（甚至两个都）不小心找成了合数，这时密码的保密性就差了很多。如果谁知道电视剧里面讲的“误差”是指什么请告诉我。另外，电视剧里提到冯∙诺依曼，说他是现代密码学的祖宗，我想是弄错了，应该是香农。冯∙诺依曼的贡献在发明计算机和提出博弈论（game theory）。

不管怎么样，我们今天用的所谓最可靠的加密方法的数学原理其实就这么简单，一点也不神秘，无非是找几个大素数做一些乘除和乘方运算就可以了。

来自：[url=http://googlechinablog.com/2007/09/blog-post_13.html]http://googlechinablog.com/2007/09/blog-post_13.html

翔子

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

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

香农第一定理指出：这个编码的长度的最小值是汉字的信息熵，也就是说任何输入方面不可能突破信息熵给定的极限。当然，香农第一定理是针对所有编码的，不但是汉字输入编码的。这里需要指出的是，如果我们将输入法的字库从二级国标扩展到更大的字库 GBK，由于后面不常见的字频率较短，平均编码长度比针对国标的大不了多少。让我们回忆一下汉字的信息熵，
H = -p1 * log p1 - ... - p6700 log p6700。
我们如果对每一个字进行统计，而且不考虑上下文相关性，大致可以估算出它的值在十比特以内，当然这取决于用什么语料库来做估计。如果我们假定输入法只能用 26 个字母输入，那么每个字母可以代表 log26=
4.7 比特的信息，也就是说，输入一个汉字平均需要敲 10/4.7= 2.1 次键。

聪明的读者也许一经发现，如果我们把汉字组成词，再以词为单位统计信息熵，那么，每个汉字的平均信息熵将会减少。这样，平均输入一个字可以少敲零点几次键盘。不考虑词的上下文相关性，以词为单位统计，汉字的信息熵大约是8比特作用，也就是说，以词为单位输入一个汉字平均只需要敲 8/4.7=1.7 次键。这就是现在所有输入法都是基于词输入的内在原因。当然，如果我们再考虑上下文的相关性，对汉语建立一个基于词的统计语言模型，我们可以将每个汉字的信息熵降到 6 比特作用，这时，输入一个汉字只要敲 6/4.7=1.3 次键。如果一种输入方法能做到这一点，那么汉字的输入已经比英文快的多了。

但是，事实上没有一种输入方法接近这个效率。这里面主要有两个原因。首先，要接近信息论给的这个极限，就要对汉字的词组根据其词频进行特殊编码。事实上像王码这类的输入方法就是这么做到，只不过它们第一没有对词组统一编码，第二没有有效的语言模型。这种编码方法理论上讲有效，实际上不实用。原因有两个，第一，很难学；第二，从认知科学的角度上讲，人一心无二用，人们在没有稿子边想边写的情况下不太可能在回忆每个词复杂的编码的同时又不中断思维。我们过去在研究语言识别时做过很多用户测试，发现使用各种复杂编码输入法的人在脱稿打字时的速度只有他在看稿打字时的一半到四分之一。因此，虽然每个字平均敲键次数少，但是打键盘的速度也慢了很多，总的并不快。这也就是为什么基于拼音的简单输入法占统治地位的原因。事实上，汉语全拼的平均长度为 2.98，只要基于拼音的输入法能利用上下文彻底解决一音多字的问题，平均每个汉字输入的敲键次数应该在三次左右，每分钟输入 100 个字完全有可能达到。

另外一个不容易达到信息论极限的输入速度的原因在于，这个理论值是根据一个很多的语言模型计算出来的。在产品中，我们不可能占有用户太多的内存空间，因此各种输入方法提供给用户的是一个压缩的很厉害的语音模型，而有的输入方法为了减小内存占用，根本没有语言模型。拼音输入法的好坏关键在准确而有效的语言模型。

另一方面，由于现有输入方法离信息论给的极限还有很大的差距，汉语输入方法可提升的空间很大，会有越来越好用的输入方法不断涌现。当然，输入速度只是输入法的一项而不是唯一的衡量标准。我们也会努力把谷歌的输入法做的越来越好。大家不妨先试试现在的版本，http://tools.google.com/pinyin/，半年后再看看我们有没有提高。

来自：http://googlechinablog.com/2007/12/blog-post.html

翔子

今年九月二十三日，Google、T-Mobile 和 HTC 宣布了第一款基于开源操作系统 Android 的 3G 手机，其中一个重要的功能是利用全球卫星定位系统实现全球导航。这个功能在其它手机中早已使用，并且早在五六年前就已经有实现这一功能的车载设备出售。其中的关键技术只有两个：第一是利用卫星定位；第二根据用户输入的起终点，在地图上规划最短路线或者最快路线。后者的关键算法是计算机科学图论中的动态规划（Dynamic Programming）的算法。
    [url=http://www.kuqin.com/upimg/allimg/081015/0026273.jpg]

在图论（请见拙著《[url=http://www.kuqin.com/math/20071204/2780.html]图论和网络爬虫》）中，一个抽象的图包括一些节点和连接他们的弧。比如说中国公路网就是一个很好的“图”的例子：每个城市一是个节点，每一条公路是一个弧。图的弧可以有权重，权重对应于地图上的距离或者是行车时间、过路费金额等等。图论中很常见的一个问题是要找一个图中给定两个点之间的最短路径（shortest path）。比如，我们想找到从北京到广州的最短行车路线或者最快行车路线。当然，最直接的笨办法是把所有可能的路线看一遍，然后找到最优的。这种办法只有在节点数是个位数的图中还行得通，当图的节点数（城市数目）有几十个的时候，计算的复杂度就已经让人甚至计算机难以接受了，因为所有可能路径的个数随着节点数的增长而成呈指数增长（或者说几何级数），也就是说每增加一个城市，复杂度要大一倍。显然我们的导航系统中不会用这种笨办法。

所有的导航系统采用的都是动态规划的办法（Dynamic Programming），这里面的规划（programming）一词在数学上的含义是“优化”的意思，不是计算机里面编程的意思。它的原理其实很简单。以上面的问题为例，当我们要找从北京到广州的最短路线时，我们先不妨倒过来想这个问题：假如我们找到了所要的最短路线（称为路线一），如果它经过郑州，那么从北京到郑州的这条子路线（比如是北京-> 保定->石家庄->郑州，称为子路线一），必然也是所有从北京到郑州的路线中最短的。否则的话，我们可以假定还存在从北京到郑州更短的路线（比如北京->济南->徐州->郑州，称为子路线二），那么只要用这第二条子路线代替第一条，我们就可以找到一条从北京到广州的全程更短的路线（称为路线二），这就和我们讲的路线一是北京到广州最短的路线相矛盾。其矛盾的根源在于，我们假设的子路线二或者不存在，或者比子路线一还来得长。

在实际实现算法时，我们又正过来解决这个问题，也就是说，要想找到从北京到广州的最短路线，先要找到从北京到郑州的最短路线。当然，聪明的读者可能已经发现其中的一个“漏洞”，就是我们在还没有找到全程最短路线前，不能肯定它一定经过郑州。不过没有关系，只要我们在图上横切一刀，这一刀要保证将任何从北京到广州的路一截二，如下图。
    [url=http://www.kuqin.com/upimg/allimg/081015/0026274.jpg]

那么从广州到北京的最短路径必须经过这一条线上的某个城市（图中蓝色的菱形）。我们可以先找到从北京出发到这条线上所有城市的最短路径，最后得到的全程最短路线一定包括这些局部最短路线中的一条，这样，我们就可以将一个“寻找全程最短路线”的问题，分解成一个个小的寻找局部最短路线的问题。只要我们将这条横切线从北京向广州推移，直到广州为止，我们的全程最短路线就找到了。这便是动态规划的原理。采用动态规划可以大大降低最短路径的计算复杂度。在我们上面的例子中，每加入一条横截线，线上平均有十个城市，从广州到北京最多经过十五个城市，那么采用动态规划的计算量是 10×10×15，而采用穷举路径的笨办法是 10 的 15 次方，前后差了万亿倍。

那么动态规划和我们的拼音输入法又有什么关系呢？其实我们可以将汉语输入看成一个通信问题，而输入法则是一个将拼音串到汉字串的转换器。每一个拼音可以对应多个汉字，一个拼音串就可以对应图论中的一张图，如下：
    [url=http://www.kuqin.com/upimg/allimg/081015/0026275.jpg]

其中，Y1,Y2,Y3,……,YN 是使用者输入的拼音串，W11,W12,W13 是第一个音 Y1 的候选汉字，W21,W22,W23,W24 是对应于 Y2 的候选汉字，以此类推。从第一个字到最后一个字可以组成很多很多句子，我们的拼音输入法就是要根据上下文找到一个最优的句子。如果我们再将上下文的相关性量化，作为从前一个汉字到后一个汉字的距离，那么，寻找给定拼音条件下最合理句子的问题就变成了一个典型的“最短路径”问题，我们的算法就是动态规划。

上面这两个例子导航系统和拼音输入法看似没什么关系，但是其背后的数学模型却是完全一样的。数学的妙处在于它的每一个工具都具有相当的普遍性，在不同的应用中都可以发挥很大的作用。

我们在下一个系列将详细介绍专门针对拼音输入法的“维特比算法”。

翔子

数学之美 一 统计语言模型
数学之美 二 谈谈中文分词
数学之美 三 隐含马尔可夫模型在语言处理中的应用
数学之美 四 怎样度量信息?
数学之美 五 简单之美：布尔代数和搜索引擎的索引

数学之美 六 图论和网络爬虫 (Web Crawlers)
数学之美 七 信息论在信息处理中的应用
数学之美 八 贾里尼克的故事和现代语言处理
数学之美 九 如何确定网页和查询的相关性
数学之美 十 有限状态机和地址识别

数学之美 十一 Google 阿卡 47 的制造者阿米特.辛格博士
数学之美 十二 余弦定理和新闻的分类
数学之美 十三 信息指纹及其应用
数学之美 十四 谈谈数学模型的重要性
数学之美 十五 繁与简 自然语言处理的几位精英

数学之美 十六 不要把所有的鸡蛋放在一个篮子里 最大熵模型
数学之美 十七 闪光的不一定是金子 谈谈搜索引擎作弊问题(Search Engine Anti-SPAM)
数学之美 十八 矩阵运算和文本处理中的分类问题
数学之美 十九 马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks)

数学之美 二十 自然语言处理的教父 马库斯
数学之美 二十一 布隆过滤器（Bloom Filter）
数学之美 二十二 由电视剧《暗算》所想到的 — 谈谈密码学的数学原理
数学之美 二十三 输入一个汉字需要敲多少个键 — 谈谈香农第一定律
数学之美 二十四 从全球导航到输入法——谈谈动态规划

来源：[url=http://googlechinablog.com/]Google 黑板报
作者：[url=http://www.cs.jhu.edu/~junwu/]吴军