BloomFilter/Bitset源码分析(PHP/C)

1.BloomFilter算法

有关BloomFilter的算法介绍和错误率分析参见wiki:

http://en.wikipedia.org/wiki/Bloom_filter

中文版的有一个:

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

2.Bitset介绍

PHP版BloomFilter引入了第三方位操作库bitset，所以使用前需安装bitset环境，下载地址是:

http://pecl.php.net/package/Bitset

 

BF库主要用到Bitset的4个方法：

• bitset_empty(int bits) - 分配位数组空间，并把每一位初始化为0，位数组长度为bitcount，其实就3行代码：

1. len = (bits+CHAR_BIT-1)/CHAR_BIT;
2. bitset_data = emalloc( len+1 );
3. memset( bitset_data, 0, len+1 );

• bitset_to_string(unsigned char *bitset_data) - 将位数组转换为字符串表示，代码就5行(- -!)

1. len *= CHAR_BIT; output_str = emalloc( len+1 ); output_str[ len ] = '\0';
2. for(count = 0; count < len; count++ )
3. output_str[count ] = ( (bitset_data[ count/CHAR_BIT ] >> (count % CHAR_BIT)) & 1 ) ? '1' : '0'; 

 

• bitset_incl(unsigned char *bitset_data, int bit) - 位数组位置bit(之前BF的hash后命中的位置)上的值置为1，实际操作就1行，不过位数组长度做成了动态的，所以还涉及erealloc之类的操作

1. bitset_data[ bit/CHAR_BIT ] |= 1 << (bit % CHAR_BIT);

• bitset_in(unsigned char *bitset_data, int bit) - 判断某个位置bit上的值是否为1，位操作语句比较精炼

1. if( bitset_data[ bit/CHAR_BIT ] & (1 << (bit % CHAR_BIT) ) )
2. RETURN_TRUE;

 

3.Linux下编译Bitset

下载bitset包，解压，进入目录安装，编译步骤如下

1. phpize (该命令是用来准备 PHP 扩展库的编译环境的)
2. ./configure
3. make
4. make install
5. 在php.ini添加extension = [编译出来的bitsit.so的位置]，重启WebServer即可

Windows下用一些工具根据config.w32编译，步骤比较复杂，俺也没搞懂，回头研究

4.BloomFilter源码分析

 
class BloomFilter
{
    public $field; // 位数组
    
    public $len; // 位数组长度
    
    // BF自己的hash函数由3个独立hash函数联立计算
    function hash($key)
    {
        // 生成3个正整数的数组，hexdec - 十六进制转十进制
        // 每个值都mod过$len
        return array(
            abs(hexdec(hash('crc32', 'm' . $key . 'a')) % $this -> len),
            abs(hexdec(hash('crc32', 'p' . $key . 'b')) % $this -> len),
            abs(hexdec(hash('crc32', 't' . $key . 'c')) % $this -> len)
            );
    } 
    // 定义初始化BF长度和位数组
    function __construct($len)
    {
        $this -> len = $len;
 
        $this -> field = bitset_empty($this -> len);
    } 
    // 通过载入BF文件进行初始化
    // BF文件可以通过file_put_contents('bloom',$bf->field)生成
    static function init($field)
    {
        $bf = new self(strlen(bitset_to_string($field)));
 
        $bf -> field = $field;
 
        return $bf;
    } 
    // 哈希一个条目
    function add($key)
    {
        foreach ($this -> hash($key) as $h) ?bitset_incl($this -> field, $h);
    } 
    // 查找条目是否在BF内
    function has($key)
    {
        foreach ($this -> hash($key) as $h) if (!bitset_in($this -> field, $h)) return false;
 
        return true;
    } 
    // 计算BF假阳性率
    // $k - hash函数个数
    // $numItems - 哈希的条目数
    function falsePositiveRate($numItems)
    {
        // 因为hash函数都是独立的，故对1做hash，形成的1值应该在3个不同位置
        // 所以$k=BF自己的hash函数(1)的值=独立的hash函数个数
        $k = count($this -> hash('1'));
 
        return pow((1 - pow((1-1 / $this -> len), $k * $numItems)), $k);
    } 
} 

5.资源连接

• 英文wiki：http://en.wikipedia.org/wiki/Bloom_filter
• PHP版BloomFilter实现：http://code.google.com/p/php-bloom-filter/
• PHP版Bitset包:http://pecl.php.net/package/Bitset
• 一个BloomFilter工作原理的Demo：http://la.ma.la/misc/js/bloomfilter/