`
lzj0470
  • 浏览: 1276872 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

数学之美系列六 -- 图论和网络爬虫 (Web Crawlers)

阅读更多

数学之美系列六 -- 图论和网络爬虫 (Web Crawlers)

<script></script>



[离散数学是当代数学的一个重要分支,也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算,我们已经介绍过了。这里我们介绍图论和互联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺便提一句,我们用 Google Trends 来搜索一下“离散数学”这个词,可以发现不少有趣的现象。比如,武汉、哈尔滨、合肥和长沙市对这一数学题目最有兴趣的城市。]

我们上回谈到了如何建立搜索引擎的索引,那么如何自动下载互联网所有的网页呢,它要用到图论中的遍历(Traverse) 算法。

图论的起源可追溯到大数学家欧拉(Leonhard Euler)。1736 年欧拉来到德国的哥尼斯堡(Konigsberg,大哲学家康德的故乡,现在是俄罗斯的加里宁格勒),发现当地市民们有一项消遣活动,就是试图将下图中的每座桥恰好走过一遍并回到原出发点,从来没有人成功过。欧拉证明了这件事是不可能的,并写了一篇论文,一般认为这是图论的开始。



图论中所讨论的的图由一些节点和连接这些节点的弧组成。如果我们把中国的城市当成节点,连接城市的国道当成弧,那么全国的公路干线网就是图论中所说的图。关于图的算法有很多,但最重要的是图的遍历算法,也就是如何通过弧访问图的各个节点。以中国公路网为例,我们从北京出发,看一看北京和哪些城市直接相连,比如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我们可以依次访问这些城市,然后我们看看都有哪些城市和这些已经访问过的城市相连,比如说北戴河、秦皇岛与天津相连,青岛、烟台和济南相连,太原、郑州和石家庄相连等等,我们再一次访问北戴河这些城市,直到中国所有的城市都访问过一遍为止。这种图的遍历算法称为“广度优先算法”(BFS),因为它先要尽可能广地访问每个节点所直接连接的其他节点。另外还有一种策略是从北京出发,随便找到下一个要访问的城市,比如是济南,然后从济南出发到下一个城市,比如说南京,再访问从南京出发的城市,一直走到头。然后再往回找,看看中间是否有尚未访问的城市。这种方法叫“深度优先算法”(DFS),因为它是一条路走到黑。这两种方法都可以保证访问到全部的城市。当然,不论采用哪种方法,我们都应该用一个小本本,记录已经访问过的城市,以防同一个城市访问多次或者漏掉哪个城市。

现在我们看看图论的遍历算法和搜索引擎的关系。互联网其实就是一张大图,我们可以把每一个网页当作一个节点,把那些超链接(Hyperlinks)当作连接网页的弧。很多读者可能已经注意到,网页中那些蓝色的、带有下划线的文字背后其实藏着对应的网址,当你点下去的的时候,浏览器是通过这些隐含的网址转到相应的网页中的。这些隐含在文字背后的网址称为“超链接”。有了超链接,我们可以从任何一个网页出发,用图的遍历算法,自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫,或者在一些文献中称为"机器人"(Robot)。世界上第一个网络爬虫是由麻省理工学院 (MIT)的学生马休.格雷(Matthew Gray)在 1993 年写成的。他给他的程序起了个名字叫“互联网漫游者”("www wanderer")。以后的网络爬虫越写越复杂,但原理是一样的。

我们来看看网络爬虫如何下载整个互联网。假定我们从一家门户网站的首页出发,先下载这个网页,然后通过分析这个网页,可以找到藏在它里面的所有超链接,也就等于知道了这家门户网站首页所直接连接的全部网页,诸如雅虎邮件、雅虎财经、雅虎新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等网页,又能找到其他相连的网页。我们让计算机不停地做下去,就能下载整个的互联网。当然,我们也要记载哪个网页下载过了,以免重复。在网络爬虫中,我们使用一个称为“哈希表”(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。

现在的互联网非常巨大,不可能通过一台或几台计算机服务器就能完成下载任务。比如雅虎公司(Google 没有公开公布我们的数目,所以我这里举了雅虎的索引大小为例)宣称他们索引了 200 亿个网页,假如下载一个网页需要一秒钟,下载这 200 亿个网页则需要 634 年。因此,一个商业的网络爬虫需要有成千上万个服务器,并且由快速网络连接起来。如何建立这样复杂的网络系统,如何协调这些服务器的任务,就是网络设计和程序设计的艺术了。

分享到:
评论

相关推荐

    examples-of-web-crawlers-python爬虫资源

    python,,QQ(Some interesting examples of python crawlers that are friendly to beginners. )

    Python 网络爬虫(Web Crawlers)学习笔记。.zip

    Python网络爬虫是数据获取的重要工具,特别是在大数据时代,它能帮助我们自动化地从互联网上收集和处理信息。本学习笔记将深入探讨Python爬虫的基本原理、常用库以及实际操作技巧。 1. **爬虫基础知识** - **...

    spidey-web-crawlers:Ruby 中的网络爬虫

    综上所述,"spidey-web-crawlers"项目是一个使用Ruby编写的网络爬虫,它可能利用Nokogiri、HTTParty和Mechanize等库来抓取和处理网页数据。实际的代码实现、特定功能以及爬取策略将取决于项目内的具体文件内容。

    数学之美系列完整版.doc

    **图论**在网络爬虫(Web Crawlers)中用于理解互联网的拓扑结构,有效地抓取和组织网页。 **最大熵模型**避免过拟合,通过最大化熵来平衡模型复杂性和数据不确定性。 **贝叶斯网络**是一种概率图模型,常用于处理...

    bank-crawlers-hapoalim:糟糕的 Hapoalim 帐户的糟糕爬虫

    gem 'bank-crawlers-hapoalim' 然后执行: $ bundle 或者自己安装: $ gem install bank-crawlers-hapoalim 用法 BankCrawlers :: Hapoalim . run "USER" , "TEUDAT ZEUT" , "PASSWORD" 贡献 分叉吧 创建您的...

    网络爬虫说明文档

    #### 知识点一:网络爬虫(Web Crawlers)的定义与作用 网络爬虫,又称为网页蜘蛛或自动索引器,是一种自动化程序,用于遍历互联网上的网页并收集信息。其核心功能在于探索和抓取网络上公开可访问的网页内容,为...

    course-crawlers:用于收集 UofT 课程数据的网络爬虫

    综上所述,"course-crawlers"是一个高效实用的工具,结合了网络爬虫技术与教育领域的具体需求,为获取和利用UofT课程数据提供了便利。其背后涉及的编程技巧、网页解析以及数据处理等知识点,对于IT从业者来说都是...

    java抓取技术源码-multithreading-crawlers:多线程爬虫--抓取淘宝商品详情页URL

    多线程爬虫--抓取淘宝商品详情页URL 本项目是一个Java编写的多线程爬虫系统。此系统与我之前开发的结合使用,共抓取了淘宝近3000个页面,从中解析到了近9万的商品详情页URL。 我并没有直接将这些商品详情页中最具...

    java实现的搜索引擎网络爬虫 使用了队列 重复爬取检测

    在现代互联网时代,网络爬虫(Web Crawlers)被广泛应用于数据抓取、分析以及搜索引擎建设等多个领域。本文将详细介绍一个基于Java实现的简易搜索引擎网络爬虫的具体设计与实现思路。该爬虫采用广度优先搜索算法遍历...

    distributed-vertical-crawlers:分布式垂直爬虫框架 & 爬虫们

    大众点评爬虫 开发计划 detect shop ID. 从已经下载的页面中解析出 ID. 起始页面, 人工选择一个皆可. 建议选择 shop list 页面. download shop profile page profile page 中解析出 review(评论), 评论数 大于等于 ...

    爬虫论文爬虫论文爬虫论文爬虫论文爬虫论文爬虫论文爬虫论文爬虫论文

    **爬虫(Web Crawlers)**是互联网数据抓取的重要工具,也被称为Web蜘蛛或机器人。它们用于自动下载互联网上的文档,是搜索引擎等系统的基础组件。 **传统广度优先爬取方法(TBFC)**是最常见的爬虫策略之一,通常...

    daedalus-crawlers-JS

    内置JavaScript的网络爬虫 建造者:dev.icarus 查看我的网站: : 我存储用JavaScript制作的所有Web爬网程序的地方。 最初,我把每个爬虫都说成是自己的仓库,但最终我厌倦了创建基本上相同的新项目,因此现在它们都...

    daedalus-crawlers-PY

    内置Python的网络爬虫 建造者:dev.icarus 查看我的网站: : 我存储使用Python创建的所有Web爬网程序的地方。 最初,我把每个爬虫都说成是自己的仓库,但最终我厌倦了创建基本上相同的新项目,因此现在它们都存储在...

    Python爬虫基础知识

    在实际应用中,Python爬虫广泛应用于数据挖掘、市场调研等多个领域,成为数据获取的重要手段之一。 #### 二、关键技术栈 1. **编程语言**:Python是首选的编程语言,因为它拥有丰富的第三方库支持。 2. **核心库**...

    crawler-user-agents:漫游器,爬虫,爬虫,蜘蛛使用的HTTP用户代理的语法模式。 拉请求欢迎

    搜寻器用户代理 该存储库包含机械手,搜寻器和蜘蛛使用的HTTP用户代理... const crawlers = require ( 'crawler-user-agents' ) ; console . log ( crawlers ) ; 用法 每个pattern都是一个正则表达式。 它应该可以使用

    有趣的Python爬虫和Python数据分析小项目(Some interesting Python crawlers and d

    有趣的Python爬虫和Python数据分析小项目(Some interesting Python crawlers and data analysis projects) 可以用Python实现的有趣的小项目,内容包括Python爬虫、Python数据分析、机器学习、深度学习等

    Python项目-有趣的Python爬虫和Python数据分析小项目

    有趣的Python爬虫和Python数据分析小项目(Some interesting Python crawlers and data analysis projects) 适合学习/练手、毕业设计、课程设计、期末/期中/大作业、工程实训、相关项目/竞赛学习等。 项目具有较高的...

Global site tag (gtag.js) - Google Analytics