搜索引擎的故事

哈克，在咱俩站着的地方的下面，你拿一根钓鱼竿就可以触到我钻出来的那个洞。看看你能不能找到。

——马克·吐温，《汤姆·索亚历险记》

有一些特别重要的算法。

首先，是大家用得最多的搜索引擎索引。在浩瀚的网络中寻找某些信息，无异于在世界上最大的草垛中寻针。

搜索引擎对我们的生活产生了深远影响。

绝大多数人每天都进行多次搜索查询，但我们极少会停下来思考这个令人惊叹的工具是如何奏效的。

搜索引擎提供的海量信息以及搜索结果的速度与质量变得如此平常，如果我们搜索的问题没有在几秒内得到回答，我们就会困惑。

我们倾向于忘记，每一个成功的搜索引擎都是从世界上最大的草垛——万维网——寻针。

事实上，搜索引擎提供的超级服务，不仅仅是针对搜索抛出一大堆花哨技术的结果，每个大型搜索引擎公司都运营着一个由无数数据中心组成的国际网络，其中包括数以千计的服务器计算机和先进的网络设备。

但没有聪明的算法来组织和检索我们请求的信息，所有这些硬件都会变得毫无用处。

搜索引擎的两大主要任务就是匹配（matching）和排名（ranking）。

当你发起一次网络搜索查询时会发生什么？搜索有两个主要阶段：匹配和排名。

一个好的搜索引擎不仅仅会挑出最好的几个命中，而且会以最有用的顺序显示它们——最匹配的页面排在第一，然后是匹配度排名第二的页面，依此类推。

在实际中，搜索引擎将匹配和排名组合成一个流程以实现一致性。

现实搜索引擎中的许多查询都有数百、数千乃至数百万个“命中”，而搜索引擎用户通常只喜欢查看几个结果，最多5个或10个。

因此，搜索引擎必须从大量命中里挑出最好的几个，以正确顺序挑选出最好的几个命中被称为“排名”。

在搜索行业的残酷世界中，搜索引擎的生死由其排名系统的质量决定。

第一个互联网级别的匹配算法叫作AltaVista，1995年推出，20世纪90年代中期的几年中，AltaVista是搜索引擎的王者。

索引的概念是所有搜索引擎背后最基础的思想。

但索引并非由搜索引擎发明：事实上，索引的思想几乎和书写本身一样古老。

比如，人类学家发现了一座具有五千年历史的巴比伦神庙图书馆，里面按学科对楔形文字泥版进行了分类。

因此，索引可以称得上是计算机科学中最古老的有用思想。

如今，“索引”这个词通常指参考书最后的一个板块。你可能想要查看的所有概念都以固定顺序（通常是按字母排序）列出，每一个概念下都列出了这个概念出现的位置（通常是页码）。

互联网搜索引擎的索引和一本书的索引有着相同的工作原理。书“页”现在成了万维网上的网页，而搜索引擎则给互联网上的每个网页分配了一个不同的页码。

想象万维网只由上面显示的3个短网页组成，它们分别分配到了页码1、2和3。通过这种简单方法，搜索引擎就已经能回答许多简单的查询，不过，不幸的是，这种简单方法完全不能满足现代搜索引擎的需要。

此时出现了另一个重要算法，就是PageRank，这是一项让谷歌腾飞的技术。

在当年《个人计算机杂志》的评论中，谷歌的精英管理层因为谷歌“以超乎寻常的技巧返回相关度极高的结果”而获奖，正是得益于谷歌用来对其搜索结果进行排名的创新算法，PageRank，使其在搜索质量上超越当时已经很受欢迎的Lycos和AltaVista。

你肯定已经知道了超链接是什么：超链接是网页上的一个短语，当你点击它时，你将被带到另一个网页。

绝大多数网络浏览器用蓝色底线显示超链接，以便能轻易识别。

其实，超链接也是老想法，来源于1945年美国工程师范内瓦·布什发表的一篇极具前瞻性的论文《诚若所思》。

在这篇涉猎广泛的论文中，布什描述了大量可能的新技术，包括一台被称作麦麦克斯的机器。

谷歌的两位联合创始人于1998年在他们著名的会议论文《解析大规模超文本网络搜索引擎》中描述了随机访问者把戏。

通过和其他许多技术结合，这一把戏的变体仍被主流搜索引擎所使用。

不过，由于众多复杂因素，应用在现代搜索引擎中的实际技术和本章描述的随机访问者把戏略有不同。

其中一个复杂因素直击PageRank的核心：有时候，假设超链接传输的合法权威性有争议。

尽管超链接能代表批评而非推荐，但这在现实中并不是个很大的问题。另一个更加严重的问题是，人们可以滥用超链接把戏，人为地提高自己网页的排名。

第三个重要的算法，叫作公钥加密。

人们喜欢传谣，也喜欢了解秘密。而由于加密的目的就是传输秘密，所以我们都是天生的密码员。

但人类进行秘密沟通要比计算机容易。

如果你想向朋友透露一个秘密，你只需在朋友耳边低声说就行，计算机要做到这一点就不那么容易了。

一台计算机没有办法“低声”向另一台计算机透露一张信用卡的卡号。如果计算机由互联网相连，它们控制不了信用卡卡号的流向，也无法控制会有哪些计算机知道卡号。

在现实生活中，如果你想要发送一份机密文件给某人，你自然会在发送前将文件封存在一个安全的密封的信封内。这并不能保证机密性，但却是正确方向上的一个合理步骤。

这也正是计算机在互联网上尝试相互进行机密通信时面临的问题。

因为互联网上的所有消息都会通过无数被称为路由器的计算机，消息的内容可以为任何访问路由器的人所见，而这也包括潜在的恶意窃听者。

因此，每一块离开你计算机并进入互联网的数据，就好像写在明信片上！

公钥加密算法是公开建立一个共享密钥。大家都知道，互联网上绝大多数加密技术的运作原理是：将消息分成块，使用加法把戏变体加密每个块，但这是加密简单的地方。

难点在于一开始要建立一个共享密钥，计算机科学家们用了一个精巧的解决方案解决这个问题，被称为为迪菲—赫尔曼密钥交换。

第四个重要的算法，叫作纠错码。

计算机有三项基本工作。最重要的工作是执行计算，即给予计算机一些输入数据，计算机必须用某种方法转化数据，并得出一个有用的答案。

但如果没有计算机执行的另外两项非常重要的工作：存储数据和传输数据，计算答案的能力基本上也没用。

对于计算机而言，精确度达到99.9999%也还是不够好。计算机必须能在存储和传输数十亿块信息的情况下，不犯任何一个错误。

要通过一个不可靠的频道进行可靠的通信，其中最根本的把戏是我们都熟悉的：要确保一些信息正确地传输，你只需重复几次该信息。这是重复把戏。

假设银行的一台计算机试图通过互联网把你的账户余额传给你。你的账户余额是5213.75美元，但不幸的是，网络不稳定，每一个数字都有20%的概率变成其他东西。你不能只发送原始消息：你要发送一些多余的东西以增加可靠性。这是冗余把戏。

公钥加密，是最精巧、最具有影响力的计算机科学思想之一，最流行的分块密码是高级加密标准AES，AES能配合多种不同配置使用，但标准配置是使用16个字母的块，配备128位密钥，进行10轮混合操作。

第五个重要的算法，叫作图形识别。

图形识别是人工智能的一部分，包括面部识别、物体识别、语音识别和笔迹识别等任务。

更具体的例子，如判定一张照片是不是你姊妹的照片，或判定手写信封上的城市及地名。

因此，图形识别可以更通俗地定义为，让计算机基于输入数据“聪明地”行动的任务，这些数据包含大量的变量。

因此，图形识别的基本任务就是处理一些变量极多的数据——如不同光照环境下的各种人脸照片，或不同人书写许多不同字的笔迹样本——并做一些有用的事。

从一开始看，图形识别的任务种类多得似乎超乎寻常。计算机能使用一个单独的图形识别技术工具包来识别笔迹、面部、语音及更多东西吗？

这一问题的可能答案之一是：盯着我们的脸看，人脑在处理多种多样的识别任务上速度超快、精确度超高。我们能编写一个计算机程序来做到相同的事吗？

在讨论那样一个程序可能用到的技术之前，我们需要统一令人眼花缭乱的多种任务，定义一个单一问题让我们来尝试解决。

要实现这一点，标准做法是将图形识别看作分类问题。我们假设要处理的数据被分解成合理大小的块，这些块被称为“样本”，每一个样本都属于可能“类”（class）的固定集之一。

比如，在一个人脸识别问题中，每一个样本都是一张人脸图片，而类则是系统能识别出的这些人的身份。

有三种相关的算法：最近邻分类器（nearest-neighbor classifier）、决策树（decision tree）以及人工神经网络（artificial neural network）。

分析引擎没有原创任何东西的权利，它只能按照我们的指令执行任何事情。

——艾达·勒芙蕾丝

心归航，再启航

愿每日微小知识激发你的深刻思考