数据结构与算法在爬虫中的应用,你知道吗?

相信很多人已经学过数据结构和算法,但是数据结构和算法有什么用呢?只需要在面试中使用算法吗?今天,我们来谈谈数据结构和算法在爬虫中的应用。虽然今天我们已经有了很多优秀的爬虫框架,但是了解内部原理对我们更有好处。

什么是爬行动物?如果我们热爱运动的同学可以理解为球探,我们会到处收集球员的信息,然后存储起来。爬虫是互联网上的侦察兵,比如搜索引擎,需要被爬虫抓取并存储。电商网站需要抓取朋友和商家的产品价格数据用c语言实现八数码问题的宽度优先搜索,以便更方便的设置产品价格。

爬虫是如何工作的?想想我们想看的新闻,进入新闻网站的首页。我们会发现主页上有很多不同的链接。比如首页上有新闻频道、科技频道、财经频道。二级分类,二级分类下还有更多的子分类。爬虫应该按什么顺序爬行?

最简单的方法是深度优先算法,也称为 DFS。每当我们看到一个未遍历的链接时,我们就会继续在下面爬行。像上面爬取新闻网站的例子,如果我们先进入技术频道,然后进入电脑,进入操作系统,进入图灵简介。链接,然后爬图灵国的链接,可能需要很长时间才能回到新闻首页用c语言实现八数码问题的宽度优先搜索,开始爬财经新闻。

显然,对于我们爬取一个网站来说,使用深度优先算法是有一定弊端的。通常我们使用广度优先算法。什么是广度优先算法?对于上面的例子,进入首页后,我们将首页放上去。技术、金融和新闻都添加到队列中。我们先爬取技术页面,将电脑、数码、机械等加入队列,然后开始处理财经页面,将财经页面的链接加入队列,然后处理新闻,像这样一个处理层按层,我们称之为广度优先搜索。

显然,不同的网站可能链接到同一个地址。例如,几乎每个页面都可以跳转到首页。我们需要一个 url 库来对不同的链接进行排名。那么如何设计去重的算法呢?最简单的就是for循环判断是否有重复,当然这样太慢了。我们还可以使用 Hashmap 或 Treemap 进行重新排序,也可以使用数据库索引进行重新排序。然而,互联网已经进入大数据时代,链接数已经超过百亿。我们需要一种更有效的重复数据删除方法。一般来说,我们可以使用布隆过滤器。对一个链接进行多次hash,存储在bitset中,可以达到很好的效率。

另外,不同url中的内容可能相同。一般我们会计算网页内容的md5,然后判断权重。判断权重的算法可以参考判断URL权重的算法。

嗯,一个基本的爬虫算法一般采用深度优先算法和广度优先算法等不同的枚举策略,使用map、bitset等数据结构存储信息,还有balance、hash table、md5等算法。,爬虫这么简单的功能,竟然包含这么多算法?!

今天我们就在这里谈一谈。如果你有兴趣,欢迎关注我。最近除了分享算法相关的话题,主要讲一下redis的原理和应用。最近也准备了一些AI相关的知识,整理后继续分享给大家。您的支持是我前进的动力。同名公众号(沙察民随世年)

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享
评论 抢沙发

请登录后发表评论