这两天看了下爬虫的技术，其中，爬虫有一项很重要的注意事项——过滤掉已经爬取过的URL地址。那么，这个过滤要怎么实现呢？参照之前的文章，或许我们可以维护两个队列，一个队列为保存已经访问过的URL地址，另一个队列为保存尚待爬取的URL地址，这样我们只需要把将要爬取URL地址去一访问的URL地址队列中查找，如果存在，那么就将这个URL地址入队到待爬取URL地址的队列中去。这样感觉很完美，但是，这样的时间开销对于大型爬虫程序是难以承受的，队列的查找再怎么快都需要 O(log2N)[ 折半查找、插值查找、斐波那契查找 ]；这个时候Hash表查找或许会是一个不错的方案，我们用一个数组来存储URL地址信息，如果这个URL爬取了，那么我们将这个URL地址利用Hash表存储，届时如果我们需要查找某一个URL地址是否被访问过，只要需要利用Hash查找，几乎可以在 O(1) 的时间开销内查找到结果，但是呢，这还是不够，就有了今天说要讲的数据结构—— Bloom Filter
Bloom Filter其实原理其实就是Hash散列表，只不过由一个Hash函数转为多个Hash函数，并且不需要存储实际URL地址数据。那么Bloom Filter是如何实现的呢？Bloom Filter是利用K个互不相关的Hash函数以及一个长度为m，默认值为0的位数组，通过将长度为l的数组s中的每一个元素映射到位数组中去，只要被映射到，那么位数组对应的数据就变为1，这就是Bloom Filter的实现，查找的时候，通过计算并查看对应位数组中的值是1还是0，如果都是1就代表元素存在，否则只要有一个0，就否定了该元素的存在性。
Bloom Filter 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| typedef unsigned int (*hash_func_p)(const char*);
typedef struct tagBloom {
unsigned int length;
char* buffer;
unsigned int func_n;
hash_func_p* func_p;
} Bloom;
Bloom* create_bloom(unsigned int length, unsigned int func_n, ...) {
Bloom* b = NULL;
va_list l;
unsigned int i = 0;
if(!(b = (Bloom*)malloc(sizeof(Bloom))))
return NULL;
if(!(b->buffer = (char*)malloc(sizeof(char) * length))) {
free(b);
return NULL;
}
if(!(b->func_p = (hash_func_p*)malloc(sizeof(hash_func_p) * func_n))) {
free(b->buffer);
free(b);
return NULL;
}
memset(b->buffer, 0, length * sizeof(char));
va_start(l, func_n);
for(i = 0; i < func_n; ++i) {
*(b->func_p + i) = va_arg(l, hash_func_p);
}
va_end(l);
b->length = length * sizeof(char);
b->func_n = func_n;
return b;
}
void destroy_bloom(Bloom *b) {
free(b->buffer);
free(b->func_p);
free(b);
b = NULL;
}
void set_bit(char *buf, unsigned int n) {
buf[n >> 3] |= 1 << (n & 7);
}
int get_bit(char *buf, unsigned int n) {
return (buf[n >> 3] & (1 << (n & 7)));
}
void add_record(Bloom *b, const char* str) {
unsigned int i = 0;
for( ; i < b->func_n; ++i) {
set_bit(b->buffer, (*(b->func_p + i))(str) % b->length);
}
}
int check_record(Bloom *b, const char* str) {
unsigned int i = 0;
for( ; i < b->func_n; ++i)
if(!get_bit(b->buffer, (*(b->func_p + i))(str) % b->length))
return 0;
return 1;
}
|
Hash函数的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include "hash.h"
unsigned int bkdr_hash(char *str) {
unsigned int seed = 13131;
unsigned int hash = 0;
while(*str)
hash = hash * seed + (*str++);
return (hash & 0x7fffffff);
}
unsigned int ap_hash(char *str) {
unsigned int hash = 0;
int i = 0;
while(*str) {
if((i & 1) == 0)
hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
else
hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
++i;
}
return (hash & 0x7fffffff);
}
unsigned int djb_hash(char *str) {
unsigned int hash = 5381;
while(*str)
hash += (hash << 5) + (*str++);
return (hash & 0x7fffffff);
}
|