位图算法缩小存储规模

搜索引擎系统中有一个很重要的部分是爬虫,而爬虫的实现上有一个关键点就是url去重,经典的去重方法是Bloom Filter。Bloom Filter利用了Hash和Bitmap来使时间和空间上的效率都有很大的提高。
当时想了一下位图算法,要真让我立刻实现它,还有点懵,于是顺手写了一段demo,测试了几个函数,分享下:
用char类型作为存储单元,一个char 8bits一般在各个平台上也不会变。
主要是搞清楚我这里设定的level和step的关系,用位运算解决set_bit和get_bit的逻辑就很容易了。
0000 0001 0010 0000
|…. ….|…. ….|
最左边的1是level 0,step 7
下一个1是level 1,step 2

#include <stdio.h>
#include <stdlib.h>

//set all to 0
void init_bitmap(char *bitmap, int num){
    for (int i = 0; i < (num/8+1); ++i){
        bitmap[i] = 0x0;
    }
}

void set_bit(char *bitmap, int n){
    int level = n/8;
    int step = n%8;
    bitmap[level] |= (0x1<<step);
}

int get_bit(char *bitmap, int n){
    int level = n/8;
    int step = n%8;
    int result = bitmap[level] & (0x1<<step);
    return result > 0? 1: 0;
}

//do not output in binary mode, just to test
void print_bitmap(char *bitmap, int num){
    int i = 0;
    for (i = 0; i < (num/8); ++i){
        printf("bitmap[%d]: %d\tfrom bit %d to %d.\n", i, bitmap[i], i*8, i*8+7);
    }
    printf("bitmap[%d]: %d\tfrom bit %d to %d.\n", i, bitmap[i], i*8, num);
}

int main(){
    int bitnum = 100;
    char *bitmap = (char *)malloc((bitnum/8+1)*sizeof(char));
    init_bitmap(bitmap, bitnum);
    set_bit(bitmap, 57);
    printf("get bit 56: %d\n", get_bit(bitmap, 56));
    printf("get bit 57: %d\n", get_bit(bitmap, 57));
    printf("get bit 58: %d\n", get_bit(bitmap, 58));
    print_bitmap(bitmap, bitnum);
    return 0;
}
Tags : ,

0 thoughts on “位图算法缩小存储规模”

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Click the right image To submit your comment: