设计一个网络爬虫

我遇到过一个面试问题: “如果你在设计一个网络爬虫，你会如何避免陷入无限循环?”我正在努力回答。

这一切是如何从头开始的。 假设谷歌最初只有一些中心页面，而现在有数百个(这些中心页面最初是如何被发现的是另一个子问题)。 当谷歌跟踪页面上的链接等等时，它是否一直制作哈希表以确保不跟踪早期访问过的页面。

如果同一个页面有两个名称(URL)说在这些天，我们有网址缩短等..。

我以谷歌为例。虽然谷歌没有泄露它的网络爬虫算法和网页排名等工作原理，但是有什么猜测吗？

46019 次浏览
小开

取决于他们的问题有多深刻。如果他们只是试图避免来回点击相同的链接，那么散列 URL 就足够了。

如果内容有成千上万的网址导向相同的内容，会怎么样呢？像 QueryString 参数一样，它不会影响任何东西，但是可以有无限次的迭代。我想您也可以对页面的内容进行散列，并比较 URL，看看它们是否类似于捕获由多个 URL 标识的内容。例如，在@Lirik 的帖子中提到的机器人陷阱。

小开

你必须有某种散列表来存储结果，你只需要在每次加载页面之前检查它。

小开

Web 基本上是一个有向图，所以你可以从 URL 中构建一个图，然后在标记访问的节点时执行 BFS 或 DFS 遍历，这样你就不会访问同一个页面两次。

小开
最佳答案

如果你想得到一个详细的答案，可以看看 本文第3.8节，它描述了一个现代刮刀的 URL-seen 测试:

在提取链接的过程中，任何 网络爬虫将遇到多个 链接到同一文档 下载和处理文件 多次，一个 URL 可见的测试必须 对每个提取的链接执行 然后将其添加到 URL 前沿。 (另一种设计是 而是在以下情况下执行 URL-seen 测试 URL 从边界删除, 但是这种方法会导致 更广阔的领域)

执行 URL 可见的测试，我们存储所有 Mercator 在规范中看到的 URL 表单中的一个大型表，称为 URL 再一次，有太多的条目 让他们都能被记住，所以 文档指纹集、 URL 集合主要存储在磁盘上。

去拯救 空格，我们不存储文本 表示 URL 中的每个 URL 而是一个固定大小的 校验和，不像指纹 提交给内容可见测试的 文件指纹集，流 根据 URL 集测试的 URL 有 非平凡的地方 减少操作的次数 备份磁盘文件，因此我们保留 流行 URL 的内存缓存。 这个缓存的直觉是 链接到一些网址是相当普遍的, 所以在内存中缓存那些流行的 将导致高内存命中率 税率。

实际上，使用内存中的 缓存2 ^ 18个条目和类 LRU 时钟更换策略，我们实现 内存的总命中率 缓存为66.2% ，命中率为9.5% 在最近添加的 URL 表中, 纯命中率为75.7% 。此外, 有24.3% 的请求没有通过 流行 URL 的缓存和 最近添加的 URL 表，大约 1 = 3在我们的缓冲区上产生命中 随机访问文件的实现, 它也驻留在用户空间中 所有这些缓冲的最终结果是 我们进行的每个成员资格测试 对 URL 集的平均结果 0.16搜索和0.17读内核 调用(其中一部分是 服务于内核的文件系统 因此，每个 URL 都设置了成员资格 测试产生六分之一的内核 调用作为成员资格测试 文件指纹设置。这些 储蓄纯粹是由于金额 网址本地化(即重复 流中固有的 URL) 在爬网过程中遇到的 URL。

基本上，它们使用散列函数对所有 URL 进行散列，该散列函数保证每个 URL 具有唯一的散列，并且由于 URL 的本地性，所以很容易找到 URL。谷歌甚至开源了他们的散列函数: CityHash

警告！
他们可能也在谈论机器人陷阱! ! ！Bot 陷阱是页面的一个部分，它不断生成带有唯一 URL 的新链接，通过跟踪该页面提供的链接，您基本上会陷入一个“无限循环”中。这不完全是一个循环，因为一个循环将是访问相同 URL 的结果，但它是一个无限的 URL 链，您应该避免爬行。

2012年12月13日更新

根据 Fr0zenFyr 的评论: 如果使用 AOPIC算法选择页面，那么很容易避免无限循环类型的 bot 陷阱。以下是 AOPIC 工作原理的总结:

  1. 获取一组 N 个种子页。
  2. 为每个页面分配 X 个信用额度，这样每个页面在爬网开始之前都有 X/N 个信用额度(即等量的信用额度)。
  3. 选择一个页面 P，其中 P 具有最高的信用额度(或者如果所有页面具有相同的信用额度，则随机抓取一个页面)。
  4. 抓取页面 P (让我们假设当它被抓取时 P 有100个信用点)。
  5. 从页面 P 中提取所有链接(假设有10个链接)。
  6. 将 P 的学分设置为0。
  7. 采取10% 的“税”，并分配到一个 Lambda 页面。
  8. 从 P 的原始信用卡中分配相同数量的信用卡给 P 页上的每个链接——税: 所以(100(P 信用卡)-10(10% 税))/10(链接) = 每个链接9个信用卡。
  9. 重复第三步。

由于 Lambda 页面不断收取税款，最终它将是最大数额的信贷页面，我们将不得不“抓取”它。我用引号表示“抓取”，因为我们实际上并没有对 Lambda 页面发出 HTTP 请求，我们只是获取它的信用值，并将它们平均分配给数据库中页面的 所有。

由于机器人陷阱只给内部链接信用，他们很少从外部获得信用，他们将不断泄漏信用(从税收)到 Lambda 页面。Lambda 页面将会平均分配信用到数据库中的所有页面，在每个循环中，bot 陷阱页面将会失去越来越多的信用，直到它的信用很少，以至于它几乎再也不会被抓取。这种情况不会发生在好的页面，因为他们经常从其他页面的反向链接获得学分。这也会导致一个动态的页面排名，你会注意到，任何时候你采取的数据库快照，排序的网页的学分数量，然后他们很可能是按照他们的 真实页面排名大致排序。

这只是避免了机器人陷阱的无限循环类型，但有 许多其他的机器人陷阱，你应该小心，并有办法绕过他们也。

小开

这里的问题不是抓取重复的 URLS，而是通过使用从 URLS 获得的散列的索引来解决。问题是抓取重复的内容。“ Crawler Trap”的每个 URL 都是不同的(年、日、 SessionID...)。

没有一个“完美”的解决方案... ... 但是你可以使用下面的一些策略:

•保持网址位于网站内部的位置。对于从页面获取 URL 的每个圈，增加级别。就像一棵树。你可以停下来在某个级别爬行，比如10(我认为谷歌使用这个)。

您可以尝试创建一种 HASH，它可以与查找类似文档进行比较，因为您无法与数据库中的每个文档进行比较。有来自谷歌的 SimHash，但我找不到任何实现使用。然后我创造了我自己的。我的哈希计数在 html 代码中的低频和高频字符，并生成一个20字节的哈希，这与 AVLTree 中的最后抓取的小缓存页面进行了比较，使用了一个带有一定容差(约2)的近邻搜索。在此哈希中不能使用对字符位置的任何引用。在“识别”陷阱之后，您可以记录重复内容的 url 模式，并开始使用该模式忽略页面。

•与谷歌一样，你可以为每个网站创建一个排名，并且对其中一个网站的“信任”程度高于其它网站。

小开

虽然这里的每个人都已经建议如何创建您的网络爬虫，这里是如何谷歌排名的网页。

谷歌根据回调链接的数量给每个页面一个排名(其他网站上有多少链接指向特定的网站/页面)。这就是所谓的相关性评分。这是基于一个事实，如果一个页面有许多其他页面链接到它，它可能是一个重要的页面。

每个站点/页面都被视为图中的一个节点。指向其他页面的链接是有向边缘。顶点的度定义为传入边的数目。传入边数较多的节点排名较高。

下面是确定 PageRank 的方法。假设页面 Pj 有 Lj 链接。如果其中一个链接指向 Pi 页面，那么 Pj 将把1/Lj 的重要性传递给 Pi。Pi 的重要性排名是由链接到它的页面所做贡献的总和。如果我们用 Bi 表示连接到圆周率的一组页面，那么我们有这个公式:

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，II我H... 。I ^ k * H 直到解收敛。也就是说，我们在 k 和 k + 1的矩阵中得到了几乎相同的数字。

现在在 I 向量中剩下的就是每一页的重要性。

有关一个简单的课堂作业例子，请参阅 http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

为了解决面试问题中的重复问题，在整个页面上做一个校验和，并且使用这个校验和或者在地图上使用一个猛击校验和作为你的关键字来跟踪访问过的页面。

小开

这是一个网络爬虫的例子。它可以用来收集 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'])

更改网址以抓取更多网站... ... 祝你好运

小开

该网络爬虫是一个计算机程序，用于收集/爬行下面的关键值(HREF 链接，图像链接，元数据。等)。它的设计就像智能跟踪不同的 HREF 链接已经从以前的网址，所以在这种方式下，爬虫可以从一个网站跳转到其他网站。通常，它被称为 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;
}
}
?>

提交答案