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