京公网安备11010502063487号爬虫的待抓队列用先进先出、后进先出还是优先级队列,决定了在预算有限时先抓到什么。这篇用一个自己造的合成站点,量化三种顺序在不同预算下抓到多少有价值的页面、待抓队列有多大、遇到“标签云”这样的低价值团簇会浪费多少。
策略 预算 100 预算 300 预算 1000 预算 3000 预算 6000 BFS(先进先出,按层) 15/6000 205/6000 872/6000 2777/6000 5634/6000 DFS(后进先出) 33/6000 223/6000 889/6000 2791/6000 5643/6000 优先级:先商品页再列表 93/6000 283/6000 949/6000 2851/6000 5703/6000 优先级:深度小的先(≈BFS) 15/6000 205/6000 872/6000 2777/6000 5634/6000 (商品页共 6000 个,全站 6374 个页面;预算 6374 时三种策略最终都会抓完)
这是我自己写的链接图,不是真实网站:首页 → 10 个分类 → 每个分类 30 个分页列表页 → 每页 20 个商品页(共 6000 个商品页),另有一团 60 页互相链接的“标签云”和几个导航页。所有结论只对这个图成立。
BFS(先进先出,按层):待抓队列峰值 270 DFS(后进先出):待抓队列峰值 72 优先级:先商品页再列表:待抓队列峰值 60 优先级:深度小的先(≈BFS):待抓队列峰值 270
预算 100 页:BFS 15、DFS 33、按 URL 模式优先抓商品页 93;预算 1000 页:872 / 889 / 949。预算越小策略越重要,接近全站大小时差别消失。注意优先级策略利用了“商品页 URL 以 /item/ 开头”这个事先知道的信息,真实站点里要靠规则或学习得到。
BFS(先进先出,按层):预算 300 时抓到商品页 205 DFS(后进先出):预算 300 时抓到商品页 223 优先级:先商品页再列表:预算 300 时抓到商品页 283 预算 300 里花在标签云上的页数:BFS 61,DFS 61,优先级 0
BFS 的待抓队列随一层的宽度增长(峰值 270),DFS 沿一条路径深入、队列小(72)。优先级策略如果只按深度排,等价于 BFS(队列峰值也是 270)。
/ → /tags → /tag/59 → /tag/58 → /tag/57 → /tag/56 → /tag/55 → /tag/54 → /tag/53 → /tag/52 → /tag/51 → /tag/50 → /tag/49 → /tag/48 → /tag/47
互相链接的低价值页面团簇会吃掉预算:BFS 与 DFS 在 300 页预算里各花了 61 页。DFS 的路径依赖首页链接的顺序,同一个站点换个链接顺序,结果可能不同;这里只用了一种顺序。