转自：Vicodin 本期的《程序员的那些事》 小七带大家了解 图论和网络爬虫 世界上不可能有比二进制更简单的计数方法了，它只有两个数字：0和1。从单纯的数学角度上来说，它甚至比我们的十进制更加合理，但是人有十根手指，使用起来比二进制要方便的多，所以在人类进化的过程中人类采用了十进制。 二进制除了是一种计数的方式外，它还可以表示逻辑的“是”与“非”,这第二个特性在索引中非常有用，布尔运算时针对二进制，尤其是第二个特性的运算，尽管今天每个搜索引擎都在宣传自己的产品如何智能，如何聪明，但是实质上都不会逃出布尔运算的框架。 布尔运算简单的不能再简单了，运算的元素只有两个：1（TRUE，真）和0（FALSE，假），基本的运算只有“与”（AND），“或”（OR），“非（NOT）”三种，而这三种运算都可以转换成“与-非”AND-NOT 运算。全部的运算只需要几张真值表就可以完全描述清楚： "与"运算真值表 “或”运算真值表 “非”运算真值表 对于这么简单的理论，人们一度对布尔运算所能解决的实际问题持怀疑态度，事实上在布尔运算被提出很长一段时间，它确实没什么像样的应用，直到香农提出用布尔代数来实现开关电路，才使得布尔代数称为数字电路的基础，所有的数学和逻辑计算全部可以转换成二进制的布尔运算 我们已经知道布尔运算不仅是一种计数的方式，还可以表示逻辑上的“是”与“非”，在文献检索的领域中，对于一个用户输入的关键词，搜索引擎要判断每篇文章是否含有这个关键词，如果含有它，则给一个逻辑值真（TURE或1），反之给一个逻辑值假（FALSE或0） 比如我们想找前几天3.15晚会关于互联网公司的新闻，但是不想知道关于三星的新闻，就可以写一个查询语句：“3.15晚会AND互联网公司AND（NOT三星），表示符合要求的内容必须同时满足三个条件：
每一条新闻对于上述的条件，都可以给出一个TURE或者FALSE的答案，根据上述真值表进行计算就可以知道每篇新闻是不是符合要求的内容。这样，逻辑推理和计算就完美的结合在了一起。 虽然在很长一段时间中，布尔代数并没有实际的应用产生，也没有发挥出相应的作用，但是布尔代数对于数学的意义等同于量子力学对于物流学的意义,它们将我们对世界的认知从连续状态拓展到离散状态。 布尔代数给了我们实现在近乎无穷数据的互联网上搜索所需的方法，但是：互联网巨大的数据如何获取，如何储存，如何尽可能高效去获取结果，这些问题也是在现实的过程中不得不面对的难题。 至此，图论又是一个不可避免的概念： 图论是离散数学的一个分支，以图为研究对象，图论中用点去代表事物，用连接两点的线去表示相应两个事物具有的某种关系。 互联网虽然很复杂，但是说穿了其实就是一张巨大的图，可以把每个网页当做一个节点，把那些超链接（Hyperlinks）当做链接网页之间的弧。 关于图的算法有很多，而其中最重要的就是图的遍历算法，也就是如何通过弧访问图的各个节点，等同到实际也就是我们如何尽可能全面的获取互联网上的信息。如果以中国公路网为例，我们从北京出发，访问所有的城市： 方案1： PS：图中序号表示遍历的次序
从北京出发，可以以此先访问那些直接和北京相连的城市，比如天津、济南等，然后看看那些城市和这些已经访问过的城市相连，比如北戴河、秦皇岛和天津相连；烟台和青岛和济南相连，而后再一次访问太原、烟台、北戴河等城市，直到把图中所有城市访问过一遍为止。 这种图的遍历算法称为“广度优先搜索”（BreadthFirst Search），因为它先尽可能“广”的访问与每个节点直接连接的其他节点。 方案2： PS：图中序号表示遍历的次序 另一种方案是从北京出发，随便找一个相连的城市作为下一个要访问的城市，比如济南，然后从济南出发到下一个城市，比如南京，再访问从南京出发的城市，一直走到头，直到找不到更远的城市了，再往回找，看看中间是否有尚未访问过的城市。 这种方案由于是一条路走到黑，才会回头去寻找其他的路径，所以称作“深度优先搜索”（Depth-First Search）。 其实在以中国公路网络进行模拟的时候，我们已经进行了一次类爬虫的爬取。 但是是实际的运用中，面临的问题远比中国公路网络要复杂，主要有以下几点： 由于对时间因素的考虑，以及互联网动态变化的特点，搜索引擎实际上的是要做到在有限时间内最多的爬取最重要的网页。显然，每个网站最重要的都是他的首页，在这个前提下BFS明显要优于DFS。 那DFS就不需要了吗？同时我们还需要考虑爬虫的分布式结构和网络通信的握手成本，如果握手的次数太多，产生大量的额外时间（Overhead Time），下载的效率就降低了。 所以总体来说，网络爬虫对网页的遍历的次序不是简单的BFS或者DFS，而是有一个相对复杂的下载优先级排序的方案，管理这个优先级的子系统一般称为调度系统（Scheduler） 在互联网早期，网页都是直接用HTML语言去书写，URL都是以文本的形式存放在网页中，前后都有明显的标识。很容易提取出来。但是如今，很多网页是用脚本语言去完成的（比如javaScript），打开网页的源代码，URL不是直接可见的文件，而是运行一段脚本后才能得到的结果。因此，网络爬虫的页面分析变得复杂很多，需要模拟浏览器运行一个网页，才能得到里面隐含的URL,有些网页的脚本写的不规范，更是给解析工作带来困难。 在互联网上，一个网页可能被多个网页指向，即在互联网这张图上有多个弧可以走到这个节点，这样在遍历这张图的时候，这个网页可能会被多次访问到，为了避免一个网页被多次下载，用一个散列表记录哪些网页已经被下载过，再遇到的时候就可以直接跳过。在一台下载服务器上建立和维护一张散列表并不是难事，但是如果同时又上千台服务器一起下载网页，维护一张统一的散列表就没有那么简单了，过大的表格和下载前后对服务器的访问会对服务器造成巨大的负担，此时存储服务器的通信就成了整个爬虫系统的瓶颈。 END 编辑 / 董靖鑫 编审 / 吴宗源 |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
