Video在线视频

大家好

这一节我们介绍大海捞针的搜索引擎

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

大家每天都要通过搜索引擎查询信息

但可能很少会想到

这个令人惊叹的互联网工具

是怎么高效工作的

令人难以置信的是

每一个搜索引擎都像“大海捞针”一样

在WWW中为我们搜寻各种相关的信息

难道你不想了解

搜索引擎本身的奥秘

不想了解搜索引擎到底是怎么工作的

搜索引擎的设计者到底是怎么构思的

技术背后到底隐藏着什么样的思想和方法

尽管搜索引擎

包括数以千计的服务器

和先进的网络设备

技术上非常复杂

但宏观上

搜索引擎的原理其实非常简单

构建一个搜索引擎

大致需要做这样三件事

一是自动下载与存储尽可能多的网页

二是建立快速有效的索引与匹配

三是根据查询相关性

对网页进行公平准确的排序

从功能的角度来看

搜索可分为匹配和排名两个阶段

搜索引擎将匹配和排名

组合成一个流程

但它们在概念上是独立的

这一节我们先讨论匹配

下一节讲排名

为便于理解

我们先看一个简单的实例

假设我们要查询人工智能

过程就像这个图所展示的一样

接下来

我们先介绍网页的下载与存储

然后讨论索引与匹配

由于搜索引擎涉及的技术过于复杂

我们只介绍一些主要的思想与方法

一 网页的自动下载与存储

虽然互联网上的WWW很复杂

但只要把一个网页当作一个节点

把网页中的那些超链接

当作连接网页的弧

就可以把WWW抽象成一张

很大的“图”

比如说这么一个图

注意哦

这个图非常庞大

有时候大到

图中的节点数可多达数千亿个

搜索引擎借助于超链接

可以从任何一个网页出发

利用图的遍历算法

自动访问WWW上可访问的

每一个网页并把它们存起来

这是任何一个搜索引擎必须做的首要工作

完成这项工作的程序叫做网络爬虫

或者叫网络蜘蛛

可以想像一下

这里的图可以看成是一张

非常非常大的蜘蛛网

网络爬虫就是网上的蜘蛛

当然这样的蜘蛛肯定不止一个

由于一个网页可能与多个网页有“关系”

遍历时一个网页有可能被多次“访问”

这显然不合适

一个网页只要下载一次就够了

为了解决这一问题

Google采用了哈希表技术

以此来记录哪些网页已经下载过了

下次再碰到他的时候

就可以跳过了

由于WWW中网页数量惊人

导致哈希表非常大

从而出现新问题

一是这个哈希表大到一台服务器存不下

需要多台服务器一起存储

二是网页下载时需要访问和维护哈希表

而哈希表又分布在多台不同的服务器上

服务器之间的通信

以及确保哈希表的一致性

就成了影响系统性能的瓶颈

我们知道量变会导致质变

必须寻求新的方法

对此伯顿 布隆

在1970年提出了布隆过滤器

很好地解决了这个问题

二是网页索引与匹配

大部分使用搜索引擎的人

都会吃惊为什么它能在

零点零几秒内找到成千上万的搜索结果

如果是扫描所有的文本

哪怕速度再快也不可能做到这一点

这里面一定暗藏技巧

这个技巧就是“索引”

它是所有搜索引擎背后最基础的思想

事实上

“索引”早就出现在书籍的最后面

它本质上就是一个表

把书籍中的每一个重要的概念

以某种顺序列出它们在书中出现的位置

也就是页码

例如 这就是某译著索引表的一个片段

事实上

搜索引擎的索引

和书籍的索引原理相同

只不过“书页”变成了网页

网页也有页码哦

要说最大的差异就是网页的数量大得多

为简单起见

假定WWW

只由3个简短的网页组成

它们的页码分别是1、2和3

就像这个图所表示的

现在

让我们为这三个网页创建一个索引表

首先按字母表顺序

为所有网页上的单词创建一个单词表

并标注每个单词所在的网页页码

比如说像这样一个表

计算机查找这样的顺序表很容易

比如查找“cat”

马上就知道它出现在第1和第3页

多词查找也不难

比如查找cat sat

搜索引擎先

分别单独查找“cat”和“sat”

然后判断它们同时出现在哪些网页之中

另一种简单的索引结构

是用一个很长的二进制数

表示一个关键字到底出现哪些网页中

每个二进制位对应一个网页

1代表网页里面有这个关键字

0代表没有

比如假定二进制数

0100 1000 1100 0001……

表示第2、第5、第9、第10

第16个网页包含“原子能”这个词

而二进制数

0010 1000 0000 0001……

表示网页包含“应用”这个词

那么要找到同时包含

“原子能”和“应用”的网页时

只要将这两个二进制数

做布尔与运算就马上可以得到

0000 1000 0000 0001……

表示第5、第16网页满足要求

需要注意的是

多词查找与短语查找不一样哦

比如 cat sat和“cat sat”

前者寻找的是只要包含

“cat”和“sat”两个单词的页面即可

甚至都不考虑先后顺序

后者查找的是

包含单词“cat”之后

紧跟单词“sat”的网页

那如何才能有效地进行短语查询呢

这就是词位置技术

它是现代搜索引擎运行良好的

核心技术思想

他的索引表不仅存储单词所在的页码

还存储所在页内的位置

你看这个图

页内每个词都按顺序编了号

然后在索引表中既记录词所在的网页

也记录所在网页内的词位置

就像这样

有了这样的索引表

查询短语“cat sat”就不难了

先查“cat”和“sat”

同时出现在哪一个网页

然后根据词位置判断

是否顺序相邻即可

容易知道

结果就是第1个网页了

你看

这个简单的词位置技术

就是让搜索引擎高效的关键技术之一

好这一节我们就介绍到这

谢谢大家