我遇到了一个采访问题“如果你正在设计一个网络爬虫，你将如何避免进入无限循环？”我试图回答它。
这一切从一开始就是如何开始的。比如谷歌开始时，一些中心页面上说有数百个（首先如何找到这些中心页面是一个不同的子问题）。当Google跟踪来自页面的链接等时，它是否继续制作哈希表以确保它不遵循先前访问过的页面。
如果同一页面有两个名称（URL），如果我们有URL缩短器等，那么该怎么办呢？
我以谷歌为例。虽然谷歌没有泄漏其网络爬虫算法和页面排名等的工作方式，但任何猜测？
如果你想得到详细的答案，请看一下section 3.8 this paper，它描述了现代刮刀的URL看见测试：
在提取链接的过程中，任何Web爬网程序都会遇到指向同一文档的多个链接。为避免多次下载和处理文档，必须先对每个提取的链接执行URL查看测试，然后再将其添加到URL边界。 （另一种设计是在从边界移除URL时执行URL看到的测试，但这种方法会产生更大的边界。）
为了执行URL看到的测试，我们将Mercator以规范形式看到的所有URL存储在一个称为URL集的大表中。同样，它们都有太多条目可以放入内存中，因此与文档指纹集一样，URL集主要存储在磁盘上。
为了节省空间，我们不会将每个URL的文本表示存储在URL集中，而是存储固定大小的校验和。与呈现给内容看见的测试的文档指纹集的指纹不同，针对URL集测试的URL流具有非平凡的局部性。因此，为了减少后备磁盘文件上的操作数，我们保留了常用URL的内存缓存。这个缓存的直觉是指向某些URL的链接非常常见，因此在内存中缓存流行的URL将导致高内存命中率。
事实上，使用2 ^ 18个条目的内存缓存和类似LRU的时钟替换策略，我们在内存缓存中实现了66.2％的总体命中率，并且在表中的命中率为9.5％。最近添加的网址，净点击率为75.7％。此外，在流行URL缓存和最近添加的URL表中丢失的24.3％请求中，大约1 = 3在我们的随机访问文件实现中产生缓冲区命中，该实现也驻留在用户空间中。所有这些缓冲的最终结果是我们对URL集执行的每个成员资格测试导致平均0.16次搜索和0.17次读取内核调用（其中一部分是从内核的文件系统缓冲区中提供的）。因此，每个URL集成员资格测试引起的内核调用数量是文档指纹集上的成员资格测试的六分之一。这些节省纯粹是由于在爬网期间遇到的URL流中固有的URL位置（即，流行URL的重复）的数量。
基本上，它们使用散列函数散列所有URL，以保证每个URL的唯一散列，并且由于URL的位置，查找URL变得非常容易。谷歌甚至开源了他们的散列函数：CityHash
警告！ 他们也可能在谈论机器人陷阱！机器人陷阱是页面的一部分，它不断生成具有唯一URL的新链接，并且通过遵循该页面所服务的链接，您将基本上陷入“无限循环”。这不是一个循环，因为循环是访问同一个URL的结果，但它是一个无限的URL链，你应该避免抓取。
根据Fr0zenFyr的评论：如果使用AOPIC算法来选择页面，那么很容易避免无限循环类型的机器人陷阱。以下是AOPIC如何工作的摘要：
由于Lambda页面不断收税，最终它将成为信用额度最大的页面，我们将不得不“抓取”它。我在引号中说“抓取”，因为我们实际上并没有为Lambda页面发出HTTP请求，我们只是将其信用分配给我们数据库中的所有页面。
由于僵尸陷阱只提供内部链接信用，而且他们很少从外部获得信用，他们将不断泄漏信用（从税收）到Lambda页面。 Lambda页面将均匀地分配给数据库中的所有页面，并且在每个循环中，机器人陷阱页面将丢失越来越多的信用，直到它具有如此少的信用，它几乎永远不会被再次爬行。良好的页面不会发生这种情况，因为它们通常会从其他页面上的反向链接中获得积分。这也会产生动态页面排名，您会注意到，每当您拍摄数据库快照时，按照他们拥有的信用额度排序页面，那么他们很可能会根据他们的真实页面排名大致排序。
这只能避免无限循环类型的机器人陷阱，但是你应该注意有many other bot traps，并且有办法绕过它们。
这是一个Web爬网程序示例。可用于收集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'])
更改网址以抓取更多网站......祝你好运
虽然这里的每个人都已经建议如何创建您的网络抓取工具，但以下是Google如何对网页进行排名。
Google根据回调链接的数量为每个页面提供排名（其他网站上指向特定网站/页面的链接数量）。这称为相关性得分。这是基于如果页面有许多其他页面链接到它的事实，它可能是一个重要的页面。
每个站点/页面都被视为图形中的节点。与其他页面的链接是有向边。顶点的度数被定义为入射边缘的数量。具有更多入射边缘的节点排名更高。
以下是PageRank的确定方式。假设页面Pj具有Lj链接。如果其中一个链接是页面Pi，则Pj将其重要性的1 / Lj传递给Pi。然后，Pi的重要性排名是链接到它的页面所做的所有贡献的总和。因此，如果我们表示通过Bi链接到Pi的页面集合，那么我们有这个公式：
Importance(Pi)= sum( Importance(Pj)/Lj ) for all links from Pi to Bi
排名放在一个称为超链接矩阵的矩阵中：H [i，j]
如果存在从Pi到Bi的链接，则该矩阵中的行为0或1 / Lj。该矩阵的另一个属性是，如果我们对列中的所有行求和，则得到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
至于解决面试问题中的重复问题，在整个页面上做一个校验和，并使用校验和或校验和的bash作为地图中的关键字来跟踪访问过的页面。
取决于他们的问题有多深。如果他们只是试图避免来回跟随相同的链接，那么散列URL就足够了。
如果内容中包含数千个导致相同内容的URL？就像QueryString参数一样，它不会影响任何东西，但可以有无限次的迭代次数。我想你也可以对页面的内容进行散列并比较URL，看看它们是否与多个URL标识的catch内容类似。例如，参见@Lirik的帖子中提到的Bot Traps。
你必须有一些哈希表来存储结果，你只需要在每个页面加载之前检查它。
这里的问题不是抓取重复的URL，而是使用从url获取的散列通过索引解析。问题是爬行重复内容。 “Crawler Trap”的每个URL都不同（年，日，SessionID ......）。
没有“完美”的解决方案......但您可以使用以下策略：
•保持网站内的网址水平。对于从页面获取URL的每个cicle，增加级别。它就像一棵树。您可以停止在某个级别抓取，例如10（我认为谷歌使用此）。
•您可以尝试创建一种可以比较的HASH来查找类似的文档，因为您无法与数据库中的每个文档进行比较。有来自谷歌的SimHash，但我找不到任何实现可以使用。然后我创造了自己的。我的哈希计数html代码中的低频和高频字符，并生成一个20字节的哈希值，与一个AVLTree内的最后一个爬网页面的小缓存进行比较，其中NearNeighbors搜索具有一定的容差（约为2）。您无法在此哈希中使用对字符位置的任何引用。在“识别”陷阱后，您可以记录重复内容的URL模式，并开始忽略该页面。
•与谷歌一样，您可以为每个网站创建排名，并在一个网站中“信任”更多。
爬网程序会保留一个包含要爬网的所有URL的URL池。为了避免“无限循环”，基本思想是在添加到池之前检查每个URL的存在。
但是，当系统缩放到某个级别时，这并不容易实现。天真的方法是将所有URL保留在哈希集中并检查每个新URL的存在。当有太多的URL不适合内存时，这将不起作用。
这里有几个解决方案。例如，我们应该将它们保存在磁盘中，而不是将所有URL存储到内存中。为节省空间，应使用URL哈希而不是原始URL。值得注意的是，我们应该保留URL的规范形式而不是原始形式。因此，如果像bit.ly这样的服务缩短了URL，那么最好获取最终的URL。为了加快检查过程，可以构建缓存层。或者您可以将其视为分布式缓存系统，这是一个单独的主题。
后Build a Web Crawler详细分析了这个问题。
我还需要使用crawler并且无法找到适合我的要求，所以在此之后我开发了基本的爬虫库以实现简单的要求。但能够实现几乎所有爬虫原则。您可以使用Entity Framework Core检查实现Downloader-Processor-Pipeline模块的DotnetCrawler github repo，并使用Entity Framework Core进行默认实现，以便将数据保存到Sql Server中。
网络爬虫是一种计算机程序，用于从给定的网站URL收集/抓取以下关键值（HREF链接，图像链接，元数据.etc）。它的设计类似于智能，可以跟踪已从先前URL获取的不同HREF链接，因此通过这种方式，Crawler可以从一个网站跳转到其他网站。通常，它称为Web蜘蛛或Web Bot。此机制始终充当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;
}
}
?>
Web基本上是一个有向图，因此您可以从URL中构建图形，然后在标记受访节点时执行BFS或DFS遍历，这样您就不会访问同一页面两次。