Google搜索引擎-信息技术:基础+实践

2023-11-01 理论教育版权反馈

【摘要】：Google的诞生可以说是一个偶然。于是Page建立了一个实验用的搜索引擎BackRub，实际上他已经在不知不觉之中建立了第一个网络爬行工具。Google以检索功能强大、搜索信息准确而倍受赞誉，一些门户性网站如雅虎、网易等也以它作为搜索引擎，世界上许多权威机构更是将其评为最佳搜索引擎。Google从功能上分为三大部分：网页爬行、标引入库和用户查询。图6-4Google运作过程示意图基于Robot的搜索过程。这样，Google就可以通过各种策略来解决排序沉没和排序漏出等问题。

Google的诞生可以说是一个偶然。1996年Page（佩奇）进入斯坦福大学攻读博士学位，他将当时还处于萌芽状态的万维网（Web）作为自己的研究方向。在研究过程中，Page发现从一个网页链接到另外一个网页非常简单，然而要想从一个网页逆着链接回去却不是件易事。换句话说，当你在浏览一个网页时，你并不知道有哪些网页可以链接到这个网页。在研究如何评价网页价值时，他发现评价网页与评价学术论文类似，不仅要看内容，还要看它所引用的文章的水平以及引用它的文章的水平。对于网页来说，引用的文章就是指它所链接的网页。

于是Page建立了一个实验用的搜索引擎BackRub，实际上他已经在不知不觉之中建立了第一个网络爬行工具。后来，Brin（布林）的加入增强了研发的力量，他们共同开发了一套网页评级系统，即著名的PageRank。此时的BackRub已经是一个功能十分强大的搜索引擎，搜索效果远远好于那些只采用文本匹配技术的搜索引擎。而且由于PageRank是根据网页链接来工作的，因此网页数量越多搜索效果越好，这一点与其他搜索引擎恰恰相反。

随着越来越多的人使用BackRub搜索引擎，Page和Brin意识到了BackRub的价值，他们为自己的搜索引擎取名为Google，这是一个数学名词，意思是数字“1”后面加上一百个“0”的数量。

Google以检索功能强大、搜索信息准确而倍受赞誉，一些门户性网站如雅虎、网易等也以它作为搜索引擎，世界上许多权威机构更是将其评为最佳搜索引擎。

Google从功能上分为三大部分：网页爬行、标引入库和用户查询。

① 网页爬行主要负责网页的抓取，由URL服务器、爬行器、存储器、分析器和URL解析器组成，爬行器是该部分的核心。

② 标引入库主要负责对网页内容进行分析，对文档进行标引并存储到数据库里，由标引器和分类器组成，该模块涉及许多文件和数据，有关于桶的操作是该部分的核心。

③ 用户查询主要负责分析用户输入的检索表达式，匹配相关文档，把检索结果返回给用户，由查询器和网页级别评定器组成，其中网页等级的计算是该部分的核心。其总体系统结构如图6-3所示。

图6-3　Google总体系统结构图

Google运作过程，如图6-4所示。

图6-4　Google运作过程示意图

（1）基于Robot的搜索过程。

Robot使用多线程并发搜索技术，主要完成文档访问代理、路径选择引擎和访问控制引擎。基于Robot的Web页搜索模块主要由URL服务器、爬行器、存储器、URL解析器四大功能部件和资源库、锚库、链接库三大数据资源构成，另外，还要借助标引器的辅助功能。具体过程是：由URL服务器发送要去抓取的URL，爬行器根据URL抓取Web页并送给存储器，存储器压缩Web页并存入数据资源库，然后由标引器分析每个Web页的所有链接并把相关的重要信息存储在anchors文件中。URL解析器读anchors文件并解析URL，然后依次转成docID，再把anchor文本变成顺排索引，送入索引库。

① URL服务器是整个Web页搜索模块的开始，主要用来管理和维护URL列表。首先由它发送一个新的URL给爬行器，让爬行器去搜索。如果爬行器遇到了不可下载的网页，就会给URL一个返回信息，然后取下一个URL。URL服务器会从文档索引库里不断地获取新的URL以供爬行器使用。

② 爬行器是整个搜索模块中最关键的一部分，它由好几个分布的爬行器组成，并协同工作。爬行器如遇到HTML的页头有“＜head＞＜meta name="robots" content="noindex， nofollow"＞＜/head＞”标记就不再抓取此页，而是返回一个空值，继续向其他方向爬行，这就有效防止爬行器标引此页及本页的相关链接页。如果网页已经标引过，就从将要爬行的网页队列中移除。Web页文本的繁殖思想是由3W蠕虫来实现的，当它搜索非文本信息时，尽可能少地下载文档，以扩展搜索度，因为非文本信息如图片等没有链接会造成爬行的中断。这样，Google就可以通过各种策略来解决排序沉没（rank sink）和排序漏出（rank loak）等问题。

③ 存储器：把爬行器抓来的Web页进行压缩并存储到数据资源库中。数据资源库包含每一个Web页的全部HTML，所有的网页都用zlib进行压缩。Google更注重zlib的压缩速度而不是压缩率，bzip对数据库的压缩率接近4：1，而zlib为3：1。这样，Google就能把147.8G的HTML文档压缩成53.5G的数据存储在库中，在数据资源库中，再对文档进行归类，加上docID前缀、文档的长度和URL。文档索引记录着每一个文档的信息，它是一个有固定长度，经docID排序的ISAM索引（Index sequential access mode）。

存在每个条目中的信息包括当前文档状态、数据库中的指针、文档校验以及其他统计信息。如果文档被爬行过，它也包含可变长文件的指针，这个称为docinfo文件，它包含文档的URL和标题。否则，指针指向仅包含URL的URL列表。(www.chuimin.cn)

④ 分析器：可以看成是标引器的一部分，也可以说是标引器的一个辅助功能部分。它分析每个Web页的所有链接并把相关的重要信息存储在anchors文件中，构成一个锚库。每当从Web页分析出一个新的URL时，为每个Web页分配一个称为docID的关联ID。这个文件包含足够的信息来决定每个链接的何去何从。锚经常提供比Web页本身更精确的页描述。锚可以存在文档，这些文档不能被基于文本的搜索引擎所标引，如图片、程序、数据库。这就为返回那些不能精确爬行的Web页提供了可能。

⑤ URL解析器：读anchors文件并把相对URL转成绝对URL，然后依次转成docID。把anchor文本变成顺排索引，存到文档索引库里，并用anchor所指向的docID进行关联。把URL转换成doID的文件，是由URL校验和及相应的docID两列组成的一个列表，并以校验和排序。为了找到一个特定URL的docID，首先计算URL的校验和，在校验和文件中进行二元查找，以找到相应的docID。执行一次批处理，通过合并文件把URL转成docID。使用这种批处理模式很关键，要不然就得为每一个链接都作一次查找，假设一个磁盘上有322，000，000个链接记录，那么这样一个过程需要2个多月的时间。它还产生成对docID的链接数据库，以用于计算所有文档的PageRanks。

（2）标引入库过程。

标引入库模块由分类器和标引器组成。标引入库模块处理大量的文件和数据，用来构建庞大的数据库，主要涉及数据资源库、词典库、链接库、桶等。桶的结构与内容非常复杂，有关桶的操作是本模块的核心。

① 分类器从桶中取出数据，按docID进行一级分类，然后按照wordID进行二级分类并产生倒排档索引。分类器产生wordID的列表并把其偏移量写到倒排档索引中。一个称为DumpLexicon的程序把这个列表和由标引器产生的词典糅和在一起并为检索器产生一个新的词典。

② 标引器有许多函数，它读数据库，解压缩文档，然后进行分析。每个文档都被转成一套单词出现频率，称之为采样数。采样数记录单词及在文档中出现的位置，字体的大小以及大写信息。标引器把这些采样数分配到一套“桶”中，创建一个部分分类的顺排索引。对于中文，Google主要采用了二元切分法，也就是为什么我们输入长于两个汉字的中文，如果不加双引号，Google会自动给以切分的原因。

③ Google共有64个桶（barrels），每个桶都存着wordID的归类，包括顺排档与倒排档。如果一个文档包含落在某个桶里的词，docID和wordID的列表以及相应的命中列表就被记录到桶里。Google存储每一个wordID时，存储的是与所在桶的最小wordID的相对差异，而不是存储实际的wordID。这样，在未排序的桶中用24位存储wordID，留下8位用来存储命中列表的长度。

倒排档索引就像顺排档一样由系列的桶组成，唯一的不同是被分类器处理过。有个重要的问题是docID应当在doclist中如何排序。一个简单的解决办法是用docID进行分类，这允许多词查询而带来的不同doclist的合并。另外一个办法是按词在每个文档中出现的频率等级进行分类存储，尽管这使得处理单个词的查询变得烦琐，但为多词查询提供了可能。Google在这两个方案中选择了折中，使用两套倒排的桶，一套为包括标题和anchor hits的命中列表，称之为短桶，另一套为所有的命中列表，称之为长桶。

在顺排档索引和倒排档索引中，命中列表占据了大量的空间。命中列表是指词在一篇文档中的出现频率，包括位置、字体和大写信息。Google为编码位置、字体和大写考虑了多种编码方案——简单编码、优化压缩编码和哈夫曼编码。由于优化压缩编码对空间的要求比简单编码低，操作过程比哈夫曼编码简单，因此，Google最终选择了优化压缩编码。

Google用两个字节的压缩编码来记录每次命中，命中类型有两种：特殊命中与普通命中。特殊命中包括URL的命中率、标题、链接文本和关键标记。普通命中含有所有的信息，包括大写位、字体大小和12位标记词在文档中出现的位置信息等。字体大小用3位来表达文档的其他内容的相对值（仅有7个值可用，因为111是特殊命中的标记）。特殊标记由大写位，字体设成7来表明是一个特殊命中，有4位表示类型，用8位标记位置。为了节省空间，命中列表的长度由顺排档中的wordID和倒排档中的docID决定，分别需要8位与5位。如果长度更长的话，在相应的位里就存着一个溢出编码，接下来的两个字节存储命中列表的实际长度。

④ 词典有几种不同的形式。对早期系统的一个重要改变是根据合理的代价分配内存。该词典包含1 400万个词条（有些生僻词没加），由两部分实现，词表和指针的哈希表。词表还有一些辅助信息用以实现其他功能。对于每个有效的wordID，词典包含指向wordID所在桶的指针。它指向docID和相应的命中列表的doclist。Doclist表明该词在所有文档中出现的所有情况。

（3）检索过程和网页级别。

Google用户查询模块主要由查询器和网页级别评定器组成。

① 查询器运行在Web服务器上，并用DumpLexicon产生的词典、倒排档索引和PageRanks一起来响应查询。首先接受用户输入的检索表达式，进行分析得出各项检索要求，提取检索词并转成wordID，接着到短桶文档列表里进行查词，遍历文档列表直到匹配所有的词条，找到一篇计算网页等级，短桶查完了，如果没有足够的匹配记录，就去查长桶。查完了所有的文档列表，就对检索结果进行排序并返回前K项，如图6-5所示。

图6-5　检索过程示意图

② 网页级别评定器是借用图书文献里的参考文献与引用文献的评价思想，利用链接网页的数量及重要性进行等级评定，而链接网页的重要性由它的链接网页的数量及重要性决定，因此是一种迭代计算。评级函数有许多参数，如类型权重和相关类型权重等。

Google搜索引擎-信息技术:基础+实践

相关推荐