Apache Nutch 1.3 学习笔记十一，页面评分机制 OPIC

2024-04-05 20:01•php•阅读 342

1. Nutch 1.3 的页面评分机制

Nutch1.3目前默认还是使用OPIC作为其网页分数算法，但其之后，已经引入了PageRank-like算法，以弥补OPIC算法的不足，目前OPIC算法还是作为Nutch中ScoreFilter扩展点的一个扩展来实现的，而新的LinkRank算法有一个叫做org.apache.nutch.scoring.webgraph的包来对网页进行分数计算，它可以解决OPIC解决不了的问题，一个是重复地抓取页面，会引起那些被抓取的页面重要性增加；另一个是同时新添加的页面必须进行抓取，这样会使整个网络的总cash流通量增加，这样会造成那些没有重复抓取的页面重要性降低。

2. 什么是OPIC算法及其特点

下面内容来自[http://www.endless-loops.com/2011/03/nutch%E6%BA%90%E7%A0%81%E4%B8%AD%E7%9A%84%E9%93%BE%E6%8E%A5%E5%88%86%E6%9E%90%E7%AE%97%E6%B3%95-497.html]

OPIC算法是针对静态图的。OPIC算法的基本思想是：每个页面都有一个初始的cash，在抓取某页面时，该页面的cash会平均地分配到其所接向的页面，总的整个网络图中总的cash量是个定值，在抓取网页的过程这些一定量的cash在页面之间流通，很直观地，OPIC算法中页面的重要性就定义为流通过程中流过该页面的cash的总量在总流通量中占的比重。

对于每个网面(图中的结点)，OPIC算法维护两个值cash与history，cash是网页当前的cash值，history表示的则是该网页从OPIC算法开始到最后一次被抓取，获得的cash的总和。cash的初始值一般为1/n (n为网页总数)，history初始值为0。

OPIC算法使用两个向量C[1,…,n] 和H[1,…,n]分别表示各个网页的cash值和history值，为了优化算法，还引入一个变量G，使每一次抓取网页时都有G=|H|=∑i H[i]，原论文中OPIC算法的伪代码如下：

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

OPIC算法的几个问题：

1.无外向链接的sink页面处理：

OPIC算法中有个虚拟网页 (virtual page)的概念，虚拟网页与所有网页之间都有双向链接。

2.收敛性：

OPIC算法将网页重要性的计算集成到了网页抓取的过程中，OPIC算法依赖于反复的抓取，一个重要的问题就是（*）式的值在页面反复抓取过程中是收敛的，只有确保这一点算法才是正确有意义的，关于收敛性的证明，原论文里有严密的证明，这里只提示一下。

3.抓取策略

上面提到OPIC算法依赖于反复抓取，那么抓取策略就是个重要问题了，抓取策略直接影响网面重要性（*）式的收敛速度，事实上，理论与实验都证明贪心法中是最好的策略，即优先抓取那些cash值高的页面。

为了解决OPIC算法的收敛性问题，后来有人提出了Adaptive OPIC算法,它主要引一个时间窗(time window)的概念，它的点主要在于将网页重要性的计算集成到网页抓取的过程中了，简化了模型，简化了网页重要性值的求解。

3. OPIC在NUTCH中的应用

在Nutch1.3的源码org.apache.nutch.scoring.opic包OPICScoringFilter类的注释里提到Nutch实现的链接分析算法是基于《Adaptive On-Line Page Importance Computaion》。Nutch把它做为一个ScoringFilter插件来对付，也就是说用户可以扩展自已的分数算法，

其中ParseOutputFormat是用来为计算分数做准备，而FetchOutputFormat中的RecordWriter集成了ParseOutputFormat,抓取解析后的网页都会通过ParseOutputFormat生成的RecordWriter写出去，而这个计算OPIC的方法就是在这个RecordWriter中调用的。

4. Nutch OPIC源代码分析

下面是OPICScoringFIlter的distributeScoreToOutlinks方法。源代码如下：

float score = scoreInjected; //得到插入的分数，不过好像没用
// 得到解析后初始化的分数，这个分数在FetchThread在对网页解析之前进行了设置
// scfilters.passScoreBeforeParsing(key, datum, content);
String scoreString = parseData.getContentMeta().get(Nutch.SCORE_KEY);
if (scoreString != null) {
try {
score = Float.parseFloat(scoreString);
} catch (Exception e) {
e.printStackTrace(LogUtil.getWarnStream(LOG));
}
}
// 得到有效的网页个数
int validCount = targets.size();
if (countFiltered) {
score /= allCount;
} else {
if (validCount == 0) {
// no outlinks to distribute score, so just return adjust
return adjust;
}
score /= validCount;
}
// internal and external score factor
float internalScore = score * internalScoreFactor; // 设置内链接的分数值，乘以一个内链接的权重因子，默认为1.0f
float externalScore = score * externalScoreFactor; // 设置外链接的分数值，乘以一个外链接的权重因子，默认为1.0f
for (Entry<Text, CrawlDatum> target : targets) {
try {
String toHost = new URL(target.getKey().toString()).getHost();
String fromHost = new URL(fromUrl.toString()).getHost();
if(toHost.equalsIgnoreCase(fromHost)){
target.getValue().setScore(internalScore); // 设置内链接的贡献值
} else {
target.getValue().setScore(externalScore); // 设置外链接的贡献值
}
} catch (MalformedURLException e) {
e.printStackTrace(LogUtil.getWarnStream(LOG));
target.getValue().setScore(externalScore);
}
}
// XXX (ab) no adjustment? I think this is contrary to the algorithm descr.
// XXX in the paper, where page "loses" its score if it's distributed to
// XXX linked pages...
return adjust;
}