搜索引擎机器人研究报告 中文全文检索网

搜索引擎机器人研究报告
http://FullSearch.Com 中文全文检索网 2006-5-12 8:27:21 在刁刁心中搜索-译
关键词：spider
从该文对googlebot的分析看，googlebot似乎是想先对网站的结构和规模做出分析，然后再规划抓取行为，googlebot的行为确实很有意思。Yahoo的机器人似乎是以月为单位周期的更新，抓取新网页和索引，感觉是想以量取胜，并且对网页似乎没有进一步的分析。感觉MSNbot在整体上还略逊于另两个竞争对手。原文连接和简单译文如下。
原文http://drunkmenworkhere.org/219
译文
Introduction
前一篇文章介绍了Binary Search Tree 2，一个关于搜索引擎行为的大规模实验，该实验使用了超过20亿张不同的网页。这个实验持续了一年，直到4月13日结束（2006年）。在这一年时间里，3个主要的搜索引擎从数十万不同的URL中请求访问了此二叉树中超过100万张页面。而drunkmenworkhere.org的主页也因为页面上的访问日志和垃圾评论从1.6KB增长到4MB。
本文将介绍此次实验的结果。
Setup
2,147,483,647张页面被标号并放置在二叉搜索树中。在这个树中，左子树中的所有节点的编号都小于根节点的编号，右子树中的所有节点的编号都大于根节点的编号，所以最左边的节点的编号为1，最右边的为2,147,483,647。
树的深度是从根节点到最远节点的层数。一颗深度为n的树，拥有2n+1 – 1个节点，用于实验的树有30层(231 = 2,147,483,648)。根节点的值为1073741824 (230)。
每一张页面都有三大主要的搜索引擎的访问监控记录，持续一年时间(between 2005-4-13 and 2006-4-13)。
To make the content of each page more interesting for the search engines, the value of each node is written out in American English (short scale) and each page request from a search bot is displayed in reversed chronological order. To enrich the zero-content even more, a comment box was added to each page (it was removed on 2006-4-13). These measures were improvements over the initialBinary Search Tree which uses inconvenient long URLs.
每一张页面中都有三棵树状图，每棵树可视化的表示一个搜索引擎对节点的抓取。图中每条线表示一个节点，线越长表示被抓取得越频繁。The tree images below are modified large versions of the original image, without the very long root node and with disconnected (wild) branches.
Overall results
从开始到现在，Yahoo! Slurp一直是最活跃的机器人程序。在一年的时间里，它请求访问了超过100万页，并且抓取了超过10万不同的网页。尽管这是一个很大的数字，但是它仍旧只占所有节点数的0.0049%。所有机器人的总体分析如下表所示。
overall statistics by search engine
Yahoo!
Google
MSN
total number of pageviews
1,030,396
20,633
4,699
number of nodes crawled
105,971
7,556
1,390
percentage of tree crawled
0.0049%
0.00035%
0.000065%
number of indexed nodes
120,000
554
1
indexed/crawled ratio
113.23%
7.33%
0.07%
在实验的一年中，pageviews和抓取数量的增长过程如figure 1 and 2所示。关于每个机器人抓取的详细描述在后续的章节中介绍。

Fig. 1 - The cumulative number of pageviews by the search bots in time.

Fig. 2 - The cumulative number of nodes crawled by the search bots in time.
图3以对数的形式显示了每个机器人在各层抓取了多少节点，根节点的层数为0，最远的节点层数为30，因为在第n层有2n 个节点，所以抓取整棵树将在此图中显示为一条直线。

Fig. 3 - The number of nodes crawled after 1 year, grouped by node level.
在12层以前，Google几乎是一条直线，12层及前的多数节点都被抓取了（5524 out of 8191），而只有少数12层以后的节点被google机器人抓取。MSN表现了相似的行为，只是抓取的更少，它在第9层以前表现为直线(656 out of 1023 nodes were crawled)。而Yahoo的直线没有向下弯曲，但随着层数的增加它也无法请求所有网页了。
相比其它机器人，Yahoo对深层节点的抓取请求的更频繁，从14层到30层，平均每个被抓取的网页有10次请求。(see fig. 4)。

Fig. 4 - The average number of pageviews per node after 1 year, grouped by node level.
Yahoo! Slurp
large version (4273x3090, 1.5MB)
animated version over 1 year (2005-04-13 - 2006-04-13, 13MB)
animated version of the first 2 hours (2006-04-14 00:40:00-02:40:00, 2.2MB)

Fig. 5 - The Yahoo! Slurp tree.
Yahoo! Slurp是发现二叉树的第一个搜索引擎。在发现它的第一个小时里，它对这个树的抓取就十分活跃，没秒2.3个节点(see theshort animation)。第一天它就抓取了接近30万节点。
在接下来的一个月中，Slurp 的活动有所降低，但是正好一个月后，它对它上次访问的所有页面都进行了第二次请求。在animation，你可以发现在2005-05-14，树的大小增加了一倍。这种现象在一个月之后又重复出现，在 2005-06-13，树的大小为原始大小的3倍。Pageviews达到了90万而抓取得网页仍然是30万。图6显示了一个月以来这种阶梯状的增长。

Fig. 6 - The cumulative number of pageviews by Yahoo! Slurp in time.
在4个月后，Slurp开始请求大量的新节点，这是继初始轮次的抓取以来的第一次。它简单的请求了所有它已经有的URL。因为它已经索引了30万页，而每一页都有两个深层的连接，所以在8月末它请求了60万页的连接（the number of pageviews jumps from 100,000 to 160,000 pages in fig. 6）抓取得节点数也番了一翻。5个月后，Yahoo! Slurp开始了频繁的请求，还是保持阶段性的“发现”(e.g. after 10 months)。

Fig. 7 - The cumulative number of nodes crawled by Yahoo! Slurp in time.
在Yahoo搜索结果中，它报告了120万个索引（当前值）这看起来不太可能因为它只访问了105,971个节点，但是每个节点可获得两个不同的域名www.drunkmenworkhere.org and drunkmenworkhere.org.
Note: the query submitted to Google and MSN yielded35,600 pages on Yahoo. Yahoo is the only search engine that returns results with the query used above.
Googlebot

large version (4067x4815, 180kB)
animated version (2005-04-13 - 2006-04-13, 1.2MB)
Fig. 8 - The Googlebot tree.
与Yahoo的树相比，google的树更像是一颗自然生长的树。这是因为google对深层节点的访问没有像访问它们的父节点一样那么频繁。Yahoo只对前3层的节点访问非常频繁，而google对前12层的访问都很频繁(see fig. 4)。
树的这种形式符合google的PageRank算法，PageRank算法定义如下：
"We assume page A has pages T1...Tn which point to it (i.e., are citations). The parameter d is a damping factor which can be set between 0 and 1. We usually set d to 0.85. There are more details about d in the next section. Also C(A) is defined as the number of links going out of page A. The PageRank of a page A is given as follows:
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) "
考虑到这棵树没有被其它的站点连接，每个节点的PageRank可以被下面的公式计算(ignoring links in the comments):
PR(node) = 0.15 + 0.85 (PR(parent) + PR(left child) + PR(right child))/3
The only unknown when applying this formula iteratively, is the PageRank of the root node of the tree. Since this node was the homepage of drunkmenworkhere.org for a year, a high rank may be assumed. The calculated PageRank tree (fig. 9) shows similar proportions as Googlebot"s real tree, so the frequency of visiting a page seems to be related to the PageRank of a page.

Fig. 9 - A binary tree of depth 17 visualising calculated PageRank as length of each line, when the PageRank of the root node is set to 100.
Googlebot显示了一些不能被PageRank解释的有趣而古怪的行为。
The rightmost branch
从一开始，googlebot就抓取更多右面的节点。在2005-07-04它试图访问最右面的节点，就是那个拥有最高编号的节点。这种选取右边节点的行为从根节点开始直到20层结束。这种畸形的弧出现在树右边的结尾。

Searching node 1

在2005-06-30，googlebot访问了1号节点，最左边的节点。它不是从根节点沿着路径找到这个节点的，那它又是怎么发现这页呢？它是否是猜测的URL还是从某个外部连接进来的？一小时后，googlebot抓取了2号节点，2号节点是1号的父节点。这两个节点在图上只是一个很小的点浮在2005-06-30的树图的左边的最上面。一周以后，在2005-07-06（在尝试寻找最右节点的两天后），在06:39:39 到06:39:59之间，googlebot用20秒的时间找到了通向这两个孤立点的路径，这条路径包括24个节点。它从树的根节点开始，直到找到2号节点，这条路径上googlebot没有选择过一条向右的分支。在大版本的图中，这条路径清晰可见。The nodes halfway the path were not requested for a second time and are represented by thin short line segments, hence the steep curve.
Yahoo-like subtree
在2005-07-23，google突然开始花费数小时在节点1073872896号附近抓取600个新节点，这些节点的大部分没有被再次访问过。
This subtree is the reason the number of nodes crawled by Googlebot, grouped by level, increases again from level 18 to level 30 in fig. 3.

在最近的6个月中，googlebot以固定的频率请求页面（大约每月260页，图10）并且阶段性的刷新它的缓存。

Fig. 10 - The cumulative number of pageviews by Googlebot in time.

Fig. 11 - The cumulative number of nodes crawled by Googlebot in time.
当搜索节点时，google返回了554个结果。排在第一的是1号和2号节点，这两个节点时树中层次最深的节点，分别在29和30层。它们如此高的排名在之前的曲线中也有所反映(Searching node 1)，它们排在前面很可能是因为它们的URL很短。在搜索结果第一页中的其它节点都在第4层，很可能是因为前3层的节点因为垃圾评论而遭到惩罚。当前结果到这里察看。
MSNbot

large version (4200x2795, 123kB)
animated version (2005-04-13 - 2006-04-13, 846kB)
Fig. 12 - The msnbot tree
MSNbot的树远小于Yahoo和Google的树。这棵树最有趣的特点是在书的右侧有一个不连续的分支。它出现在2005-04-29, 当msnbot  访问node 2045877824时。这个节点有一个两周以前的评论：I hereby claim this name in the name of...well, mine. Paul Pigg.
一周以前，msnbot请求了这个节点，googlebot以访问过这个点。这个位于24层的随即的节点被抓取了，因为一条连接来几Paul Pigg的站点masterpigg.com (now dead,Google cache)。所有3个搜索引擎都通过这个连接访问了该节点，并且这三个搜索引擎都没有把它和树的其它部分连接在一起。你可到此察看node 2045877824。
MSNbot从不连续的节点沿上下两个方向抓取，并创建了一个子树。这个子树导致了从18层到30层的一个子树，见图3。
第2大的不连续分支在图的中上部，来自一个连接uu-dot.com，这两个不连续的树在googlebot的树上也能清楚地看到。

Fig. 13 - The cumulative number of pageviews by msnbot in time.

Fig. 14 - The cumulative number of nodes crawled by msnbot in time.
如上图所示，msnbot事实上在5个月后停止了对二叉树的抓取，MSN Search返回的结果数量是如何得出的，与此图的关系不得而知。
Spam bots
在一年中，5265条评论出现在103个不同的节点中。其中32个节点没有被任何搜索引擎访问，大多数（3652）评论出现在根节点中，评论中的词汇统计如下。
top 50 of most frequently spammed words
count
word
1
32743
http
2
23264
com
3
12375
url
4
8636
www
5
5541
info
6
4631
viagra
7
4570
online
8
4533
phentermine
9
4512
buy
10
4469
html
11
3531
org
12
3346
blogstudio
13
3194
drunkmenworkhere
14
2801
free
15
2772
cialis
16
2371
to
17
2241
u
18
2169
generic
19
2054
cheap
20
1921
ringtones
21
1914
view
22
1835
a
23
1818
net
24
1756
the
25
1658
buddy4u
26
1633
of
27
1633
lelefa
28
1580
xanax
29
1572
blogspot
30
1570
tramadol
31
1488
mp3sa
32
1390
insurance
33
1379
poker
34
1310
cgi
35
1232
sex
36
1198
teen
37
1193
in
38
1158
content
39
1105
aol
40
1099
mime
41
1095
and
42
1081
home
43
1034
us
44
1022
valium
45
1020
josm
46
1012
order
47
992
is
48
948
de
49
908
ringtone
50
907
i
Top50的词清楚地显示，多数垃圾与药品相关。以下的饼图显示了相关的药品。

Fig. 15 - The share of various medicines in comment spam.
从文本中过滤出了域名，所有主要的域名如图16所示，以频率排序。

Fig. 16 - Number of spammed domains by top level domain
Many email addressses submitted by the spam bots were non-existing addresses @drunkmenworkhere.org, which explains the high rank of this domain in the chart of most frequently spammed domains (fig. 17).

Fig. 17 - Most frequently spammed domains
相关文章： 中文搜索引擎技术揭密:网络蜘蛛  ; 主要中文网页搜索引擎介绍