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地址过分密集的访问 适当地规划网页的抓取，限制单位时间内对一个网站抓取网页的数量,体系结构,质量 在有限的时间，搜集