搜索引擎如何抓取网页(IT皇冠上的明珠也不为过：一下搜索引擎：网页抓取)

　　搜索引擎如何抓取网页(IT皇冠上的明珠也不为过：一下搜索引擎：网页抓取)

　　我们每天都使用谷歌和百度等搜索引擎。你有没有想过搜索引擎是如何实现的？看似简单的搜索，其实在技术细节上非常复杂。毫不夸张地说，搜索引擎是 IT 皇冠上的明珠。今天我们就简单的看一下搜索引擎的原理，看看它是如何工作的。

　　让我们专注于第一步：网络抓取。

　　这一步的一般操作如下：给爬虫分配一组起始网页。我们知道网页实际上收录许多超链接。爬虫爬取网页后，会解析提取网页中的所有超链接，然后依次进行爬取。取出这些超链接，然后提取网页的超链接。以这种方式不断重复提取基于超链接的网页。

　　如下所示：

　　如上图，最终形成了一个图，那么问题就变成了如何遍历这个图。

　　一、什么是图遍历？

　　从给定连通图中的某个顶点出发，沿着某些边访问图中的所有顶点，并使每个顶点只访问一次，称为图遍历，这是图的基本操作。

　　遍历的本质是寻找每个顶点的连接点的过程。

　　图的特点：图中可能存在环，图的任何一个顶点都可能与其他顶点相连。在访问了某个顶点之后，它可能会沿着一些边返回到之前访问过的顶点。

　　以游览公园为例，从公园入口v1开始，如何用最短的距离游览完公园内的所有七个景点，就是一个典型的图遍历。

　　遍历图有两种常用的方法：

　　深度优先搜索 - DFS 广度优先搜索 - BFS 二、什么是深度优先搜索？

　　拿经典的迷宫图来看看如何穿越。

　　问题：如何从迷宫入口开始，点亮迷宫中的所有灯？

　　Step 1：从顶点开始遍历（迷宫的入口），它的相邻顶点有左右两盏灯，我们随机选择右边的一个点亮。

　　第二步：以点亮的灯为顶点继续遍历。它有两个相邻的顶点：入口灯和右下角的灯。由于入口灯已经点亮，我们只能点亮右下角的灯。

　　第三步：重复以上步骤，以点亮的灯为顶点继续遍历，直到道路失效。如下所示：

　　第四步：无路可走后，沿着原路返回，继续寻找没有亮的灯，直到所有的灯都亮了。到目前为止，我们已经完全实现了深度优先搜索。如下所示：

　　总结：

　　深度优先搜索的主要思想是从图中一个未访问的顶点V开始，沿着一条路走到尽头，然后从路尽头的节点回到前一个节点，然后从另一条通往终点的路……

　　递归地重复这个过程，直到遍历完所有的顶点。

　　三、什么是广度优先搜索？

　　问题：如何从条目 1 遍历整个树？

　　第一步：首先遍历节点1-2、3、4的所有节点。

　　第二步：然后分别遍历节点2、3、4-5、6、7、8的所有节点。

　　第三步：分别遍历节点5、6、7、8的所有节点——9、10。

　　总结：

　　具体思路：从图中的某个顶点1开始，访问1后，依次访问1的每个未访问的相邻点，然后从这些相邻点依次访问它们的相邻点，使“第一个访问的顶点”成为邻接的顶点在后面访问的顶点的邻接之前被访问”，直到图中所有已经访问过的顶点的邻接都被访问过。如果此时图中还有未访问的顶点，则需要另一个未访问的顶点被选为新的起点，重复上述过程，直到图中的所有顶点都被访问过。

　　简单来说，广度优先遍历是指从图中一个未遍历的节点开始，先遍历这个节点的相邻节点，然后依次遍历每个相邻节点的相邻节点。

　　所以广度优先遍历也称为层序遍历，先遍历第一层（节点1)，再遍历第二层（节点2,3,4),第三层） (5, 6, 7, 8), 四楼 (9, 10).

　　四、什么是堆栈？

　　栈是一种线性存储结构，只能从表的一端访问数据，遵循“先进后出”的原则。

　　例如，我们经常使用浏览器查找各种网站 的信息。假设先浏览A页，然后关闭A页跳转到B页，再关闭B页跳转到C页。此时，如果我们想回到A页，我们有两种选择：

　　再次搜索找到页面A；使用浏览器的“后备”功能。浏览器会先回退到页面 B，然后再回退到页面 A。

　　浏览器的“回退”功能的实现使用了底层的栈存储结构。

　　五、什么是队列？

　　与栈结构不同，队列的两端都是“开放的”，要求数据只能从一端进入，从另一端出来。队列中数据的进入和退出应该遵循“先进先出”的原则，即最高级队列的数据元素也应该最先退出队列。

　　队列的应用也非常广泛，只要符合“先到先得”特点的应用都可以使用队列作为其数据组织方式。例如，在一个多用户系统中，多个用户排成一列以分时循环使用 CPU 和主存。

　　栈和队列在图遍历中的应用：

　　由于深度优先搜索是一种先进后出算法，因此它是使用堆栈实现的。广度优先搜索是一种先进先出算法，使用队列实现。

　　以二叉树为例，看看如何使用栈来实现 DFS。

　　也以上面的二叉树为例，看看如何使用队列实现广度优先遍历。

　　六、如何抓取网络？

　　回到开头提到的搜索引擎，我们继续看网页爬虫的大致思路。

　　如果是广度优先遍历：先依次爬取第一层的起始网页，然后依次爬取各个网页中的超链接。

　　如果是深度优先遍历：首先爬取起始页1，然后爬取本页中的链接，爬取完成后再爬取起始页2。

　　实际上，爬虫使用了深度优先和广度优先两种策略。比如在起始页中，有些页面比较重要（权重较高），那么先对这个页面做深度优先遍历，遍历完再遍历其他页面。（相同权重）起始页是广度优先遍历。

　　本文由@CARRIE 原创 发布