26 December 2014
想自学一下搜索引擎,记录一下目前了解到的东西,也和大家分享。

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

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

简单点的解析方法,根据文字和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 .*?>;

######参考文献

原文链接:如何开发搜索引擎——爬虫(一),转载请注明来源!

EOF

欢迎加微信交流与吐槽



本站总访问量次; 本站访客数人次; 本文总阅读量次;