数学之美系列一:图论和网络爬虫 (Web Crawlers)
建立一个搜索引擎大致需要做这样几件事:自动下载尽可能多的网页;建立快速有效的索引;根据相关性对网页进行公平准确的排序。
数学之美系列一:图论和网络爬虫 (Web Crawlers)
如何自动下载互联网所有的网页呢,它要用到图论中的遍历(Traverse) 算法。
图论中所讨论的的图由一些节点和连接这些节点的弧组成。如果把中国的城市当成节点,连接城市的国道当成弧,那么全国的公路干线网就是图论中所说的图。关于图的算法有很多,但最重要的是图的遍历算法,也就是如何通过弧访问图的各个节点。以中国公路网为例,从北京出发,看一看北京和哪些城市直接相连,比如说和天津、济南、石家庄、南京、沈阳、大同直接相连。可以依次访问这些城市,然后看看都有哪些城市和这些已经访问过的城市相连,比如说北戴河、秦皇岛与天津相连,青岛、烟台和济南相连,太原、郑州和石家庄相连等等,再一次访问北戴河这些城市,直到中国所有的城市都访问过一遍为止。这种图的遍历算法称为“广度优先算法”(BFS),因为它先要尽可能广地访问每个节点所直接连接的其他节点。另外还有一种策略是从北京出发,随便找到下一个要访问的城市,比如是济南,然后从济南出发到下一个城市,比如说南京,再访问从南京出发的城市,一直走到头。然后再往回找,看看中间是否有尚未访问的城市。这种方法叫“深度优先算法”(DFS),因为它是一条路走到黑。这两种方法都可以保证访问到全部的城市。当然,不论采用哪种方法,都应该用一个小本本,记录已经访问过的城市,以防同一个城市访问多次或者漏掉哪个城市。
现在看看图论的遍历算法和搜索引擎的关系。互联网其实就是一张大图,可以把每一个网页当作一个节点,把那些超链接(Hyperlinks)当作连接网页的弧。很多读者可能已经注意到,网页中那些蓝色的、带有下划线的文字背后其实藏着对应的网址,当点下去的的时候,浏览器是通过这些隐含的网址转到相应的网页中的。这些隐含在文字背后的网址称为“超链接”。有了超链接,可以从任何一个网页出发,用图的遍历算法,自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫,或者在一些文献中称为"机器人"。世界上第一个网络爬虫是由麻省理工学院 的学生马休.格雷在 1993 年写成的。他给他的程序起了个名字叫“互联网漫游者”("www wanderer")。以后的网络爬虫越写越复杂,但原理是一样的。
我们来看看网络爬虫如何下载整个互联网。假定我们从一家门户网站的首页出发,先下载这个网页,然后通过分析这个网页,可以找到藏在它里面的所有超链接,也就等于知道了这家门户网站首页所直接连接的全部网页,诸如雅虎邮件、雅虎财经、雅虎新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等网页,又能找到其他相连的网页。我们让计算机不停地做下去,就能下载整个的互联网。当然,我们也要记载哪个网页下载过了,以免重复。在网络爬虫中,我们使用一个称为“哈希表”(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。
现在的互联网非常巨大,不可能通过一台或几台计算机服务器就能完成下载任务。比如雅虎公司宣称他们索引了 200 亿个网页,假如下载一个网页需要一秒钟,下载这 200 亿个网页则需要 634 年。因此,一个商业的网络爬虫需要有成千上万个服务器,并且由快速网络连接起来。如何建立这样复杂的网络系统,如何协调这些服务器的任务,就是网络设计和程序设计的艺术了。
分享到:
相关推荐
Python 网络爬虫(Web Crawlers)学习笔记。
网络爬虫我用于个人项目的网络爬虫存储库
Bank::Crawlers::Hapoalim (蹩脚的)Hapoalim 在线界面的(蹩脚的)爬虫。 安装 将此行添加到应用程序的 Gemfile 中: gem 'bank-crawlers-hapoalim' 然后执行: $ bundle 或者自己安装: $ gem install ...
有趣的Python爬虫和Python数据分析小项目(Some interesting Python crawlers and data analysis projects).zip 软件开发设计:应用软件开发、系统软件开发、移动应用开发、网站开发C++、Java、python、web、C#等语言...
有趣的Python爬虫和Python数据分析小项目(Some interesting Python crawlers and data analysis projects) 可以用Python实现的有趣的小项目,内容包括Python爬虫、Python数据分析、机器学习、深度学习等
在Node.js中,您可以require该软件包获取一组搜寻器用户代理。 const crawlers = require ( 'crawler-user-agents' ) ; console . log ( crawlers ) ; 用法 每个pattern都是一个正则表达式。 它应该可以使用
大众点评爬虫 开发计划 detect shop ID. 从已经下载的页面中解析出 ID. 起始页面, 人工选择一个皆可. 建议选择 shop list 页面. download shop profile page profile page 中解析出 review(评论), 评论数 大于等于 ...
reddit_crawlers, 将尝试制作有趣的reddit爬虫,提供一些洞察力 reddit_crawlers将尝试制作有趣的reddit爬虫,提供一些洞察力使用 python praw库对于着色 bot: 我们使用以下 python 附加软件包:...
本项目是一个Java编写的多线程爬虫系统。此系统与我之前开发的结合使用,共抓取了淘宝近3000个页面,从中解析到了近9万的商品详情页URL。 我并没有直接将这些商品详情页中最具价值的数据(商品信息)提取出来,因为...
本项目旨在通过使用JAVA语言实现一个基于目标网页特征(网页内容特征和URL正则特征)和广度优先搜索策略的多线程聚焦爬虫程序框架。通过使用此框架可以简单、高效地完成具备个性化需求的爬虫程序的开发定制。 ###...
课程爬虫用于收集 UofT 课程数据的网络爬虫。
Python爬虫和Python数据分析小项目(Some Python crawlers and data analysis projects) 适合学习/练手、毕业设计、课程设计、期末/期中/大作业、工程实训、相关项目/竞赛学习等。 项目具有较高的学习借鉴价值,也可...
适用于 Flipkart 和亚马逊的 Scrapy 爬虫使用“apt-get install scrapy”在ubuntu上安装scrapy git clone 项目并从项目根目录运行“scrapy crawl amazon/flipkart”。 ##MIT 许可证
有趣的Python爬虫和Python数据分析小项目(Some interesting Python crawlers and data analysis projects) 适合学习/练手、毕业设计、课程设计、期末/期中/大作业、工程实训、相关项目/竞赛学习等。 项目具有较高的...
Python Web Scraping Cookbook is a solution-focused book that will teach you techniques to develop high-performance scrapers and deal with crawlers, sitemaps, forms automation, Ajax-based sites, and ...
SeimiCrawler是一个敏捷的,支持分布式的Java爬虫开发框架,希望能在最大程度上降低新手开发一个可用性高且性能不差的爬虫系统的门槛,以及提升开发爬虫系统的开发效率。在SeimiCrawler的世界里,绝大多数人只需...
If programming is magic then web scraping is surely a form of wizardry. By writing a simple automated program, you can query web servers, request data, and parse it to extract the information you need...