编写 iPhone Friendly 的 Web 应用程序 (Part 2 - Viewport)

Posted: 26 Dec 2007 03:48 AM CST

在了解到iPhone的一些常见布局法后，我们就可以开始着手编写一个真正能在iPhone上跑的页面了。小声说一句，之前我说要布局讨论完了，要进入交互逻辑开发，后来细心一想发现不行，有些东西不讲的话将会对布局带来问题，绕过去的话并不怎么优雅，因此继续讲布局。

首先要说的就是viewport，也就是可视区域。对于桌面浏览器，我们都很清楚viewport是什么，就是出去了所有工具栏、状态栏、滚动条等等之后用于看网页的区域，这是真正有效的区域。（无论你屏幕多大，如果你装足够多的toolbar，你的viewport最终也会消失掉。）在桌面浏览器中，viewport的大小是与浏览器窗口大小直接相关的，窗口大了viewport自然就大，同时随着viewport的改变，页面布局可能也跟着变。例如 width: 100%的页面宽度就总是和viewport宽度一致。

然而iPhone的Safari不是这样理解viewport的，它基于viewport呈现页面，然后用户缩放页面后viewport保持不变，仅仅是页面内容按比例缩放了。举个例子，在不设置viewport的情况下，默认viewport为宽度980（单位是像素），这时候页面的呈现出来的布局和在桌面短viewport宽度为980时呈现的结果一致，然而因为iPhone屏幕宽度为320，因此按比例缩小了。因此，一张宽度为320的图片，在默认viewport下会这样显示：

可以看到，图片按比例缩小了，这对于传统Web页面直接在iPhone上面显示来说是很好的事情，因为如果传统Web页面在980宽度的桌面浏览器viewport中显示正常的话，iPhone上显示也绝对正常。然而这对于Web应用程序来说则不是好事，因为我们需要按照980宽度来设计将来会以320宽度显示的页面，一个应该显示为320*80的元素，必须设计为980*245，这多麻烦！

因此我们需要改变viewport，让它变成这样：

实际上应该怎么做呢？我们有几个选择，因此先让我们看看到底我们能够设置哪些属性吧。我们可以操作的属性有4个：

• width - viewport的宽度
• height - viewport的高度
• initial-scale - 初始的缩放比例
• minimum-scale - 允许用户缩放到的最小比例
• maximum-scale - 允许用户缩放到的最大比例
• user-scalable - 用户是否可以手动缩放

这6个属性，我们可以设置其中的一个或者多个，iPhone会根据你设置的属性自动推算其他属性值，而非直接采用默认值。这点很重要，在完全不设置的时候有默认viewport，在你设置一个属性后其它值是自动推算出来的，不再是默认的。

如果你把initial-scale=1，那么width和height在竖屏时自动为320*356（不是320*480因为地址栏等都占据空间），横屏时自动为480*208。

类似地，如果你仅仅设置了width，就会自动推算出initial-scale以及height。例如你设置了width=320，竖屏时initial-scale就是1，横屏时则变成1.5了。

那么到底这些设置如何让Safari知道？其实很简单，就一个meta，形如：

<meta id="viewport" name="viewport" content="width=320; initial-scale=1.0; maximum-scale=1.0; user-scalable=0;"/>

在设置了initial-scale=1之后，我们终于可以以1:1的比例进行页面设计了。下一步我们就可以正式进入页面布局的细节设计了，如果你想继续关注iPhone开发话题的话，欢迎订阅：

• Cat in Chinese (feed)
• Cat in dotNET (feed)

--
由 钢盅郭子 于 12/27/2007 09:13:00 上午 在 №0千年老妖猴 上发表

编写 iPhone Friendly 的 Web 应用程序 (Part 2 - Viewport)

Posted: 26 Dec 2007 03:48 AM CST

在了解到iPhone的一些常见布局法后，我们就可以开始着手编写一个真正能在iPhone上跑的页面了。小声说一句，之前我说要布局讨论完了，要进入交互逻辑开发，后来细心一想发现不行，有些东西不讲的话将会对布局带来问题，绕过去的话并不怎么优雅，因此继续讲布局。

首先要说的就是viewport，也就是可视区域。对于桌面浏览器，我们都很清楚viewport是什么，就是出去了所有工具栏、状态栏、滚动条等等之后用于看网页的区域，这是真正有效的区域。（无论你屏幕多大，如果你装足够多的toolbar，你的viewport最终也会消失掉。）在桌面浏览器中，viewport的大小是与浏览器窗口大小直接相关的，窗口大了viewport自然就大，同时随着viewport的改变，页面布局可能也跟着变。例如 width: 100%的页面宽度就总是和viewport宽度一致。

然而iPhone的Safari不是这样理解viewport的，它基于viewport呈现页面，然后用户缩放页面后viewport保持不变，仅仅是页面内容按比例缩放了。举个例子，在不设置viewport的情况下，默认viewport为宽度980（单位是像素），这时候页面的呈现出来的布局和在桌面短viewport宽度为980时呈现的结果一致，然而因为iPhone屏幕宽度为320，因此按比例缩小了。因此，一张宽度为320的图片，在默认viewport下会这样显示：

可以看到，图片按比例缩小了，这对于传统Web页面直接在iPhone上面显示来说是很好的事情，因为如果传统Web页面在980宽度的桌面浏览器viewport中显示正常的话，iPhone上显示也绝对正常。然而这对于Web应用程序来说则不是好事，因为我们需要按照980宽度来设计将来会以320宽度显示的页面，一个应该显示为320*80的元素，必须设计为980*245，这多麻烦！

因此我们需要改变viewport，让它变成这样：

实际上应该怎么做呢？我们有几个选择，因此先让我们看看到底我们能够设置哪些属性吧。我们可以操作的属性有4个：

• width - viewport的宽度
• height - viewport的高度
• initial-scale - 初始的缩放比例
• minimum-scale - 允许用户缩放到的最小比例
• maximum-scale - 允许用户缩放到的最大比例
• user-scalable - 用户是否可以手动缩放

这6个属性，我们可以设置其中的一个或者多个，iPhone会根据你设置的属性自动推算其他属性值，而非直接采用默认值。这点很重要，在完全不设置的时候有默认viewport，在你设置一个属性后其它值是自动推算出来的，不再是默认的。

如果你把initial-scale=1，那么width和height在竖屏时自动为320*356（不是320*480因为地址栏等都占据空间），横屏时自动为480*208。

类似地，如果你仅仅设置了width，就会自动推算出initial-scale以及height。例如你设置了width=320，竖屏时initial-scale就是1，横屏时则变成1.5了。

那么到底这些设置如何让Safari知道？其实很简单，就一个meta，形如：

<meta id="viewport" name="viewport" content="width=320; initial-scale=1.0; maximum-scale=1.0; user-scalable=0;"/>

在设置了initial-scale=1之后，我们终于可以以1:1的比例进行页面设计了。下一步我们就可以正式进入页面布局的细节设计了，如果你想继续关注iPhone开发话题的话，欢迎订阅：

• Cat in Chinese (feed)
• Cat in dotNET (feed)

--
由 钢盅郭子 于 12/27/2007 09:13:00 上午 在 №0千年老妖猴 上发表

编写 iPhone Friendly 的 Web 应用程序 (Part 2 - Viewport)

Posted: 26 Dec 2007 03:48 AM CST

在了解到iPhone的一些常见布局法后，我们就可以开始着手编写一个真正能在iPhone上跑的页面了。小声说一句，之前我说要布局讨论完了，要进入交互逻辑开发，后来细心一想发现不行，有些东西不讲的话将会对布局带来问题，绕过去的话并不怎么优雅，因此继续讲布局。

首先要说的就是viewport，也就是可视区域。对于桌面浏览器，我们都很清楚viewport是什么，就是出去了所有工具栏、状态栏、滚动条等等之后用于看网页的区域，这是真正有效的区域。（无论你屏幕多大，如果你装足够多的toolbar，你的viewport最终也会消失掉。）在桌面浏览器中，viewport的大小是与浏览器窗口大小直接相关的，窗口大了viewport自然就大，同时随着viewport的改变，页面布局可能也跟着变。例如 width: 100%的页面宽度就总是和viewport宽度一致。

然而iPhone的Safari不是这样理解viewport的，它基于viewport呈现页面，然后用户缩放页面后viewport保持不变，仅仅是页面内容按比例缩放了。举个例子，在不设置viewport的情况下，默认viewport为宽度980（单位是像素），这时候页面的呈现出来的布局和在桌面短viewport宽度为980时呈现的结果一致，然而因为iPhone屏幕宽度为320，因此按比例缩小了。因此，一张宽度为320的图片，在默认viewport下会这样显示：

可以看到，图片按比例缩小了，这对于传统Web页面直接在iPhone上面显示来说是很好的事情，因为如果传统Web页面在980宽度的桌面浏览器viewport中显示正常的话，iPhone上显示也绝对正常。然而这对于Web应用程序来说则不是好事，因为我们需要按照980宽度来设计将来会以320宽度显示的页面，一个应该显示为320*80的元素，必须设计为980*245，这多麻烦！

因此我们需要改变viewport，让它变成这样：

实际上应该怎么做呢？我们有几个选择，因此先让我们看看到底我们能够设置哪些属性吧。我们可以操作的属性有4个：

• width - viewport的宽度
• height - viewport的高度
• initial-scale - 初始的缩放比例
• minimum-scale - 允许用户缩放到的最小比例
• maximum-scale - 允许用户缩放到的最大比例
• user-scalable - 用户是否可以手动缩放

这6个属性，我们可以设置其中的一个或者多个，iPhone会根据你设置的属性自动推算其他属性值，而非直接采用默认值。这点很重要，在完全不设置的时候有默认viewport，在你设置一个属性后其它值是自动推算出来的，不再是默认的。

如果你把initial-scale=1，那么width和height在竖屏时自动为320*356（不是320*480因为地址栏等都占据空间），横屏时自动为480*208。

类似地，如果你仅仅设置了width，就会自动推算出initial-scale以及height。例如你设置了width=320，竖屏时initial-scale就是1，横屏时则变成1.5了。

那么到底这些设置如何让Safari知道？其实很简单，就一个meta，形如：

<meta id="viewport" name="viewport" content="width=320; initial-scale=1.0; maximum-scale=1.0; user-scalable=0;"/>

在设置了initial-scale=1之后，我们终于可以以1:1的比例进行页面设计了。下一步我们就可以正式进入页面布局的细节设计了，如果你想继续关注iPhone开发话题的话，欢迎订阅：

• Cat in Chinese (feed)
• Cat in dotNET (feed)

--
由 钢盅郭子 于 12/27/2007 09:13:00 上午 在 №0千年老妖猴 上发表

编写 iPhone Friendly 的 Web 应用程序 (Part 2 - Viewport)

Posted: 26 Dec 2007 03:48 AM CST

在了解到iPhone的一些常见布局法后，我们就可以开始着手编写一个真正能在iPhone上跑的页面了。小声说一句，之前我说要布局讨论完了，要进入交互逻辑开发，后来细心一想发现不行，有些东西不讲的话将会对布局带来问题，绕过去的话并不怎么优雅，因此继续讲布局。

首先要说的就是viewport，也就是可视区域。对于桌面浏览器，我们都很清楚viewport是什么，就是出去了所有工具栏、状态栏、滚动条等等之后用于看网页的区域，这是真正有效的区域。（无论你屏幕多大，如果你装足够多的toolbar，你的viewport最终也会消失掉。）在桌面浏览器中，viewport的大小是与浏览器窗口大小直接相关的，窗口大了viewport自然就大，同时随着viewport的改变，页面布局可能也跟着变。例如 width: 100%的页面宽度就总是和viewport宽度一致。

然而iPhone的Safari不是这样理解viewport的，它基于viewport呈现页面，然后用户缩放页面后viewport保持不变，仅仅是页面内容按比例缩放了。举个例子，在不设置viewport的情况下，默认viewport为宽度980（单位是像素），这时候页面的呈现出来的布局和在桌面短viewport宽度为980时呈现的结果一致，然而因为iPhone屏幕宽度为320，因此按比例缩小了。因此，一张宽度为320的图片，在默认viewport下会这样显示：

可以看到，图片按比例缩小了，这对于传统Web页面直接在iPhone上面显示来说是很好的事情，因为如果传统Web页面在980宽度的桌面浏览器viewport中显示正常的话，iPhone上显示也绝对正常。然而这对于Web应用程序来说则不是好事，因为我们需要按照980宽度来设计将来会以320宽度显示的页面，一个应该显示为320*80的元素，必须设计为980*245，这多麻烦！

因此我们需要改变viewport，让它变成这样：

实际上应该怎么做呢？我们有几个选择，因此先让我们看看到底我们能够设置哪些属性吧。我们可以操作的属性有4个：

• width - viewport的宽度
• height - viewport的高度
• initial-scale - 初始的缩放比例
• minimum-scale - 允许用户缩放到的最小比例
• maximum-scale - 允许用户缩放到的最大比例
• user-scalable - 用户是否可以手动缩放

这6个属性，我们可以设置其中的一个或者多个，iPhone会根据你设置的属性自动推算其他属性值，而非直接采用默认值。这点很重要，在完全不设置的时候有默认viewport，在你设置一个属性后其它值是自动推算出来的，不再是默认的。

如果你把initial-scale=1，那么width和height在竖屏时自动为320*356（不是320*480因为地址栏等都占据空间），横屏时自动为480*208。

类似地，如果你仅仅设置了width，就会自动推算出initial-scale以及height。例如你设置了width=320，竖屏时initial-scale就是1，横屏时则变成1.5了。

那么到底这些设置如何让Safari知道？其实很简单，就一个meta，形如：

<meta id="viewport" name="viewport" content="width=320; initial-scale=1.0; maximum-scale=1.0; user-scalable=0;"/>

在设置了initial-scale=1之后，我们终于可以以1:1的比例进行页面设计了。下一步我们就可以正式进入页面布局的细节设计了，如果你想继续关注iPhone开发话题的话，欢迎订阅：

• Cat in Chinese (feed)
• Cat in dotNET (feed)

--
由 钢盅郭子 于 12/27/2007 09:13:00 上午 在 №0千年老妖猴 上发表

写 iPhone Friendly 的 Web 应用程序 (Part 1 - 布局入门)

Posted: 25 Dec 2007 07:47 AM CST

--
由 钢盅郭子 于 12/26/2007 09:25:00 上午 在 №0千年老妖猴 上发表

 

--
由 钢盅郭子 于 12/26/2007 12:03:00 下午 在 №0千年老妖猴 上发表

 

--
由 钢盅郭子 于 12/16/2007 07:35:00 下午 在 №0千年老妖猴 上发表

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

作者：Google（谷歌）研究员，吴军

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

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

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

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

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

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

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

--
Posted By 钢盅郭子 to №0千年老妖猴 at 12/05/2007 08:21:00 下午

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

作者：Google（谷歌）研究员，吴军

前一阵子看了电视剧《暗算》，蛮喜欢它的构思和里面的表演。其中有一个故事提到了密码学，故事本身不错，但是有点故弄玄虚。不过有一点是对的，就是当今的密码学是以数学为基础的。（没有看过暗算的读者可以看一下介绍，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。



这个过程大致可以概况如下：



公开密钥的好处有：

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）。

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

--
由 钢盅郭子 于 12/05/2007 08:19:00 下午 在 №0千年老妖猴 上发表

用了几天Gmail最新版本的界面——页面顶部有个链接可以在“Newer Version”/“Older version”（这里似乎有一个文本不统一的bug）之间切换——发表一些个人看法：

1. 首次进入Gmail时页面打开的速度比以前慢了（如果在Firefox里用了Firebug插件，还有一些兼容性问题，暂时关闭Firebug比较好）
2. 不同的文件夹、标签及邮件时都有各自的URL了，过去刷新页面总是会跳回到收件箱，现在可以保持当前浏览状态
3. 各种操作的弹出对话框（比如“Apply Label”时“New Label”）不再是默认样式而是Google特有的风格
4. 在邮件会话顶部，提供了其所属Label的快速链接和删除功能
5. 可以对标签进行自定义颜色了（邮件醒目）

暂时就这些吧

--
由 钢盅郭子 于 12/05/2007 08:22:00 下午 在 №0千年老妖猴 上发表

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

作者：Google 研究员，吴军

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

马库斯教授长期当任宾夕法尼亚大学计算机系主任，直到他在几年前从 AT&T 找到皮耶尔替代他为止。作为一个管理者，马库斯显示出在自然处理和计算机科学方面的卓识的远见。在指导博士生时，马库斯发现语料库在自然语言处理中的重要 性。马库斯呕心沥血，花了十几年工夫建立了一系列标准的语料库，提供给全世界的学者使用。这套被称为 LDC 的语料库，是当今全世界自然语言处理的所有学者都使用的工具。我们在以前的系列中讲到，当今的自然语言处理几乎都是使用给予统计的方法。要做统计，就需要 大量有代表性的数据。利用这些数据开发一个自然语言处理系统的过程，可以统称为训练。比如，我们要训练一个汉语分词系统，我们需要一些已经分好词的中文句 子。当然这些句子需要有代表性。如果想知道一个分词系统的准确性，我们也需要一些人工分好词的句子进行测试。这些人工处理好的文字数据库，成为语料库 (corpus)。如果每个研究室都人工建立几个语料库，不仅浪费时间精力，而且发表文章时，数据没有可比性。因此，马库斯想到了建立一系列标准的语料库 为全世界的学者用。他利用自己的影响力让美国自然科学基金会和 DARPA 出钱立项，联络的多所大学和研究机构，建立的数百个标准的语料库。其中最著名的是 PennTree
Bank 的语料库。PennTree Bank 覆盖多种语言（包括中文）。每一种语言，它有几十万到几百万字的有代表性的句子，每个句子都有的词性标注，语法分析树等等。LDC 语料库如今已成为全世界自然语言处理科学家共用的数据库。如今，在自然语言处理方面发表论文，几乎都要提供基于 LDC 语料库的测试结果。

马 库斯给予他的博士生研究自己感兴趣的课题的自由，这是他之所以桃李满天下的原因。马库斯对几乎所有的自然语言处理领域有独到的见解。和许多教授让博士生去 做他拿到基金的项目，马库斯让博士生提出自己有兴趣的课题，或者用他已有的经费支持学生，或者为他们的项目区申请经费。马库斯高屋建瓴，能够很快的判断一 个研究方向是否正确，省去了博士生很多 try-and-error 的时间。因此他的学生有些很快地拿到的博士学位。

作为系主任，马库 斯在专业设置方面显示出卓识的远见。我有幸和他在同一个校务顾问委员会任职，一起讨论计算机系的研究方向。马库斯在几年前互联网很热门、很多大学开始互联 网研究时，看到 bioinformatics (生物信息学）的重要性，在宾夕法利亚大学设置这个专业，并且在其他大学还没有意识到时，开始招聘这方面的教授。马库斯还建议一些相关领域的教授，包括后 来的系主任皮耶尔把一部分精力转到生物信息学方面。马库斯同时向他担任顾问的其他一些大学提出同样的建议。等到网络泡沫破裂以后，很多大学的计算机系开始 向生物信息学转向，但是发现已经很难找到这些方面好的教授了。我觉得，当今中国的大学，最需要的就是马库斯这样卓有远见的管理者。

过几天我又要和马库斯一起开顾问委员会的会议了，不知道这次他对计算机科学的发展有什么见解。

--
由 钢盅郭子 于 12/04/2007 10:57:00 下午 在 №0千年老妖猴 上发表

数学之美系列二十一 - 布隆过滤器（Bloom Filter）

作者：Google（谷歌）研究员，吴军

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

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

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

--
由 钢盅郭子 于 12/04/2007 10:58:00 下午 在 №0千年老妖猴 上发表

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

作者：Google 研究员，吴军

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



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

和马尔可夫链类似，贝叶斯网络中的每个状态值取决于前面有限个状态。不同的是，贝叶斯网络比马尔可夫链灵活，它不受马尔可夫链的链状结构的约束，因此可以更准确地描述事件之间的相关性。可以讲，马尔可夫链是贝叶斯网络的特例，而贝叶斯网络是马尔可夫链的推广。

使 用贝叶斯网络必须知道各个状态之间相关的概率。得到这些参数的过程叫做训练。和训练马尔可夫模型一样，训练贝叶斯网络要用一些已知的数据。比如在训练上面 的网络，需要知道一些心血管疾病和吸烟、家族病史等有关的情况。相比马尔可夫链，贝叶斯网络的训练比较复杂，从理论上讲，它是一个 NP-complete 问题，也就是说，对于现在的计算机是不可计算的。但是，对于某些应用，这个训练过程可以简化，并在计算上实现。

值得一提的是 IBM Watson 研究所的茨威格博士 (Geoffrey Zweig) 和西雅图华盛顿大学的比尔默 (Jeff Bilmes) 教授完成了一个通用的贝叶斯网络的工具包，提供给对贝叶斯网络有兴趣的研究者。

贝叶斯网络在图像处理、文字处理、支持决策等方面有很多应用。在文字处理方面，语义相近的词之间的关系可以用一个贝叶斯网络来描述。我们利用贝叶斯网络，可以找出近义词和相关的词，在 Google 搜索和 Google 广告中都有直接的应用。

--
由 钢盅郭子 于 12/04/2007 09:19:00 下午 在 №0千年老妖猴 上发表

数学之美 系列十八 - 矩阵运算和文本处理中的分类问题

2007年1月1日 下午 03:10:00 发表者：Google 研究员，吴军

我 在大学学习线性代数时，实在想不出它除了告诉我们如何解线性方程外，还能有什么别的用途。关于矩阵的许多概念，比如特征值等等，更是脱离日常生活。后来在 数值分析中又学了很多矩阵的近似算法，还是看不到可以应用的地方。当时选这些课，完全是为了混学分的学位。我想，很多同学都多多少少有过类似的经历。直到 后来长期做自然语言处理的研究，我才发现数学家们提出那些矩阵的概念和算法，是有实际应用的意义的。

在自然语言处理中，最常见的两类的分 类问题分别是，将文本按主题归类（比如将所有介绍亚运会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种体育运动的名称个归成一类）。这两种 分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决这两个问题的，让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。

分 类的关键是计算相关性。我们首先对两个文本计算出它们的内容词，或者说实词的向量，然后求这两个向量的夹角。当这两个向量夹角为零时，新闻就相关；当它们 垂直或者说正交时，新闻则无关。当然，夹角的余弦等同于向量的内积。从理论上讲，这种算法非常好。但是计算时间特别长。通常，我们要处理的文章的数量都很 大，至少在百万篇以上，二次回标有非常长，比如说有五十万个词（包括人名地名产品名称等等）。如果想通过对一百万篇文章两篇两篇地成对比较，来找出所有共 同主题的文章，就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章，完成这一百万篇文章相关性比较就需要十五年时间。注意，要真正完成文章 的分类还要反复重复上述计算。

在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（Singular Value Decomposition，简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先，我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文 章，每一列对应一个词。



在上面的图中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 个词在第 i 篇文章中出现的加权词频（比如，TF/IDF)。读者可能已经注意到了，这个矩阵非常大，有一百万乘以五十万，即五千亿个元素。

奇 异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X，一个一百乘以一百的 矩阵B，和一个一百乘以五十万的矩阵Y。这三个矩阵的元素总数加起来也不过1.5亿，仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数量级以 上。



三 个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越 相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因此， 我们只要对关联矩阵A进行一次奇异值分解，w 我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。

现 在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中的许多概念，比如矩阵的特征值等等，以及数值分析的各种算法就统统用上了。在很长时 间内，奇异值分解都无法并行处理。（虽然 Google 早就有了MapReduce 等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。）最近，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，我认为这是 Google 中国对世界的一个贡献。

--
由 钢盅郭子 于 12/04/2007 09:03:00 下午 在 №0千年老妖猴 上发表

数学之美 系列十七 闪光的不一定是金子 谈谈搜索引擎作弊问题(Search Engine Anti-SPAM)

作者：Google 研究员 吴军

自从有了搜索引擎，就有了针对搜索引擎网页排名的作弊(SPAM)。以至于用户发现在搜索引擎中排名靠前的网页不一定就是高质量的，用句俗话说，闪光的不一定是金子。

搜索引擎的作弊，虽然方法很多，目的只有一个，就是采用不正当手

--
由 钢盅郭子 于 12/04/2007 08:53:00 下午 在 №0千年老妖猴 上发表

数学之美 系列十六 - 不要把所有的鸡蛋放在一个篮子里 -- 谈谈最大熵模型（下）

作者：Google 研究员，吴军

我们上次谈到用最大熵模型可以将各种信息综合在一起。我们留下一个问题没有回答，就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式，现在只需要确定指数函数的参数就可以了，这个过程称为模型的训练。

最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂，大致可以概括为以下几个步骤：
1. 假定第零次迭代的初始模型为等概率的均匀分布。
2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把相应的模型参数变小；否则，将它们便大。
3. 重复步骤 2 直到收敛。

GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是，这两人没有能对这种算法的物理含义进行很好地解释。后来是由数学家希萨（Csiszar)解释清楚的，因此，人们在谈到这个算法 时，总是同时引用 Darroch 和Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都很长，需要迭代很多次才能收敛，而且不太稳定，即使在 64 位计算机上都会出现溢出。因此，在实际应用中很少有人真正使用 GIS。大家只是通过它来了解最大熵模型的算法。

八十年代，很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面的改进，提出了改进迭代算法 IIS（improved iterative scaling）。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此，在当时也只有 IBM 有条件是用最大熵模型。

由于最大熵模型在数学上十分完美，对科学家们有很大的诱惑力，因此不少研究者试图把自己的问题用一个类似最大熵的 近似模型去套。谁知这一近似，最大熵模型就变得不完美了，结果可想而知，比打补丁的凑合的方法也好不了多少。于是，不少热心人又放弃了这种方法。第一个在 实际信息处理应用中验证了最大熵模型的优势的，是宾夕法尼亚大学马库斯的另一个高徒原 IBM 现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似，而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问 题，比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词等）、句子成分（主谓宾）通过最大熵模型结合起来，做出了当时世界上 最好的词性标识系统和句法分析器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统，至今仍然是使用单一方法最好的系统。科学家们从拉纳帕提 的成就中，又看到了用最大熵模型解决复杂的文字信息处理的希望。

但是，最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如 何简化最大熵模型的计算量。终于有一天，我对我的导师说，我发现一种数学变换，可以将大部分最大熵模型的训练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时，他没有找出我的推导中的任何破绽，接着他又回去想了两天，然后告诉我我的算法是对的。从此，我们就 建造了一些很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以后，为了训练一个包含上下文信息，主题信息和语法信息 的文法模型(language model)，我并行使用了 20 台当时最快的 SUN 工作站，仍然计算了三个月。由此可见最大熵模型的复杂的一面。最大熵模型快速算法的实现很复杂，到今天为止，世界上能有效实现这些算法的人也不到一百人。 有兴趣实现一个最大熵模型的读者可以阅读我的论文。

最大熵模型，可以说是集简与繁于一体，形式简单，实现复杂。值得一提的是，在Google的很多产品中，比如机器翻译，都直接或间接地用到了最大熵模型。

讲 到这里，读者也许会问，当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何事吗？他们在九十年代初贾里尼克离开 IBM 后，也退出了学术界，而到在金融界大显身手。他们两人和很多 IBM 语音识别的同事一同到了一家当时还不大，但现在是世界上最成功对冲基金(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)。我们知道，决定股票涨落的因素可能有几十甚至上百种，而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。达拉皮 垂兄弟等科学家在那里，用于最大熵模型和其他一些先进的数学工具对股票预测，获得了巨大的成功。从该基金 1988 年创立至今，它的净回报率高达平均每年 34%。也就是说，如果 1988 年你在该基金投入一块钱，今天你能得到 200 块钱。这个业绩，远远超过股神巴菲特的旗舰公司伯克夏哈撒韦（Berkshire Hathaway)。同期，伯克夏哈撒韦的总回报是 16 倍。

值得一提的是，信息处理的很多数学手段，包括隐含马尔可夫模型、子波变换、贝叶斯网络等等，在华尔街多有直接的应用。由此可见，数学模型的作用。

--
由 钢盅郭子 于 12/04/2007 08:05:00 下午 在 №0千年老妖猴 上发表

数学之美 系列十六 - 不要把所有的鸡蛋放在一个篮子里 -- 谈谈最大熵模型（上）

作者：Google 研究员，吴军

[我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里，这样可以降低风险。在信息处理中，这个原理同样适用。在数学上，这个原理称为最大熵原理(the maximum entropy principle)。这是一个非常有意思的题目，但是把它讲清楚要用两个系列的篇幅。]

前段时间，Google 中国研究院的刘骏总监谈到在网络搜索排名中，用到的信息有上百种。更普遍地讲，在自然语言处理中，我们常常知道各种各样的但是又不完全确定的信息，我们需要用一个统一的模型将这些信息综合起来。如何综合得好，是一门很大的学问。

让 我们看一个拼音转汉字的简单的例子。假如输入的拼音是"wang-xiao-bo"，利用语言模型，根据有限的上下文(比如前两个词)，我们能给出两个最 常见的名字“王小波”和“王晓波”。至于要唯一确定是哪个名字就难了，即使利用较长的上下文也做不到。当然，我们知道如果通篇文章是介绍文学的，作家王小 波的可能性就较大；而在讨论两岸关系时，台湾学者王晓波的可能性会较大。在上面的例子中，我们只需要综合两类不同的信息，即主题信息和上下文信息。虽然有 不少凑合的办法，比如：分成成千上万种的不同的主题单独处理，或者对每种信息的作用加权平均等等，但都不能准确而圆满地解决问题，这样好比以前我们谈到的 行星运动模型中的小圆套大圆打补丁的方法。在很多应用中，我们需要综合几十甚至上百种不同的信息，这种小圆套大圆的方法显然行不通。

数学上最漂亮的办法是最大熵(maximum entropy)模型，它相当于行星运动的椭圆模型。“最大熵”这个名词听起来很深奥，但是它的原理很简单，我们每天都在用。说白了，就是要保留全部的不确定性，将风险降到最小。让我们来看一个实际例子。

有 一次，我去 AT&T 实验室作关于最大熵模型的报告，我带去了一个色子。我问听众“每个面朝上的概率分别是多少”，所有人都说是等概率，即各点的概率均为1/6。这种猜测当然 是对的。我问听众们为什么，得到的回答是一致的：对这个“一无所知”的色子，假定它每一个朝上概率均等是最安全的做法。（你不应该主观假设它象韦小宝的色 子一样灌了铅。）从投资的角度看，就是风险最小的做法。从信息论的角度讲，就是保留了最大的不确定性，也就是说让熵达到最大。接着，我又告诉听众，我的这 个色子被我特殊处理过，已知四点朝上的概率是三分之一，在这种情况下，每个面朝上的概率是多少？这次，大部分人认为除去四点的概率是 1/3，其余的均是 2/15，也就是说已知的条件（四点概率为 1/3）必须满足，而对其余各点的概率因为仍然无从知道，因此只好认为它们均等。注意，在猜测这两种不同情况下的概率分布时，大家都没有添加任何主观的假 设，诸如四点的反面一定是三点等等。（事实上，有的色子四点反面不是三点而是一点。）这种基于直觉的猜测之所以准确，是因为它恰好符合了最大熵原理。

最 大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。（不做主观假设这 点很重要。）在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫“最大熵模型”。我们常说，不要把所有 的鸡蛋放在一个篮子里，其实就是最大熵原理的一个朴素的说法，因为当我们遇到不确定性时，就要保留各种可能性。

回到我们刚才谈到的拼音转 汉字的例子，我们已知两种信息，第一，根据语言模型，wang-xiao-bo 可以被转换成王晓波和王小波；第二，根据主题，王小波是作家，《黄金时代》的作者等等，而王晓波是台湾研究两岸关系的学者。因此，我们就可以建立一个最大 熵模型，同时满足这两种信息。现在的问题是，这样一个模型是否存在。匈牙利著名数学家、信息论最高奖香农奖得主希萨（Csiszar）证明，对任何一组不 自相矛盾的信息，这个最大熵模型不仅存在，而且是唯一的。而且它们都有同一个非常简单的形式 -- 指数函数。下面公式是根据上下文（前两个词）和主题预测下一个词的最大熵模型，其中 w3 是要预测的词（王晓波或者王小波）w1 和 w2 是它的前两个字（比如说它们分别是“出版”，和“”），也就是其上下文的一个大致估计，subject 表示主题。



我们看到，在上面的公式中，有几个参数 lambda 和 Z ，他们需要通过观测数据训练出来。

最大熵模型在形式上是最漂亮的统计模型，而在实现上是最复杂的模型之一。我们在将下一个系列中介绍如何训练最大熵模型的诸多参数，以及最大熵模型在自然语言处理和金融方面很多有趣的应用。

--
由 钢盅郭子 于 12/04/2007 08:04:00 下午 在 №0千年老妖猴 上发表

数学之美 系列十五 繁与简 自然语言处理的几位精英

作者：吴军，Google 研究员

我 在数学之美系列中一直强调的一个好方法就是简单。但是，事实上，自然语言处理中也有一些特例，比如有些学者将一个问题研究到极致，执著追求完善甚至可以说 完美的程度。他们的工作对同行有很大的参考价值，因此我们在科研中很需要这样的学者。在自然语言处理方面新一代的顶级人物麦克尔 · 柯林斯 (Michael Collins) 就是这样的人。


柯林斯：追求完美

柯 林斯从师于自然语言处理大师马库斯 (Mitch Marcus)（我们以后还会多次提到马库斯），从宾夕法利亚大学获得博士学位，现任麻省理工学院 (MIT) 副教授（别看他是副教授，他的水平在当今自然语言处理领域是数一数二的），在作博士期间，柯林斯写了一个后来以他名字命名的自然语言文法分析器 (sentence parser)，可以将书面语的每一句话准确地进行文法分析。文法分析是很多自然语言应用的基础。虽然柯林斯的师兄布莱尔 (Eric Brill) 和 Ratnaparkhi 以及师弟 Eisnar 都完成了相当不错的语言文法分析器，但是柯林斯却将它做到了极致，使它在相当长一段时间内成为世界上最好的文法分析器。柯林斯成功的关键在于将文法分析的 每一个细节都研究得很仔细。柯林斯用的数学模型也很漂亮，整个工作可以用完美来形容。我曾因为研究的需要，找柯林斯要过他文法分析器的源程序，他很爽快地 给了我。我试图将他的程序修改一下来满足我特定应用的要求，但后来发现，他的程序细节太多以至于很难进一步优化。柯林斯的博士论文堪称是自然语言处理领域的范文。它像一本优秀的小说，把所有事情的来龙去脉介绍的清清楚楚，对于任何有一点计算机和自然语言处理知识的人，都可以轻而易举地读懂他复杂的方法。

柯 林斯毕业后，在 AT&T 实验室度过了三年快乐的时光。在那里柯林斯完成了许多世界一流的研究工作诸如隐含马尔科夫模型的区别性训练方法，卷积核在自然语言处理中的应用等等。三年 后，AT&T 停止了自然语言处理方面的研究，柯林斯幸运地在 MIT 找到了教职。在 MIT 的短短几年间，柯林斯多次在国际会议上获得最佳论文奖。相比其他同行，这种成就是独一无二的。柯林斯的特点就是把事情做到极致。如果说有人喜欢“繁琐哲 学”，柯林斯就是一个。


布莱尔：简单才美

在研究方法上，站在柯林斯对立面的典型是他的师兄艾里克 · 布莱尔 (Eric Brill) 和雅让斯基，后者我们已经介绍过了，这里就不再重复。与柯林斯从工业界到学术界相反，布莱尔职业路径是从学术界走到工业界。与柯里斯的研究方法相反，布莱 尔总是试图寻找简单得不能再简单的方法。布莱尔的成名作是基于变换规则的机器学习方法 (transformation rule based machine learning)。这个方法名称虽然很复杂，其实非常简单。我们以拼音转换字为例来说明它：

第一步，我们把每个拼音对应的汉字中最常见的找出来作为第一遍变换的结果，当然结果有不少错误。比如，“常识”可能被转换成“长识”；

第二步，可以说是“去伪存真”，我们用计算机根据上下文，列举所有的同音字替换的规则，比如，如果 chang 被标识成“长”，但是后面的汉字是“识”，则将“长”改成“常”；

第三步，应该就是“去粗取精”，将所有的规则用到事先标识好的语料中，挑出有用的，删掉无用的。然后重复二三步，直到找不到有用的为止。

布 莱尔就靠这么简单的方法，在很多自然语言研究领域，得到了几乎最好的结果。由于他的方法再简单不过了，许许多多的人都跟着学。布莱尔可以算是我在美国的第 一个业师，我们俩就用这么简单的方法作词性标注 (part of speech tagging)，也就是把句子中的词标成名词动词，很多年内无人能超越。（最后超越我们的是后来加入 Google 的一名荷兰工程师，用的是同样的方法，但是做得细致很多）布莱尔离开学术界后去了微软研究院。在那里的第一年，他一人一年完成的工作比组里其他所有人许多 年做的工作的总和还多。后来，布莱尔又加入了一个新的组，依然是高产科学家。据说，他的工作真正被微软重视要感谢 Google，因为有了 Google，微软才对他从人力物力上给于了巨大的支持，使得布莱尔成为微软搜索研究的领军人物之一。在研究方面，布莱尔有时不一定能马上找到应该怎么 做，但是能马上否定掉一种不可能的方案。这和他追求简单的研究方法有关，他能在短时间内大致摸清每种方法的好坏。

由于布莱尔总是找简单有 效的方法，而又从不隐瞒自己的方法，所以他总是很容易被包括作者我自己在内的很多人赶上和超过。好在布莱尔很喜欢别人追赶他，因为，当人们在一个研究方向 超过他时，他已经调转船头驶向它方了。一次，艾里克对我说，有一件事我永远追不上他，那就是他比我先有了第二个孩子 ：）

在接下来了系列里，我们还会介绍一个繁与简结合的例子。

--
由 钢盅郭子 于 12/04/2007 09:56:00 上午 在 №0千年老妖猴 上发表

数学之美 十四 谈谈数学模型的重要性

作者：吴军，Google 研究员

[注：一直关注数学之美系列的读者可能已经发现，我们对任何问题总是在找相应的准确的数学模型。为了说明模型的重要性，今年七月份我在 Google 中国内部讲课时用了整整一堂课来讲这个问题，下面的内容是我讲座的摘要。］

在 包括哥白尼、伽利略和牛顿在内的所有天文学家中，我最佩服的是地心说的提出者托勒密。虽然天文学起源于古埃及，并且在古巴比伦时，人们就观测到了五大行星 （金、木、水、火、土）运行的轨迹，以及行星在近日点运动比远日点快。（下图是在地球上看到的金星的轨迹，看过达芬奇密码的读者知道金星大约每四年在天上 画一个五角星。）



但是真正创立了天文学，并且计算出诸多天体运行轨迹的是两千年前古罗马时代的托勒密。虽然今天我们可能会嘲笑托勒密犯的简单的错误，但是真正了解托勒密贡献的人都会对他肃然起敬。托勒密发明了球坐标，定义了包括赤道和零度经线在内的经纬线，他提出了黄道，还发明了弧度制。

当 然，他最大也是最有争议的发明是地心说。虽然我们知道地球是围绕太阳运动的，但是在当时，从人们的观测出发，很容易得到地球是宇宙中心的结论。从地球上 看，行星的运动轨迹是不规则的，托勒密的伟大之处是用四十个小圆套大圆的方法，精确地计算出了所有行星运动的轨迹。（托勒密继承了毕达格拉斯的一些思想， 他也认为圆是最完美的几何图形。）托勒密模型的精度之高，让以后所有的科学家惊叹不已。即使今天，我们在计算机的帮助下，也很难解出四十个套在一起的圆的 方程。每每想到这里，我都由衷地佩服托勒密。一千五百年来，人们根据他的计算决定农时。但是，经过了一千五百年，托勒密对太阳运动的累积误差，还是差出了 一星期。


地心说的示意图，我国天文学家张衡的浑天地动说其实就是地心说。

纠 正地心说错误不是靠在托勒密四十个圆的模型上再多套上几个圆，而是进一步探索真理。哥白尼发现，如果以太阳为中心来描述星体的运行，只需要 8-10 个圆，就能计算出一个行星的运动轨迹，他提出了日心说。很遗憾的事，哥白尼正确的假设并没有得到比托勒密更好的结果，哥白尼的模型的误差比托勒密地要大不 少。这是教会和当时人们认为哥白尼的学说是邪说的一个原因，所以日心说要想让人心服口服地接受，就得更准确地描述行星运动。

完成这一使命 的是开普勒。开普勒在所有一流的天文学家中，资质较差，一生中犯了无数低级的错误。但是他有两条别人没有的东西，从他的老师第谷手中继承的大量的、在当时 最精确的观测数据，以及运气。开普勒很幸运地发现了行星围绕太阳运转的轨道实际是椭圆形的，这样不需要用多个小圆套大圆，而只要用一个椭圆就能将星体运动 规律描述清楚了。只是开普勒的知识和水平不足以解释为什么行星的轨道是椭圆形的。最后是伟大的科学家牛顿用万有引力解释了这个问题。

故事 到这里似乎可以结束了。但是，许多年后，又有了个小的波澜。天文学家们发现，天王星的实际轨迹和用椭圆模型算出来的不太符合。当然，偷懒的办法是接着用小 圆套大圆的方法修正，但是一些严肃的科学家在努力寻找真正的原因。英国的亚当斯和法国的维内尔（Verrier）独立地发现了吸引天王星偏离轨道的海王 星。

讲座结束前，我和 Google 中国的工程师们一同总结了这么几个结论：
１.　一个正确的数学模型应当在形式上是简单的。（托勒密的模型显然太复杂。）
２.　一个正确的模型在它开始的时候可能还不如一个精雕细琢过的错误的模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去。（日心说开始并没有地心说准确。）
３.　大量准确的数据对研发很重要。
４.　正确的模型也可能受噪音干扰，而显得不准确；这时我们不应该用一种凑合的修正方法来弥补它，而是要找到噪音的根源，这也许能通往重大发现。

在网络搜索的研发中，我们在前面提到的单文本词频/逆文本频率指数（TF/IDF) 和网页排名（page rank)都相当于是网络搜索中的“椭圆模型”，它们都很简单易懂。

--
由 钢盅郭子 于 12/04/2007 09:50:00 上午 在 №0千年老妖猴 上发表

数学之美 系列十三 信息指纹及其应用

作者：吴军，Google 研究员

任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹（Fingerprint)。只要算法设计的好，任何两段信息的指纹都很难重复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。

我们在图论和网络爬虫一 文中提到，为了防止重复下载同一个网页，我们需要在哈希表中纪录已经访问过的网址（URL)。但是在哈希表中以字符串的形式直接存储网址，既费内存空间， 又浪费查找时间。现在的网址一般都较长，比如，如果在 Google 或者百度在查找数学之美，对应的网址长度在一百个字符以上。下面是百度的链接

http://www.baidu.com/s?ie=gb2312&bs=%CA%FD%D1%A7%D6%AE%C3%C0&sr=&z=&cl=3&f=8
&wd=%CE%E2%BE%FC+%CA%FD%D1%A7%D6%AE%C3%C0&ct=0

假 定网址的平均长度为一百个字符，那么存贮 200 亿个网址本身至少需要 2 TB，即两千 GB 的容量，考虑到哈希表的存储效率一般只有 50%，实际需要的内存在 4 TB以上。即使把这些网址放到了计算机的内存中，由于网址长度不固定，以字符串的形式查找的效率会很低。因此，我们如果能够找到一个函数，将这 200 亿个网址随机地映射到128 二进位即 16 个字节的整数空间，比如将上面那个很长的字符串对应成一个如下的随机数:

893249432984398432980545454543

这 样每个网址只需要占用 16 个字节而不是原来的一百个。这就能把存储网址的内存需求量降低到原来的 1/6。这个16 个字节的随机数，就称做该网址的信息指纹（Fingerprint)。可以证明，只要产生随机数的算法足够好，可以保证几乎不可能有两个字符串的指纹相 同，就如同不可能有两个人的指纹相同一样。由于指纹是固定的 128 位整数，因此查找的计算量比字符串比较小得多。网络爬虫在下载网页时，它将访问过的网页的网址都变成一个个信息指纹，存到哈希表中，每当遇到一个新网址 时，计算机就计算出它的指纹，然后比较该指纹是否已经在哈希表中，来决定是否下载这个网页。这种整数的查找比原来字符串查找,可以快几倍到几十倍。

产 生信息指纹的关键算法是伪随机数产生器算法（prng)。最早的 prng 算法是由计算机之父冯诺伊曼提出来的。他的办法非常简单，就是将一个数的平方掐头去尾，取中间的几位数。比如一个四位的二进制数 1001（相当于十进制的9），其平方为 01010001 (十进制的 81）掐头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机，也就是说两个不同信息很有可能有同一指纹。现在常用的 MersenneTwister 算法要好得多。

信息指纹的用途远不止网址的消重，信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性, 也就是说,
无 法根据信息指纹推出原有信息，这种性质， 正是网络加密传输所需要的。比如说，一个网站可以根据用户的Cookie 识别不同用户，这个 cookie 就是信息指纹。但是网站无法根据信息指纹了解用户的身份，这样就可以保护用户的隐私。在互联网上，加密的可靠性，取决于是否很难人为地找到拥有同一指纹的 信息， 比如一个黑客是否能随意产生用户的 cookie。从加密的角度讲 MersenneTwister，算法并不好，因为它产生的随机数有相关性。

互 联网上加密要用基于加密伪随机数产生器（csprng)。常用的算法有 MD5 或者 SHA1 等标准，它们可以将不定长的信息变成定长的 128 二进位或者 160 二进位随机数。值得一提的事，SHA1 以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌， 因为这和黑客能真正攻破你的注册信息是还两回事。

信息指纹的虽然历史很悠久，但真正的广泛应用是在有了互联网以后，这几年才渐渐热门起来。

--
由 钢盅郭子 于 12/04/2007 09:43:00 上午 在 №0千年老妖猴 上发表