中国的博客，走近我们的产品、技术和文化
Google 中国的博客，走近我们的产品、技术和文化
数学之美 系列十五 繁与简 自然语言处理的几位精英
2006年8月23日
发表者：吴军，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，微软才对他从人力物力上给于了巨大的支持，使得布莱尔成为微软搜索研究的领军人物之一。在研究方面，布莱尔有时不一定能马上找到应该怎么做，但是能马上否定掉一种不可能的方案。这和他追求简单的研究方法有关，他能在短时间内大致摸清每种方法的好坏。
由于布莱尔总是找简单有效的方法，而又从不隐瞒自己的方法，所以他总是很容易被包括作者我自己在内的很多人赶上和超过。好在布莱尔很喜欢别人追赶他，因为，当人们在一个研究方向超过他时，他已经调转船头驶向它方了。一次，艾里克对我说，有一件事我永远追不上他，那就是他比我先有了第二个孩子 ：）
在接下来了系列里，我们还会介绍一个繁与简结合的例子。
没有最高的山峰 — Google 全球编程挑战赛报名开始
2006年8月17日
发表者：陶宁，Google （谷歌）员工
第四届 Google（谷歌）全球编程挑战赛（Google Code Jam）已于 8 月 15 日正式开锣，与年初在国内举行的 Google（谷歌）中国区编程挑战赛不同，此次比赛面向全球开放、全球所有感兴趣程序员均可报名参加。
《没有最高峰》（Ain’t No Mountain High Enough），一首我们 Googler 很喜爱的歌，每当音乐响起，都有一种要奔跑、想跳跃的激动。我们希望，Google（谷歌）编程挑战赛也能为所有参与者带去同样充满热情、兴味盎然、孜孜 以求的激动。
现在，报名已经开始，北京时间 9 月 6 日，注册通道就会关闭。与此同时，第一回合资格赛将拉开帷幕，10 月 28 日全球进入前 100 名的选手会在 Google（谷歌）的全程赞助下聚集纽约分部展开终极PK。
此次 Google（谷歌）全球编程挑战赛的奖品非常丰厚，除全程赞助 100 名选手参加决赛外，冠军将获得 10,000 美元奖金，而所有进入决赛的选手最少也会获得 750 美元奖金。
Google（谷歌）全球编程挑战赛 2003 年首次举办，四年来，全球平台和独特的互动式 PK 赛制使它迅速成为全球编程员最热衷参与的世界级编程大赛之一，几年来，参赛选手数量成倍增长。
近年来，中国选手在这一国际赛事中的技术水平和比赛成绩也不断提高。
想与世界上最优秀的程序员一决高下吗？登录
www.google.com/codejam2006
看看今年年初 Google（谷歌）中国区编程挑战赛的花絮：
Google 实习拾趣
2006年8月13日
发表者：华宇，Google 中国工程研究院实习生
来 Google 实习了一个月了，一些趣事记录如下--
最受欢迎的人 —— 饭 Host
Google 的每位实习生都有一位工程师作为他/她的 Host，负责带领实习生参与项目，当然还要管饭。吃饭是很重要的，特别是咱中国人。吃饭也很有讲究，有的 Host 比较喜欢带大家去食堂吃，也有 Host 喜欢带大家去餐馆吃。我们是实习生，是公司最重要的人物，肩负着体验公司文化、传播公司理念的重任，当然要去餐馆享用美食 (上岛咖啡凑合，全聚德最好:-)。跟错 Host 的实习生吃完食堂回来无奈之余，只好想尽各种办法诱导 Host 去餐馆。
第一招是吹耳边风。每当要吃饭的时候，就不停的跟 Host 说其他组的实习生又去了某餐馆啦，食堂菜太差啦等等。谁知道 Host 说：“天将降大任于斯人也，必先...饿其体肤...。”
第二招是打时间差。由于楼下公共食堂每天中午 12:40 点左右就差不多关了，因此只要拖到 12:30 大家还没下楼，就只好委屈一点去餐馆啦！结果 Host 上了一回当之后，每天不到 12:20 跑过来叫大家“咱们快走，食堂就要关门了”...
两次铩羽而归的实习生们并没有放弃，秉承着“如果不能打败他，就离开他”的理念，拿出了最后的必杀技！实习生们的原则是，“谁去餐馆，谁就是我的 Host。”于是每次饭前可以看到，少数几个从不去食堂的 Host 的座位旁，挤满了从其他组前来蹭饭的实习生们，那人是相当地多啊。于是这几位 Host 很荣幸地被大家评为“饭 Host”，就是每到饭前他们就成为我们的 Host。
老大的照片
我在的项目组有三个员工。我刚进项目组的那会儿，两个员工每天工作到晚上 12 点，而另外一个员工——我们的老大，正在太平洋某小岛上结婚。人生大事自然是第一位的，所以另外两个员工也毫无怨言。几天后老大带着满脸的幸福回来，带回一堆照片。照片的展示方式比较特别。老大用
Google Earth
写脚本做了一个视频，演示他们在地球上从一个地方飞到另外一个地方，每飞到一个地方就放映在这个地方拍摄的照片，从国内到国外，从年幼到成熟，从相识到相知…… 配上音乐，这个长达半个小时的视频楞是让老大放了七八遍，一拨人看完又来一拨。看得我都想结婚了...
存在即合理
Google 的工程师干活最常用是 VIM、Emacs 和 Eclipse。用 VIM 或 Emacs 的人占多数，用 Eclipse 人较少。于是少数派经常遭到众人鄙视。少数派认为，存在即合理，因此用 Eclipse 是合理的。众人认为，存在即合理，因此众人的鄙视是合理的。
程序员的冲动
我实在太喜欢 C++ 了。每当打开一个空白文档，手指有一种莫名的冲动，会不由自主地键入"#include
"。
一些好玩的 Google Talk 签名
“爱生活， 爱 Coding”
“早起修 Bug， 一天工作都有劲”
“每一个整洁的接口背后都有一个龌龊的实现”
“自从咱用了 Unit Test,，腰不酸了，背不痛了，腿也不抽筋了”
“珍爱小拇指，远离 Emacs”
数学之美 十四 谈谈数学模型的重要性
2006年8月9日
发表者：吴军，Google 研究员
[注：一直关注数学之美系列的读者可能已经发现，我们对任何问题总是在找相应的准确的数学模型。为了说明模型的重要性，今年七月份我在 Google 中国内部讲课时用了整整一堂课来讲这个问题，下面的内容是我讲座的摘要。］
在包括哥白尼、伽利略和牛顿在内的所有天文学家中，我最佩服的是地心说的提出者托勒密。虽然天文学起源于古埃及，并且在古巴比伦时，人们就观测到了五大行星（金、木、水、火、土）运行的轨迹，以及行星在近日点运动比远日点快。（下图是在地球上看到的金星的轨迹，看过达芬奇密码的读者知道金星大约每四年在天上画一个五角星。）
但是真正创立了天文学，并且计算出诸多天体运行轨迹的是两千年前古罗马时代的托勒密。虽然今天我们可能会嘲笑托勒密犯的简单的错误，但是真正了解托勒密贡献的人都会对他肃然起敬。托勒密发明了球坐标，定义了包括赤道和零度经线在内的经纬线，他提出了黄道，还发明了弧度制。
当然，他最大也是最有争议的发明是地心说。虽然我们知道地球是围绕太阳运动的，但是在当时，从人们的观测出发，很容易得到地球是宇宙中心的结论。从地球上看，行星的运动轨迹是不规则的，托勒密的伟大之处是用四十个小圆套大圆的方法，精确地计算出了所有行星运动的轨迹。（托勒密继承了毕达格拉斯的一些思想，他也认为圆是最完美的几何图形。）托勒密模型的精度之高，让以后所有的科学家惊叹不已。即使今天，我们在计算机的帮助下，也很难解出四十个套在一起的圆的方程。每每想到这里，我都由衷地佩服托勒密。一千五百年来，人们根据他的计算决定农时。但是，经过了一千五百年，托勒密对太阳运动的累积误差，还是差出了一星期。
地心说的示意图，我国天文学家张衡的浑天地动说其实就是地心说。
纠正地心说错误不是靠在托勒密四十个圆的模型上再多套上几个圆，而是进一步探索真理。哥白尼发现，如果以太阳为中心来描述星体的运行，只需要 8-10 个圆，就能计算出一个行星的运动轨迹，他提出了日心说。很遗憾的事，哥白尼正确的假设并没有得到比托勒密更好的结果，哥白尼的模型的误差比托勒密地要大不少。这是教会和当时人们认为哥白尼的学说是邪说的一个原因，所以日心说要想让人心服口服地接受，就得更准确地描述行星运动。
完成这一使命的是开普勒。开普勒在所有一流的天文学家中，资质较差，一生中犯了无数低级的错误。但是他有两条别人没有的东西，从他的老师第谷手中继承的大量的、在当时最精确的观测数据，以及运气。开普勒很幸运地发现了行星围绕太阳运转的轨道实际是椭圆形的，这样不需要用多个小圆套大圆，而只要用一个椭圆就能将星体运动规律描述清楚了。只是开普勒的知识和水平不足以解释为什么行星的轨道是椭圆形的。最后是伟大的科学家牛顿用万有引力解释了这个问题。
故事到这里似乎可以结束了。但是，许多年后，又有了个小的波澜。天文学家们发现，天王星的实际轨迹和用椭圆模型算出来的不太符合。当然，偷懒的办法是接着用小圆套大圆的方法修正，但是一些严肃的科学家在努力寻找真正的原因。英国的亚当斯和法国的维内尔（Verrier）独立地发现了吸引天王星偏离轨道的海王星。
讲座结束前，我和 Google 中国的工程师们一同总结了这么几个结论：
１. 一个正确的数学模型应当在形式上是简单的。（托勒密的模型显然太复杂。）
２. 一个正确的模型在它开始的时候可能还不如一个精雕细琢过的错误的模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去。（日心说开始并没有地心说准确。）
３. 大量准确的数据对研发很重要。
４. 正确的模型也可能受噪音干扰，而显得不准确；这时我们不应该用一种凑合的修正方法来弥补它，而是要找到噪音的根源，这也许能通往重大发现。
在网络搜索的研发中，我们在前面提到的单文本词频/逆文本频率指数（TF/IDF) 和网页排名（page rank)都相当于是网络搜索中的“椭圆模型”，它们都很简单易懂。
怎样使用 Google 帮助中心，解决您的问题？
2006年8月8日
发表者：产品支持小组一成员
经常有朋友问我，你在 Google 做什么？ 当听说我的工作是用户支持（User Support）的时候，更多的问题就接踵而至了：Google 的产品不大都免费的吗？免费产品也提供技术支持？ 你们提供中文支持服务吗？ 你们接听用户电话吗？…… 不一而足。而我每次看到Google 爱好者们满怀热情和期待，写了洋洋洒洒上千字的邮件向我们提出有关 Google 产品方面的建议或使用时的问题，却因发错了地方而无法得到及时的回复，我都会感到很遗憾。所以就会有提笔写一篇向广大中国用户介绍如何使用
Google 用户帮助中心
的文章的冲动。现在终于可以借 Google 中国黑板报来与大家探讨这个问题了。
什么是帮助中心？
Google 目前在中国正式发布的中文产品包括
Google 网页搜索
、
Google 工具栏
、
Google 桌面
等等，我们还在不断努力为中国用户提供更多的产品。
对于已经发布的所有产品，我们都分别为它们建立了“
帮助中心
”。帮助中心中的内容一般包括：使用入门、功能介绍、疑难问题解答等。我们的理想目标是能够在帮助中心里提供尽可能多的信息，让用户能够“自己动手，丰衣足食”。因此，当您遇到问题的时候，我们的建议是，先“探索”一下我们的帮助中心吧。如果您能够在帮助中心的帮助下自己解决问题，是不是很有成就感呢？ 而且这也给我们发邮件并等我们回复要快捷得多。当然，如果您实在找不到答案，或者您遇到的问题非常棘手，您也可以很容易地通过发送电子邮件
与我们联系
（我们不提供电话服务）。
如何使用 Google 帮助中心？
要进入某个 Google 产品的帮助中心其实很简单，您只需在浏览器窗口中输入
www.google.cn/support
就可以进入 Google 帮助中心的中文页面，在该页的右下角，您可以看到常用的 Google 不同产品帮助中心的链接。点击链接，就可以进入相应产品的帮助中心。
如果某个产品没有出现在帮助中心首页，还有一种方法，那就是从Google 主页先进入该产品的页面，然后该页面右上角点击进入“帮助”的链接就可以了。
我们现在举个例子，如果您想了解有关 Google 工具栏的信息， 就请在 www.google.cn/support 页面的右下角点击“
工具栏
”链接。或者，在 google.cn 中点击 “
更多
”，然后选择“工具栏”，在进入“工具栏”页面之后，找到“帮助”链接，然后点击它就能进入 Google 工具栏的帮助中心了。
可能有人会抱怨：嗯，要我自己在帮助中心里寻找答案，那简直象大海捞针一样，该有多麻烦啊。不用担心，可别忘了，Google 最擅长的是搜索，这一技术当然也要在我们的帮助中心上加以应用了。看到位于帮助中心页面右方的“搜索工具栏帮助的搜索框了吗? 下面我就以 Google 桌面的帮助中心为例，来告诉大家如何在帮助中心中寻找问题的答案。
例如，如果您想知道如何在 Google 桌面中搜索 PDF 文件。您只要简单地在帮助中心上的搜索框中输入搜索条件“PDF”，按一下回车键，您就会看到在此帮助中心上所有
与“PDF”相关的内容
：
从这个列表中选取最接近您问题的链接，点击进入，这样就可以找到答案了。
在下面的
网址中
包含一些缩小搜索范围的小窍门，好好运用这些小窍门吧，您的搜索将更有效率： http://www.google.cn/intl/zh-CN//help/refinesearch.html
如何与我们联系？
如果您在帮助中心上逛了半天，也尝试了用不同的关键字进行搜索，但仍找不到答案，或者您遇到的问题比较复杂（比如说，您的电脑有特殊配置），或者您有话想对我们说，您可能就需要给我们发邮件了。在帮助中心的很多页面上，我们都设置了“
与我们联系
”的链接。点击这些链接，您将被要求进行一些选择或回答一些问题，这是为了帮助我们能够更具体地了解您所遇到的问题，然后您就可以发送邮件给我们了。请注意，您可千万别对这些选项或问题感到不耐烦，您提供的信息越精确详细，就越能帮助我们尽快找到问题的原因从而更准确地答复您。如果您要反映的问题不在我们提供的问题列表中，您就要在列表下方的问题说明框中详细描述您所遇到的困难以及您所使用的设备的基本情况了。
在完成了这一步骤后，轻轻按一下“提交”，您就已经完成了给我们发送邮件的步骤了。接下来，请耐心等待，我们会尽快答复您。
您可能会问……
尽管我在上面已经简单介绍了有关如何使用帮助中心以及给我们发送邮件的方法，但您可能还会问一些问题，例如：
“我发了邮件给你们，但是为什么我只收到了一封自动回复呢？”
“我发了邮件，可是你们的回信中只是问我更多的问题呢？”
“为什么你们说不清楚我邮件中所反映的问题呢？”
……
事实上，尽管我们努力最大限度地帮助每一位用户，但由于人手有限，人工回答每一封邮件几乎是不可能的，因此，我们下了很大的功夫打造我们的帮助中心。对于一般的问题，例如 “如何使用某某功能”、“安装某项Google 产品的系统需求”、“如何安装”、“如何卸载”等等，帮助中心上都有答案。因此，对于这类问题，我们一般会发送一封自动回复邮件给您，将帮助中心的网址提供给您，以便您寻找答案。
请注意，如果您遇到比较复杂的问题，例如在安装了某 Google 软件后系统出现一些问题(尽管这相当少见) ，您在给我们发送邮件时，请尽可能地将您所遇到的问题进行详细描述，并告诉我们您的电脑系统状况等等。如果您在第一封邮件中就能提供给我们足够的信息，那么，我们可能用一封邮件就能解决您所遇到的问题，这样就大大节省了您的宝贵时间。当然，如果您提供的信息不完全，我们还是会发邮件向您进一步询问的。
您也许觉得难以置信，但事实上，我们常常会看到一些让我们摸不着头脑的邮件，例如“电脑玩不转了”等等。这时，我们就只好告诉用户：我们不完全明白您的要求，请您向我们发送一些更详细的信息。但是这样一来，在邮件的往复中，时间不知不觉地可能已经过了好几天了。
您也可以帮助别人
我们知道，在 Google 爱好者中有很多电脑高手（您也许就是其中之一）。有些用户对于 Google 产品的精通程度甚至不亚于我们，还有些用户可能遇到过一些问题，但是通过自己的琢磨或我们的帮助最后解决了问题。为了给这部分用户提供一个分享经验和知识 的平台，我们创立了
Google 用户论坛
。 因此，您大可以常到论坛看看 ，看看最近的热点问题是什么。如果您恰巧知道答案，您不妨告诉大家。如果您有问题，您也可以在这里提问，说不定哪位热心的“大侠”立刻就能帮您解决。 希望大家在能够在这里广交朋友，多多交流，提高水平 。
最后，请注意，如果您有关于其他 Google 产品的问题，可千万不要发送到 Google 黑板报。尽管 Google 黑板报已经成为我们与中国用户进行贴心交流的工具，我们也会阅读每一封用户来信，但是我们并不直接回复发送到这里的邮件。因此，您如果有关于 Google 产品方面的问题，还是要到相应产品的帮助中心上提交才行。
数学之美 系列十三 信息指纹及其应用
2006年8月3日
发表者：吴军，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 以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌， 因为这和黑客能真正攻破你的注册信息是还两回事。
信息指纹的虽然历史很悠久，但真正的广泛应用是在有了互联网以后，这几年才渐渐热门起来。
用 Google 趋势，看看这个世界都在想什么？
2006年7月31日
发表者：吴丹丹，黑板报小组
今天是 7 月的最后一天，也是中国人的“情人节”七夕节，Google 中国发布了其
Google Trends （谷歌趋势）
的中文版本，目前您在
Google 实验室
里可以看到。其实 Google Trends（谷歌趋势）对中国的用户来说并不陌生，它是在今年的 5 月 11 日的 Google 全球媒体日 (Google Press Day) 上正式发布的，一经发布就在国内的 Google 用户中引起了不小的反馈，很多用户都在
自己的博客
中表达了喜爱之情。
今天发布的 Google 趋势中文版是完整功能的版本，包括界面的中文化和新闻文章引用，使大家可以更有深度的了解国人搜索的趋势。
比如您要比较“王菲”和“张曼玉”在 Google 上被搜索的趋势，只要在搜索框里输入“
王菲，张曼玉
”，然后点击“搜索趋势”。出现的结果页上如下：您可以看到如股票曲线图般的“搜索趋势记录图”，位于趋势记录图上方的曲线表示在 Google 上关于“王菲”和“张曼玉”各自的搜索量趋势，位于趋势记录图下方的是新闻引用量图表，表示她们分别在 Google 新闻中的出现次数。如果发现关于“王菲”和“张曼玉”的新闻引用量出现峰值，Google 趋势会在图表中进行标记，然后自动选择新闻文章发表时间接近该峰值的一篇 Google 新闻稿件，并显示其标题。
在图表的下方你可以看到“王菲”和“张曼玉”搜索趋势分布图：即在哪些城市、国家/地区、语言中最受关注，被搜索的最多。我们看到对“王菲”关注最多的是西安、天津和重庆...
当然，Google 趋势的使用还有一些小技巧，比如你要了解有多少搜索包含“新浪”和“Sina”其中的任意之一，只需使用竖线（"|"）将其分隔，即“
新浪| Sina
”。还有，如果你要从搜索结果中排除字词，可使用减号。例如，若要了解多少搜索包含"王菲"但不包含"李亚鹏"，你可以输入“
王菲 - 李亚鹏
”。需要注意的是当您使用上述任一个符号时，Google 趋势将仅显示搜索量图表，右边的新闻引用部分尚不支持高级功能。
好吧，看看中文版的 Google Trends（谷歌趋势）能给我们带来多少新奇又好玩的体验。
“中国之最”大起底
用 Google Trends（谷歌趋势）做分析和调查是最恰当不过，而基于全球中文搜索数据基础的 Google Trends（谷歌趋势）更是全球中文用户的共同平台，从中我们可以看到很多或者有趣的现象。
最快乐的人
：谁是中国最快乐的一群人呢？来自温州的朋友独占鳌头，而且还把第二位，同时也是最追求“幸福”的人杭州远远的甩在后面。
最让人留恋的节日
：这个人群恐怕就是正在看这篇文章的广大网民了，虽然根据调查，我国的网民结构是绝对的年轻人占主导，但这些网民似乎更关注比自己小的多的孩子们，因为搜索“六一儿童节”的远远超过了搜索“五四青年节”的人，不知道是不是大家都想回到童年时光而对“六一儿童节”恋恋不舍呢？
最爱玩的城市
：有钱又有闲的感觉的确不错，上海、北京、深圳三地的朋友可算是国内旅游市场当仁不让的三甲之选，想到每年黄金周的时候万人齐旅游，火车飞机齐出动的壮观场景，就可见 Google Trends（谷歌趋势）的所言非虚。
最爱血拼购物的城市
：有爱玩的就一定会有爱购物的，北京，上海，天津，深圳四地的朋友们可算是拉动内需的强大力量了，他们是国内最爱“购物”的人了，虽然购物欲望强烈但却也懂得持家有道，所以这四个城市同时也入选了“最爱打折”城市的前五强。
最具创业激情的地方
：这个选项多少有些出乎意料，原来想象中的创业热土北京和上海止步于十强之外，而中国最具创业激情的五大城市则是南京、南昌和苏州，老牌创业城市深圳和广州也跻身五强，看来这里依然是无数创业者所钟爱的地方。十强中北方的济南，南方的成都，中部的长沙，看来中国处处都涌动着创业的激情和梦想。
最众口不再难调的菜肴
：众口不再难调这句话在川菜的面前就不再正确了，无论是曾经火爆一时的水煮鱼、香辣蟹还是经典的火锅小炒，川菜在国内可谓所向披靡，无往而不利，几乎受到了全中国普罗大众的共同欢迎，不仅把传统的粤菜，鲁菜，本帮菜，苏杭菜打得“落花流水”，就算是同是以酸辣为味的湘菜和黔菜也得甘拜下风。川菜，似乎成了无可争议的菜肴天下第一。
最小资化的城市
：什么是小资最喜欢的呢？泡吧，K 歌还有咖啡、西餐厅，在这些项目上，被称为“东方巴黎”的上海果然不负众望，分别获得了“最喜欢
酒吧
”的城市，“最喜欢
卡拉OK
”的城市，与此同时，它在“最关注留学”“咖啡”和“西餐厅”等项目的 PK 中都有上佳表现，同时这里也是最青睐国际名品的地方，上海也是全球搜索
LV
中排名最高的大陆城市，看来，小资早已经是海派风格的一部分了。
老百姓最关注的头等大事
：买房子，恐怕是现在很多中国老百姓的关注的头等大事，所以无论是“买房”、“二手房”都是搜索量居高不下，而且地域分布广泛，不分南北东西，就连买房后的头等大事，“
装修
”也成为了老百姓最关注的关键词。看来，“买房置地”这件老百姓几千年来的头等大事，今日依然。
最温馨的 PK 结果
：选择情人节和母亲节的 PK 多少有些担心，曾经以为似乎受到更多关注的情人节会大胜并不流行的母亲节，但结果却让人出乎意料，刚刚被人们所了解的母亲节在很多城市与情人节不相上下，而且地域遍布全国。由此想到了那句老话，母爱，是天底下最大的爱。所有人都应该感谢母亲，感谢母爱。
也许对从事营销的人来说，
Google Trends（谷歌趋势）
可以把握市场趋势，预测消费走向，；对社会学者来说它观察社会动态，体察民间热点；而对我们所有的用户而言，Google Trends（谷歌趋势）是一款虽然很小，但很有趣很好玩的产品。如果你喜欢，那就到 Google Trends（谷歌趋势）上去试试，有了什么新发现，一定要与大家分享。
Google 工程师文化 -- 互助篇
2006年7月21日
发表者：吴颉，Google 工程师
一年多前，因为 Google 的飞速成长，公司曾做过一个工程师们对公司各方面满意程度的调查。记得公布汇总结果的时候有这么两条：
先公布的是大家最满意的一点:
-- 同事们真是太友好了，我可以随时向同事提问题，他们总是及时地给予帮助。
紧接着公布的是大家最抱怨的一点：
-- 新人实在是太多了，我总是被问题打断，白天没法集中精力干事，只有晚上才能干些事。
不禁引得哄堂大笑。 显然，对同样的问题，不同的角度有不同的结论。
不过抱怨归抱怨，同事们依然很耐心。为了增进工作效率，许多项目负责人或者有各种经验的员工，建立了各种常见问题答疑录（FAQ)， 起到了知识共享、承前启后的作用。 大家还自发地建立了各种各样的邮件列表作为帮助热线， 以便针对性地答疑。大家都知道，有时“不耻下问”是解决问题的最好办法；今天你是提问者，明天你就可能回答别人的提问。
有一个邮件列表是针对“项目设计文件”（Design Document)的。 产品开发前， 工程师们会向这个邮件列表征询关于项目设计文件的意见反馈。 公司的第一名雇员 Craig, 至今依然常会在百忙之中给各种项目设计文件提出细致的、建设性的意见，用他丰富的开发经验给项目把把关。当然，据说 Craig 是那种能够一边用键盘写着流畅的电子邮件，一边当面与你对答的“一心二用”的专家，非一般人可比。
有一次，我一天内连续两次麻烦 Michael （一位编译器方面的内行） 关于某个特定版本编译器的一些特殊细节。 Michael 不厌其烦，热心地帮我寻找解决方案。 由于 Michael 在纽约办公室，许多技术细节只能通过电子邮件来交流。我最后告诉他问题解决了，向他表示感谢。Michael 在电子邮件里只回复了一个词：
W00t
!
哎，又是一个看不懂的词。 我还是 Google 了一下才知道这位工程师是很高兴能够帮我解决问题。
我曾经通过问问题，结识了不少优秀的工程师，学习到了很多技术知识。后来，我负责的系统日渐成熟，我也有了自己撰写的 FAQ,有机会回答同事们这一方面的问题。我想，许多人都是在被帮助中和帮助人中感受快乐吧。
数学之美 系列 12 - 余弦定理和新闻的分类
2006年7月20日
发表者：吴军，Google 研究员
余弦定理和新闻的分类似乎是两件八杆子打不着的事，但是它们确有紧密的联系。具体说，新闻的分类很大程度上依靠余弦定理。
Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻，它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点，我们需要想办法用一组数字来描述一篇新闻。
我们来看看怎样找一组数字，或者说一个向量来描述一篇新闻。回忆一下我们在“
如何度量网页相关性
”一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有实词，我们可以计算出它们的单文本词汇频率/逆文本频率值（TF/IDF)。不难想象，和新闻主题有关的那些实词频率高，TF/IDF 值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如，词汇表有六万四千个词，分别为
单词编号 汉字词
------------------
1 阿
2 啊
3 阿斗
4 阿姨
...
789 服装
....
64000 做作
在一篇新闻中，这 64,000 个词的 TF/IDF 值分别为
单词编号 TF/IDF 值
==============
1 0
2 0.0034
3 0
4 0.00052
5 0
...
789 0.034
...
64000 0.075
如果单词表中的某个次在新闻中没有出现，对应的值为零，那么这 64,000 个数，组成一个64,000维的向量。我们就用这个向量来代表这篇新闻，并成为新闻的特征向量。如果两篇新闻的特征向量相近，则对应的新闻内容相似，它们应当归在一类，反之亦然。
学过向量代数的人都知道，向量实际上是多维空间中有方向的线段。如果两个向量的方向一致，即夹角接近零，那么这两个向量就相近。而要确定两个向量方向是否一致，这就要用到余弦定理计算向量的夹角了。
余弦定理对我们每个人都不陌生，它描述了三角形中任何一个夹角和三个边的关系，换句话说，给定三角形的三条边，我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为 a, b 和 c，对应的三个角为 A, B 和 C，那么角 A 的余弦 --
如果我们将三角形的两边 b 和 c 看成是两个向量，那么上述公式等价于
其中分母表示两个向量 b 和 c 的长度，分子表示两个向量的内积。举一个具体的例子，假如新闻 X 和新闻 Y 对应向量分别是
x1,x2,...,x64000 和
y1,y2,...,y64000,
那么它们夹角的余弦等于，
当两条新闻向量夹角的余弦等于一时，这两条新闻完全重复（用这个办法可以删除重复的网页）；当夹角的余弦接近于一时，两条新闻相似，从而可以归成一类；夹角的余弦越小，两条新闻越不相关。
我们在中学学习余弦定理时，恐怕很难想象它可以用来对新闻进行分类。在这里，我们再一次看到数学工具的用途。
Google 的工程师文化 -- T恤篇
2006年7月14日
发表者：吴颉，Google 工程师
工程师们最喜爱的服装莫过于 T 恤。 一件"酷"的 T 恤， 会引来路人许多羡慕的目光。前面
郑群的博客
中提到， Google经常有免费的 T 恤，不过 T 恤柜里发放的都是几种常见的样式。 这里我来谈谈一些特殊的 T 恤版本。
新产品的发布:
大家辛辛苦苦地工作了数月， 到了产品发布的日子， 庆贺的项目之一常常是一件专门设计的T恤。 这既鼓舞士气， 又是给产品做广告。 穿着这样一件特殊版本的T恤走在公司里，大街上，可以自豪地告诉同事、亲朋：瞧，我参与了这么酷的产品的工作！
Gmail
刚发布的时候, 公司宣布给用户 1 G (1G = 1000 兆) 的免费存储空间。 这在当时是件不可思议的事情， 因为当时雅虎和 MSN 分别只提供 6 兆和 2 兆的存储空间。而 Google 又刻意选在四月一号愚人节这一天发布消息，这让许多用户不知真假，也算是和大家开了个不大不小的玩笑。
为了纪念这件事, 全公司的员工都有幸领到一件写有以下字样的T恤：
“在 2004 年愚人节这一天, Google 给了我 1G 空间。”
(Google gave me a gig. April 1st, 2004)
Google Earth
(Google 地球)发布的时候， T 恤正中印着一个圆圆的地球，四周写着：
“（地球）都 47 亿年了，怎么还是测试版?”
(4.7 billion years, still in Beta?)
不禁博得众人一笑。
节日标志:
Google 主页上经常会变更特殊的节日徽标。比如说，
世界地球日
、
情人节
都曾被搬上过 T 恤。
各种活动:
公司内部经常有各种各样的活动，常常有热心人张罗新的 T 恤版本。
例如，公司定期去各个大学招聘时，热情的校友们会专门提前向 Dennis Hwang (Google 节日徽标的设计者)预订他们的母校版。这里 Google 的徽标经常会被巧妙的改成与学校相关的内容，我至少见过耶鲁和卡耐基梅隆两个版本。
Google 还致力于女性工程师的招聘， 这在前面
王忻的博客
中也曾提到。有一款 T 恤就是专门给女性工程师们设计的。特别值得一提的是， Google 的 T 恤分男女两种，女式的小巧玲珑，不是松松垮垮的，深得女同胞们的喜爱。还曾有 Google 外的女友向我讨要过 Google 的女式 T 恤。
随着 Google 中国的成立，这不，现在我们又增添了 Google 中国谷歌版，Google 中国编程挑战赛版，随着许多优秀的中国工程师的加盟，我们相信，不久我们将会看到更多的具有中国产品特色的版本！
Google 三八妇女节 T-shirt
Google 本地搜索推出146 个城市全屏地图，增加地址搜索、路线规划新功能
2006年7月12日
发表者: 黄靖新，产品经理
Google 本地搜索
最近推出全动态、可拖放的全屏地图，新增全国 146 个城市的具体地址搜索、知名商业网点和旅游景点搜索、点到点路线规划等实用功能。这是我们不断提高用户搜索体验的又一个尝试。
以下是我们对一些常见问题的回答。
问：Google 本地搜索这次变化对用户有什么好处？
Google 本地搜索的更新主要体现在可拖放的全屏动态地图，直观清晰，整合了全国 146 个城市的详细街区地图、道路信息和附近的商业、旅游景点信息和公司黄页信息，使用户一图在手，可以轻松直观地搜寻到全国各个城市的街区街道和周边信息，并轻松规划出行路线。
问：更新后的 Google 本地搜索和其它类似服务相比，有什么独特的地方？
我们新增的地址搜索让用户灵活地搜索已覆盖城市的街区街道，小至胡同和住宅小区，都可以找到。您不妨试试找一下自家或单位的地址。
我们的驾车指南可实现非商家地址的门到门规划（例如，从您家到同事家的路线图），还会象高端车载导航系统一样，详尽告知途经道路名称和行驶细节（例如，提醒驾车司机预先靠左、靠右等）。这是因为我们的数据合作伙伴就是高端车载导航数据的提供商。
另外，在本地商家/服务搜索方面，我们整合了线上和线下的公开信息资源、商家自主上传资源和合作伙伴信息资源，优化了搜索排序的程序。在没有人工干预的情况下，我们的各类本地信息搜索结果较为接近大众认可的真实情况。您可尝试查找“北京附近的商店”（或“北京 商店”）, “上海 公园”，“广州 大学”，“西单 小吃”等。我们会持续努力，为您提供最有参考价值的搜索结果。
问：能举些用户用好本地搜索的实例吗？
本地搜索对用户出行、购物、娱乐、饮食、办公等都很有帮助。它能抓取整合商家最新发布的动态信息，并快捷地提供给关心的用户。今年的高考刚刚结束，如果你是行将入校的新生，要计划暑期出游、预先摸清校园环境、估算到校园的出租车费用时，不妨试试 Google 本地搜索。
问：有什么使用小诀窍吗？
对一些耳熟能详的地点景点名称，您可以直接搜索，例如“王府井”、“陆家嘴”、“外滩”、“越秀公园”。
进行地址搜索时，如果要查附近的某类信息，就在地址后面空格，然后键入要查的类别名称就好。喜欢直观的用户可键入 “xx 附近的xx” 来查询。
要查路线，最快的方法是点击“驾车指南”小标签，然后输入起止地址。需返程路线，点击“返程”链接即可。
对喜欢快捷键的朋友，试试用键盘的上下左右箭头键，翻上页键、翻下页键、 home 和 end 键，加号（＋）键，减号（－）键，看看是否有适合你的方便用法。
如果您找不到一些熟悉的名称，请在
本地搜索页面
左上角的反馈中告诉我们。
问：Google 本地搜索有卫星图片吗？
Google 本地搜索暂不提供卫星图片。
问：如何了解更详细的产品信息并提供反馈？
您可以参考我们的
帮助中心
或新功能简介，了解更为详细的产品信息。同时欢迎您给我们提供反馈，帮助我们提高，谢谢。
数学之美 系列十一 - Google 阿卡 47 的制造者阿米特.辛格博士
2006年7月10日
发表者：Google 研究员，吴军
枪迷或者看过尼古拉斯.凯奇（Nicolas Cage)主演的电影“战争之王”（Lord of
War)的人也许还记得影片开头的一段话：（在所有轻武器中，）最有名的是阿卡 47( AK47)冲锋枪(也就是中国的五六式冲锋枪的原型），因为它从不卡壳、从不损坏、可在任何环境下使用、可靠性好、杀伤力大并且操作简单。
我认为，在计算机中一个好的算法，应该向阿卡 47 冲锋枪那样简单、有效、可靠性好而且容易读懂(或者说易操作），而不应该是故弄玄虚。Google 的杰出工程师阿米特.辛格博士 (Amit Singhal) 就是为 Google 设计阿卡 47 冲锋枪的人，在公司内部，Google 的排序算法便是以他的名字命名的。
从加入 Google 的第一天，我就开始了和辛格长期而愉快的合作，而他一直是我的一个良师益友。辛格、Matt Cutts（中国一些用户误认为他是联邦调查局特工，当然他不是）、马丁和我四个人当时一同研究和解决网络搜索中的作弊问题（Spam)。我们需要建一个分类器，我以前一直在学术界工作和学习，比较倾向找一个很漂亮的解决方案。我设计了一个很完美的分类器，大约要花三个月到半年时间来实现和训练，而辛格认为找个简单有效的办法就行了。我们于是尽可能简化问题，一、两个月就把作弊的数量减少了一半。当时我们和公司工程副总裁罗森打了个赌，如果我们能减少 40% 的作弊，他就送我们四个家庭去夏威夷度假，后来罗森真的履约了。这个分类器设计得非常小巧（只用很小的内存），而且非常快速（几台服务器就能处理全球搜索的分类），至今运行得很好。
后来我和辛格一起又完成了许多项目，包括对中、日、韩文排名算法的改进。每一次，辛格总是坚持找简单有效的解决方案。这种做法在 Google 这个人才济济的公司常常招人反对，因为很多资深的工程师怀疑这些简单方法的有效性。不少人试图用精确而复杂的办法对辛格的设计的各种“阿卡47” 进行改进，后来发现几乎所有时候，辛格的简单方法都接近最优化的解决方案，而且还快得多。另一条选择简单方案的原因是这样设计的系统很容易查错（debug)。
当然，辛格之所以总是能找到那些简单有效的方法，不是靠直觉，更不是撞大运，而是靠他丰富的研究经验。辛格早年从师于搜索大师萨尔顿(Salton)教授，毕业后就职于 AT&T 实验室。在那里，他和两个同事半年就搭起了一个中等规模的搜索引擎，这个引擎索引的网页数量虽然无法和商用的引擎相比，但是准确性却非常好。在 AT&T，他对搜索问题的各个细节进行了仔细的研究，他的那些简单而有效的解决方案，常常是深思熟虑去伪存真的结果。
辛格非常鼓励年轻人不怕失败，大胆尝试。一次一位刚毕业不久的工程师因为把带有错误的程序推出到 Google 的服务器上而惶惶不可终日。辛格安慰她讲，你知道，我在 Google 犯的最大一次错误是曾经将所有网页的相关性得分全部变成了零，于是所有搜索的结果全部是随机的了。这位工程师后来为 Google 开发了很多好的产品。
辛格在 AT&T 时确立了他在学术界的地位，但是，他不是一个满足于做实验写论文的人，于是他离开了实验室来到了当时只有百、十人的 Google。在这里，他得以施展才智，重写了 Google 的排名算法，并且一直在负责改进它。辛格因为舍不得放下两个孩子，很少参加各种会议，但是他仍然被学术界公认为是当今最权威的网络搜索专家。2005年，辛格作为杰出校友被请回母校康乃尔大学计算机系在 40 年系庆上作报告，获得这一殊荣的还有大名鼎鼎的美国工程院院士，计算机独立磁盘冗余阵列（RAID)的发明人凯茨(Randy Katz) 教授。
黑板报文章分类
2006年7月6日
发表者：吴丹丹，Google 黑板报小组
最近细心的读者可能会发现我们在右边添加了“黑板报文章分类”一栏，这是因为随着黑板报文章的增多并涉及各个方面，很多读者反映他们翻找文章比较困难。所以我们希望这样的分类，一是方便大家查找浏览黑板报文章，二也使我们的定位更加清晰。
黑板报开办到现在已经快 5 个月了，感谢大家对我们的支持和鼓励。从 2 月份到现在，每篇文章经手，对这个我们公司与用户交流的平台我很有感情。下面就是我这几个月来自己比较喜欢的几篇文章，算是 editor's picks，当然不可能穷尽我都喜欢的文章，但也算有代表性，与大家分享吧。
产品：
怎样用 Google Earth 探索世界杯场馆？
"站在巨人的肩膀上" - Google 杰出工程师谈学术搜索
怎样向 Google 提问?
技术：
谈 Page Rank – Google 的民主表决式网页排名技术
数学之美系列
文化：
自己动手, 丰衣足食(之一)
一地鸡毛
我对女性做工程师的一点看法
其它：
客座博客：有感于谷歌中文图书搜索合作伙伴计划
开复的北京美食篇
数学之美 系列十 有限状态机和地址识别
2006年7月5日
发表者：吴军，Google 研究员
地址的识别和分析是本地搜索必不可少的技术，尽管有许多识别和分析地址的方法，最有效的是有限状态机。
一个有限状态机是一个特殊的有向图（参见有关
图论的系列
），它包括一些状态（节点）和连接这些状态的有向弧。下图是一个识别中国地址的有限状态机的简单的例子。
每一个有限状态机都有一个启始状态和一个终止状态和若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件。比如，在上图中，当前的状态是“省”，如果遇到一个词组和（区）县名有关，我们就进入状态“区县”；如果遇到的下一个词组和城市有关，那么我们就进入“市”的状态，如此等等。如果一条地址能从状态机的起始状态经过状态机的若干中间状态，走到终止状态，那么这条地址则有效，否则无效。比如说，“北京市双清路83号”对于上面的有限状态来讲有效，而“上海市辽宁省马家庄”则无效（因为无法从市走回到省）。
使用有限状态机识别地址，关键要解决两个问题，即通过一些有效的地址建立状态机，以及给定一个有限状态机后，地址字串的匹配算法。好在这两个问题都有现成的算法。有了关于地址的有限状态机后，我们就可又用它分析网页，找出网页中的地址部分，建立本地搜索的数据库。同样，我们也可以对用户输入的查询进行分析，挑出其中描述地址的部分，当然，剩下的关键词就是用户要找的内容。比如，对于用户输入的“北京市双清路附近的酒家”，Google 本地会自动识别出地址“北京市双清路”和要找的对象“酒家”。
上述基于有限状态机的地址识别方法在实用中会有一些问题：当用户输入的地址不太标准或者有错别字时，有限状态机会束手无策，因为它只能进行严格匹配。（其实，有限状态机在计算机科学中早期的成功应用是在程序语言编译器的设计中。一个能运行的程序在语法上必须是没有错的，所以不需要模糊匹配。而自然语言则很随意，无法用简单的语法描述。）
为了解决这个问题，我们希望有一个能进行模糊匹配、并给出一个字串为正确地址的可能性。为了实现这一目的，科学家们提出了基于概率的有限状态机。这种基于概率的有限状态机和离散的马尔可夫链（详见前面关于
马尔可夫模型
的系列）基本上等效。
在八十年代以前，尽管有不少人使用基于概率的有限状态机，但都是为自己的应用设计专用的有限状态机的程序。九十年代以后，随着有限状态机在自然语言处理的广泛应用，不少科学家致力于编写通用的有限状态机程序库。其中，最成功的是前 AT&T 实验室的三位科学家，莫瑞（Mohri）, 皮瑞尔（Pereira） 和瑞利（Riley）。他们三人花了很多年时间，编写成一个通用的基于概率的有限状态机 C 语言工具库。由于 AT&T 有对学术界免费提供各种编程工具的好传统，他们三人也把自己多年的心血拿出来和同行们共享。可惜好景不长，AT&T 实验室风光不再，这三个人都离开了 AT&T，莫瑞成了纽约大学的教授，皮瑞尔当了宾西法尼亚大学计算机系系主任，而瑞利成了 Google 的研究员，AT&T 实验室的新东家不再免费提供有限状态机 C 语言工具库。虽然此前莫瑞等人公布了他们的详细算法，但是省略了实现的细节。因此在学术界，不少科学家能够重写同样功能的工具库，但是很难达到 AT&T 工具库的效率（即运算速度），这的确是一件令人遗憾的事。
这个夏天 -- Google (谷歌) 中国工程研究院实习项目正式开始
2006年7月3日
发表者：谷雪梅，Google 工程师
这个星期开始，Google (谷歌) 中国工程研究院第一次招聘的 50 个暑假实习生就要从全国各地到北京，开始为期两个月的工作。这批实习生经过我们层层严格的选拔，可以说，进了实习项目一般有比较好的机会拿到 Google 的正式 offer ，而且这是一个极好的体验公司文化、工作氛围的机会。我们也致力于为实习生提供最好的条件和体验，希望实习能成为大家一段难忘的经历。我想没有什么比亲身体会 Google 更有说服力的吧。:)
在硅谷总部的时候，觉得带实习生实在是件简单不过的事。春天温暖的下午，工程师们吃着冰激淋筛选简历，然后两轮面试，再写个项目计划，之后等着实习生在五、六月间出现就好了。所以当今年三月在北京被告知我们要开始 Google 中国工程研究院的暑期实习计划的时候，第一个出现在脑海里的就是哈根达斯冰激淋......
可惜，冰激淋并没有出现。
对 Google (谷歌)文化有所了解的人都知道，这是一个几乎任何事情都必须自力更生的地方。在北京，我们工程师资源还没有那么多，不可能给所有投简历的学生做面试。那么笔试？几番辩论之后决定下来，然后就是出笔试题，既要考基本的算法和编程，又要大家没见过；既要有挑战性，也要让优秀的学生在有限的时间之内答出来，而且需要的答案还不能太长，否则没时间判卷了。前后出了很多版本，累坏了我们的工程师活题库罗青山。
这只是工作一小部分，也是最轻松的一个部分。大学项目组 (University Program) 做了所有其它工作，直到五月中下旬带着工程师到北京、上海、杭州、合肥和西安的各个学校。
这是 Google 实习生项目的第一次笔试，很多细节也没有做得很好。由于英译中出现的偏差和印刷错误，我们的选择题没能非常真实地反映学生的水平。 5 月 23 号晚上，在上海结束笔试后，我们十来个人推翻了本来的判卷规则，决定把所有学生的编程和算法题都看一遍，而选择题只作为参考。本来最喜欢问算法复杂度的一群人也忘了批改 400 份试卷的复杂度是多少，于是从深夜 11 点起开始工作; 可是不久以后，复杂度又上升了，因为大家决定优秀的试卷要有第二个人复查。
实习生选拔过程中还有很多小事 —— 在清华，准备的几百份试卷居然不够，我们的工程师不得不在开考前几分钟气喘吁吁地跑去复印。在上海交大，校园里没有出租车，从光彪楼抱着将近两百份试卷走到校门口，实在是锻炼臂力和耐力的好机会。
过程虽然辛苦，但也有不少乐趣。
25 日下午，郑欣和我非常幸运，4 个面试学生里有三个实力超强，其中还有一位 15 岁上大学的少年大学生。面试之前看他的成绩单，好像体育不太好。问他是怎么回事，他很委屈地觉得让一个本来该上初三的学生达到大一的体能标准非常不合理。
一天后，我们的另一位工程师方坤面哭了一个学生。他说学生前一分钟还在微笑，然后就对着题目掉下了眼泪。我们批评他后知后觉，他倒觉得自己很无辜。
又过了一天，还是方坤，遇上一位“霸王面”，自己从同学那里得知我们的酒店地址，就跑过来要求被面试。方坤礼貌地说，规则不能被打破，因为要对其他同学公平，但是我们可以聊一聊。之后我们几次说起这位同学，虽然不鼓励这样的霸王面，但是，他的热情和执著精神令人非常感动。
同时进行的是实习项目的选定，开复给我的意见是要民主，要所有工程师一起决定。自下向上(bottom up) 本来就是我们的习惯，所以没费什么力气就决定由每个工程师提出实习项目，然后通过投票方式选出前 20 个给实习生做。
我们开通了一个内部网页，让大家上传自己的实习项目。没有两个星期，该页面已经布满了 40 多个项目。说好某个星期五下午是截止日期，但出于疏忽，我忘了把页面锁好，结果两天以后又多了十几个。开复两个月前还担心我们没有足够多、足够有趣的项目给实习生做，现在好了，大家挤破头，为 50 名实习生准备了 60 个项目，很多提交人在项目后面都列上该项目的优点，有人洋洋洒洒写了若干条，不遗余力地“做广告”。
曾经在 UCSB 任职的张智威教授 (Edward Chang)加入 Google (谷歌)中国后是 engineering director，但也不得不参加了项目竞标。人在总部的他有好几次发来长长的邮件，说明项目的重要性，对 Google 未来的巨大影响，还不厌其烦地给我们讲项目的具体实施，以确保项目的入围。
投票那天，洪峰刚好要到浙大给讲座，临上飞机前 40 分钟打电话到投票的会议室，机场广播声作为背景辉映着他的讲话。几个在总部的工程师和项目经理也打电话过来，当时已经是那边的深夜，其中工程师吴颉居然从头坚持到尾，下线的时候已经是美国的凌晨 3 点。在会议室里，大家讨论相当激烈，有时候，哪怕项目提议人被问得无话可说，也会有其他工程师跳出来，“我来顶一下”，两肋插刀之中还不失公平。平时永远和颜悦色的“老大”不止一次和颜悦色地指出：“我看不出你这个项目有什么好做的。”更不要说我们的“Mr. No” 产品经理 Yuke —— 他的任务之一就是为你的项目泼冷水。
公平投票的好处是结果令大多数人满意，坏处是大家不一定满足你的迫切需求。其中有的人虽然职位相对高一些，提出的项目也都非常重要而急迫，但是同事们只通过了其中的一项，（我的也一样，郁闷中……）。和其它项目相反，洪峰恐怕要高兴坏了，鉴于从机场打电话显示出的真诚和项目的乐趣程度， 32 个投票人里他征服了26 位，荣获第一高票。
在选择实习项目的过程里，很多工程师学到了不少项目管理的知识。原来，大家做项目最重要的出发点就是“酷”，并对Yuke 不停地挑毛病，不停地说 "No" 很不理解。现在面临 60 个项目，要把其中 2/3 都刷掉，大家也必须学会说"不" 。这个项目有意思吗？能做完吗？容易使用吗？用户会喜欢吗？对大多数用户有意义吗？我们的竞争对手会做吗？会做得比我们好吗？每一个过关的项目都要经过这样的挑战，即使洪峰那个得票率超过 80% 的也不例外。
说了这么多面试和实习项目，暑假里最有趣的部分还没有提到。大学项目组为实习生准备了丰富多彩的培训和工余活动—— 丰富多彩到正式员工眼红的地步。不公平啊，为什么我当初没有这样的待遇；我不要当工程师了，退回去做实习生比较好...... 斗争的结果是给实习生的活动大家都可以参加。本来嘛，独乐乐不如众乐乐。
实习生还没有来，我们仍是路漫漫其修远兮。暑假里，30 个带实习生的工程师不仅要准备很详细的项目计划，每两个星期都要做一次审评，还有中期审核和最后的项目演示。
在过去两个月里深深感到，大家的工作热情和团结合作会让 Google (谷歌) 中国工程研究院的第一次实习项目非常精彩。期待着这个火热的夏天。
標籤
编程之夏，UR
创新
创意改善社会 公益温暖中国
促进智能能源利用
大学
谷歌翻译，即时相机翻译，Instant Camera Translation
谷歌十周年系列
谷歌艺术与文化
观妙中国，Shadow Art，智玩皮影
广告
广告安全
互联网，Internet
科技
女性开发者
社会
视频广告
数据中心
数字营销
搜索
网站管理员
文化研究所
艺术计划
音乐搜索
愚人节
增强型广告系列
智能隐形眼镜项目
中小企业
adexchange
Admob
admob sdk
Ads
Adsense
AdWords
android
android m
Android应用开发中国大学生挑战赛
App Inventor
Calendar
cardboard
CES
Chrome
Chrome Web Store
Chrome，Chrome实验
Chrome实验
CI
Code Jam
corporate
Creative
Cross-device
Cultural Institute
culture
Data Center
DevArt
Developer
display
diversity
Doodle
DoubleClick
G+
G2G，Culture
GA&C
gaming
Global Impact Awards
Gmail
Gogle科学挑战赛
Good to Know
Google Ads
Google AdWords
Google Analytics
Google Art Project
Google Arts & Culture
Google Code-in竞赛
Google Demo Day Asia
Google Docs
Google Doodle
Google Drive
Google Drive 云端硬盘
Google Fiber
Google Font
Google for Startups
Google Green
Google I/O
Google Image Search
Google Keep
Google partners
Google Play
Google Science Fair
Google Search
Google Top Contributor Summit
Google Translate
Google Trend
Google Trends
Google Zeitgeist 2012
Google安全系统
Google博士生奖研金
Google翻译
Google奖学金
Google杰出贡献者峰会
Google科学挑战赛
Google网站管理员
Google网站管理员，Webmaster
Google文化研究所
Google在线营销挑战赛
Google中国教育高峰会
IME 输入法
Innovation
Made with Code
maps
mobile ads
mobile ads sdk
Modoo
moonshot
native ads
Nexus
programmatic buying
Project X
Pwn20wn及Pwnium3 黑客大赛
Remarketing. Ads
Search
Security
smb
Solve for X
Street view
student
UR
VR
Web Platform Docs
web security
Webmaster
year in search 2014
YouTube
zeitgeist
博客归档
2026
10月
8月
5月
4月
3月
2月
2025
11月
8月
6月
5月
4月
3月
2024
12月
11月
10月
8月
7月
6月
5月
4月
3月
2月
1月
2023
12月
11月
10月
9月
5月
4月
3月
2月
2022
11月
10月
5月
4月
2月
1月
2021
10月
9月
5月
4月
3月
2月
2020
12月
5月
4月
3月
2019
10月
8月
7月
6月
5月
4月
3月
2018
12月
10月
9月
8月
7月
6月
5月
3月
2月
1月
2017
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2016
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2015
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2014
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2013
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2012
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2011
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2010
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2009
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2008
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2007
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2006
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
Feed
