读算法简史：从美索不达米亚到人工智能时代11搜索网络

1.小型计算机 1.1.到了20世纪70年代，小型计算机已在科研院所、大学和大公司中广泛应用 1.2.小型计算机在高度和周长上与美式冰箱相似，它比老式的大型计算机便宜得多，但仍然很昂贵 2.微型计算机 2.1.1976年 2.1.1.史蒂夫·乔布斯(Steve Jobs)和史蒂夫·沃兹尼亚克(Steve Wozniak)向冷清的市场推出了第一台预装微型计算机 2.1.2.苹果1号(Apple I)非常便宜，一个人就可以购买和使用 2.2.VisiCalc 2.2.1.VisiCalc是世界上第一个商业电子表格程序，允许用户在屏幕上的表格中输入文本、数字和公式 2.2.2.VisiCalc的秘密武器是，当数字输入电子表格时，会自动执行公式中指定的计算 2.2.3.人们购买苹果2号(Apple II)只是为了使用VisiCalc 2.3.IBM于1981年推出了自己的个人计算机 2.3.1.在公司庞大销售网络的支持下，IBM个人计算机在商业上取得了成功 2.4.1984年 2.4.1.苹果推出了第一台使用图形用户界面的平价计算机 2.4.1.1.苹果设计精美的麦金托什(Macintosh)计算机配备了键盘、高分辨率显示屏，还有一个具有革命性的鼠标 2.4.1.2.鼠标让用户能够通过点击图标和菜单来控制计算机 2.4.1.2.1.鼠标很受欢迎 2.4.1.2.2.老式的文本命令是给那些极客用的东西 2.4.1.3.程序可以在可调窗口中并排运行 2.4.2.尽管将图形用户界面商业化的是苹果公司，但这项技术是在其他地方发明的 2.4.2.1.鼠标则是SRI的道格拉斯·恩格尔巴特(Douglas Engelbart)发明的 2.4.2.2.图形用户界面是在鲍勃·泰勒的指导下在施乐的帕洛阿尔托研究中心开发出来的 3.万维网 3.1.虽然图形用户界面让使用单台计算机的工作变得更加容易，但通过网络访问数据仍然是件麻烦事 3.2.解决问题的方案不是来自计算机行业，而是欧洲的一个粒子物理实验室 3.3.蒂姆·伯纳斯-李 3.3.1.Tim Berners-Lee 3.3.2.1955年出生于伦敦 3.3.3.毕业于牛津大学，获得物理学学位 3.3.4.伯纳斯-李的父母曾是“费兰蒂·马克1号”的程序员，他追随父母的脚步，成为一名专业的软件开发人员 3.3.5.提出了一个方案，用户的台式计算机可以下载和查看存储在远程计算机（或称为服务器）上的电子页面 3.3.5.1.在用户计算机上运行的一个叫作浏览器的软件会向服务器发送请求，并显示远程页面 3.3.5.2.每个页面可以由一个唯一的名称标识来识别，该名称包括服务器的ID和该文件的文件名（位于服务器ID之后） 3.3.5.3.完整标识符现在被称为页面的统一资源定位符(uniform resource locator，URL) 3.3.6.在伯纳斯-李的坚持下，CERN免费发布了万维网的规范和软件 3.3.7.随着万维网越发受到关注，蒂姆·伯纳斯-李离开了CERN，去创立并领导万维网联盟(World Wide Web Consortium，W3C) 3.3.7.1.W3C是一个非营利性组织，旨在与产业界的合作伙伴合作开发和推广万维网 3.3.7.2.该联盟至今仍是万维网标准的守护者 3.3.7.3.万维网的标准遵循了伯纳斯-李的理想，一直是开放、免费和公开的 3.3.7.4.任何人都可以搭建兼容的网络浏览器或服务器，不必申请许可或支付版税 3.3.8.2004年，英国女王授予蒂姆·伯纳斯-李爵士爵位，以表彰他的成就 3.3.9.在2016年获得了图灵奖 3.4.伯纳斯-李的方案的一个关键特点是，网页中包含超链接 3.4.1.超链接（或简称为链接）是一段文本或图像，上面标记了对另一个网页的引用 3.4.2.超链接最早是由万尼瓦尔·布什在1945年发表的一篇展望未来的文章中提出的 3.4.2.1.联网的计算机和软件可以把布什的设想变成现实 3.5.伯纳斯-李和罗伯特·卡约(Robert Cailliau)整合出了一份详细的文件来描述这个系统 3.5.1.把这个系统命名为万维网(WorldWideWeb，WWW)，突出了互联网的全球可及范围以及网页之间超链接连接的特性 3.5.2.一个是网页文件格式（允许的内容）的正式定义 3.5.3.另一个是规定浏览器和服务器软件用于通信的讯息和行为的协议(protocol) 3.6.在项目获得批准后的一年内，伯纳斯-李完成了第一个万维网浏览器和服务器的软件 3.6.1.1991年8月6日，世界上第一个网站上线 3.7.马赛克(Mosaic)浏览器与伯纳斯-李的服务器软件兼容，但重要的是，它能在微软的Windows系统上运行 3.8.万维网为世界提供了一个成本低、稳定可靠、易于使用的信息共享平台 4.亚马逊推荐 4.1.杰夫·贝索斯在30岁时是德肖公司(DE Shaw &namp; Company)最年轻的高级副总裁 4.2.格雷格·林登 4.2.1.Greg Linden 4.2.2.推荐系统将有助于把亚马逊的主页浏览量转化为图书的销量 4.2.3.与传统的一刀切式广告相比，个性化推荐可以增加每次主页浏览量带来的销售额 4.2.4.林登的算法是基于一个简单的直觉 4.2.4.1.如果人们通常一起购买两种产品，那么已经拥有一种产品的顾客很可能也会购买另一种 4.2.4.2.林登的算法会记录亚马逊网站上所有的购物记录 4.2.4.3.相似度评分 4.2.5.算法工作原理 4.2.5.1.以相似度表和用户购买历史记录为输入 4.2.5.2.创建一个空列表 4.2.5.3.对购买历史中的每一本书重复以下步骤 4.2.5.3.1.从相似度表中找到匹配的行 4.2.5.3.2.对该行的每一列重复以下步骤 4.2.5.3.2.1.如果相似度评分大于0，那么将匹配的书名和评分添加到列表中 4.2.5.3.2.2.到达该行的末尾后，停止重复 4.2.5.3.3.到达购买历史记录的末尾后，停止重复 4.2.5.4.从列表中删除所有重复项 4.2.5.5.删除用户已经购买的那些书 4.2.5.6.根据相似度评分对列表进行排序 4.2.5.7.输出相似度评分最高的书名 4.3.数据集变大能显著提高推荐的准确性 4.3.1.产品相似度表中的数据越多，用户的历史记录越广泛，推荐的效果就能越好 4.3.2.随着更多数据的积累，突兀的结果消失了，主要趋势开始显现 4.3.3.只要有足够的数据，推荐算法就能达到惊人的准确性 4.4.从本质上讲，推荐就是广告 4.4.1.区别在于推荐是个性化的 4.4.2.它是根据个人的兴趣量身定制的 5.谷歌网络搜索 5.1.佩奇对已经存在的以论文为基础的学术研究论文排名系统很熟悉 5.1.1.究论文的排名通常根据的是它们在其他出版物中被引用的次数 5.1.2.其中的理念是，一篇论文被参考或引用的次数越多，它就越重要 5.2.佩奇开发了一种算法，用于对网页的重要性进行排序 5.2.1.“页面排序算法”(PageRank)，从名字就能看出是他开发的 5.2.1.1.页面排序算法是斯坦福大学的专利 5.2.1.2.谷歌从斯坦福大学获取了将该算法用于其搜索引擎的独家授权，代价是180万股股份 5.2.1.3.2005年，斯坦福大学以3.36亿美元的价格出售了其谷歌股份 5.2.1.3.1.这笔交易很可能使页面排序算法成为史上最具价值的算法 5.2.2.页面排序算法不仅仅是统计引用次数，它还考虑了被评级页面的链接页面的重要性 5.2.3.页面排序算法是基于网站开发人员的集体智慧对网页进行排名的 5.2.4.每个网页都会被分配一个页面等级分数：分数越高，该网页越重要 5.2.5.一个页面的得分等于链接到它的各个页面的加权页面等级分之和再加上一个阻尼项(damping term) 5.2.6.一个链接页面的等级分以3种方式进行加权 5.2.6.1.它被乘以从链接页面到被评分页面的链接数 5.2.6.2.对结果进行标准化(normalization)，意思是将结果除以链接页面上的链接数量 5.2.6.2.1.其基本原理是，在同等条件下，来自包含许多链接的页面的超链接，其价值低于来自链接数量较少的页面的超链接 5.2.6.3.将这个页面等级分乘以一个阻尼系数(damping factor) 5.2.6.3.1.这个阻尼系数是一个恒定值（通常为0.85），它模拟的是用户可能跳转到一个随机页面而不是进入一个链接 5.2.6.3.2.阻尼项通过在所有链接页面的加权等级分之和的基础上加上1减去阻尼系数得到的值（通常为0.15）来补偿这一点 5.2.7.页面等级分可以被看作一名随机选择链接的网络冲浪者抵达某个特定页面的概率 5.2.8.计算页面等级分的算法是迭代算法 5.3.用网络爬虫(web crawler)下载万维网的摘要 5.4.“古戈尔”(Googol)这个词 5.4.1.一个古戈尔是一个1后面跟着100个0 5.4.2.把这个词误写成了“谷歌”(Google) 5.4.3.布林为新网站设计了一个五颜六色的标识 5.5.到了1998年7月，谷歌搜索引擎已经索引了2400万个页面 5.5.1.最关键的是，相比其竞争对手，谷歌的搜索结果遥遥领先 5.6.谷歌从风险投资公司红杉资本(Sequoia Capital)和凯鹏华盈(Kleiner Perkins)获得了2500万美元的投资 5.6.1.红杉资本和凯鹏华盈从过去到现在一直是硅谷的显贵 5.7.关键字广告 5.7.1.AdWords 5.7.2.“关键字广告”允许广告商出价将他们的链接与页面等级排序结果一起列在谷歌搜索页面上 5.7.3.推广链接和页面等级排序结果做了清晰的划分，以便用户能够区分页面等级排序的结果和广告 5.7.4.事实证明，“关键字广告”比传统广告更有效 5.7.5."关键字广告”把免费的网络搜索变成了一座金矿