如何开发搜索引擎——爬虫（一）

爬虫抓取网页的过程可以抽象为数据结构里面的有向图，超链接就是图的边，网页内容是节点。那么抓取的遍历方式，也就是广度优先遍历或者是深度优先遍历。图当中比较复杂的是防止回路，实际抓取当中会由于网站设计的多样导致循环抓取，需要有一套完善的机制来防止回路。

网页内容的抓取也是一个复杂的问题，网页内部除了正文，还可能会有一些用户的联系信息、广告等其它数据。网页内容的抓取，微软最早设计了视觉抓取算法，就是模拟人通常观察一个网页会看的地方进行抓取。这个东西比较复杂，没有研究过。

简单点的解析方法，根据文字和HTML标签的比例进行抓取：通常，网页的正文都是连续的，并且其HTML标签不会很复杂，占比例较小，而其它部分，例如导航、广告等內容，通常HTML标签的数量会多余文字数量。可以对网页进行实验，拟合出一个近似的比例来进行抓取。

上面说的是通用的方法，还有一些情况，比如要去抓取今天NBA比赛的比分，这个通过上面的方式就很难了。一般去抓取这些内容的网页固定，比如都是去新浪体育去抓取，每个队的名字、比分都是在固定的HTML标签内，短时间内不会变化。这个时候就可以通过模板的方式进行抓取。

下面是一些当时学习的笔记，供大家参考：

• 为什么是图？ 在图论中，连通图基于连通的概念。在一个无向图G中，若从顶点v_i到顶点v_j有路径相连（当然从v_j到v_i也一定有路径），则称v_i和v_j是连通的。
• 用哪种遍历方式，深度还是广度遍历？ 网页的抓取策略可以分为深度优先、广度优先和最佳优先三种。深度优先在很多情况下会导致爬虫的陷入(trapped)问题，目前常见的是广度优先和最佳优先方法。广度优先搜索策略是指在抓取过程中，在完成当前层次的搜索后，才进行下一层次的搜索。最佳优先搜索策略按照一定的网页分析算法，预测候选URL与目标网页的相似度，或与主题的相关性，并选取评价最好的一个或几个URL进行抓取。它只访问经过网页分析算法预测为“有用”的网页。深度优先搜索策略从起始网页开始，选择一个URL进入，分析这个网页中的URL，选择一个再进入。重要网页通常距离种子较近，而过度深入抓取到的网页却价值很低。
• 遍历要防止回环，如果操作？ 欧拉回路：从图中一个节点出发，经过图中所有边一次且仅一次，最后回到出发点，当且仅当图中所有节点的度都是偶数。 用哈希表防止回环，一般网址较长，用MD5或16位的MD5作为作为key用于验证重复。为了防止爬虫意外中断的情况，访问记录应该保存在硬盘当中而不是内存里面。可以用redis解决。 布隆过滤器也可以用来防止回路。 用最多抓取次数防止回路（节流）。
• 根据url判定是相同页面还是根据内容判断是相同页面？ url别名。 内容指纹，通过MD5计算。
• html解析 提取超链接、提取缩略图、提取内容。 单行匹配s从头到尾匹配，.可以匹配到任意字符，包括换行符；多行匹配m以换行符为单位进行匹配，所以此时.无法匹配到换行符。
  • 匹配html：(?is)<.*?>。(?is)是模式修改符。意思是将后面的匹配模式修改成IGNORECASE和SINGLELINE，IGNORECASE就是忽略大小写，SINGLELINE就是规定特殊字符“.” 匹配任意的字符，包括换行符。默认情况下，特殊字符“.”不匹配换行符；
  • 匹配超链接：(?is)<a .*?</a>；
  • 匹配图片：(?is)<img .*?>；

参考文献

原文链接：如何开发搜索引擎——爬虫（一），转载请注明来源！