欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

爬虫url查重方式总结

程序员文章站 2022-07-14 08:37:47
...

最近做爬虫,在check阶段最后这几天总是遇到内存溢出的问题,分析了一下java堆,发现就是过多的url string存储导致的。今天就总结下url查重的几种方法。

看到网上也有些文章讨论了这个问题,但会略有不同,希望能用两天晚上内存溢出的经验帮助到做爬虫的同志们。当然还要说明一下,这里的爬虫主要是单站的定制爬虫,全网爬虫不是主要考虑的范围。

 

首先,罗列一下所有的方法:

1. HashSet存URL

2. 压缩字符串存入HashSet

3. 改写的字典树

4. Bloom Filter

5. BerkeleyDB

6. NormalDB

 

1. HashSet存URL

这是最简单最直观的方式了,但看一下我直接用webmaigc框架中的文件cache调度器调度时候吃到得麻烦也许就比较直观了。这是仅仅存储了很小一部分数据后的情况。

 

2. 压缩字符串存入HashSet

既然太占空间,压缩每个的长度是个比较好的办法。通过md5单向编码url值,可以将每个url的大小都控制在16byte。这种方法没有实践,但如果较小的站点改方法可以很快的修改代码并有不错的效果,因为实际的url存储起来是很占内存空间的。

 

3. 改写的字典树

当时遇到问题后走的不同的思考路线,对于单站而言,公用前缀是非常多的而且长的,因此就希望利用这种特性,字典树肯定是最好的选择。通过屏蔽特殊符号的方式使用字典树可以得到不错的效果,目前测试过程中10w数量级的网页在普通机器不存在任何问题。附上具体代码:

 

/**
 * URL查找树,去除掉非字符和数字的符号,构造字典树
 * 
 * @author Jason wu
 */

public class URLTrieTree {
	
	//单词查找树根节点,根节点为一个空的节点 
	private Vertex root = new Vertex();

	//单词查找树的节点(内部类)
	private class Vertex {
		//单词出现次数统计 
		int wordCount;
		//以某个前缀开头的单词,它的出现次数 
        int prefixCount;  
		//子节点用数组表示
		Vertex[] vertexs = null;

		/**
		 * 树节点的构造函数
		 */
		public Vertex() {
			wordCount = 0;
			prefixCount = 0;
		}
	}

	/**
	 * 单词查找树构造函数
	 */
	public URLTrieTree() {}

	/**
	 * 向单词查找树添加一个新单词
	 * 
	 * @param word
	 *            单词
	 */
	public synchronized void addWord(String word) {
		if(countWord(word)<=0)
			addWord(root, word.toLowerCase());
	}

	/**
	 * 向单词查找树添加一个新单词
	 * 
	 * @param root 单词查找树节点
	 * @param word 单词
	 */
	private void addWord(Vertex vertex, String word) {
		if (word.length() == 0) {
			vertex.wordCount++;
		} else if (word.length() > 0) {
			int index = -1, i=0;
			try{
				for(;(index = getIndex(word.charAt(i)))==-1;i++){}
			}catch(IndexOutOfBoundsException e){
				vertex.wordCount++;
				return;
			}
			
			if(vertex.vertexs == null)
				vertex.vertexs = new Vertex[26+10];
			if (null == vertex.vertexs[index]) {
				vertex.vertexs[index] = new Vertex();
			}
			vertex.prefixCount++;
			addWord(vertex.vertexs[index], word.substring(i+1));
		}
	}

	/**
	 * 统计某个单词出现次数
	 * 
	 * @param word 单词
	 * @return 出现次数
	 */
	public synchronized int countWord(String word) {
		return countWord(root, word.toLowerCase());
	}

	/**
	 * 统计某个单词出现次数
	 * 
	 * @param root 单词查找树节点
	 * @param word 单词
	 * @return 出现次数
	 */
	private int countWord(Vertex vertex, String word) {
		if (word.length() == 0) {
			return vertex.wordCount;
		} else {
			int index = -1, i=0;
			try{
				for(;(index = getIndex(word.charAt(i)))==-1;i++){}
			}catch(IndexOutOfBoundsException e){
				return vertex.wordCount;
			}
			if (vertex.vertexs == null
					|| null == vertex.vertexs[index]) {
				return 0;
			} else {
				return countWord(vertex.vertexs[index], word.substring(i+1));
			}
		}
	}
	
	/** 
     * 调用深度递归算法得到所有单词,用于测试
     * @return 单词集合 
     */  
    private List<String> listAllWords() {  
        List<String> allWords = new ArrayList<String>();  
        return depthSearchWords(allWords, root, "");  
    }  
  
    /** 
     * 递归生成所有单词 
     * @param allWords 单词集合 
     * @param vertex 单词查找树的节点 
     * @param wordSegment 单词片段 
     * @return 单词集合 
     */   
    private List<String> depthSearchWords(List<String> allWords, Vertex vertex,  
            String wordSegment) {  
    	if(vertex.vertexs == null)
    		return allWords;
    	
        Vertex[] vertexs = vertex.vertexs;  
        for (int i = 0; i < vertexs.length; i++) {  
            if (null != vertexs[i]) {  
                if (vertexs[i].wordCount > 0) {  
                    allWords.add(wordSegment + buildChar(i));  
                    if(vertexs[i].prefixCount > 0){  
                        depthSearchWords(allWords, vertexs[i], wordSegment + buildChar(i));  
                    }  
                } else {  
                    depthSearchWords(allWords, vertexs[i], wordSegment + buildChar(i));  
                }  
            }  
        }  
        return allWords;  
    }  
    
    private int getIndex(char c){
		int index = -1;
		if(c>='a' && c<='z')
			index = c - 'a';
		else if(c>='0' && c<='9')
			index = c - '0' + 26;
		return index;	
	}
    
    /**
     * 返回对应的char,需要保证index正确
     * @param index
     * @return
     */
    private char buildChar(int index){
    	if(index>=0 && index<26){
    		return (char)(index + 'a');
    	}else{
    		return (char)(index-26 + '0');
    	}
    }
}

 

 

这是参考网上的代码的实现,有个需要注意的地方就是vertexs数组一定要在使用的时候初始化,不然就像我刚改动完这个代码之后第二天发现只比方法1多出几倍的网页。

 

4. Bloom Filter

第一次接触Bloom Filter,但感觉到了它的美妙,今天跑半天的网页量占据的内存空间就足够支持整站的存储,但需要提前预估和计算m、n、k的大小来解决错误率问题,上一中字典树的方式只是理论上存在错误的可能,但实际使用过程中没有这种问题出现。

具体原理和参数计算这有篇很好的文章

http://blog.csdn.net/jiaomeng/article/details/1495500

既然是学习的,具体实现肯定仍旧是参考网上的代码。但是通过Java自带的BitSet管理位图就会遇到问题了,因为boolean占用一个bit仅仅是java虚拟机标准里面的规定,hotspot的boolean是占用一个字节的,也就是白白浪费了很多字节,当申请的空间较大的时候这是很严重的浪费。因此需要自己实现一个Bitmap,这也比较简单,另外不同hash可以通过简单的种子不同来区分。

附上代码

 

public class BloomFilter{
	
	// BitMap 的大小,如果利用Java自带的BitSet则由于boolean在hotspot虚拟机下是占用一个字节的原因无法设置很大。
	private static final int DEFAULT_SIZE = 1<<28; 
	
	// 不同哈希函数的种子,一般应取质数 
	private static final int[] seeds = new int[] { 
		2, 5, 7, 11, 13, 23, 31, 37, 41, 47, 61, 71, 89};
	
	private BitMap bits = new BitMap(DEFAULT_SIZE);
	
	// 哈希函数对象 
	private SimpleHash[] func =new SimpleHash[seeds.length];
	
	public BloomFilter(){
		for (int i =0; i < seeds.length; i++){
			func[i] =new SimpleHash(DEFAULT_SIZE, seeds[i]);
		}
	}

	/**
	 * 将字符串标记到bits中
	 * @param value
	 */
	public synchronized void add(String value){
		for (SimpleHash f : func){
			bits.set(f.hash(value));
		}
	}

	/**
	 * 判断字符串是否已经被bits标记
	 * @param value
	 * @return
	 */
	public synchronized boolean contains(String value){
		if (value == null){
			return false;
		}
		boolean ret =true;
		for (SimpleHash f : func){
			ret = ret && bits.get(f.hash(value))==0?false:true;
		}
		return ret;
	}

	/**
	 * 哈希函数类 
	 * @author admin
	 */
	public static class SimpleHash {
		private int cap;
		private int seed;

		public SimpleHash(int cap, int seed){
			this.cap = cap;
			this.seed = seed;
		}

		/**
		 * hash函数,采用简单的加权和hash
		 * @param value
		 * @return
		 */
		public int hash(String value){
			int result =0;
			int len = value.length();
			for (int i =0; i < len; i++){
				result = seed * result + value.charAt(i);
			}
			return (cap -1) & result;
		}
	}
	
	public static class BitMap{
		private final int INT_BITS = 32;
		private final int SHIFT = 5 ;// 2^5=32 
		private final int MASK = 0x1f; // 2^5=32
		
		int bitmap[];
		
		public BitMap(int size){
			bitmap = new int[size/INT_BITS];
		}
		
		/**
		 * 设置第i位
		 * i >> SHIFT 相当于 i / (2 ^ SHIFT),
		 * i&MASK相当于mod操作 m mod n 运算
		 * @param i
		 */
		void set(int i) {
			bitmap[i >> SHIFT] |= 1 << (i & MASK);
		}
		
		/**
		 * 获取第i位
		 * @param i
		 * @return
		 */
		int get(int i) {
			return bitmap[i >> SHIFT] & (1 << (i & MASK));
		}
		
		/**
		 * 清除第i位
		 * @param i
		 * @return
		 */
		int clear(int i) {
			return bitmap[i >> SHIFT] & ~(1 << (i & MASK));
		}
	}
}

 

 

5. BerkeleyDB

Heritrix的实现方式,这里就不多说了,因为BerkeleyDB支持Key-value的方式,而且与程序在同一进程空间执行,因此是个不错的选择。但是相比于之前的而言,将查重工作放在磁盘上做当然是在内存不够使用的时候才采用,注:对于JD、Amazon这样的电商网站规模是不需要采用这种方式的,所以预计单站爬虫查重操作不需要移到外存。另外如果有并行需求,只要量不大,在服务器上3、4两种方法一般都是可以满足的。

6. DB

普通数据库就不细了,单站可以采取sqlite加快查重速度,但如果避免数据重复读写等采用DB也是可选的方案,但是时间开销确实增加较多。

 

就不做总结陈词了,以上这些方案足够普通的爬虫需要了,但像搜索引擎这种肯定还有很多改善的方案。