搜索引擎基本原理及实现技术PPT学习课件

搜索引擎基本原理及实现技术,1,搜索引擎的工作原理,通用搜索引擎的架构示意图,2,2020/6/11,通用的网络爬虫的框架,3,2020/6/11,爬虫技术总体介绍：(一)网络爬虫是一个自动提取网页的程序，它为搜索引擎从Internet网上下载网页，是搜索引擎的重要组成。网络爬虫使用多线程技术，让爬虫具备更强大的抓取能力。网络爬虫还要完成信息提取任务，对于抓取回来的网页提取出来:新闻、电子图书、行业信息等。对于MP3、图片、Flash等各种不同内容，要实现自动识别、自动分类及相关属性测试（例如：MP3文件要包含的文件大小，下载速度等属性）。,4,2020/6/11,(二)抓取对象：1.静态网页：爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列,直到满足系统的一定停止条件。2.动态网页:分析动态网页参数，按照一定规章，“拼”出所有要被抓取内容URL，只抓取这些特定范围内动态网页。3.特殊内容：比如RSS、XML数据，情况特殊需特殊处理。如新闻的滚动新闻页面，需要爬虫不停地监控扫描，发现新内容马上就进行抓取。4.文件对象：图片，MP3、Flash、视频等文件的抓取，都要特殊处理。比如说：图片抓取出来后，要知道图片文件类型、图片文件的大小、图片的像素大小，还要转换出来缩略图。,5,2020/6/11,爬虫分类,批量型爬虫有明确的抓取范围和目标，当达到这个设定的目标后，即停止抓取过程。增量型爬虫（商业搜索引擎属于此类）持续不断的抓取，对抓到的网页定期更新垂直型爬虫仅关注特定主题内容或者属于特定行业的网页，难点是如何识别网页是否属于指定范畴。,6,2020/6/11,优秀爬虫的特性,高性能URL队列的存储方式会影响性能可扩展性多台服务器多线程抓取，不同区域部署数据中心，将爬虫分配到不同的数据中心健壮性再次启动时能恢复之前抓取的内容和数据结构友好性爬虫禁抓协议和网页禁抓标记,7,2020/6/11,禁止爬虫的几种情况,User-agent:GoogleBotDisallow:/tmp/Disallow:/cgi-bin/Disallow:/users/paranoid/,Robot.txt,禁止索引网页内容,禁止抓取网页链接,8,2020/6/11,Content标签对应的具体含义,9,2020/6/11,爬虫质量的评价标准1、覆盖率2、抓取网页的时新性3、抓取网页的重要性大型商业搜索引擎一般至少包含两套不同目的爬虫系统，一套（freshbot）主要考虑网页的时新性，一套（deepcrawlbot）针对更新不那么频繁的网页。,10,2020/6/11,网页抓取策略,1、宽（广）度优先遍历策略2、深度优先遍历策略3、非完全pagerank策略4、OPIC策略（OnlinePageImportanceComputation）5、大站优先策略,11,2020/6/11,宽（广）度优先策略,将新下载网页中发现的链接直接插入待抓取URL队列的末尾。也就是指网络爬虫会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取在此网页中链接的所有网页。抓取顺序：1,2,3,4,5,6,7,8,9,12,2020/6/11,深度优先策略,从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接.抓取顺序：1,2,5,6,3,7,4,8,9,13,2020/6/11,PageRank简介,1）在初始阶段：网页通过链接关系构建起Web图，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。2）在一轮中更新页面PageRank得分的计算方法：在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。,14,2020/6/11,非完全PageRank策略,对于已经下载的网页，加上待抓取URL队列中的URL一起，形成网页集合，在此集合内进行pagerank计算，计算完成后，将待抓取URL队列里的网页按照PageRank得分由高到低排序，形成的序列就是爬虫接下来应该依次抓取的URL列表。每当下载K个的网页，就将所有下载页面重新计算一遍其非完全的PageRank值。,15,2020/6/11,OPIC策略,OnlinePageImportanceComputation。该算法实际上也是对页面进行一个重要性打分。在算法开始前，给所有页面一个相同的初始现金（cash）。当下载了某个页面P之后，将P的现金分摊给所有从P中分析出的链接，并且将P的现金清空。对于待抓取URL队列中的所有页面按照现金数进行排序。,16,2020/6/11,大站优先策略,以网站为单位来衡量网页重要性，对于待抓取URL队列中的所有网页，根据所属的网站进行分类。对于待下载页面数多的网站，优先下载。,17,2020/6/11,网页更新策略,历史参考策略用户体验策略聚类抽样策略,18,2020/6/11,历史参考策略,假设:过去频繁更新的网页，将来更新也会很频繁。原理：利用泊松过程来对网页的变化建模，预测下次变化时间。将网页划分成不同区域，忽略广告栏或者导航栏等不重要区域的变化，精力集中在变化的主题内容上。,19,2020/6/11,用户体验策略,假设：用户往往只查看前3页的搜索内容。原理：保存网页的多个历史版本，根据过去每次内容变化对搜索质量的影响，得出一个平均值，作为判断爬虫抓取该网页时机的参考依据，对质量影响越厉害的网页，越优先调度重新抓取。,20,2020/6/11,聚类抽样策略,前面两种更新策略都有一个前提：需要网页的历史信息。存在两个问题：1）系统要是为每个系统保存多个版本的历史信息，增加了很多的系统负担；2）新的网页完全没有历史信息，无法确定更新策略。,21,2020/6/11,聚类抽样策略,聚类抽样策略认为，网页具有很多属性，类似属性的网页，可以认为其更新频率也是类似的。要计算某一个类别网页的更新频率，只需要对这一类网页抽样，以他们的更新周期作为整个类别的更新周期。,22,2020/6/11,分布式抓取系统结构,一般来说，抓取系统需要面对的是整个互联网上数以亿计的网页。单个抓取程序不可能完成这样的任务。往往需要多个抓取程序一起来处理。一般来说抓取系统往往是一个分布式的三层结构。,最下一层是分布在不同地理位置的数据中心，在每个数据中心里有若干台抓取服务器，而每台抓取服务器上可能部署了若干套爬虫程序。这就构成了一个基本的分布式抓取系统。,23,2020/6/11,主从式基本结构,有一台专门的Master服务器来维护待抓取URL队列，它负责每次将URL分发到不同的Slave服务器，而Slave服务器则负责实际的网页下载工作。Master服务器除了维护待抓取URL队列以及分发URL之外，还要负责调解各个Slave服务器的负载情况。以免某些Slave服务器过于清闲或者劳累。这种模式下，Master往往容易成为系统瓶颈。,24,2020/6/11,对等式工作结构,所有的抓取服务器在分工上没有不同。每一台抓取服务器都可以从待抓取在URL队列中获取URL，然后对该URL的主域名的hash值H，然后计算Hmodm（其中m是服务器的数量，以上图为例，m为3），计算得到的数就是处理该URL的主机编号。弊端：扩展性较差。,25,2020/6/11,一致性哈希将URL的主域名进行哈希运算，映射为一个范围在0-232之间的某个数。而将这个范围平均的分配给m台服务器，根据URL主域名哈希运算的值所处的范围判断是哪台服务器来进行抓取。如果某一台服务器出现问题，那么本该由该服务器负责的网页则按照顺时针顺延，由下一台服务器进行抓取。,26,2020/6/11,暗网抓取,查询组合问题文本框填写问题,27,2020/6/11,网络爬虫的实现,28,2020/6/11,链接的存储,队列的数据结构待爬取队列已爬取队列失效链接错误链接,29,2020/6/11,网页抓取,Jsoup.jar官方网站/相关学习资料,30,2020/6/11,getElementById(Stringid)用id获得元素getElementsByTag(Stringtag)用标签获得元素getElementsByClass(StringclassName)用class获得元素getElementsByAttribute(Stringkey)用属性获得元素用下面方法获得元素的数据：attr(Stringkey)获得元素的数据attr(Stringkey,Stringvalue)t设置元素数据attributes()获得所以属性id(),className()classNames()获得idclass得值text()获得文本值text(Stringvalue)设置文本值html()获取htmlhtml(Stringvalue)设置htmlouterHtml()获得内部html,31,2020/6/11,trydoc=Jsoup.connect(urlStr).userAgent(Mozilla/5.0(Windows;U;WindowsNT5.1;zh-CN;rv:5)/设置User-Agent.timeout(5000)/设置连接超时时间.get();catch(MalformedURLExceptione)log.error(e);return;catch(IOExceptione)if(einstanceofSocketTimeoutException)log.error(e);return;if(einstanceofUnknownHostException)log.error(e);return;log.error(e);return;,32,2020/6/11,system.out.println(doc.title();Elementhead=doc.head();Elementsmetas=head.select(meta);for(Elementmeta:metas)Stringcontent=meta.attr(content);Elementbody=doc.body();Elementses=body.select(a);for(Iteratorit=es.iterator();it.hasNext();)Elemente=(Element)it.next();href=e.attr(href);,33,2020/6/11,链接提取,机关部处,招生就业,合作交流,34,2020/6/11,工业和信息化部,35,2020/6/11,提高爬虫效率,多线程抓取优化存储结构根据不同类型的链接分别制定抓取策略,36,2020/6/11,实例说明,37,2020/6/11,主要步骤,1.输入：种子页面网址、抓取深度、抓取线程数2.根据初始url获取种子页面的内容注：1）url的合法性（两种方法）a、判断url是否符合协议规则b、判断url是否可以打开while(counts=3)tryURLurl=newURL(urlStr);HttpURLConnectioncon=(HttpURLConnection)url.openConnection();intstate=con.getResponseCode();if(state=200)retu=ok;,38,2020/6/11,break;catch(Exceptionex)counts+;continue;2）种子页面要获取的内容包含标题、正文文本、超链接（开源jar包：jsoup）Documentdoc=Jsoup.connect(sUrl).get();Elementslinks=doc.select(ahref);for(Elementlink:links)StringlinkHref=link.attr(href);/得到href属性中的值，也就是ur地址StringlinkTitle=budge(link.text();/得到锚点上的文字说明,39,2020/6/11,3.根据抓取深度来进行多线程抓取，其实就是多次重复步骤2注：判断url的重复性，推荐用hashset来存储HashSetallurlSet=newHashSet()/定义hashsetallurlSet.contain(url)/判断url是否已经存在allurlSet.add(url)/添加url到allurlSet中4.抓取的过程中要存储页面的信息。存储的