《数学之美》阅读记录三

今天看到了介绍搜索引擎和网络爬虫的原理。

搜索引擎如何能在0.几秒内给出搜索结果呢?如果是单纯的进行每个网页的文字扫描,想必大家都知道不可能这么快的。搜索引擎做了一件事,就是给网页添加索引,就好比图书馆给每本书添加了个编号,这样就加速了我们找书的速度;同样的,有了索引,在索引中找一个关键字和在茫茫的网页中找这个关键字比起来根本就不是一个数量级的。

谈到这个索引,就不得不谈到布尔代数。布尔代数只有0和1两个状态,一开始出现的时候不被人注意,人们认为这么简单的数学没有什么用处,后来香农把它带入了电路后才慢慢进入了人们的视野,人们也慢慢离不开它。

网络爬虫的原理就是模拟浏览器浏览页面,然后把页面上的超链接copy下来。虽然看起来简单,但是互联网上是时刻变化的,可能上一秒爬虫爬过的地方,下一秒就改变了。因此,爬虫在选择爬取链接时要有所取舍,是先爬取页面的首页,还是一条路黑到底,直接爬完。一般页面首页是比较重要的,先把就近的所有第一层超链接爬完再爬下一层就是所谓的“广度优先搜索”;而一个页面一直爬到底再爬下一个页面的是“深度优先搜索”。不过一般实际应用中还要考虑建立新连接需要TCP三次握手的时间,会结合“广度优先搜索”和“深度优先搜索”优点,协调好“广度”与“深度”之间的度。

除了广度与深度之间的度外,网络爬虫要做的工作还有就是页面的分析和URL的提取,并且还有记录好已经爬取过的页面,要做标记,避免重复爬取。