搜索引擎基本原理及实现技术

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