web-crawler - 面试问题: Honeypots and web crawlers

Question

我最近在准备面试时读了一本书，并遇到了以下问题:

当你的爬虫遇到一个蜜 jar 并生成一个无限子图供你漫步时，你会怎么做？

我想找到这个问题的一些解决方案。就我个人而言，我会采用某种形式的深度有限搜索来防止连续遍历。或者也许使用某种形式的机器学习来检测模式。想法？

Answer 1

最常见的无限子图是通过链接深度来阻止的。因此，您获得了一组初始 URL，并且将从每个 URL 遍历到有限的深度。在限制遍历深度的同时，您可以使用一些启发式方法根据网页特征动态调整它。可以找到更多信息，例如here .

另一种选择是尝试某种模式匹配。但根据生成子图的算法，这将是一项相当(非常非常非常)困难的任务。这至少也是一个相当昂贵的操作。

面试问题(关于检测无限循环):

如果他们问这个问题，有人想听到对 Halting problem 的引用。

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.