`
Dustin
  • 浏览: 314385 次
  • 性别: Icon_minigender_1
  • 来自: 广州/成都
社区版块
存档分类
最新评论

OPIC in Nutch

阅读更多

  庄子曾说:“吾生也有涯,而知也无涯,以有涯随无涯,殆已”。当然,我们不能拿老祖宗这句话作为消极怠工的借口,不过在学习和工作的时候,的确需要要分辨事情的轻重缓急,否则一味蛮干,最终结果只能是--“殆已”。

  突然发现这句话对于网络爬虫也是很有启发意义的,对于浩瀚无边的互联网而言,网络爬虫涉及到页面确实只是冰山一角。因此,如何确定一个页面的重要性,从而在抓取过程中进行合理的调度,以最小的代价(硬件、带宽)获取到最大的利益(数量最多的重要的网页)是设计网络爬虫过程中的一个核心问题。
  一个页面是否重要本来是一个比较主观的问题,见仁见智。但是如果大部分人都认为一个页面是重要的,那么我们大都会相信众人的判断,认为这个页面的确“重要”的——这就是Google的PageRank算法的核心思想。不过在具体PageRank中,这个判断的过程是采用网页间的超链接来实现的。PageRank成就了Google的辉煌,自然有它的过人之处,不过PageRank计算对象是所有“已经抓取下来”的网页,该算法通过这些网页的相互连接关系以迭代的方式计算出各个网页的重要性——页面的PageRank。也就是说,我们在计算PageRank的过程中,是不会有新的页面加入的,我们将这种计算方式称为“离线”(off-line)的计算方式。PageRank能够很好地反应出已有页面间的相对重要性,因此十分适合于查询结果的排序。但是,PageRank是一种离线的计算方式,在一次计算过程中不能加入新的页面,而且计算过程是一个迭代过程,需要较长的计算时间,因此并不适合于网络爬虫的URL调度,动态决定URL的抓取顺序。
  针对这个问题,大家提出了很多解决方案[1]。其中,Abiteboul (Abiteboul et al., 2003)[2] 提出了一种基于OPIC (On-line Page Importance Computation)算法的抓取策略.在OPIC中,每一个页面都有一个初始的"cash” 。在抓取的过程中,这些"cash"将会平均地分配给该页面指向的页面,这个分配过程是一次完成的。基于OPIC的网络爬虫在抓取过程中将以待抓取页面累积的"cash"的多少为依据,优先抓取"cash"数量最多的页面。OPIC算法如下所示,其中C[i]表示页面i当前的Cash,H[i]表示在计算过程中页面i累计收到的cash的总数。

   

OPIC:
On-line Page Importance Computation

for each i let C[i] := 1/n ;
for each i let H[i] := 0 ;
let G:=0 ;
do forever
begin
 choose some node i ;
 %% each node is selected
 %% infinitely often

 H[i] += C[i];
 %% single disk access per page

 for each child j of i,
 do C[j] += C[i]/out[i];
 %% Distribution of cash
 %% depends on L

 G += C[i];
 C[i] := 0 ;
end

 

  Nutch使用了OPIC作为默认的URL调度策略,但是当前版本(0.9)的OPIC实现与Abiteboul在论文提出的OPIC并不完全相同,具体表现为:

  1. Nutch中并没有区分C[i]和H[i],使用score一个变量记录页面累积的分数,在分配过程中也是将这个累积的分数全部平均分配给子页面,分配完毕后分数也并不清零。

  2. Nutch中并没有virtual root page,也就是说叶子页面(即没有outlink的页面)的分数将会丢失。 

 

  Nutch分数计算功能是通过插件的形式提供的,用户可以通过新增插件的方式改变Nutch积分方式。Nutch提供了一个计算分数的接口 ScoringFilter,完成计算分数功能的类通过实现该接口以影响Nutch分数的计算方式,其默认的OPIC分数计算方法由类 OPICScoringFilter 提供。此外,参与计算分数的类还有 ScoringFilters,ParseOutputFormat。其中 ScoringFilters 负责将各个计分插件加载到系统中,并实现链式计分的过程;而ParseOutputFormat 在解析结果输出之前,将页面的分数分配到该页面的各个子页面中,使得Nutch的更新模块可以使用这些数据更新CrawlDB数据库。

  为了能够形象地展示Nutch的URL调度过程,我构建了一个微型的站点,站点只包含了五张网页,其拓扑结构如下图所示。

 

 

 

  下面表格展示了Nutch的抓取流程,表格中,每一行中被粗体标注数字对应的URL为被调度器选中的URL,将在下一轮被抓取;“*”表示该网页已被抓取;“--”表示该网页尚未被系统获知。

 

 

A

B

C

D

E

0injected

1.0

--

--

--

--

1

1.0*

0.5

0.5

--

--

2

1.0*

0.5*

0.5

0.25

0.25

3

1.0*

0.5*

0.5*

0.25

0.75

4

1.0*

1.25*

0.5*

0.25

0.75*

5

1.0*

1.25*

0.5*

0.25*

0.75*

 

  其实社区中也注意到Nutch在实现OPIC上的问题,也提出了自己的解决方案,具体的内容可以参考Nutch官方wiki上FixingOpicScoring[3]一文。

 

Reference
[1] Abiteboul et al., 2003  http://www2003.org/cdrom/papers/refereed/p007/p7-abiteboul.html
[2] Baeza-Yates, R., Castillo, C., Marin, M. and Rodriguez, A. (2005). Crawling a Country: Better Strategies than Breadth-First for Web Page Ordering. In Proceedings of the Industrial and Practical Experience track of the 14th conference on World Wide Web, pages 864–872, Chiba, Japan. ACM Press.
[3] Fixing the OPIC algorithm in Nutch  http://wiki.apache.org/nutch/FixingOpicScoring

 

分享到:
评论

相关推荐

    nutch2.3.1安装文档教程

    summary-basic|scoring-opic|urlnormalizer-(pass|regex|basic)protocol-http|urlfilter-regex|parse-(html|tika|metatags)|index-(basic|anchor|more|metadata) <name>searcher.dir <value>other-searcher-...

    Nutch 1.3 学习笔记

    - **页面评分机制**:Nutch支持多种页面评分算法,如OPIC和LinkRank,这些机制有助于提高搜索结果的相关性和质量。学习笔记第11章提供了OPIC和LinkRank的具体实现细节。 - **Nutch 2.0的主要变化**:学习笔记的最后...

    Nutch插件开发和服务器发布流程

    <value>protocol-http|urlfilter-regex|parse-(html|tika)|index-(basic|anchor)|urlnormalizer-(pass|regex|basic)|scoring-opic|index-self ``` #### 二、插件发布流程 **1. 连接到Linux服务器** - 使用...

    基于OPIC搜集策略的网络爬虫的设计.pdf

    本文讨论了一种基于OPIC搜集策略的网络爬虫的设计,包括爬虫的数据结构、系统模块设计以及相关算法的设计思想。文章还对设计和实现过程中遇到的关键问题进行了评论,并提出了相应的解决方案。 首先,我们明确网络...

    综合检测三Unit5-6(附录音MP3及参考答案).pdf

    这篇文档是针对中学八年级英语的一份综合检测试卷,涵盖了Unit 5到Unit 6的内容。这份试卷主要分为两个部分:听力和笔试,总计100分。 在听力部分,试题设计了各种类型来测试学生的听力理解能力。...

    基于Lucene的医疗搜索引擎排序算法的研究.pdf

    文中提到了几种改进方法,比如张贤的结合词频加权、Direct Hit和PageRank的排序算法,沙阳阳的Vector-PageRank算法,以及袁恩阁的Nutch、中文分词和OPIC排序算法。这些方法都试图解决主题漂移和网页权重分配不均衡的...

    05互联网数据采集-Python.pdf

    在数据采集阶段,爬虫会依据一定的策略,如深度优先策略、广度优先策略、局部PageRank策略或OPIC策略,来决定如何访问和抓取网页内容。 深度优先策略优先访问当前节点的子节点,适用于垂直搜索或站内搜索,但可能...

    pc923数据手册.pdf

    LED作为信号输入端,当电流通过时,会发出特定波长的光,而OPIC则包含一个光探测元件和一个信号处理电路,集成在同一芯片上。当LED发出的光照到OPIC上的光探测元件时,会产生电信号,进而经过内部电路处理后输出,...

    网路爬虫基本原理

    OPIC策略通过给页面分配初始资金,并根据下载页面时获得的链接对资金进行分配,以此来决定抓取顺序。 除了基本的抓取策略,爬虫还涉及更新策略,决定何时重新抓取已下载的网页。历史参考策略依据以往更新历史来预测...

    夏普光耦选型手册

    OPIC输出型光耦通常具有更高的响应速度和更强的抗噪声能力,适用于需要高速数据传输或高抗噪声的应用场景。手册中并未给出具体型号及相关参数,建议参考实际产品目录或联系制造商获取更多信息。 ##### 3. 封装类型...

    网络爬虫基本原理.pdf

    5. OPIC策略:给每个页面分配初始现金,下载页面后将现金分给其链接的页面,按现金数排序抓取。 6. 大站优先策略:优先抓取属于大型网站的页面,因为这些网站通常包含大量信息。 更新策略是处理互联网动态性的关键...

    固体光电子学绪论.ppt

    6. 光电子集成:随着微电子技术的发展,光电子器件的集成化成为可能,光子集成电路(OPIC)和光电混合集成电路的出现,使得光电子系统更加紧凑、高效。 7. 光电子材料与器件:研究新型半导体材料、超导材料、纳米...

    PC900V/PC900VQ

    11. 光电耦合器的“OPIC”:指的是集成了光检测元件和信号处理电路于单一芯片的光电耦合器,是夏普公司的注册商标。 12. 输出特性图表:提供了输入和输出的转移特性,例如前向电压VF、电流IC、耦合电容Ct、输出电压...

    PC4D10S.pdf

    根据提供的文件内容,PC4D10S.pdf 是一个关于PC4D10SNIP0F系列产品的数据手册,这个系列的产品是一款光耦合器,也即光电耦合器(OPIC)。以下是该数据手册中所包含的知识点: 1. 产品系列介绍:PC4D10SNIP0F系列是...

    基于python语言的web数据挖掘与分析研究.pdf

    此外,还有其他算法如Opic策略,它通过算法改进,试图平衡广度和深度的搜索,但其准确性可能受到影响。 本文通过对Web数据挖掘技术的研究分析,提出了以Python及相关库为主要工具,并结合模块化实现方法,建立了一...

    PC929.pdf

    11. **商标和标准**:"OPIC"是SHARP公司的商标,它代表了一种集成光检测元件和信号处理电路的单芯片解决方案。 在实际应用中,工程师会根据这些参数和特性来选择PC929作为隔离和保护电路的一部分,特别是在驱动...

Global site tag (gtag.js) - Google Analytics