我最近在准备面试时读了一本书,并遇到了以下问题:
当你的爬虫遇到一个蜜 jar 并生成一个无限子图供你漫步时,你会怎么做?
我想找到这个问题的一些解决方案。就我个人而言,我会采用某种形式的深度有限搜索来防止连续遍历。或者也许使用某种形式的机器学习来检测模式。想法?
最佳答案
最常见的无限子图是通过链接深度来阻止的。因此,您获得了一组初始 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.
关于web-crawler - 面试问题: Honeypots and web crawlers,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6780461/