网络爬虫基本原理 高剑飞 ACM2013 2018/11/152018/11/15.

Presentation on theme: "网络爬虫基本原理 高剑飞 ACM2013 2018/11/152018/11/15."— Presentation transcript:

1 网络爬虫基本原理 高剑飞 ACM2013 2018/11/152018/11/15

2 目录 1 4 基本描述 抓取策略 2 5 需要理解的算法 更新策略 3 6 数据分类 Reference ACM2013
2018/11/152018/11/15

3 网络爬虫 网络爬虫（又被称为网页蜘蛛，网络机器人），是一种按照一定的规则，自动的抓取万维网信息的程序或者脚本，是搜索引擎的重要组成。传统爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列，直到满足系统的一定停止条件。 ACM2013 2018/11/152018/11/15

4 聚焦爬虫 传统爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列,直到满足系统的一定停止条件。聚焦爬虫的工作流程较为复杂，需要根据一定的网页分析算法过滤与主题无关的链接，保留有用的链接并将其放入等待抓取的URL队列。然后，它将根据一定的搜索策略从队列中选择下一步要抓取的网页URL，并重复上述过程，直到达到系统的某一条件时停止。另外，所有被爬虫抓取的网页将会被系统存贮，进行一定的分析、过滤，并建立索引，以便之后的查询和检索；对于聚焦爬虫来说，这一过程所得到的分析结果还可能对以后的抓取过程给出反馈和指导。 ACM2013 2018/11/152018/11/15

5 简单流程 :: BFS 下载网页库 已抓取URL 种子URL 待抓取URL DNS解析 && 网页数据 分析 作为初始URL 下载网页
进入已抓取队列 种子URL 待抓取URL 从队列信息中抽取新的URL ACM2013 2018/11/152018/11/15

6 需要理解的算法 ACM2013 2018/11/152018/11/15 1.关键字匹配 :: 字符串匹配
KNUTH-MORRIS-PRATT算法（KMP算法） 有限自动机算法 *BOYER-MOORE算法 2.网页内容冗余 :: 卡时 3.大数量网页处理 :: *分布式 4.防止重复遍历 :: 字符串Hash ACM2013 2018/11/152018/11/15

7 数据分类 ACM2013 2018/11/152018/11/15 1.已下载未过期网页 2.已下载已过期网页：
抓取到的网页实际上是互联网内容的一个镜像与备份，互联网是动态变化的，一部分互联网上的内容已经发生了变化，这时，这部分抓取到的网页就过期了。 3.待下载网页： 也就是待抓取URL队列中的那些页面。 4.可知网页： 还没有抓取下来，也没有在待抓取URL队列中，但是可以通过对已抓取页面或者待抓取URL对应页面进行分析获取到的URL，认为是可知网页。 5.不可知网页： 还有一部分网页，爬虫是无法直接抓取下载的 ACM2013 2018/11/152018/11/15

8 数据分类 :: Baidu 已抓取未过期 已抓取已过期 已知网页 ACM2013 2018/11/152018/11/15

9 数据分类 :: Baidu 不可知网页 ACM2013 2018/11/152018/11/15

10 抓取策略 :: 暴力 ACM2013 2018/11/152018/11/15 1.深度优先搜索 2.广度优先搜索 3.大站优先策略
对于待抓取URL队列中的所有网页，根据所属的网站进行分类。对于待下载页面数多的网站，优先下载。这个策略也因此叫做大站优先策略。 ACM2013 2018/11/152018/11/15

11 抓取策略 :: 技巧 ACM2013 2018/11/152018/11/15 4.反向链接数策略
反向链接数是指一个网页被其他网页链接指向的数量。反向链接数表示的是一个网页的内容受到其他人的推荐的程度。因此，很多时候搜索引擎的抓取系统会使用这个指标来评价网页的重要程度，从而决定不同网页的抓取先后顺序。 在真实的网络环境中，由于广告链接、作弊链接的存在，反向链接数不能完全准确评价网页的重要程度。因此，搜索引擎往往考虑一些可靠的反向链接数。 ACM2013 2018/11/152018/11/15

12 抓取策略 :: 技巧 ACM2013 2018/11/152018/11/15 5.Partial PageRank策略
Partial PageRank算法借鉴了PageRank算法的思想。对于已经下载的网页，连同待抓取URL队列中的URL，形成网页集合，计算每个页面的PageRank值，计算完之后，将待抓取URL队列中的URL按照PageRank值的大小排列，并按照该顺序抓取页面。 6.OPIC策略策略 该算法实际上也是对页面进行一个重要性打分。在算法开始前，给所有页面一个相同的初始现金（Cash）。当下载了某个页面P之后，将P的现金分摊给所有从P中分析出的链接，并且将P的现金清空。对于待抓取URL队列中的所有页面按照现金数进行排序。 ACM2013 2018/11/152018/11/15

13 更新策略 :: 可持久化数据结构 ACM2013 2018/11/152018/11/15 1.历史参考策略
顾名思义，根据页面以往的历史更新数据，预测该页面未来何时会发生变化。一般来说，是通过泊松过程进行建模进行预测。 2.用户体验策略 尽管搜索引擎针对于某个查询条件能够返回数量巨大的结果，但是用户往往只关注前几页结果。因此，抓取系统可以优先更新那些现实在查询结果前几页中的网页，而后再更新那些后面的网页。这种更新策略也是需要用到历史信息的。用户体验策略保留网页的多个历史版本，并且根据过去每次内容变化对搜索质量的影响，得出一个平均值，用这个值作为决定何时重新抓取的依据。 ACM2013 2018/11/152018/11/15

14 更新策略 :: 统计学改进 ACM2013 2018/11/152018/11/15 3.聚类抽样策略
前面提到的两种更新策略都有一个前提：需要网页的历史信息。这样就存在两个问题：第一，系统要是为每个系统保存多个版本的历史信息，无疑增加了很多的系统负担；第二，要是新的网页完全没有历史信息，就无法确定更新策略。 而聚类抽样策略认为，网页具有很多属性，类似属性的网页，可以认为其更新频率也是类似的。要计算某一个类别网页的更新频率，只需要对这一类网页抽样，以他们的更新周期作为整个类别的更新周期。 ACM2013 2018/11/152018/11/15

15 Reference ACM2013 2018/11/152018/11/15 wawlian的个人博客
《这就是搜索引擎——核心技术详解》　　张俊林　　电子工业出版社 《搜索引擎技术基础》　　　　　　　　　刘奕群等　清华大学出版社 ACM2013 2018/11/152018/11/15

16 谢谢观看 ACM2013 2018/11/152018/11/15