搜索引擎技术基础.ppt

《搜索引擎技术基础.ppt》由会员分享，可在线阅读，更多相关《搜索引擎技术基础.ppt（34页珍藏版）》请在三一办公上搜索。

1、搜索引擎原理,目录,一、搜索引擎总体介绍二、爬虫技术介绍三、中文分词和排序算法介绍四、查询/存储技术、Cache Server介绍,一、搜索引擎总体介绍,(一)搜索引擎定义“搜索引擎”技术，完全来源于历史悠久的全文检索技术。“搜索引擎”从字面上可拆分为“搜”、“索”、“引擎”三个含义。“搜”就是大量信息的抓取，抓取回来后的信息进行智能提取、排重、质量分析等处理。“索”就是大量处理后信息的存储、信息排序、快速查询等。“引擎”就是指系统不但能存储亿级的数据，而且还能有巨大的并发处理能力，这样的系统才有资格被叫着“引擎”。,一、搜索引擎总体介绍,(二)搜索引擎主要核心技术：搜索引擎主要核心技术为:(

2、1)中英文分词语言处理；(2)排序算法；(3)网络爬虫；(4)查询/存储技术,（三）搜索引擎的组成部分 搜索引擎一般包括四个组成部分：搜索器、索引器、检索器、用户接口搜索器（爬虫SPIDER）的功能是在Internet中漫游，发现和搜集信息。索引器(INDEXER)的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于描述文档以及生成文档集的索引表。检索器(SEARCHER)的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。用户接口(USER INTERFACE)的作用是输入用户查询、显示查询结果、提供用户相关性反

3、馈机制。主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时的信息。,一、搜索引擎总体介绍,(四)系统图：,二、爬虫技术介绍,(一)爬虫技术总体介绍：网络爬虫是一个自动提取网页的程序，它为搜索引擎从Internet网上下载网页，是搜索引擎的重要组成。网络爬虫使用多线程技术，让爬虫具备更强大的抓取能力。网络爬虫还要完成信息提取任务，对于抓取回来的网页提取出来:新闻、电子图书、行业信息等。对于MP3、图片、Flash等各种不同内容，要实现自动识别、自动分类及相关属性测试（例如：MP3文件要包含的文件大小，下载速度等属性）。,二、爬虫技术介绍,(二)抓取对象：1.静态网页：爬

4、虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列,直到满足系统的一定停止条件。2.动态网页:分析动态网页参数，按照一定规章，“拼”出所有要被抓取内容URL，只抓取这些特定范围内动态网页。3.特殊内容：比如RSS、XML数据，情况特殊需特殊处理。如新闻的滚动新闻页面，需要爬虫不停地监控扫描，发现新内容马上就进行抓取。4.文件对象：图片，MP3、Flash、视频等文件的抓取，都要特殊处理。比如说：图片抓取出来后，要知道图片文件类型、图片文件的大小、图片的像素大小，还要转换出来缩略图。,二、爬虫技术介绍,(三)抓取策略：1.深度优

5、先策略：对于一些大网站及静态网页为主的抓取内容，采取深度策略抓取，便于在最短时间内获得最大量内容。2.广度优先策略:对于一些动态网页或小网站，采取广度策略抓取，同时对多个网站进行抓取，减小对各个小网站的压力，避免造成恶意攻击。3.合作抓取策略:由被抓取网站，提供可被抓取内容的sitemap网站地图，双方协议好，只抓取这些特定内容，在抓取速度及时间上双方前期进行协商。另外还可以完全由被抓取方，提供详细内容，抓取过程都可以省略一些步骤。,三、中文分词和排序算法介绍,(一)中文分词：中文本身存在着很大的歧义性，同样一句话，不同的断句，表达的意思就不一样。这对于计算机去做机器分析，就带来了巨大的困难。

6、下面的中文断句，来自百度广告宣传片:我知道你不知道我知道你不知道我知道你不知道,三、中文分词和排序算法介绍,(一)中文分词：另外中文的具体含义，还必须放在具体的前后语言环境中去分析。比如说：乒乓球拍卖完了我去学校商店，发现乒乓 球拍 卖 完 了在今天的慈善拍卖会上，世界冠军们夺冠时的乒乓球 拍卖 完 了 中文分词，在具体的算法实现上分为三种：1.字符串匹配(正序、逆序、最少切分、最大切分等)2.基于理解（词法，句法等方式处理）3.基于统计在中文搜索引擎中，目前基本上是这三种算法混合使用。第二种的算法实现起来过于复杂，所以以第一种和第三种算法为主。,三、中文分词和排序算法介绍,(一)中文分词：语

7、言本身也是在不停的进化和发展的，新的词语层出不穷，一些老的词语渐渐被弃用。作为中文分词的基础-词库，其新词补充和老词删除就是非常重要的工作。“超级女声”、“超女”、“李宇春”、“八荣八耻”、“非典”，当这些新词的出现时，搜索引擎需要快速捕捉到，并且马上把其添加到分词系统中去。如何判断那些词是新词，这就全部倚靠算法来实现。新词捕捉主要来源于新闻和网络BBS论坛，主要机制是依靠统计程序，统计上升速度最高的词。另外作为搜索引擎公司，对众多用户的搜索词进行“用户行为”分析，也能提高其“新词补充”效果。,三、中文分词和排序算法介绍,(二)排序算法：搜索引擎的排序算法（ranking algorithm）

8、，决定了各个网页、图片、MP3等数据的重要性排列顺序，也决定了最终用户查询到的数据排序。搜索引擎的排序算法是人工智能的完满体现，它是对百亿级数据进行重要性分析的数学实现。“PageRank”是Google公司在排序算法上的专利技术，也是Google能从众多搜索引擎公司中脱颖而出的最核心技术，作为其搜索服务能够超过其他竞争对手最有力的武器。不同搜索引擎公司排序算法的优劣，直接决定了广大搜索引擎用户对搜索服务的选择，在互联网上，一个普通用户更换搜索服务只需要5秒钟，所以排序算法就成为了各个搜索引擎公司最核心机密。另外，每个搜索引擎公司也必须不停地改进其排序算法。,三、中文分词和排序算法介绍,(二)

9、排序算法：排序算法部分参考指标：,三、中文分词和排序算法介绍,(二)排序算法：排序算法虽然解决了网页排序的问题，但是有时候有些搜索结果还是很难让用户满意。为此，搜索引擎排序算法一项重要改进：“聚类”，就被引进来提高排序效果。“聚类”方法，是把网页分类成各种不同类型，比如说：分类为“体育”、“娱乐”、“军事”、“旅游”、“金融”、“政治”、“汽车”、“房产”等。针对每一种分类，各自有一套专用的排序算法。当查询词为“高尔夫”时，查询结果为“体育”+“汽车”，排序算法为通用算法；但当查询词为“高尔夫 伍兹”时，其分类就能确定为“体育”，其排序算法就采用“体育”类别的算法。,三、中文分词和排序算法介绍

10、,(二)排序算法：排序算法是决定了各个网页的排序，但是对于一些特殊情况，也需要“人工干预”，毕竟一个通用算法并不能解决所有问题。比如说：查询词为“北理”，其实含义是“北京理工大学”。在Google的搜索结果中，第一个就是“北京理工大学”，但在“北京理工大学”网页中根本找不到“北理”两个字。以下是搜索结果：北京理工大学以工为主，包含理工、管理、法律、外语的多科性全国重点大学。/-42k-类似网页“人工干预”是排序算法，非常重要的一个补充，大大改进了搜索结果。搜索引擎公司的竞价排名和滚动排名，也都是“人工干预”的范畴。,(二)排序算法：GOOGLE的PageRank技术PageRank 技术是Go

11、ogle 检索结果的一种排序算法,中文通常译为页面级别或页面等级,根据这个算法,Google 认为每个网页都有一个反映其重要性的值,值越高表明其页面级别越高,即网页越重要;网页的质量和重要性也可以通过其它网页对其超文本链接的数量来衡量,具体来说,假如网页A 有一个指向网页B 的链接,则意味着网页A 认为网页B 是重要的。Google 根据网页被链接的数量来评定其重要性。假如有10 个网页指向网页A,而指向网页B 的链接却只有2 个,则说明网页A 比网页B更加重要。,(二)排序算法：GOOGLE的PageRank技术事实上,在实际计算网页的PageRank 值时,Google 还考虑到网页A 的

12、所有链入网页(链接到某网页的其它网页称为该网页的链入网页)对它的推荐能力(即由于它们对网页A的链接,使人们认为网页A 的重要程度)和推荐程度(即它们认为网页A 的重要程度)。一个网页本身的PageRank 值越高,则它对其链出网页(从某个网页链出的网页称为该网页的链出网页)的推荐能力就越大;一个网页的链出网页越少,那么它对其中一个链出网页的推荐程度就越高。,我们可以用以下公式来简要表达Google 关于网页PageRank 值的计算:PR(A)=(1-d)+d(PR(T1)/C(T1)+.+PR(Tn)/C(Tn)其中,PR(A)是指网页A 的PageRank 值;T1,T2,.,Tn 是网页

13、A 的链入网页;PR(T i)是指网页T i 的PageRank 值(i=1,2,.n);C(T i)是指网页T i 的链出网页的数量(i=1,2,.n);d 是一个衰减因子,0 d 1,通常取值为0.85。,(二)排序算法：GOOGLE的PageRank技术可见,一个网页的PageRank 值,主要取决于以下三个因素:(1)该网页的链入数量;(2)该网页的链入网页本身的PageRank 值;(3)该网页的链入网页本身的链出数量。显然,根据以上公式,一个网页的链入数量越多、这些链入网页的PageRank 值越高、这些链入网页本身的链出数量越少,则该网页的PageRank 值越高。,(二)排序算

14、法：GOOGLE的超文本匹配分析技术(Hypertext-Matching Analysis)不仅仅关注关键词在网页上出现的次数,它还对该网页的内容加以分析，如分析关键词的字体、字号以及关键词在网页中出现的精确位置,并且对该网页以及该网页所链接的内容进行全面检查,从而判断该网页与检索需求的匹配程度。,四、查询/存储技术、Cache Server介绍,(一)查询/存储技术：存储技术是搜索引擎在提供搜索服务时的关键技术，系统如何去存储上百亿的网页数据，如何科学高效地提供搜索结果，这些都会影响用户的“搜索用时”。搜索引擎之所以能够给同时给众多用户，在豪秒级的范围内就能提供搜索结果，其技术秘密就是绝大

15、部分查询结果都是提前完成运算，搜索结果早已存储在其服务器上。数据的存储，当然会受硬件条件的影响，不能够把所有数据都存储在内存中，部分数据还需存储在硬盘中，这其中就有个存储策略。存储网页数据时，权值高的网页数据存储在内存，权值低的存储在硬盘。,四、查询/存储技术、Cache Server介绍,(一)查询/存储技术：搜索引擎的数据存储主要分为两部分：第一部分：网页数据，包含：网页编号、URL、标题、内容摘要、网页大小等。第二部分：词库索引数据，包含：中文词库中的字词、英文单词、每个字词对应网页编号队列等。网页编号是唯一编号，不得重复。查询时，通过词库索引得到网页编号，然后在网页数据中，得到各自网页

16、的相关数据。,四、查询/存储技术、Cache Server介绍,(一)查询/存储技术：对于每一个网页，包含：网页编号、URL、标题、内容摘要、网页大小等信息。可由下面结构体来描述：(1)网页编号char16(2)URLchar256(3)标题char56(4)内容摘要char256(5)网页大小char8这样一来，每个网页数据的存储大小为592字节。网页数据的网页编号是连续的，所以网页数据的存储也可以连续存储。,四、查询/存储技术、Cache Server介绍,(一)查询/存储技术：“网页数据”的存储分为内存存储和硬盘文件存储两种方式:(1)内存存储方式时，因为每个网页数据都是大小一样的，再加

17、上数据存储是连续的，所以在查询时，只要知道数据存储的起始位置，就可直接算出网页数据的开始及结束位置，从而获得网页数据信息。1G内存大概能存储180万条网页信息（每条592字节）。(2)硬盘文件方式存储，把连续一定数量的网页数据信息，写入到一个文件中去，比如说10万条存储为一个文件，然后把全部硬盘存储的网页数据都存储到硬盘文件系统中去。这样一来，基于硬盘文件存储的网页数据在读取时，就要先算出来网页数据存储在那个文件，然后打开文件读去出来该网页数据信息。硬盘文件方式存储，也是全文检索系统中最主要的存储方式。内存存储查询速度快，但信息存储总量有限；硬盘文件方式存储查询速度慢，高并发查询时还容易造成硬

18、件快速损耗，但存储容量巨大。,四、查询/存储技术、Cache Server介绍,(一)查询/存储技术：“词库索引数据”的存储采用内存存储方式:对于每一篇网页内容，采用存储的分词算法进行处理，分出来的词为最多的分法，方便对各个相关字词都能建立索引。所有的网页内容都以按照排序算法从大到小的顺序排列好，所以，每个字词的网页索引队列也是按照排序算法从大到小的排列。词库中所有字词，都是按照Hash分布来排列，便于查询词分词后能够快速找个各个词库中字词对于的网页结果ID队列。,四、查询/存储技术、Cache Server介绍,(一)查询/存储技术：搜索引擎常规存储/查询步骤如下：(1)对搜索词进行分词处理

19、，看能分出来多少个字词；举例说明：比如说用户的搜索词为“北大搜索引擎”，系统在接到这个查询语句后，对其进行查询词分词处理，分词后为“北大”+“搜索引擎”。,用户查询词,北大搜索引擎,北大+搜索引擎,查询词分词后,四、查询/存储技术、Cache Server介绍,(一)查询/存储技术：搜索引擎常规存储/查询步骤如下：(2)通过Hash查找到步骤(1)中各个字词的网页ID队列；举例说明：系统得到“北大”和“搜索引擎”各自的Hash值，比如说Hash值“北大”为256，“搜索引擎”为1024，然后找到这两个词各自的网页ID队列，如下图所示两个队列为“网页ID队列2”和“网页ID队列4”。,北大,25

20、6,256,北京,北大,网页ID序列1,网页ID序列2,搜索引擎,1024,1024,搜索,搜索引擎,网页ID序列3,网页ID序列4,四、查询/存储技术、Cache Server介绍,(一)查询/存储技术：搜索引擎常规存储/查询步骤如下：(3)对步骤(2)中找到个各个网页ID队列做“与”、“或”、“非”的逻辑运 算；(4)获得最后的搜索结果网页ID队列。举例说明：“北大”和“搜索引擎”对应队列为“网页ID队列2”和“网页ID队列4”，对这两个队列做“与”运算。,北大,网页ID序列2,1,3,5,9,11,搜索引擎,网页ID序列4,1,2,5,8,11,与运算,1,5,11,网页ID序列,四、查

21、询/存储技术、Cache Server介绍,(一)查询/存储技术：搜索引擎常规存储/查询步骤如下：(5)完成分页显示处理，计算出最后要显示的各个网页ID队列(互联网搜索网页时一般每页显示10条,所以,这个数目最多为10)，通过这些网页ID，查找到相关的网页结构体存储内容，显示搜索结果给用户。举例说明：“北大”和“搜索引擎”是用户查询词进行分词出来的两个词，在具体的网页标题和网页内容摘要中，分别对这两个词做红色醒目标记。,四、查询/存储技术、Cache Server介绍,(二)Cache Server：WebServer在接受到搜索请求后，对搜索结果完成查询时分词处理，然后向“索引服务器”发出查

22、询请求，“索引服务器”返回结果；WebServer对结果进行必要处理，然后向“网页内容”服务器通信，获得各个网页内容；最后WebServer给用户显示搜索结果。,WebServer,索引服务器Index Server,网页内容服务器Page Content Server,用户,四、查询/存储技术、Cache Server介绍,(二)Cache Server：在对用户行为进行分析后发现，非常多的查询词经常被用户查询，这些词被称为“搜索高频词”。为此，设计出来Cache Server(CS)用于存储这些高频词的搜索结果，每当后台系统更新后，这些高频词先进行查询，然后把查询结果放到CS中，从而减少系

23、统后台压力。,WebServer,用户,CS,索引服务器Index Server,网页内容服务器Page Content Server,四、查询/存储技术、Cache Server介绍,(二)Cache Server：CS还可以部署在“索引服务器”、“网页内容服务器”和WebServer之间，提高这两个后台服务器的效率。,WebServer,CS,CS,索引服务器Index Server,网页内容服务器Page Content Server,四、查询/存储技术、Cache Server介绍,(二)Cache Server：CS自我定期更新策略:CS在其设计中，重点考虑其拦截率，所以，CS的自我定期更新策略就特别重要。CS在其初始化阶段，其存储数据主要来源于原来的日志统计结果；在CS运行后，CS要实时监控当前数据流，并定期进行自我更新，把那些没有被访问过或低访问率的数据删除，增加新增数据。CS虽然可以提高数据访问时的速度，但如果设计出来的CS命中率过低的话，对整个系统效率还反而带来降低，所以CS不能滥用，要结合系统实际负荷来设计和部署CS系统。,