百度、Google搜索引擎核心技术是怎么实现的?这个问题背后的技术非常吸引人!

 

搜索引擎

搜索引擎(search engine)是指根据一定的算法策略,运用特定的计算机程序,搜集互联网上的网页等信息,再对信息进行组织和处理后,并将处理后的信息显示给用户,是为用户提供检索服务的系统。

全文搜索引擎是名副其实的搜索引擎,国外代表有Google,国内则有著名的百度。

它们从互联网提取各个网站的信息(以网页文字为主),建立起数据库,并能检索与用户查询条件相匹配的记录,按一定的排列顺序返回结果。

根据搜索结果来源的不同,全文搜索引擎可分为两类:

1)一类拥有自己的检索程序(Indexer),俗称“蜘蛛”(Spider)程序或“机器人”(Robot)程序,能自建网页数据库,搜索结果直接从自身的数据库中调用,上面提到的Google和百度就属于此类;

2)另一类则是租用其他搜索引擎的数据库,并按自定的格式排列搜索结果,如Bing、Lycos搜索引擎。

用户输入关键词进行检索,搜索引擎从索引数据库中找到匹配该关键词的网页;

例如搜索“米扑科技”:https://www.baidu.com/s?wd=mimvp.comhttps://www.baidu.com/s?wd=米扑科技

 

为了用户便于判断,除了网页标题和URL外,还会提供一段来自网页的摘要以及其他信息。

搜索引擎一般由搜索器、索引器、检索器、用户接口四个部分组成:

1)搜索器:其功能是在互联网中漫游,发现和搜集网页等信息;

2)索引器:其功能是理解搜索器所搜索到的信息,从中抽取出索引项,用于表示文档以及生成文档库的索引表;

3)检索器:其功能是根据用户的查询在索引库中快速检索文档,进行相关度评价,对将要输出的结果排序,并能按用户的查询需求合理反馈信息;

4)用户接口:其作用是接纳用户查询、显示查询结果、提供个性化查询项。

 

纯净搜索引擎(无自己的爬虫蜘蛛)

这类搜索引擎没有自己的信息采集系统,利用别人现有的索引数据库,主要关注检索的理念、技术和机制等。

 

垂直搜索引擎(如科学研究的文献库、论文库)

垂直搜索引擎是相对通用搜索引擎的信息量大、查询不准确、深度不够等提出来的新的搜索引擎服务模式,通过针对某一特定领域、某一特定人群或某一特定需求提供的有一定价值的信息和相关服务。其特点就是“专、精、深”,且具有行业色彩,相比较通用搜索引擎的海量信息无序化,垂直搜索引擎则显得更加专注、具体和深入。
 

 

搜索引擎的定义

搜索引擎是传统IR技术在Web环境中的应用。一般来说,搜索引擎是一种用于帮助用户在Internet上查询信息的搜索工具,它以一定的策略在Internet中搜索,发现信息,对信息进行理解,提取,组织和处理,并为用户提供检索服务,从而起到信息导航的目的。

搜索引擎的体系结构

典型的搜索引擎结构一般由以下三个模块组成:信息采集模块(Crawler),索引模块(Indexer),查询模块(Searcher)

1)Crawler:从web中采集网页数据,俗称爬虫蜘蛛。

2)Indexer:对Crawler采集数据进行分析生成索引。

3)Searcher:接受查询请求,通过一定的查询算法获取查询结果,返回给用户。

 

Crawler(爬虫蜘蛛)

Crawler负责页面信息的采集,工作实现基于以下思想:既然所有网页都可能链接到其他网站,那么从一个网站开始,跟踪所有网页上的所有链接,就有可能检索整个互联网。Crawler首先从待访问URL队列中获取URLs,根据URL从中抓取网页数据,然后对网页进行分析,从中获取所有的URL链接,并把它们放到待访问的URL队列中,同时将已访问URL移至已访问的URL队列中。不断重复上面的过程。

 

Crawler 关键问题

1)多线程抓取时的任务调度问题

搜索引擎会产生多个Crawler同时对网页进行抓取,这里需要一个好的分布式算法,使得既不重复抓取网页,又不漏掉重要的站点。

2)网页评估

在抓取网页时存在一定的取舍,一般只会抓20%左右的网页。评估算法中典型的油Google发明的PgaeRank。

3)更新策略

每经过一段时间,Crawler对以抓取的数据经行更新,保证索引网页是最新的。

4)压缩算法

网页抓取后,通过一定的压缩机制保存到本地,从而减少存储容量,同时也减少各服务器之间的网络通信开销

5)Indexer

搜索引擎在完成用户的检索请求时,并不是即时的检索Web数据,而是从预先采集的网页数据中获取。要实现对采集页面的快速访问,必须通过某种检索机制来完成。

页面数据可以用一系列关键字来表示,从检索来说,这些关键词描述了页面的内容,只要找到页面,便可以找到其中的关键词;反过来,通过关键词对页面创建索引,便可以根据关键字快速的找到相应的网页。其原理很简单,可以参见米扑博客:倒排索引

 

Indexer中存在的问题

1)索引存储:

一般来讲,数据量(收录量)和索引量的比例接近1:1,索引的存储一般采用分布式策略,检索的数据分布在不同的服务器上,Google存储索引的服务器大概有1000多台,网页数据库再多一两个数量级,即几十万台服务器集群。

2)索引更新:

页面数据更新时,索引数据必须相应的更新,更新策略一般采用增量索引方式。

3)索引压缩:

索引也存在数据压缩的问题。索引压缩是通过对具体索引格式的研究实现压缩。

4)网页相似性支持:

索引的结构还必须为网页相似性分析提供支持,也就是我们常见的多个待选结果。

5)多语言,多格式支持:

网页数据具有多种编码格式,通过Unicode、UTF-8,索引支持多种编码查询。同时索引还必须有对Word,Excel等文件格式进行分析的功能。

6)Searcher

Searcher是直接与用户进行交互的模块,在接口上有多种实现的方式,常见的主要是Web、App方式。

Searcher通过某种接口方式,接受用户查询,对查询进行分词(stemming)处理,获取查询关键字。通过Indexer获取与查询关键字匹配的网页数据,经过排序后返回给用户。

 

Searcher中的问题

1)检索结果的排序:对不同的用户采用不同的排序策略。

2)排序结果排重:排重可以提高结果数据的质量。

3)检索结果的相似性分析:主要用在类似网页功能中,需要在索引结构中提供支持。

4)检索的速度:主要依赖索引结构的设计。同时在体系结构上还有很多技术可以用来提升速度。如:Cache,负载均衡等。

 


搜索引擎的核心技术

1)分布式技术:

当搜索引擎处理数据达到一定规模时,为了提高系统的性能,必须采用分布式技术。

Crawler通过多个服务器互相合作,提高数据采集的速度。

Indexer在生成索引数据时通过并行算法,在不同机器上同时进行。

Searcher也可以在不同的机器上进行同时查询,提高速度。

 

2)中文分词:

分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。

现有分词算法可以分为三大类:基于字符串比配的的分词方法、基于理解的分词方法、基于统计的分词方法

 

3)网页排序:

现在搜索引擎中网页的 排序主要利用了页面间的链接关系,描述链接的文本以及文本自身内容,重要的链接分析算法有Hits和Pagerank,HillTop等。

 

4)海量数据存储:

搜索引擎的挑战之一就是处理数据的巨大,如何存储如此大的数据,数据的更新,快速的检索...

 

5)压缩技术:

压缩技术极大的减少了数据的存储大小,节约了传输带宽,一般的压缩比可达到八到十分之一,甚至更高压缩比

对于不同类型的数据,需要采用不同的压缩方法,主要的数据压缩主要有:网页数据的压缩和索引数据的压缩。

选择压缩技术主要从开放性,速度与压缩比等多方面进行综合考虑。

Google中选择了Alib(RFC1950)进行压缩,在压缩速度上Zlib超过Bzip,压缩比上Bzip好于Zlib。

 

 

参考推荐

倒排索引