我遇到了一个面试问题：“如果你要设计一个网络爬虫，你会如何避免陷入无限循环？”我正在尝试回答这个问题。
这一切从开始的地方开始。假设谷歌从一些主页面开始，比如说几百个（如何找到这些主页面是一个不同的子问题）。当谷歌跟随一个页面的链接等等时，它是否会创建一个哈希表来确保它不会再次访问之前已经访问过的页面？
如果同一个页面有两个名称（URL），比如在我们使用URL缩短器等工具的今天呢？
我以谷歌为例。虽然谷歌不透露其网络爬虫算法和页面排名等的工作原理，但你有什么猜测吗？
8个回答
87
如果您想获取详细答案，请查看本文的第3.8节，其中描述了现代爬虫的URL-seen测试：
在提取链接的过程中，任何Web爬虫都会遇到对同一文档的多个链接。为了避免多次下载和处理文档，必须在将提取的每个链接添加到URL前沿之前对其进行URL-seen测试。（另一种设计是在从前沿移除URL时执行URL-seen测试，但这种方法会导致更大的前沿。）为了执行URL-seen测试，我们以规范形式将Mercator看到的所有URL存储在一个名为URL集的大型表中。同样，由于条目太多而无法全部放入内存中，因此像文档指纹集一样，URL集主要存储在磁盘上。
为了节省空间，我们不会在URL集中存储每个URL的文本表示，而是存储固定大小的校验和。与提交给内容-seen测试的文档指纹集不同，测试与URL集相比具有相当数量的局部性。为了减少对后备磁盘文件的操作次数，我们因此保留了流行URL的内存缓存。这个缓存的直觉是，某些URL的链接非常常见，因此在内存中缓存流行的URL将导致高内存命中率。
事实上，使用2^18个条目的内存缓存和类似LRU的时钟替换策略，我们在内存缓存的整体命中率为66.2％，在最近添加的URL表上的命中率为9.5％，从而获得了75.7％的净命中率。此外，在流行URL的缓存和最近添加的URL表中都未命中的24.3％的请求中，约有1/3在我们的随机访问文件实现的缓冲区中产生命中，该实现也驻留在用户空间中。所有这些缓冲的净结果是，我们对URL集执行的每个成员资格测试都会导致平均0.16个查找和0.17个读取内核调用（其中一部分是由内核的文件系统缓冲区提供的）。因此，每个URL集成员资格测试引起的内核调用数量仅为成员资格测试文档指纹集的六分之一。这些节省纯粹是由于在爬行期间遇到的URL流中固有的URL局部性（即流行URL的重复）所致。
基本上，谷歌使用哈希函数对所有URL进行哈希处理，以确保每个URL具有唯一的哈希值，并且由于URL的地域性，查找URL变得非常容易。Google甚至公开了它们的哈希函数：CityHash。
注意！
他们可能也在谈论机器人陷阱！！！机器人陷阱是页面的一部分，它会不断生成具有唯一URL的新链接，您将通过跟随该页面提供的链接而被困在“无限循环”中。这不完全是一个循环，因为循环是访问相同的URL的结果，但这是应避免爬行的无限URL链。
更新12/13/2012- 世界末日过后的第二天 :)
根据Fr0zenFyr的评论：如果使用AOPIC算法选择页面，则可以相当轻松地避免无限循环类型的机器人陷阱。以下是AOPIC工作原理的摘要：
- 获取一组N个种子页面。
- 为每个页面分配X数量的信用，使得每个页面在爬行开始前都有X/N的信用（即相同数量的信用）。
- 选择一个页面P，其中P具有最高的信用额（或者如果所有页面都有相同的信用额，则随机爬行一个页面）。
- 爬取页面P（假设在爬取时P有100个信用点）。
- 从页面P中提取所有链接（假设有10个链接）。
- 将P的信用设置为0。
- 收取10％的“税”并将其分配给Lambda页面。
- 从P的原始信用-税中为P发现的每个链接平均分配相等数量的信用：因此（100（P信用）- 10（10％税））/10（链接数）=每个链接9个信用点。
- 从步骤3重复。
由于Lambda页面持续收集税款，最终它将成为信用额最大的页面，我们将不得不“爬行”它。我用引号括起来说“爬行”，因为我们实际上不会为Lambda页面发出HTTP请求，我们只是获取它的信用并将它们平均分配给所有数据库中的页面。
由于机器人陷阱只给内部链接信用，并且它们很少从外部获得信用，它们将不断地泄漏信用（从税收中），并将这些信用平均分配给数据库中的所有页面。在每个周期中，机器人陷阱页面将失去越来越多的信用，直到它的信用非常少，几乎再也无法被爬取。好的页面不会出现这种情况，因为它们经常从其他页面上找到的后向链接获得信用。这也导致动态页面排名，您会注意到，每当您对数据库进行快照，按其所拥有的信用数量对页面进行排序时，它们很可能大致按其真实页面排名排序。这只避免了无限循环类型的机器人陷阱，但是还有许多其他机器人陷阱，您应该注意，并且还有方法可以避开它们。
- Kiril
9
非常好的解释。我之前也有关于循环的同样问题（已经得到了回答），以及机器人陷阱（仍在寻找一个好的解决方法）。如果SO允许，我会额外给CityHash +1。干杯 ;) - Fr0zenFyr
@Fr0zenFyr 哈哈哈，我想这就是我对世界末日的关注程度吧 :) - Kiril
也许是个愚蠢的问题，但Lambda页面是分配税款的页面吗？它似乎没有解释就被介绍了。 - Casper
@Casper 这只是一个占位符，用于积累税收抵免。它并不代表一个真实的页面；可以将其视为数据结构中的哨兵，在爬取时会导致所有税收累积信用分配到其他“真实”页面上。 - Filipe Gonçalves
1@raju 这并不是每个周期都会发生的，它只会在你“爬行”lambda时发生。 “爬行”lambda 不应该经常发生，而且您可以异步地执行它。 它不需要实时发生，只需要最终发生即可。 - Kiril
显示剩余4条评论
7
虽然这里已经有人建议如何创建网络爬虫，但以下是Google如何排名网页的方法。
Google根据回调链接的数量（其他网站指向特定网站/页面的链接数量）给每个页面一个排名。这被称为相关性得分。这是基于这样一个事实：如果一个页面有很多其他页面链接到它，那么它可能是一个重要的页面。
每个站点/页面都被视为图中的一个节点。链接到其他页面的链接是有方向的边缘。顶点的度被定义为入边的数量。入边数量更高的节点排名更高。
以下是PageRank的确定方式。假设页面Pj有Lj个链接。如果其中一个链接指向页面Pi，则Pj将向Pi传递其重要性的1/Lj。Pi的重要性排名是所有链接到它的页面所做贡献的总和。因此，如果我们用Bi表示链接到Pi的页面集合，则有以下公式：
Importance(Pi)= sum( Importance(Pj)/Lj ) for all links from Pi to Bi
排名被放置在一个称为超链接矩阵的矩阵中：H[i,j]
该矩阵中的一行要么是0，要么是1/Lj（如果存在从Pi到Bi的链接）。该矩阵的另一个特性是，如果我们将列中的所有行相加，得到的结果为1。
现在，我们需要将此矩阵乘以一个名为I的特征向量（具有特征值1），使其满足以下条件：
I = H*I
现在我们开始迭代：IH，IIH，IIIH .... I^k *H，直到解决方案收敛。也就是说，在第k步和第k+1步中，矩阵中的数字基本相同。现在I向量中剩下的部分就是每个页面的重要性。
对于一个简单的课堂作业示例，请参见http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html 至于在面试问题中解决重复问题，可以对整个页面执行校验和，并使用该校验和或校验和的哈希作为键在映射中跟踪访问过的页面。
- Adrian
5
1如果页面输出动态内容，则校验和可能会不同。 - edocetirwi
@edocetirwi 很好的观点，我想你得寻找其他东西或以某种有意义的方式将其与URL结合起来。 - Adrian
哦，所以你只需要对具有维度“互联网上的每个网页”x“互联网上的每个网页”的超链接矩阵进行积分。很容易？！？考虑到它是一个非常稀疏的矩阵，具体应该如何做呢？ - CpILL
@CpILL，你晚了7年，但是有聪明的方法可以在不爆炸的情况下乘以大矩阵；如果你想要一个生产就绪的解决方案，我愿意接受付款。 - Adrian
@Adrian 我相信你是个专业人士...但我注意到Stackoverflow上大多数都是开发者，我们喜欢自己动手解决问题，这也是我们来这里的原因！ :D - CpILL
1
这取决于他们的问题意图有多深入。如果他们只是试图避免来回跟踪相同的链接，那么哈希URL就足够了。
那么对于具有成千上万个指向相同内容的URL的内容呢？比如一个不影响任何内容但可以有无限次迭代的QueryString参数。我想你也可以哈希页面内容并比较URL以查看它们是否类似，以捕获由多个URL标识的内容。例如，参见@Lirik帖子中提到的Bot Traps。
- mellamokb
1
这让我想到了另一个问题。我们如何对整个页面的内容进行哈希处理？这样的页面至少有两页。哪种哈希函数能够将两页合并为一个值？通常这样的哈希输出大小是多少？ - xyz
0
网络爬虫是一种计算机程序，用于从给定的网站URL中收集/抓取以下关键值（HREF链接、图像链接、元数据等）。它被设计成智能地跟随已从前一个URL获取的不同HREF链接，以此方式，爬虫可以从一个网站跳转到其他网站。通常称之为网络蜘蛛或网络机器人。这种机制始终是Web搜索引擎的支柱。
请在我的技术博客中找到源代码 - http://www.algonuts.info/how-to-built-a-simple-web-crawler-in-php.html
<?php
class webCrawler
{
public $siteURL;
public $error;
function __construct()
{
$this->siteURL = "";
$this->error = "";
}
function parser()
{
global $hrefTag,$hrefTagCountStart,$hrefTagCountFinal,$hrefTagLengthStart,$hrefTagLengthFinal,$hrefTagPointer;
global $imgTag,$imgTagCountStart,$imgTagCountFinal,$imgTagLengthStart,$imgTagLengthFinal,$imgTagPointer;
global $Url_Extensions,$Document_Extensions,$Image_Extensions,$crawlOptions;
$dotCount = 0;
$slashCount = 0;
$singleSlashCount = 0;
$doubleSlashCount = 0;
$parentDirectoryCount = 0;
$linkBuffer = array();
if(($url = trim($this->siteURL)) != "")
{
$crawlURL = rtrim($url,"/");
if(($directoryURL = dirname($crawlURL)) == "http:")
{ $directoryURL = $crawlURL; }
$urlParser = preg_split("/\//",$crawlURL);
//-- Curl Start --
$curlObject = curl_init($crawlURL);
curl_setopt_array($curlObject,$crawlOptions);
$webPageContent = curl_exec($curlObject);
$errorNumber = curl_errno($curlObject);
curl_close($curlObject);
//-- Curl End --
if($errorNumber == 0)
{
$webPageCounter = 0;
$webPageLength = strlen($webPageContent);
while($webPageCounter < $webPageLength)
{
$character = $webPageContent[$webPageCounter];
if($character == "")
{
$webPageCounter++;
continue;
}
$character = strtolower($character);
//-- Href Filter Start --
if($hrefTagPointer[$hrefTagLengthStart] == $character)
{
$hrefTagLengthStart++;
if($hrefTagLengthStart == $hrefTagLengthFinal)
{
$hrefTagCountStart++;
if($hrefTagCountStart == $hrefTagCountFinal)
{
if($hrefURL != "")
{
if($parentDirectoryCount >= 1 || $singleSlashCount >= 1 || $doubleSlashCount >= 1)
{
if($doubleSlashCount >= 1)
{ $hrefURL = "http://".$hrefURL; }
else if($parentDirectoryCount >= 1)
{
$tempData = 0;
$tempString = "";
$tempTotal = count($urlParser) - $parentDirectoryCount;
while($tempData < $tempTotal)
{
$tempString .= $urlParser[$tempData]."/";
$tempData++;
}
$hrefURL = $tempString."".$hrefURL;
}
else if($singleSlashCount >= 1)
{ $hrefURL = $urlParser[0]."/".$urlParser[1]."/".$urlParser[2]."/".$hrefURL; }
}
$host = "";
$hrefURL = urldecode($hrefURL);
$hrefURL = rtrim($hrefURL,"/");
if(filter_var($hrefURL,FILTER_VALIDATE_URL) == true)
{
$dump = parse_url($hrefURL);
if(isset($dump["host"]))
{ $host = trim(strtolower($dump["host"])); }
}
else
{
$hrefURL = $directoryURL."/".$hrefURL;
if(filter_var($hrefURL,FILTER_VALIDATE_URL) == true)
{
$dump = parse_url($hrefURL);
if(isset($dump["host"]))
{ $host = trim(strtolower($dump["host"])); }
}
}
if($host != "")
{
$extension = pathinfo($hrefURL,PATHINFO_EXTENSION);
if($extension != "")
{
$tempBuffer ="";
$extensionlength = strlen($extension);
for($tempData = 0; $tempData < $extensionlength; $tempData++)
{
if($extension[$tempData] != "?")
{
$tempBuffer = $tempBuffer.$extension[$tempData];
continue;
}
else
{
$extension = trim($tempBuffer);
break;
}
}
if(in_array($extension,$Url_Extensions))
{ $type = "domain"; }
else if(in_array($extension,$Image_Extensions))
{ $type = "image"; }
else if(in_array($extension,$Document_Extensions))
{ $type = "document"; }
else
{ $type = "unknown"; }
}
else
{ $type = "domain"; }
if($hrefURL != "")
{
if($type == "domain" && !in_array($hrefURL,$this->linkBuffer["domain"]))
{ $this->linkBuffer["domain"][] = $hrefURL; }
if($type == "image" && !in_array($hrefURL,$this->linkBuffer["image"]))
{ $this->linkBuffer["image"][] = $hrefURL; }
if($type == "document" && !in_array($hrefURL,$this->linkBuffer["document"]))
{ $this->linkBuffer["document"][] = $hrefURL; }
if($type == "unknown" && !in_array($hrefURL,$this->linkBuffer["unknown"]))
{ $this->linkBuffer["unknown"][] = $hrefURL; }
}
}
}
$hrefTagCountStart = 0;
}
if($hrefTagCountStart == 3)
{
$hrefURL = "";
$dotCount = 0;
$slashCount = 0;
$singleSlashCount = 0;
$doubleSlashCount = 0;
$parentDirectoryCount = 0;
$webPageCounter++;
while($webPageCounter < $webPageLength)
{
$character = $webPageContent[$webPageCounter];
if($character == "")
{
$webPageCounter++;
continue;
}
if($character == "\"" || $character == "'")
{
$webPageCounter++;
while($webPageCounter < $webPageLength)
{
$character = $webPageContent[$webPageCounter];
if($character == "")
{
$webPageCounter++;
continue;
}
if($character == "\"" || $character == "'" || $character == "#")
{
$webPageCounter--;
break;
}
else if($hrefURL != "")
{ $hrefURL .= $character; }
else if($character == "." || $character == "/")
{
if($character == ".")
{
$dotCount++;
$slashCount = 0;
}
else if($character == "/")
{
$slashCount++;
if($dotCount == 2 && $slashCount == 1)
$parentDirectoryCount++;
else if($dotCount == 0 && $slashCount == 1)
$singleSlashCount++;
else if($dotCount == 0 && $slashCount == 2)
$doubleSlashCount++;
$dotCount = 0;
}
}
else
{ $hrefURL .= $character; }
$webPageCounter++;
}
break;
}
$webPageCounter++;
}
}
$hrefTagLengthStart = 0;
$hrefTagLengthFinal = strlen($hrefTag[$hrefTagCountStart]);
$hrefTagPointer =& $hrefTag[$hrefTagCountStart];
}
}
else
{ $hrefTagLengthStart = 0; }
//-- Href Filter End --
//-- Image Filter Start --
if($imgTagPointer[$imgTagLengthStart] == $character)
{
$imgTagLengthStart++;
if($imgTagLengthStart == $imgTagLengthFinal)
{
$imgTagCountStart++;
if($imgTagCountStart == $imgTagCountFinal)
{
if($imgURL != "")
{
if($parentDirectoryCount >= 1 || $singleSlashCount >= 1 || $doubleSlashCount >= 1)
{
if($doubleSlashCount >= 1)
{ $imgURL = "http://".$imgURL; }
else if($parentDirectoryCount >= 1)
{
$tempData = 0;
$tempString = "";
$tempTotal = count($urlParser) - $parentDirectoryCount;
while($tempData < $tempTotal)
{
$tempString .= $urlParser[$tempData]."/";
$tempData++;
}
$imgURL = $tempString."".$imgURL;
}
else if($singleSlashCount >= 1)
{ $imgURL = $urlParser[0]."/".$urlParser[1]."/".$urlParser[2]."/".$imgURL; }
}
$host = "";
$imgURL = urldecode($imgURL);
$imgURL = rtrim($imgURL,"/");
if(filter_var($imgURL,FILTER_VALIDATE_URL) == true)
{
$dump = parse_url($imgURL);
$host = trim(strtolower($dump["host"]));
}
else
{
$imgURL = $directoryURL."/".$imgURL;
if(filter_var($imgURL,FILTER_VALIDATE_URL) == true)
{
$dump = parse_url($imgURL);
$host = trim(strtolower($dump["host"]));
}
}
if($host != "")
{
$extension = pathinfo($imgURL,PATHINFO_EXTENSION);
if($extension != "")
{
$tempBuffer ="";
$extensionlength = strlen($extension);
for($tempData = 0; $tempData < $extensionlength; $tempData++)
{
if($extension[$tempData] != "?")
{
$tempBuffer = $tempBuffer.$extension[$tempData];
continue;
}
else
{
$extension = trim($tempBuffer);
break;
}
}
if(in_array($extension,$Url_Extensions))
{ $type = "domain"; }
else if(in_array($extension,$Image_Extensions))
{ $type = "image"; }
else if(in_array($extension,$Document_Extensions))
{ $type = "document"; }
else
{ $type = "unknown"; }
}
else
{ $type = "domain"; }
if($imgURL != "")
{
if($type == "domain" && !in_array($imgURL,$this->linkBuffer["domain"]))
{ $this->linkBuffer["domain"][] = $imgURL; }
if($type == "image" && !in_array($imgURL,$this->linkBuffer["image"]))
{ $this->linkBuffer["image"][] = $imgURL; }
if($type == "document" && !in_array($imgURL,$this->linkBuffer["document"]))
{ $this->linkBuffer["document"][] = $imgURL; }
if($type == "unknown" && !in_array($imgURL,$this->linkBuffer["unknown"]))
{ $this->linkBuffer["unknown"][] = $imgURL; }
}
}
}
$imgTagCountStart = 0;
}
if($imgTagCountStart == 3)
{
$imgURL = "";
$dotCount = 0;
$slashCount = 0;
$singleSlashCount = 0;
$doubleSlashCount = 0;
$parentDirectoryCount = 0;
$webPageCounter++;
while($webPageCounter < $webPageLength)
{
$character = $webPageContent[$webPageCounter];
if($character == "")
{
$webPageCounter++;
continue;
}
if($character == "\"" || $character == "'")
{
$webPageCounter++;
while($webPageCounter < $webPageLength)
{
$character = $webPageContent[$webPageCounter];
if($character == "")
{
$webPageCounter++;
continue;
}
if($character == "\"" || $character == "'" || $character == "#")
{
$webPageCounter--;
break;
}
else if($imgURL != "")
{ $imgURL .= $character; }
else if($character == "." || $character == "/")
{
if($character == ".")
{
$dotCount++;
$slashCount = 0;
}
else if($character == "/")
{
$slashCount++;
if($dotCount == 2 && $slashCount == 1)
$parentDirectoryCount++;
else if($dotCount == 0 && $slashCount == 1)
$singleSlashCount++;
else if($dotCount == 0 && $slashCount == 2)
$doubleSlashCount++;
$dotCount = 0;
}
}
else
{ $imgURL .= $character; }
$webPageCounter++;
}
break;
}
$webPageCounter++;
}
}
$imgTagLengthStart = 0;
$imgTagLengthFinal = strlen($imgTag[$imgTagCountStart]);
$imgTagPointer =& $imgTag[$imgTagCountStart];
}
}
else
{ $imgTagLengthStart = 0; }
//-- Image Filter End --
$webPageCounter++;
}
}
else
{ $this->error = "Unable to proceed, permission denied"; }
}
else
{ $this->error = "Please enter url"; }
if($this->error != "")
{ $this->linkBuffer["error"] = $this->error; }
return $this->linkBuffer;
}
}
?>
- Karthikeyan Moorthy
2
1这并没有真正回答问题：“如果你正在设计一个网络爬虫，你会如何避免陷入无限循环？”请改进你的回答。 - Brian Tompsett - 汤莱恩
嗨Brian先生，谢谢您的评论。实际上，我们需要为这个类创建一个实例，然后才能应用并使用它。 - Karthikeyan Moorthy
0
你需要一个哈希表来存储结果，在每次页面加载之前都要检查它。
- chuchu
0
这里的问题不是爬取重复的URL，而是爬取重复的内容。每个“爬虫陷阱”的URL都不同（年份、日期、SessionID等）。解决方案并不完美，但您可以使用以下策略之一：
• 保留一个字段，表示URL在网站中的级别。对于从页面获取URL的每个循环，增加级别。它将像一棵树一样。您可以停止在某个级别上进行爬取，例如10（我认为Google使用此方法）。
• 您可以尝试创建一种HASH，以便比较相似的文档，因为您无法与数据库中的每个文档进行比较。Google有SimHash，但我找不到任何可用的实现。然后我自己创建了一个。我的哈希计算HTML代码中低频和高频字符，并生成一个20字节的哈希值，该哈希值与AVLTree中最近邻居搜索的小缓存中的最后爬取页面进行比较，容忍度约为2。在“识别”陷阱后，您可以记录重复内容的URL模式，并开始忽略具有相同模式的页面。
• 保留一个字段，表示URL在网站中的级别。对于从页面获取URL的每个循环，增加级别。它将像一棵树一样。您可以停止在某个级别上进行爬取，例如10（我认为Google使用此方法）。
• 您可以尝试创建一种HASH，以便比较相似的文档，因为您无法与数据库中的每个文档进行比较。Google有SimHash，但我找不到任何可用的实现。然后我自己创建了一个。我的哈希计算HTML代码中低频和高频字符，并生成一个20字节的哈希值，该哈希值与AVLTree中最近邻居搜索的小缓存中的最后爬取页面进行比较，容忍度约为2。在“识别”陷阱后，您可以记录重复内容的URL模式，并开始忽略具有相同模式的页面。
• 像谷歌一样，您可以为每个网站创建排名，并对其中一个比其他网站更加“信任”。
- lexmooze
-1
这是一个网络爬虫示例。可用于收集MAC地址以进行MAC欺骗。
#!/usr/bin/env python
import sys
import os
import urlparse
import urllib
from bs4 import BeautifulSoup
def mac_addr_str(f_data):
global fptr
global mac_list
word_array = f_data.split(" ")
for word in word_array:
if len(word) == 17 and ':' in word[2] and ':' in word[5] and ':' in word[8] and ':' in word[11] and ':' in word[14]:
if word not in mac_list:
mac_list.append(word)
fptr.writelines(word +"\n")
print word
url = "http://stackoverflow.com/questions/tagged/mac-address"
url_list = [url]
visited = [url]
pwd = os.getcwd();
pwd = pwd + "/internet_mac.txt";
fptr = open(pwd, "a")
mac_list = []
while len(url_list) > 0:
try:
htmltext = urllib.urlopen(url_list[0]).read()
except:
url_list[0]
mac_addr_str(htmltext)
soup = BeautifulSoup(htmltext)
url_list.pop(0)
for tag in soup.findAll('a',href=True):
tag['href'] = urlparse.urljoin(url,tag['href'])
if url in tag['href'] and tag['href'] not in visited:
url_list.append(tag['href'])
visited.append(tag['href'])
将URL更改为爬取更多的网站......祝好运
- ashish jha
-1
嗯，网络基本上是一个有向图，因此您可以将URL构建成一个图，然后进行BFS或DFS遍历，同时标记已访问的节点，以便不重复访问同一页。
- Pepe
2
3但是，如何首先构建图形呢？如果我们不想要重复的节点，即我们只想为URL创建一个节点，那么在构建图形时，您需要一种方法来检测和丢弃重复项。 - xyz
@learnerforever 嗯，那是真的...老实说，我只写过一个简单的爬虫，只处理了大约100个链接，所以进入每个页面并不是一个很大的问题。但是，当你将其应用于整个网络时，我可以看到问题的出现。Lirik的论文似乎值得一读... - Pepe
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接