文档介绍：网页的收集
1
内容
网页分布的若干特点
Crawler的任务和方法
提高质量:“全”和“好”
改善性能:并行与分布
节省资源:避免“同义”地址
礼貌工作:不给网站造成明显负载
预先知识要求:HTML,HTTP,基本网络程序设计,理解根据一个url抓取一篇网页的程序(fetcher)
2
不同IR系统的资源性质
事先存在、范围明确、固定不变的文档集合
例如,全唐诗,全宋诗,古典哲学著作,…
部分存在,定期更新的文档集合
例如,生物医学周刊,《计算机学报》,CDAL,…
随时间推移逐渐失效的流数据(Streaming data)
例如,沪市股票新闻,国际期货行情,…
分布的,特有(proprietary)信息
例如,联合数据库,CALIS,…
分布的,链接的,公开可访问的文档
例如,Web
不同类型有不同的技术需求
3
网页分布的若干特点
网页:内容(C),物理存在(P),IP地址(A), url(L)
存在有大量内容相同,但物理上不同的,url不同,IP地址不同的网页镜像,拷贝
同一篇(物理)网页可能被多个url指向
. ..
一个url可能对应多个IP地址,从而多个物理的网页(尽管此时内容大都是相同)
例如,一些大门户网站采用的负载分配技术()
4
网页的CPAL(0:不同;1:相同)
C
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
P
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
A
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
L
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
存在
有
有怪
有
无
无
无
无
无
有
有
有
无
无
无
有
有
* 假设没有一台服务器安装两块网卡从而对应两个IP的情况,
5
Web有向图
<href …>
<href …>
<href …>
<href …>
<href …>
<href …>
<href …>
网页为节点
HTML链接引用为有向边
6
有向图的连通性
强连通(strong connectivity):任何两点存在一条有向通路
“根连通”:存在一个节点,从它到每一个其他节点都有一条有向通路
定理:一个强连通的有向图一定是根连通的
7
Web有向图的性质
Web graph at any instant of time contains k-connected subgraphs (but we do not know the value of k, nor do we know a-priori the structure of the web-graph).
If we knew every connected web subgraph, we could build a k-web-spanning forest, but this is a very big "IF.“
还可以细一些,我们实际可以关心“根连通子图”(但)找到那些“根”不容易
8
Web Graph-Search Algorithms I
PROCEDURE SPIDER1(G)
Let ROOT := any URL from G
Initialize STACK <stack data structure>
Let STACK := push(ROOT, STACK)
Initialize COLLECTION <big file of URL-page pairs>
While STACK is not empty,
URLcurr := pop(STACK)
PAGE := look-up(URLcurr)
STORE(<URLcurr, PAGE>, COLLECTION)
For every URLi in PAGE,
push(URLi, STACK)
Return COLLECTION
What is wrong with the above algorithm?
9
Depth-first Search
1
2
3
4
5
6
7
numbers = order in
which nodes are
visited
10