第六章web检索技术

1、信息组织、存储与检索信息组织、存储与检索第六章第六章 Web 检索技术检索技术信息组织、存储与检索信息组织、存储与检索Web 检索概述检索概述信息组织、存储与检索信息组织、存储与检索The World Wide Webn 1989年，蒂姆伯纳斯李在日内瓦欧洲离子物理研究所（CERN）开发计算机远程控制时首次提出了Web概念，并在1990年圣诞节前推出了第一个浏览器。 n 接下来的几年中，他设计出HTTP、URL和HTML的规范，使网络能够为普通大众所应用 n超文本传输协议(HTTP，HyperText Transfer Protocol)是互联网上应用最为广泛的一种网络传输协议 ;n统一资源定

2、位符（URL，UniformResourceLocator）也被称为网页地址，是因特网上标准的资源的地址;n超文本标注语言（HTML,HyperText Markup Language ）是为“网页创建和其它可在网页浏览器中看到的信息”设计的一种标记语言。信息组织、存储与检索信息组织、存储与检索Web Search 历史历史n1990年，搜索引擎的祖先Archie，是第一个自动索引互联网上匿名FTP网站文件的程序；n1993年，早期的 web robots (spiders) 用于收集 URL:nWorld Wide Web WanderernALIWEB (Archie-Like Index

3、 of the WEB)nWWW Worm (The World Wide Web Worm)n1994年，Stanford 博士生 David Filo和Jerry Yang 开发手工划分主题层次的Yahoo；信息组织、存储与检索信息组织、存储与检索Web Search 历史历史n1994年4月，WebCrawler是互联网上第一个支持搜索文件全部文字的全文搜索引擎；n1994年7月，Lycos提供相关性排序、前缀匹配和字符相近限制，第一个在搜索结果中使用了网页自动摘要，且数据量 较大；n1995年， Metacrawler元搜索引擎，用户只需提交一次搜索请求，由元搜索引擎负责将从各独立搜索

4、引擎返回的所有查询结果，集中起来后返回给用户；信息组织、存储与检索信息组织、存储与检索Web Search 历史历史n1995年12月，AltaVista是第一个支持自然语言搜索的搜索引擎，是第一个实现高级搜索语法的搜索引擎（如AND, OR, NOT等) ；n1995年，Larry Page开始学习搜索引擎设计，于1997年注册了的域名，1997年底，开始提供Demo。1999年2月，Google完成了从Alpha版到Beta版的蜕变。Google公司则把1998年9月27日认作自己的生日。nGoogle在Pagerank、动态摘要、网页快照、多文档格式支持、多语言支持、用户界面等功能上的革

5、新，再次永远改变了搜索引擎的定义；信息组织、存储与检索信息组织、存储与检索Web Search 历史历史n北大天网 1997年10月29日正式在CERNET上提供服务；n2000年1月，李彦宏与徐勇在北京中关村创立了百度（Baidu）公司；n2001年8月发布B搜索引擎Beta版；n2001年10月22日正式发布Baidu搜索引擎；n核心技术：超链接分析，通过分析链接网站的多少来评价被链接的网站质量。信息组织、存储与检索信息组织、存储与检索Web Challenges for IRn 数据的分布性：数据的分布性：文档散落在数以百万计的不同服务器上，没有预先定义的拓扑结构相连。n 不稳定的数据高

6、比例：不稳定的数据高比例：许多文档迅速地添加或删除n 大规模：大规模：网络数据量的指数增长，由此引发了一系列难以处理的规模问题。n 无结构和冗余信息：无结构和冗余信息：每个HTML页面没有统一的结构, 许多网络数据是重复的，将近 30% 的重复网页.n 数据的质量数据的质量: 许多内容没有经过编辑处理，数据可能是错误的，无效的。错误来源有录入错误，语法错误等。n 异构数据：异构数据：多媒体数据, 语言,字符集等. 信息组织、存储与检索信息组织、存储与检索中文网页增长情况中文网页增长情况信息组织、存储与检索信息组织、存储与检索Web Search的三种形式的三种形式n 基于超文本/超媒体的信息浏

7、览；n 基于目录的信息查询；n由人工收集或者由Web站点的作者主动提交文档；n人工对Web站点和文档进行评价、分类并给出简要描述；n按照主题分类并以树状的形式对Web信息资源进行组织；n对Web信息资源的分类以及描述信息建立索引；n 基于搜索引擎的信息检索；n使用robot遍历Web，将Web上的信息下载到本地文档库；n对文档内容进行自动分析并建立索引；n检查索引找出与用户查询相匹配的文档（或链接）。信息组织、存储与检索信息组织、存储与检索Web信息检索系统的分类信息检索系统的分类Web搜索引擎元搜索引擎信息检索agent目录用户信息组织、存储与检索信息组织、存储与检索信息组织、存储与检索信息

8、组织、存储与检索Web 搜索引擎工作原理搜索引擎工作原理信息组织、存储与检索信息组织、存储与检索Web搜索引擎的工作过程搜索引擎的工作过程n网页爬行下来；n预处理：网页去重，正文提取，分词等；n建立索引；n接受用户请求，检索词串的处理，查询重构；n找到满足要求的列表；n根据连接和文本中的词进行排序输出。信息组织、存储与检索信息组织、存储与检索Web搜索引擎的结构搜索引擎的结构信息组织、存储与检索信息组织、存储与检索Web搜索引擎的基本要求搜索引擎的基本要求n搜索引擎示意图搜索引擎网页数据库q1, q2, q3 L1, L2, L3 qi：用户通过浏览器提交的查询词或者短语Lj：在一个可接受的时

9、间可接受的时间内返回一个和用户查询匹配匹配的网页信息列表列表信息组织、存储与检索信息组织、存储与检索Web搜索引擎的基本要求搜索引擎的基本要求n相关概念n可以接受的时间n即响应时间，通常在“秒”级，是衡量搜索引擎可用性的一个基本指标n匹配n网页中以某种形式包含有 q 的内容n列表n蕴含着一种“序”信息组织、存储与检索信息组织、存储与检索Web搜索引擎体系结构搜索引擎体系结构n 小型的搜索引擎系统一般是集中式的结构 n系统实现简单，花费的资源比较少 n自身处理能力比较弱，能支持同时访问用户数量也比较小 n 很多搜索引擎采用了升级Web数据采集系统硬件的方法 n使用大型机和并行机作为采集系统的硬件

10、使采集能力提高 n升级硬件的方法扩展性有限，性价比也不高 n 用网络连接多台微机组成一个分布式的机群系统提供的分布式网络服务 n 现代网络服务的体系结构已经由集中式向分布式转变 信息组织、存储与检索信息组织、存储与检索分布式结构分布式结构:主次结构主次结构信息组织、存储与检索信息组织、存储与检索分布式结构分布式结构:对等结构对等结构信息组织、存储与检索信息组织、存储与检索Web搜索引擎系统组成搜索引擎系统组成nWeb搜索引擎系统可以被分成以下四个大的子系统：nWeb数据采集系统n网页预处理系统n索引检索系统n检索结果排序系统信息组织、存储与检索信息组织、存储与检索Web信息采集信息采集信息组织

11、、存储与检索信息组织、存储与检索Web信息采集的特点及意义信息采集的特点及意义n信息采集是搜索引擎获得数据来源的过程，保证了信息检索的召回率；n信息采集的目标：快速获得高质量的网页；n最主要的作用n采集网上的信息n网页，文本，ppt, doc ,音乐，图片n及时更新信息n增加新出现的链接n删除死链接信息组织、存储与检索信息组织、存储与检索Spiders (Robots/Crawlers/Wander)n从一个URL根集开始搜索；n根据这些网页的链接寻找另外的网页；n将遇到的所有新的网页建立索引；n也允许直接索引用户提交的网页；信息组织、存储与检索信息组织、存储与检索爬取过程爬取过程WebURL

12、s frontierUnseen WebSeedpagesURLs crawledand parsed信息组织、存储与检索信息组织、存储与检索采集的遍历算法采集的遍历算法n广度优先 VS 深度优先n广度优先：先采集完同一层的网页，再采集下一层网页；n深度优先：先沿一条路径采到叶节点，再从同层其他路径进行采集；n网站采集 VS 全局URL采集n网站采集：一个网站一个网站采集；n全局URL采集：将所有URL放入一个URL池，从中使用某种方法进行选择；信息组织、存储与检索信息组织、存储与检索Web数据采集系统的分类数据采集系统的分类n基于整个网络的数据采集：基于整个网络的数据采集：一段时间以后重新采

13、集所有网页，全部采完以后替换原来的网页；n采集数据广，采集速度快，适用于广泛主题的搜索；n采集数据乱，数据利用率低，页面失效率高，采集周期长；n增量式数据采集：增量式数据采集：只按照某种策略采集那些可能新增、变化的网页，并删除那些已经不存在的网页；n极大地减小数据采集量进而极大地减小采集时空开销；n增加了一定的判别开销。信息组织、存储与检索信息组织、存储与检索Web数据采集系统的分类数据采集系统的分类n 基于主题的数据采集：基于主题的数据采集：选择性的搜寻那些与预先定义好的主题集相关页面进行采集 ；n给定特定的种子URL，垂直搜索；n采集页面更加有针对性，采集效率更高；n采集速度较慢，判别相关

14、性带来较大的开销n 迁移的迁移的Web数据采集：数据采集：被采集者自己上载到要采集的服务器中，在当地进行采集，并将采集结果压缩后，回传到本地 ；n大量的节省了Web资源，大量的剪裁工作将在被采集对象的服务器上完成 ；n不被采集对象所信任 ；信息组织、存储与检索信息组织、存储与检索Crawler基本思想基本思想信息组织、存储与检索信息组织、存储与检索WebWeb有向图有向图网页为节点HTML链接引用为有向边信息组织、存储与检索信息组织、存储与检索系统框图系统框图信息组织、存储与检索信息组织、存储与检索抓取网页通信实例抓取网页通信实例信息组织、存储与检索信息组织、存储与检索单个采集线程个工作过程单

15、个采集线程个工作过程n 将url解析成host和file；n例如：url： http:/ nfile: /asp/customercenter/center_home.aspn 根据host（ ）做DNS解析；n 创建一个socket，用于网络通信；n 把创建的socket编号和DNS解析得到的网络地址作为参数传递给connect()函数，进行本地服务器和远程网页服务器的连接操作；信息组织、存储与检索信息组织、存储与检索单个采集线程个工作过程单个采集线程个工作过程n在本地服务器缓冲区中组装http请求；n用write()函数将组装好的http头发给网页服务器；n调用read()函数读从网页服务

16、器返回的网页数据；n当read()函数返回的字节数是0的时候，说明网页已经下载完毕；n调用close()函数终止与网页服务器的连接；n将网页保存到本地服务器；信息组织、存储与检索信息组织、存储与检索采集中的采集中的“礼貌礼貌”问题问题n遵守网站上发布的Robot.txt 采集限制协议；n采集时尽量不要太过密集地采集某个网站，这种密集访问导致普通用户正常浏览网站产生困难。有些网站会严密控制这种密集访问行为。信息组织、存储与检索信息组织、存储与检索网页预处理网页预处理信息组织、存储与检索信息组织、存储与检索网页预处理任务网页预处理任务n网页去重n网络上可能会出现多个域名对应同一个网站的情况或者网站

17、的互相转载;n去除重复的网页是为了避免同一个网站的内容被多次采集和索引;n网页正文提取n在建立索引之前，将网页中对建立索引无用的信息（如广告信息，一些无用的连接信息，一些脚本语言等）进行清理;n分词等信息组织、存储与检索信息组织、存储与检索网页重复情况网页重复情况n内容相同的网页分为四种情况n网页正文完全相同；n网页正文大部分相同只是一些地方做了少量变动；n一个网页的正文是另一个网页的一部分；n两个网页的某些段落相同；n其中前两种情况在相同网页中所占比例最大，大致占到80%左右信息组织、存储与检索信息组织、存储与检索网页去重方法网页去重方法n现在广泛使用的是基于指纹识别（fingerprint

18、ing）思想的网页内容重复性判断方法。n主要思想n是抽取出网页内容中的一系列字符串，计算这些字符串hash值产生指纹；n判断两网页是否相同时只需计算它们的相同指纹个数是否大于一定的阈值即可。信息组织、存储与检索信息组织、存储与检索网页去重方法网页去重方法基于文本块基于文本块n 网页进行预处理，去除格式化信息以及非文字信息n 对网页文本利用一定的策略进行分块，利用hash函数计算每一块的hash值，产生记录文本块信息的三元组，其中h是利用此文本块计算出的hash值，r是文本块所属的网页的编号，l是此文本块在网页正文中的位置；n 将信息存放到hash表中；n 对含有相同文本块的所有网页进行统计；n

19、 如果相同文本块个数占网页中所有文本块个数的比例大于一个阈值则认为两个网页是相同的。信息组织、存储与检索信息组织、存储与检索网页去重方法网页去重方法利用利用shingle和超级和超级shinglen 将文档中一段连续的文字串称为一个shinglen 判断重复的方法n获取网页，对每一篇网页进行预处理，去除结构信息和html信息，产生对应的文字信息；n利用文本信息产生与每个网页对应的shingle集合；n利用两文本的shingle集合来计算两个文本的相同度，如果大于一个阈值则认为这两个网页是内容重复的网页。 (A)、(B)分别是两个文本中包含的shingle集合| )()(| )()(|),(BS

20、ASBSASBAr信息组织、存储与检索信息组织、存储与检索n两种随机选择shingle的方法n将一篇文本D的所有shingle随机排序，然后挑选出前m个保留，挑选出来的shingle记为Fm(D)；n将D中随机排序后的所有shingle的序号对数m进行模运算，保留所有计算结果为0即序号是m的倍数的shingle，这些shingle的集合记为Vm(D)；| )()(| )()(|),(BVAVBVAVBArmmmm网页去重方法网页去重方法利用利用shingle和超级和超级shingle信息组织、存储与检索信息组织、存储与检索网页去重方法网页去重方法基于集合统计基于集合统计n 对文档进行预处理，移

21、除文档中的格式信息等，将文档分解成单词流;n 利用从样本集合中统计出的词的idf并利用一定的策略保留重要的单词（相同的单词只保留一个）；n 利用哈希算法将保留下来的单词计算出一个hash值，并且生成二元组；n 将按照hash值的大小存放到树形结构中，如果树形结构中已经存在和此文档相同hash值的文档则说明它们是内容重复的文档。信息组织、存储与检索信息组织、存储与检索网页去重方法网页去重方法其他其他n 利用相似度计算进行网页去重n 基本思想：利用向量余弦夹角的方法n 计算每两个网页文本向量之间的余弦夹角值，如果该值小于一个阈值，则认为两个网页相同。信息组织、存储与检索信息组织、存储与检索信息组织

22、、存储与检索信息组织、存储与检索正文提取正文提取n大部分网页中除了包含它的主要有用信息（正文）外还含有许多的噪声信息：n网站的导航信息n相关链接和广告等n正文提取的任务就是从给定的网页中抽取出正文信息n文件信息组织、存储与检索信息组织、存储与检索基于基于DOM树的正文提取树的正文提取n DOM（Document Object Model）是由W3C组织发布的一种访问和操作HTML文档的规范。DocumentElement：Text：IloveIR-LABElement：Text：WelcometoHtmlElement：Element：信息组织、存储与检索信息组织、存储与检索基于基于DOM树的

23、正文提取步骤树的正文提取步骤n 利用网页的源文件建立一个DOM树结构；n 遍历DOM树，从网页中删除掉所有不是正文的信息n 广告信息的移除：首先需要建立一个经常更新的广告服务器列表，如果地址是指向列表中的广告服务器地址则将此链接节点删除n 链接群的移除：计算每一个节点所包含的链接个数相对非链接的词个数的比例，如果比例大于一个给定的阈值则删除此节点n 删除不包含重要信息的节点：用户事先指定一些不重要的HTML标签以及一个有用标签至少需要包含多少字符n 上述非正文信息移除掉后，DOM树中剩余的内容就是正文信息，可以直接从余下的树节点中抽取出正文信息信息组织、存储与检索信息组织、存储与检索相关排序相

24、关排序信息组织、存储与检索信息组织、存储与检索搜索引擎的排序重要性搜索引擎的排序重要性n 排序很重要n65%一70%的网民点击搜索结果的第一页。n20%-25%的网民点击搜索结果第二页n3%-4%的网民点击量其他的网页n 排序算法为各公司的机密n Google 拥有PageRank技术n百度拥有超链分析技术n SEO（ Search Engine Optimization搜索引擎优化）n互相博弈信息组织、存储与检索信息组织、存储与检索早期的相关排序技术早期的相关排序技术n根据网页中词项出现的频率进行相关性判断；n用户检索词在网页中的权重高的网页放在靠前的位置n导致关键词堆砌作弊信息组织、存储与

25、检索信息组织、存储与检索超链接分析技术前提超链接分析技术前提nWeb页面内的超链接包含了该页面对其链出页面的判断信息；（出度）n对Internet上的任意一个页面，被其他页面的链接数（即该页面的链入数）越多，表示该页面越受欢迎，其重要性也就越高。（入度）信息组织、存储与检索信息组织、存储与检索链接分析技术分类链接分析技术分类n基于随机冲浪模型，如：PageRank算法n基于Hub和Authority相互加强模型，如：HITS算法信息组织、存储与检索信息组织、存储与检索随机冲浪模型随机冲浪模型n用户选择的起始网页是随机的；n用户会从起始网页含有的超链接中随机选择一个页面继续浏览；n当用户沿着超链

26、接前进了一定数量的网页后，可能会对主题厌倦，这时用户会重新随机选择一个网页进行浏览；n用户会重复以上的过程若干次。信息组织、存储与检索信息组织、存储与检索PageRank算法算法n Larry Page和 Sergey Brin于1998年提出PageRank算法；n 基于以下两个基本假设：n数量假设：如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要；n质量假设：越是质量高的页面指向页面A，则页面A越重要。n 某个页面可能被访问的次数就被定义为网页的权值，即PageRank值；n PageRank值是网页的重要性评价，和用户输入的查询没有任何关系，即算法是主题无关的。信息

27、组织、存储与检索信息组织、存储与检索PageRank 基本思想基本思想n如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR(T)/L(T)，其中PR(T) 为T的PageRank值，L(T)为T的出链数n网页A的PageRank值为一系列类似于T的页面重要性得分值的累加。信息组织、存储与检索信息组织、存储与检索PageRank计算过程计算过程n 在初始阶段：在初始阶段：每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。n 在一轮中更新页面在一轮中更新页面PageRan

28、k得分的计算方法：得分的计算方法：每个页面将其当前的PageRank值平均分配到本页面包含的出链上，每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。 信息组织、存储与检索信息组织、存储与检索PageRank 计算过程计算过程信息组织、存储与检索信息组织、存储与检索PageRank算法举例算法举例n 假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面都链向A，那么A的PR值将是B，C及D的和，则PR(A)=PR(B)+PR(C)+PR(D)；

29、n 继续假设B也有链接到C，并且D也有链接到包括A 的3个页面，则3)()(2)()(DPRCPRBPRAPR信息组织、存储与检索信息组织、存储与检索Pagerank计算公式计算公式NiiiPCPPRddAPR1)()()1 ()(其中，PR(A)是页面A的Pagerank值，PR(Pi)是页面Pi的Pagerank值，页面Pi指向页面A，C(Pi)是页面Pi含有的链接数量，d是阻尼系数，一般取0.85。信息组织、存储与检索信息组织、存储与检索Pagerank算法的特点算法的特点n优点：n是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大

30、降低了查询响应时间。n缺点：n1）人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低；n2）旧的页面等级会比新页面高。信息组织、存储与检索信息组织、存储与检索HITS (Hyperlink-Induced Topic Search)算法的提出算法的提出n 基于商业或竞争因素考虑，很少有WEB网页指向其竞争领域的权威网页n比如“Microsoft” 和 “Netscape”都是浏览器的权威主页，但并不互指；n 权威网页很少具有显式的描述，n比如Google主页不会明确给出WEB搜索引擎之类的描述信息；n PageRank算法中对于向外链接的权值贡献是平均的，H

31、ITS算法考虑了不同链接的重要性 信息组织、存储与检索信息组织、存储与检索HITS算法基本思想算法基本思想n Kleinberg于1998年提出HITS算法n 两个重要概念nAuthority 页面(权威页面权威页面)：是指与某个领域或者某个话题相关的高质量网页；nHub页面(枢纽页面枢纽页面)：指的是包含了很多指向高质量“Authority”页面链接的网页。n 基本思想n一个好的” Authority”页面会被很多好的” Hub ”页面指向；n一个好的” Hub”页面会指向很多好的” Authority”页面；信息组织、存储与检索信息组织、存储与检索Hubs and Authoritiesn

32、合起来趋向于形成如图:Hubs Authorities信息组织、存储与检索信息组织、存储与检索HITS算法简介算法简介n1.根集合(root set)n将查询q提交给基于关键字查询的检索系统，从返回结果页面的集合总取前n个网页作为根集合，记为root，则root满足：n1)root中的网页数量较少；n2)root中的网页是与查询q相关的网页 ；n3)root中的网页包含较多的权威(Authority)网页； 信息组织、存储与检索信息组织、存储与检索HITS算法简介算法简介n2.扩展集合basen在根集root的基础上，凡是与根集内网页有直接链接指向关系的网页都被扩充到集合base。根集基本集信

33、息组织、存储与检索信息组织、存储与检索HITS算法简介算法简介n3.计算扩展集base中所有页面的Hub值（中心度）和Authority值（权威度）n网页i的Authority值a (i) = h (i) ；n网页i的Hub值h (i) = a (i) ；n对a (i)、h (i)进行规范化处理：na (i) = a (i)/|a(i)| ；h (i) = h (i)/ |h(i)| ；n不断重复，若权值没有明显变化，则结束计算；n4.输出排序结果：将页面根据Authority权值得分由高到低排序，取权值最高的若干页面作为响应用户查询的搜索结果输出。信息组织、存储与检索信息组织、存储与检索HI

34、TS算法举例算法举例信息组织、存储与检索信息组织、存储与检索HITS算法的特点算法的特点n优点：n是与用户输入的查询请求密切相关的；n缺点：n计算效率较低；n主题漂移问题；n易被作弊者操纵结果；n结构不稳定。信息组织、存储与检索信息组织、存储与检索HITS算法与算法与PageRank算法比较算法比较n HITS算法是与用户输入的查询请求密切相关的，而PageRank算法与查询请求无关；n HITS算法计算效率比PageRank算法低；n HITS算法只计算base内网页之间的链接关系，Pagerank算法对所有互联网页面进行计算；n PageRank适合部署在服务器端，而HITS算法适合部署在客户端；n HITS算法适合处理具体的用户查询，而Page