谷歌研究院（Google）数学之美与浪潮之巅

Google 数学之美 浪潮之巅 吴军 Google研究院 2008年12月30日整理

数学之美 & 浪潮之巅 吴军 Google 研究院 2008 年 12 月 30 日整理 I

目录 Google黑板报 1.数学之美 011 1.1.数学之美系列一一 统计语言模型..1 1.2.数学之美系列二一谈谈中文分词… 5 1.3.数学之美系列三一 隐含马尔可夫模型在语言处理中的应用.9 1.4. 数学之美系列四一怎样度量信息？…13 1.5.数学之美系列五一简单之美：布尔代数和搜索引擎的索引....17 1.6.数学之美系列六一 图论和网络爬虫(Web Crawlers)......... 22 1.7.数学之美系列七一信息论在信息处理中的应用.… 26 1.8.数学之美系列八一 贾里尼克的故事和现代语言处理..…29 1.9.数学之美系列九一 如何确定网页和查询的相关性… 35 1.10.数学之美系列十一有限状态机和地址识别…39 1.11.数学之美系列十一一G0ogle阿卡47的制造者阿米特.辛格博士. 42 1.12.数学之美系列十二一余弦定理和新闻的分类 45 1.13.数学之美系列十三 一信息指纹及其应用.. 49 1.14.数学之美系列十四一谈谈数学模型的重要性.…52 1.15.数学之美系列十五一繁与简自然语言处理的几位精英.… 55 1.16.数学之美系列十六（上）一不要把所有的鸡蛋放在一个篮子里-谈谈最大熵模型 59 1.17.数学之美系列十六（下）一不要把所有的鸡蛋放在一个篮子里-最大熵模型.63 1.18.数学之美系列十七一闪光的不一定是金子-谈谈搜索引擎作弊问题 (Search Engine Anti-SPAM)............67 1.19.数学之美系列十八一矩阵运算和文本处理中的分类问题.…70 1.20.数学之美系列十九一马尔可夫链的扩展贝叶斯网络(Bayesian Networks) 74 1.21.数学之美系列二十一自然语言处理的教父-马库斯…76 1.22.数学之美系列二十一一布隆过滤器(Bloom Filter).........79 1.23.数学之美系列二十二一由电视剧《暗算》所想到的-谈谈密码学的数学原理 82 1.24.数学之美系列二十三一输入一个汉字需要敲多少个键-谈谈香农第一定律87 1.25.数学之美系列二十四一从全球导航到输入法-谈谈动态规划… 91 2.浪潮之巅 … 97 2.1.浪潮之巅第一章一帝国的余辉(AT&T)（一）. 97 2.2.浪潮之巅第一章一帝国的余辉(AT&T)(二) .102

目录 1. 数学之美 ................................................................1 1.1. 数学之美系列一 — 统计语言模型 .................................................. 1 1.2. 数学之美系列二 — 谈谈中文分词 .................................................. 5 1.3. 数学之美系列三 — 隐含马尔可夫模型在语言处理中的应用.................... 9 1.4. 数学之美系列四 — 怎样度量信息?............................................... 13 1.5. 数学之美系列五 — 简单之美：布尔代数和搜索引擎的索引.................. 17 1.6. 数学之美系列六 — 图论和网络爬虫 (Web Crawlers) ...................... 22 1.7. 数学之美系列七 — 信息论在信息处理中的应用................................ 26 1.8. 数学之美系列八 — 贾里尼克的故事和现代语言处理 .......................... 29 1.9. 数学之美系列九 — 如何确定网页和查询的相关性............................. 35 1.10. 数学之美系列十 — 有限状态机和地址识别 ..................................... 39 1.11. 数学之美系列十一 — Google 阿卡 47 的制造者阿米特.辛格博士 ........ 42 1.12. 数学之美系列十二 — 余弦定理和新闻的分类 .................................. 45 1.13. 数学之美系列十三 — 信息指纹及其应用........................................ 49 1.14. 数学之美系列十四 — 谈谈数学模型的重要性 .................................. 52 1.15. 数学之美系列十五 — 繁与简 自然语言处理的几位精英 ...................... 55 1.16. 数学之美系列十六(上)—不要把所有的鸡蛋放在一个篮子里-谈谈最大熵模型 59 1.17. 数学之美系列十六(下)— 不要把所有的鸡蛋放在一个篮子里-最大熵模型.. 63 1.18. 数学之美系列十七 — 闪光的不一定是金子 -- 谈谈搜索引擎作弊问题 (Search Engine Anti-SPAM) ............................................................ 67 1.19. 数学之美系列十八 — 矩阵运算和文本处理中的分类问题..................... 70 1.20. 数学之美系列十九 — 马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks) 74 1.21. 数学之美系列二十 — 自然语言处理的教父 -- 马库斯........................ 76 1.22. 数学之美系列二十一 — 布隆过滤器（Bloom Filter） ....................... 79 1.23. 数学之美系列二十二 — 由电视剧《暗算》所想到的-谈谈密码学的数学原理 82 1.24. 数学之美系列二十三 — 输入一个汉字需要敲多少个键-谈谈香农第一定律 87 1.25. 数学之美系列二十四 — 从全球导航到输入法-谈谈动态规划................. 91 2. 浪潮之巅 .............................................................. 97 2.1. 浪潮之巅第一章 — 帝国的余辉（AT&T)（一） ............................... 97 2.2. 浪潮之巅第一章 — 帝国的余辉（AT&T)（二） ..............................102 I

目录 2.3.浪潮之巅第一章一 帝国的余辉(AT&T)(三) .106 2.4.浪潮之巅第一章一 帝国的余辉 (AT&T)(四) .111 2.5.浪潮之巅第二章 一蓝色巨人(IBM) (-) .114 2.6.浪潮之巅第二章一 蓝色巨人(IBM)(二) .119 2.7. 浪潮之巅第二章 蓝色巨人(IBM)(三) .124 2.8.浪潮之巅第二章一 蓝色巨人(IBM)(四) .130 2.9.浪潮之巅第二章一蓝色巨人(IBM)(五) .134 2.10.浪潮之巅第二章一蓝色巨人(IBM)(六) .137 2.11.浪潮之巅第三章一“水果”公司的复兴（乔布斯和苹果公司） (一) .141 2.12.浪潮之巅第三章 “水果”公司的复兴 (乔布斯和苹果公司)（二） .147 2.13.浪潮之巅第三章一“水果”公司的复兴 (乔布斯和苹果公司)（三） ..150 2.14.浪潮之巅第三章一"水果"公司的复兴（乔布斯和苹果公司）（四） ..154 2.15.浪潮之巅第四章一计算机工业的生态链（一） .158 2.16.浪潮之巅第四章一计算机工业的生态链（二） .163 2.17.浪潮之巅第四章一 计算机工业的生态链（三） .167 2.18.浪潮之巅第五章一 奔腾的芯（英特尔一Intel)(一） .172 2.19.浪潮之巅第五章一奔腾的芯（英特尔一Intel) (二) .177 2.20.浪潮之巅第五章一奔腾的芯（英特尔一Intel))(三） .181 2.21.浪潮之巅第五章一 奔腾的芯（英特尔一Intel)(四） .186 2.22.浪潮之巅第五章一 奔腾的芯（英特尔一Intel)(五） .189 2.23.浪潮之巅第六章一互联网的金门大桥（思科）（一） ..193 2.24.浪潮之巅第六章一 互联网的金门大桥（思科）（二） ..196 2.25.浪潮之巅第六章一 互联网的金门大桥（思科）（三） .199 2.26.浪潮之巅第六章一互联网的金门大桥（思科） (四) 203 2.27.浪潮之巅第七章一硅谷的见证人（惠普公司）（一） .212 2.28.浪潮之巅第七章一硅谷的见证人一惠普公司（二） 217 2.29.浪潮之巅第七章一硅谷的见证人一惠普公司（三） ...221 2.30.浪潮之巅第七章一 硅谷的见证人一惠普公司（四）】 ..225 2.31.浪潮之巅第七章一硅谷的见证人一惠普公司（五）》 ,228 2.32.浪潮之巅第八章一没落的贵族一摩托罗拉（一） .233 2.33.浪潮之巅第八章一没落的贵族一摩托罗拉（二） .236 2.34.浪潮之巅第八章一没落的贵族一摩托罗拉（三） .240 2.35.浪潮之巅第八章一没落的贵族一摩托罗拉（四）》 245 2.36.浪潮之巅第八章一没落的贵族一摩托罗拉（五） 249 2.37.浪潮之巅第八章一没落的贵族一摩托罗拉（六） ,253 2.38.浪潮之巅第九章一硅谷的另一面（一） … 258 2.39.浪潮之巅第九章一硅谷的另一面（二） ,265 2.40.浪潮之巅第九章一硅谷的另一面（三）》 .269 2.41.浪潮之巅第九章一硅谷的另一面（四） .276 2.42.浪潮之巅第九章一硅谷的另一面（五） .280 2.43.浪潮之巅第十章一短暂的春秋一与机会失之交臂的公司（一) .289 2.44.浪潮之巅第十章一短暂的春秋— 与机会失之交臂的公司（二） .296 2.45.浪潮之巅第十章一短暂的春秋 与机会失之交臂的公司（三） .303 2.46.浪潮之巅第十章一短暂的春秋— 与机会失之交臂的公司（四） .308

目录 2.3. 浪潮之巅第一章 — 帝国的余辉（AT&T）（三） ..............................106 2.4. 浪潮之巅第一章 — 帝国的余辉（AT&T）（四） ..............................111 2.5. 浪潮之巅第二章 — 蓝色巨人（IBM）（一）...................................114 2.6. 浪潮之巅第二章 — 蓝色巨人（IBM）（二）...................................119 2.7. 浪潮之巅第二章 — 蓝色巨人（IBM）（三）...................................124 2.8. 浪潮之巅第二章 — 蓝色巨人（IBM）（四）...................................130 2.9. 浪潮之巅第二章 — 蓝色巨人（IBM）（五）...................................134 2.10. 浪潮之巅第二章 — 蓝色巨人（IBM）（六）...................................137 2.11. 浪潮之巅第三章 — “水果”公司的复兴 （乔布斯和苹果公司）（一） ...141 2.12. 浪潮之巅第三章 — “水果”公司的复兴 （乔布斯和苹果公司）（二） ...147 2.13. 浪潮之巅第三章 — “水果”公司的复兴 （乔布斯和苹果公司）（三） ...150 2.14. 浪潮之巅第三章 — "水果"公司的复兴 （乔布斯和苹果公司）（四）.......154 2.15. 浪潮之巅第四章 — 计算机工业的生态链（一）...............................158 2.16. 浪潮之巅第四章 — 计算机工业的生态链（二）...............................163 2.17. 浪潮之巅第四章 — 计算机工业的生态链（三）...............................167 2.18. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（一）.......................172 2.19. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（二）.......................177 2.20. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（三）.......................181 2.21. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（四）.......................186 2.22. 浪潮之巅第五章 — 奔腾的芯（英特尔—Intel）（五）.......................189 2.23. 浪潮之巅第六章 — 互联网的金门大桥（思科）（一）........................193 2.24. 浪潮之巅第六章 — 互联网的金门大桥（思科）（二）........................196 2.25. 浪潮之巅第六章 — 互联网的金门大桥（思科）（三）........................199 2.26. 浪潮之巅第六章 — 互联网的金门大桥（思科）（四）........................203 2.27. 浪潮之巅第七章 — 硅谷的见证人（惠普公司）（一）........................212 2.28. 浪潮之巅第七章 — 硅谷的见证人—惠普公司（二） .........................217 2.29. 浪潮之巅第七章 — 硅谷的见证人—惠普公司（三） .........................221 2.30. 浪潮之巅第七章 — 硅谷的见证人—惠普公司（四） .........................225 2.31. 浪潮之巅第七章 — 硅谷的见证人—惠普公司（五） .........................228 2.32. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（一）............................233 2.33. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（二）............................236 2.34. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（三）............................240 2.35. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（四）............................245 2.36. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（五）............................249 2.37. 浪潮之巅第八章 — 没落的贵族—摩托罗拉（六）............................253 2.38. 浪潮之巅第九章 — 硅谷的另一面（一）.......................................258 2.39. 浪潮之巅第九章 — 硅谷的另一面（二）.......................................265 2.40. 浪潮之巅第九章 — 硅谷的另一面（三）.......................................269 2.41. 浪潮之巅第九章 — 硅谷的另一面（四）.......................................276 2.42. 浪潮之巅第九章 — 硅谷的另一面（五）.......................................280 2.43. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（一）.........289 2.44. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（二）.........296 2.45. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（三）.........303 2.46. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（四）.........308 II

目录 2.47.浪潮之巅第十章一短暂的春秋一与机会失之交臂的公司（五） .317 2.48.浪潮之巅第十章一短暂的春秋一与机会失之交臂的公司（六） .326 2.49.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital) ...333 2.50.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital)) .338 2.51.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital) ..344 2.52.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital) ..352 2.53.浪潮之巅第十一章一幕后的英雄一风险投资(Venture Capital).360 2.54.浪潮之巅第十一章一幕后的英雄-风险投资(Venture Capital)..367 2.55.浪潮之巅第十二章一信息产业的规律性（一）..376 2.56.浪潮之巅第十二章一信息产业的规律性（二).388 2.57.浪潮之巅第十二章一 信息产业的规律性（三） .397 m

目录 2.47. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（五）.........317 2.48. 浪潮之巅第十章 — 短暂的春秋——与机会失之交臂的公司（六）.........326 2.49. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......333 2.50. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......338 2.51. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......344 2.52. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......352 2.53. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......360 2.54. 浪潮之巅第十一章 — 幕后的英雄—风险投资（Venture Capital）.......367 2.55. 浪潮之巅第十二章 — 信息产业的规律性 (一) ................................376 2.56. 浪潮之巅第十二章 — 信息产业的规律性 (二) ................................388 2.57. 浪潮之巅第十二章 — 信息产业的规律性 (三) ................................397 III

数学之美 1.数学之美 吴军，Google研究员 1.1.数学之美系列一一统计语言模型 2006年4月3日上午08：15：00 从本周开始，我们将定期刊登Go0g1e科学家吴军写的《数 学之美》系列文章，介绍数学在信息检索和自然语言处理中的主 导作用和奇妙应用。 发表者：吴军，Google研究员 前言 也许大家不相信，数学是解决信息检索和自然语言处理的最 好工具。它能非常清晰地描述这些领域的实际问题并且给出漂亮 的解决办法。每当人们应用数学工具解决一个语言问题时，总会 感叹数学之美。我们希望利用G00g1e中文黑板报这块园地，介 绍一些数学工具，以及我们是如何利用这些工具来开发Google 产品的。 系列一：统计语言模型(Statistical Language Models) G00g1e的使命是整合全球的信息，所以我们一直致力于研究 如何让机器对信息、语言做最好的理解和处理。长期以来，人类 一直梦想着能让机器代替人来翻译语言、识别语音、认识文字（不

数学之美 1.数学之美 吴军, Google 研究员 1.1. 数学之美系列一 — 统计语言模型 2006 年 4月3日 上午 08:15:00 从本周开始，我们将定期刊登 Google 科学家吴军写的《数 学之美》系列文章，介绍数学在信息检索和自然语言处理中的主 导作用和奇妙应用。 发表者: 吴军, Google 研究员 前言 也许大家不相信，数学是解决信息检索和自然语言处理的最 好工具。它能非常清晰地描述这些领域的实际问题并且给出漂亮 的解决办法。每当人们应用数学工具解决一个语言问题时，总会 感叹数学之美。我们希望利用 Google 中文黑板报这块园地，介 绍一些数学工具，以及我们是如何利用这些工具来开发 Google 产品的。 系列一： 统计语言模型 (Statistical Language Models) Google 的使命是整合全球的信息，所以我们一直致力于研究 如何让机器对信息、语言做最好的理解和处理。长期以来，人类 一直梦想着能让机器代替人来翻译语言、识别语音、认识文字（不 1