本文共 2327 字,大约阅读时间需要 7 分钟。
这一代以google的PageRank为最大代表,主要分析链接见得关系
这一代主要是分析用户行为,以理解用户为最大目标
互联网页面可以分为5个部分:
* 已下载页面集合 * 过期页面集合 * 待下载页面集合 * 可知页面集合 * 不可知页面集合爬虫可划分为三类:
* 批量型 (Batch Crawler): 抓取比较明确的范围和目标。 * 增量型 (Incremental Crawler): 不断抓取,及时更新。 * 垂直型 (Focused Crawler): 抓取某个特定主题内容。就是对已经下载的网页应用PageRank算法,得到需要下载的URL和顺序。
OCIP就是在线页面重要性计算,可以看做是PageRank的一种改进算法。在算法开始之前,每个页面都有一个相同的cash值,每当下载一个页面,就把cash值平均分配各页面的中的连接,把自己的cash值清空,然后根据cash的大小排序,形成带抓取的页面。
以网站为抓取单位,大网站优先。
该策略建立在:过去频繁更新的网页,以后也会频繁更新,所以为了估计出网页合适更新,可以通过历史更新情况来判断。这种方法通常利用泊松过程对网页变化建模。
也就是用户越先看到的网页,越先更新。就是根据网页重要度来更新,因为越重要的网页越排在最前面,而用户搜索一个主题之后,会看的网页结果基本都是前面的。
把不通的网页分类,然后对每个类别进行采样分析更新频率,通过得到的该频率来设定这一类网页的更新周期。
也就是一般不再连接中的网页或是数据。 比如机票查询,酒店信息查询等需要输入查询条件,然后在数据库中组合数据的信息。
Google提出了富含信息查询模板 (Informative Query Templates) 技术。原理:把每一个查询条件作为一个维度,然后一维度一维度的累加查询,只到最后查询出来的内容大多数重复或相同内容,则停止。重复或相似内容越少,则说明包含的信息越丰富,即称为富含信息。
Google的这个算法ISIT,和数据挖掘里面的Apriori很像。分布式爬虫一般分为3个层级:
* 分布式数据中心 * 分布式服务器 * 分布式爬虫程序主从分布式爬虫,其中有一台专门负责分配URL连接的服务器,并且处理带抓取URL,以及负责抓取服务器的负载调度。
Google早期就是采用这种架构,但是URL分配服务器容易形成瓶颈。对等分布式爬虫没有URL分配服务器,每台服务器都是一样的。具体URL分配问题,是通过对域名Hash后取模,然后分配到相应的服务器。(Mercator 爬虫采用次架构)。
为了解决Hash取模的问题,UbiCrawler爬虫提出了一致性哈希方法 (Consistent Hash) 来确定分配工作。单词-文档矩阵是表达两者之间包含关系的一种概念模型。
搜索引擎索引其实就是单词-文档矩阵的具体数据结构。可以有不通的方法来实现这个,比如倒排索引,签名文件,后缀树等方式。但是各项试验数据显示,倒排索引是最佳实现。
倒排索引的一些基本术语:
文档集合:
最简单的到排列表:
带词频的到排列表:
带词频和位置信息的倒排列表:
单词词典主要未来维护所有出现过的单词和相关信息,以及单词对应的到排列表在倒排文件中的位置。
所以用来构建单词词典的数据结构,查找效率非常重要,一般使用哈希表+链表和树形结构。在实际系统中,不存在实际的文档标号,而是存储文档差值(D-Gap). 这样以便节约空间。