基于WebView的网络爬虫

网络爬虫,又称网络蜘蛛,就是按照特定规则自动获取网站或者网页信息的程序。它是互联网数据挖掘的最基本组成部分,比较常见的应用就是搜索引擎。

将近一年以前,开始在业余时间编写一个自动下载图片的Android软件。到现在基本实现了网络爬虫部分。

在最近的测试中最多的几次花了十几个小时扫描了一个网站中全部的32.5万个网页URL,共扫描到23.5万张图片URL。软件运行环境是一台两百多¥的Android平板(七彩虹 E708 Q2),CPU是全志A31,内存768M。软件在上面那次扫描完毕后占有的内存在50M左右。

就测试结果来说,这个网络爬虫在时间和空间上都能够满足需要,并且其中用到的技术也稍微算得上复杂,编写过程中也遇到一些障碍和曲折。所以现在有必要做个总结。

这个网络爬虫的基本原理是:扫描并记录当前网页中未记录过的同站网页地址和图片地址,然后从网页地址记录中找一个未扫描过并且和当前网页地址最相近的网页,作为下一次要扫描的对象。以此类推,最终将完整扫描一个站点。

要实现一个网络爬虫,最基本的就是要能获取到指定网页的源代码并解析。在开始的时候考虑过使用一些开源的HTML解析库,比如jsoup。但是这类解析器大都只能解析HTML,如果需要爬取的网页不仅仅是HTML,比如有些网页的图片是用Javascript从网站上动态获取的。所以还需要解析Javascript,当然也有一些开源的Javascript引擎可以用,不过那样做就太复杂了。最直接了当的还是用WebView,因为它本身几乎就是一个浏览器,我们只需要告诉它网页URL,从网络上下载并解析网页源码就是它自己去完成了。

网络爬虫获取到网页源码后,就要从中得到它感兴趣的数据,在我实现的这个网络爬虫里也就是指向其他页面和目标图片资源的的URL。然而WebView并没有直接提供能够获取网页源码中这两类URL的接口,不过也不是说完全没有办法。根据Android WebView的使用中的说明,WebView提供了在Java层调用网页中Javascript层的接口,这样就可以用下面的代码获取到网页中指向其他页面和目标图片资源的的URL。

	private void scanPageWithJS()
	{
		spider.loadUrl("javascript:" + "var i;"
		        + "var img=document.getElementsByTagName(\"img\");"
		        + "var imgSrc=\"\";"
		        + "for(i=0; i<img.length; i++)"
		        + "{imgSrc+=(img[i].src+' ');}"
		        + "SpiderCrawl.recvImgUrl(imgSrc);"
		        + "var a=document.getElementsByTagName(\"a\");"
		        + "var aHref=\"\";"
		        + "for(i=0; i<a.length; i++)"
		        + "{aHref+=(a[i].href+' ');}"
		        + "SpiderCrawl.recvPageUrl(aHref);"
		        + "SpiderCrawl.onCurPageScaned();");
	}

在WebView加载完指定网页后,调用这个函数。其中spider就是一个WebView对象。loadUrl的参数字符串中,javascript后面跟的就是Javascript代码。其中SpiderCrawl是Java层提供给Javascript层的接口名称,在WebView初始化的时候通过spider.addJavascriptInterface(this, “SpiderCrawl”);添加的。

使用WebView还有一个比较麻烦问题,就是它加载并解析网页需要占用大量的Native堆内存。就上面那次扫描来说,不加载图片,每个网页大约占用100K,加载图片的话,内存消耗将更为可观。并且占用的内存并不会自动释放,即使销毁WebView对象,依然如此。这样的话,扫描的网页多到一定数目,应用占用的内存将会超出系统的极限,最终导致内存溢出,应用闪退。之前在我的测试机上,不加载图片,扫描的网页数目达到1万多的时候必然发生闪退。当时被这个问题困扰了一个多星期,最后才发现是这个原因。

Android WebView的使用中所讲的,这个问题可能是Android系统本身的BUG,目前较好的解决方案就是把WebView放到单独的进程中,然后到WebView占用内存较大或者系统内存紧张时重启WebView所在的进程。这样就能强制释放掉WebView占用的内存。

但是这样做还有一个问题,就是WebView进程必须保存扫描到的网页和图片URL,否则进程重启后,这些URL也会一并被清除。最开始时打算用Android内置的Sqlite数据库,但是数据库归根到底就是磁盘(Android系统大多数情况下存储介质是Flash,这里说磁盘只是为了方便)文件,读写操作最终都是磁盘IO。当数据量较大读写较频繁时,数据库有可能成为瓶颈。其实采用数据库的方案我并没有测试过,只是感觉不如纯内存操作的性能好。更重要的原因是希望借助这个机会,自己去实现一些大数据量操作所需要的算法。所以最终采用共享内存来做扫描数据存储。

所谓共享内存就是在不同进程间共享相同一段或者多段物理内存。具体的操作方式是:进程A申请一段共享内存,并得到一个指代这段共享内存的文件描述符。然后使用进程间通信的方式把这个文件描述符传给进程B。进程B使用文件描述符映射共享内存到自己的虚拟内存空间,然后就可直接访问这段共享内存。由于实际访问的是同一段物理内存,所以共享内存一般是用作对速度敏感的进程间通信。不过因为只有当所有映射了这段共享内存的进程都被关闭时,这段内存才会被操作系统回收,所以可以使用一个进程用来向系统申请并一直保有共享内存,然后WebView进程映射共享内存并用来存储URL,WebView进程重启后再从共享内存中恢复这些URL并继续扫描。

在这个网络爬虫的实现中,为了不至于频繁进行共享内存的创建和映射(需要进程间通信),不可能每条URL都各去申请一段共享内存。所以每次申请1MB的内存块并将起始地址放到一个指针数组中。每新增一个URL时,直接从内存块中顺序分配一段合适大小的内存段用来存储这个新增URL,到内存块被用完之后,再新申请一块1MB的共享内存。

这个网络爬虫扫描一个网页,其实就是扫描这个网页上的每一个同站网页URL和图片URL,并判断扫描到的URL是新的还是已经存储了的。简而言之就是判断一个字符串是否存在于一个字符串集合。最直接的方法是直接拿这个字符串跟字符串集合里的每一个字符串用诸如strcmp的方式一个一个字符地对比。这种方式的扫描一个URL的算法时间复杂度就是O(SN),其中S是单个URL的平均长度,N是已存储的URL个数。所以这种最容易想到的方法只能用于数据量较小的情况,当存储的URL数目大到几万几十万甚至上百万时再这样逐字符对比就显得比较笨了。假设已存储了10万URL,平均每条URL长度100字节,那么处理一个10个待扫描URL的网页就需要对比1亿次。这还是很简单的网页,一般稍大一些的网页都有上百个URL。

所以凡是对性能有点追求的网络爬虫算法都不会用上面这种方式。绝大部分搜索引擎使用的方式是记录每条URL的散列值,然后直接对比散列值而不是URL本身。所谓散列值就是使用散列函数把源数据转换为一个数值。如果散列值不同那么源数据一定不同;由于散列函数是把长度较长的数据转换为长度较短的数值,所以散列值相同而是源数据不一定相同,即有可能发生碰撞,设计良好的散列函数计算出的散列值应该尽量减小散列值发生碰撞的概率。

MD5(Message Digest Algorithm 5)是目前常用的散列函数之一。虽然自从山东大学的王小云教授成功破解MD5之后,在安全领域,准确地说是数字签名领域中,MD5正在被SHA256取代。但是这个破解的是MD5的抗逆向性,也就是逆向计算出具有相同散列值的数据,即伪造数据。MD5的散列性能依然很好,所以此处使用MD5作为散列函数依然可行。

使用MD5散列值之后,扫描一个URL的时间复杂度变为O(N),相比较最初的O(SN)已经降低了很多,不过还算不上质变。因为依然还要把全部已存储URL的散列值都对比一遍才能确定已存储URL中不存在指定URL。之前做过这种方式的测试,URL存储在一个链表中,搜索一个URL时就遍历链表。当已存储URL数达到10万之后,扫描一个网页中所有URL所需的时间多达10s左右,这显然是无法接受的。所以此处不能直接使用链表这种数据结构。

在目标集合中确定是否存在一个元素最快的算法是哈希表。它的时间复杂度是O(1),也就是不管数据集有多大,搜索一次所需的步骤是一样的。因为它直接把元素键值作为元素存储地址,所以搜索一个元素时,只需要通过元素键值直接(或者做一下必要的转换)寻址就行。但是哈希表只能用于数据集大小固定,并且在一开始就必须分配全部数据集所需的空间。扫描网站时,无法事先确定到底有多少URL,只能动态添加URL。所以也不能使用哈希表。

因而需要一种数据结构能够同时满足如下两个条件:

1.搜索元素不必遍历整个数据集。

2.能够动态添加元素。

二叉树就能同时满足上面两个条件。二叉树的每个元素(或者说节点)至少有三个参数:父节点、左子节点、右子节点。父节点为空的节点是根节点,子节点为空的节点是叶节点。每个节点的键值小于左子节点键值,大于右子节点键值。所以搜索指定键值时只需要沿着根节点一路比较下去,大向左,小向右,止于相等的节点或者叶节点。如果止于叶节点时也没能找到相等的节点,则说明二叉树中没有这个键值。二叉树相较链表的优势是每次比较都能排除一部分而不是一个节点。

构建二叉树时,最好的情况是对每个节点而言,其左右子树高度差最大为1,即完全平衡。最坏的情况就是整个二叉树只有一条路经,根节点到叶节点是一个由大到小或者由小到大的序列,即整个二叉树变成了一个链表,这样从根节点开始搜索时效率就跟链表一样了。所以构建二叉树时应该尽量使二叉树平衡。

红黑树是一种常用的自平衡二叉树。它在二叉树三个参数的基础上增加一个参数用以表示节点的颜色。另外红黑树必须满足以下条件:

1.节点颜色为红或者黑。

2.根节点颜色为黑。

3.黑色节点的子节点可以是红或黑色节点,红色节点的子节点必须是黑色节点。

4.从根节点到每个叶节点的路径上,黑色节点的数目相同。

红黑树在添加或者删除节点时需要通过旋转(不超过三次)和变色操作来满足上面的约束条件。红黑树从根节点到每个叶节点的路径长度最大相差一倍,接近平衡。搜索红黑树的时间复杂度是O(lg(n)),在数据量较大时,相比较链表的处理速度提升相当明显。

在本文开始时提到的那次测试中一共32.5万个URL节点的红黑树高度,即从根节点到叶节点最长路径的节点数,只有22。也就是说确定一个URL是否已存储,最多只需要比较22次。而如果使用链表,最多需要比较32.5万次。使用红黑树后,扫描(不包括下载)一个网页所需的时间都小于100ms。所以能够满足快速扫描的需要。

扫描完一个网页后,就要确定下一个要扫描的网页。一般图片或者新闻网站中同一篇文章里的图片都是同一主题的,同一主题图片在扫描时应该被放到一起。如果一篇文章就在一个网页里,这倒好办。不过大部分较长一点的文章都会被分配到不同的页面里用诸如上一页、下一页的链接来导航。并且同属于一篇文章的页面,URL都很相似。URL末尾处加上1、2、3之类的序号来区分,所以可以通过比较页面URL的相似度来判断是否同属一篇文章。

具体的操作方式是新增的页面URL放入红黑树的同时加入一个双向链表中,扫描完一个页面后,以这个页面为中心沿链表分别向前、向后最多比较5000个URL,以与当前页面URL差别最小的作为下次扫描的URL。然后把当前URL从链表中删除。

也许这种方式并不是最好的,还有改进的空间。不过目前测试来看,像这样计算出一个待扫描页面URL的时间最多不超过100ms。所以尚能接受,更好的方式留待以后再探索了。

如下即存储URL所用的数据结构:

#pragma pack(1)
typedef struct
{
	u32 poolPtr;
	u32 offset;
} urlNodeRelativeAddr;

typedef struct
{
	u64 md5_64;
	u8 pad;
	u8 color;
	u16 len;
	urlNodeRelativeAddr nextNodeAddr;
	urlNodeRelativeAddr prevNodeAddr;

	urlNodeRelativeAddr left;
	urlNodeRelativeAddr right;
	urlNodeRelativeAddr parent;
} nodePara;

typedef struct
{
	nodePara para;
	char url[MAX_SIZE_PER_URL];
} urlNode;

typedef struct
{
	urlNodeRelativeAddr head;
	urlNodeRelativeAddr tail;

	urlNodeRelativeAddr root;

	urlNodeRelativeAddr curNode;
	u32 processed;
	u32 len;
	u32 height;
} urlTree;



typedef struct
{
	urlTree pageUrlTree;
	urlTree imgUrlTree;
	u32 urlPoolNum;
} t_spiderPara;


typedef struct memPool
{
	u8 mem[SIZE_PER_URLPOOL];
	u32 idleMemPtr;
} t_urlPool;
#pragma pack()

如上所示,这些核心的数据存储不是用Java而是C实现的,主要是因为目前对Java中那些数据结构的类(实在太多)还不甚了解,另外也不认为Java能达到C的数据存储和处理效率。

项目源码:https://github.com/gk969/UltimateImgSpider

基于WebView的网络爬虫》上有3条评论

发表评论

电子邮件地址不会被公开。

*