Web搜索引擎工作原理和体系结构.ppt
第二章 Web搜索引擎工作原理和体系结构,张 宇信息检索研究室计算机科学与技术学院,主要内容,基本要求网页搜集预处理查询服务体系结构本章小结,主要内容,基本要求网页搜集预处理查询服务体系结构本章小结,基本要求,搜索引擎示意图,搜索引擎,网页数据库,q1,q2,q3,L1,L2,L3,qi：用户通过浏览器提交的查询词或者短语Lj：在一个可接受的时间内返回一个和用户查询匹配的网页信息列表,基本要求,相关概念可以接受的时间即响应时间，通常在“秒”级，是衡量搜索引擎可用性的一个基本指标匹配网页中以某种形式包含有 q 的内容列表蕴含着一种“序”,基本要求,搜索引擎三段式工作流程,网页搜集,预处理,查询服务,主要内容,基本要求网页搜集预处理查询服务体系结构本章小结,网页搜集,搜索引擎软件系统操作的数据用户查询内容不可预测海量网页数量上动态变化需要系统去抓取,网页搜集,网页的抓取时机即时抓取用户提交查询的时候即时去网上抓取网页缺点：系统效益不高（重复抓取网页）预先搜集（直接或间接）定期搜集每次搜集替换上一次的内容优点：实现简单缺点：时新性（freshness）不高；重复搜集带来的额外宽带开销增量搜集,网页搜集,网页的抓取时机（续）增量搜集开始时搜集一批网页，以后只搜集新出现的网页搜集那些在上次搜集后有过改变的网页发现自从上次搜索后已经不再存在了的网页，并从网页库中删除优点：每次搜集的网页量不是很大，可以经常启动搜集过程；时新性比较高缺点：系统实现比较复杂；不仅搜集过程复杂，而且后续创建索引的过程也很复杂,网页搜集,如何抓取网页爬取Web上的网页集合看成一个有向图搜集过程搜集过程从给定的初始URL集合S（种子）开始沿着网页中的链接，按照先深、先广或者某种遍历策略，不停地从S中移出URL，下载相应的网页解析出网页中的超链接URL，看是否已经被访问过，将未访问过的URL加入集合S,网页搜集,如何爬取网页（续）方法2系统第一次全面网页搜集后，系统维护相应的URL集合S，以后的搜集基于该集合每搜到一个网页，如果它发生改变并含有新的URL，则将它们对应的网页也抓取回来，并将这些新的URL也放到集合S中如果S中某个URL对应的网页不存在了，则将它从S中删除,网页搜集,如何爬取网页（续）方法3网站拥有者主动向搜索引擎提交它们的网址（为了达到宣传的目的）系统在一定时间内（两天到数月不等）定向向那些网站派出“蜘蛛”（spider）程序，扫描该网站所有的网页并将有关信息存入数据库中,主要内容,基本要求网页搜集预处理查询服务体系结构本章小结,预处理,关键词的提取网页源文件文字内容HTML标记为支持后面的查询服务，需要从网页源文件中提取出能够代表它的内容的一些特征关键词是这种特征最好的代表词典分词软件（切词软件）网页由一组词来表示：p=t1,t2,t3,tn，ti 去除停用词（stop words）,预处理,重复或转载网页的清除重复网页网页的内容完全相同，未加任何修改转载网页网页的内容基本相同，但有可能有一些额外的编辑信息天网统计结果表明，网页的重复率大约为4（2003）搜集网页时消耗机器时间和网络带宽资源出现在查询结果中，会引起用户的抱怨,预处理,链接分析传统信息检索仅仅分析正文内容的文字，最多加上词频，TF（term frequency）文档频率：DF（document frequency）引入HTML标记，会有所改善和之间的内容要比和之间的内容重要指向其他文档、网页的链接“北大学报”、“北京大学学报社会科学版”,预处理,网页重要程度计算搜索引擎返回给用户的是：一个和用户查询相关的结果列表一个网页如何比另一个网页重要？被引用多的就是重要的（Google，PageRank）,主要内容,基本要求网页搜集预处理查询服务体系结构本章小结,查询服务,预处理之后得到的结果的内部表示：原始网页文档URL和标题编号所含的重要关键词的集合（以及它们在文档中出现的位置信息）其他一些指标（重要程度、分类代码）,查询服务,查询服务子系统的功能系统得到一个关键词输入，能迅速给出相关文档编号的集合输出，从“集合”生成“列表”倒排文件的生成（放到预处理阶段更合适）,查询服务,查询方式和匹配查询方式：用户提交查询的形式利用词或者短语来直接表达用户信息需求代表了大多数的情况实现起来比较简单q0表示用户提交的原始查询q0=“网络与分布式系统实验室”分词：“网络 与 分布式 系统 实验室”删除那些没有查询意义或者在每篇文档中都会出现的词最后形成参加匹配的查询词表：q=网络，分布式，系统，实验室,查询服务,结果排序给定一个查询结果的集合：R=r1,r2,rn列表，就是按照某种评价方式，确定出R中元素的一个顺序确定检索结果和查询之间的相关性的难点不仅和查询词有关，而且和用户背景有关基于词汇出现频度的方法一篇文档中包含的查询中的词越多，该文档就应排在前面一个词在越多的文档中出现，该词用于区分文档文档相关性的作用越小,查询服务,文档摘要搜索引擎给出的结果每个条目有三个基本元素：标题、网址和摘要摘要生成方法静态方式按规则提取网页正文中的文字生成的摘要和用户查询需求无关动态方式响应查询的时候，根据查询词在文档中出现的位置，提取出周围的文字，在显示时查询词标亮为了保证效率，在预处理阶段需要记录每个词在文档中出现的位置,主要内容,基本要求网页搜集预处理查询服务体系结构本章小结,搜索引擎的体系结构,体系结构,效率如何利用尽量少的资源（计算机设备、网络带宽、时间）来完成预定的网页搜集量一台计算机利用多个进程上百个进程或上千个进程利用多台计算机同时进行搜集（第六章）并不是设备越多越好，网络带宽会成为瓶颈分布式搜集，让多台设备分布在网络上的不同位置服务器方可能来不及提供所需的网页,体系结构,“礼貌”网页被搜索引擎索引，从而可能得到更多的访问流量搜索引擎的“密集”抓取活动阻碍了用户通过浏览器的访问监视器监视是否有来源于单个IP地址过分密集的访问适当地规划网页的抓取，限制单位时间内对一个网站抓取网页的数量,体系结构,质量在有限的时间，搜集有限的网页，不要漏掉那些很重要的网页越多人看过的网页越重要PageRank保证每个网页不被重复抓取,主要内容,基本要求网页搜集预处理查询服务体系结构本章小结,本章小结,掌握搜索引擎的三段式工作流程掌握网页搜集、预处理、查询服务的基本功能了解搜索引擎的体系结构,
