精华内容
下载资源
问答
  • Bloom Filter 和 Counting Bloom FilterBloom-FilterBit-map的升级版本,至少从我了解这个算法的顺序上来说。Bloom-Filter原理大致是吧所需插入的元素用k个Hash函数散列到一个以bit为单位的Hash表上。只支持插入和...

    Bloom Filter 和 Counting Bloom Filter

    Bloom-Filter是Bit-map的升级版本,至少从我了解这个算法的顺序上来说。Bloom-Filter原理大致是吧所需插入的元素用k个Hash函数散列到一个以bit为单位的Hash表上。只支持插入和查询,并且有false positive的可能。

    Counting-Bloom-Filter又是BF的升级版,增加了几个bit用于计数,并且支持删除功能,同样有false positive的可能。

    Variable-Increment Counting Bloom Filter

    在2012年的Infocom上有一篇对Counting-Bloom-Filter算法的改进,
    The Variable-Increment Counting Bloom Filter

    其中的第二种改进算法大致是这样的。

    用一个大小为数个bit的count数组替代CBF中的2个数组,count数组中所存的元素以及存放的位置由两组Hash函数确定。

    H={h1,h2,...hn},G={g1,g2,...gn}

    hi(x)size of Hash table gi(x)DL ,其中 DL=[L,2L1], L=2i

    插入

    最初的内存状态是这样的:

    0000 0000 0000 0000...0000 0000

    假设插入一个元素 x
    h1(x)=0 h2(x)=3 g1(x)=3 g2(x)=2  DL={2,3}

    插入元素后的内存状态:
    0011 0000 0000 0010...0000 0000

    再插入一个元素 y
    h1(y)=0 h2(y)=1 g1(y)=2 g2(y)=2  DL={2,3}

    插入元素后的内存状态:
    0101 0010 0000 0010...0000 0000

    查询

    假设我们要查询 y 是否在表内。首先,确定表内的位置即,h1(y)=0 h2(y)=1

    •  ValueOf( h2( y ) )[L,2L1] g2( y )=ValueOf( h2( y ) ) ,如若不然,则 y 就不再表内。

    •  ValueOf( h1( y ) )[2L,3L1] ValueOf( h2( y ) )g2( y )<L ,如若不然,则 y 就不再表内。

    • 最后一种情况,对于一个元素z  ValueOf( h1( z ) )[3L,) 则无法确定是不是在表内,就可能会出现false poitive

    查询

    删除的思路大概就是插入的反操作。代码还没有写出来。

    代码

    class memoryCountBloomFilter
    {
    public:
        memoryCountBloomFilter ():table(nullptr) 
        {
            initArr();
        }
        ~memoryCountBloomFilter () 
        {
            if (table != nullptr)
                delete[] table;
        }
        void insertElem (int elem);
        bool queryElem (int elem);
        typedef unsigned short int ctype;
        std::string ptrMemState ();
    private:
        static const unsigned int tableSize = 8;
        static const unsigned int L = 16;
        ctype* table;
        bool initArr();
        ctype getCount (int elem);
        /*
            用于确定第一个位置
        */
        unsigned int h1 (int elem);
        /*
            用于确定第二个位置
        */
        unsigned int h2 (int elem);
        /*
            第一个位置的值
        */
        ctype g1 (int elem);
        /*
            第二个位置的值
        */
        ctype g2 (int elem);
    };
    
    inline memoryCountBloomFilter::ctype memoryCountBloomFilter::getCount (int elem)
    {
        return elem % 2 + 2;
    }
    
    bool memoryCountBloomFilter::initArr()
    {
        table = new ctype[tableSize];
        if (table != nullptr)
        {
            memset(table, 0, tableSize * sizeof(ctype));
            return true;
        }
        else
        {
            return false;
        }
    }
    
    unsigned int memoryCountBloomFilter::h1 (int elem)
    {
        return elem % tableSize;
    }
    
    unsigned int memoryCountBloomFilter::h2 (int elem)
    {
        elem >>= 5;
        unsigned int mark = 7;  // 0000 0111
        return mark & elem;
    }
    
    memoryCountBloomFilter::ctype memoryCountBloomFilter::g1 (int elem)
    {
        return elem % 15 + 16;
    }
    
    memoryCountBloomFilter::ctype memoryCountBloomFilter::g2 (int elem)
    {
        unsigned int mark = 15;
        elem >>= 5;
        mark &= elem;
        return mark + 16;
    }
    
    void memoryCountBloomFilter::insertElem (int elem)
    {
        table[h1(elem)] += g1(elem);
        int t1 = h1(elem), t2 = g1(elem);
        table[h2(elem)] += g2(elem);
        int t3 = h2(elem), t4 = g2(elem);
    }
    
    bool memoryCountBloomFilter::queryElem (int elem)
    {
        unsigned int p1 = table[h1(elem)], p2 = table[h2(elem)];
        if (p1 == 0 || p2 == 0)
            return false;
        if (L <= p1 && p1 <= (2 * L - 1))
            if (g1(elem) == p1)
                goto next;
            else
                return false;
        if ((2 * L) <= p1 && p1 <= (3 * L - 1))
            if (L <= g1(elem) && g1(elem) <= (p1 - L))
                goto next;
            else
                return false;
        if (p1 >= 3 * L)
            goto next;
        return false;
    next:
        if (L <= p2 && p2 <= (2 * L - 1))
            if (g2(elem) == p2)
                return true;
            else
                return false;
        if ((2 * L) <= p2 && p2 <= (3 * L - 1))
            if (L <= g2(elem) && g2(elem) <= (p2 - L))
                return true;
            else
                return false;
        if (p2 >= 3 * L)
            return true;
        return false;
    }
    
    std::string memoryCountBloomFilter::ptrMemState ()
    {
        std::string ret;
        for (size_t i = 0; i < tableSize; ++i)
        {
            ret += bitsInMemory(table[i]);
            ret += '\n';
        }
        return ret;
    }
    展开全文
  • 明白了哈希的原理,bit-map就好说了。 bit-map的核心思想是:所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。每一个bit空间都是存储单元,而不像整型数据,即便是int a =1,仍要占用32...

    明白了哈希的原理,bit-map就好说了。
    bit-map的核心思想是:所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。每一个bit空间都是存储单元,而不像整型数据,即便是int a =1,仍要占用32个字节的空间,当数据量很大时,就会造成严重的空间浪费。由此可见,bit-map可以极大的节省空间,但bit-map只能用来进行一些简单的操作,比如,查询元素是否存在于数据中,数据去重,数据排序等。值得注意的是,数字型数据更适合bit-map,如果是文本记录或者字符串,很难都被哈希函数映射为整型数字。

    排序
    首先bit-map初始化为全零,通过一个哈希函数,分别将数据映射到bit-map的某一位置,将该位置处数据置1。看一个《编程珠玑》上的例子,元素为{4,7,2,5,3}用bit-map来存储,元素4存储的位置如下:
    这里写图片描述
    依次存储:
    这里写图片描述
    可以看到这里映射选取的比较简单,同时依次遍历bit-map还完成了排序。

    查询元素是否在数据集合中的问题
    首先同样哈希函数依次将数据映射标记到bit-map中,查询元素映射到某一位置已经标记为1,判定为存在。当然bit-map这样会出现误判,错误率也很高,效果并不理想,这就是bit-map扩展为bloom filter的原因。因此查询元素是否在数据集合中的问题,应该用布隆过滤器来解决(见下文)。

    数据去重问题
    例1:)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。
    可以理解为从0-99999999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==12MBytes,这样,就用了小小的12M左右的内存表示了所有的8位数的电话。
    同样存储大数据的方法用于以下例子:
    2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。大约需要300M左右。这里为了查重,使用两个bit值来表示三种状态,不存在,存在,重复分别标记为00,01,11。将数据依次映射到此bit-map中,最后遍历输出bit-map的key值即可。

    Bloom Filter
    布隆过滤器可以看成是对bit-map的扩展,它采用K个哈希函数进行映射,这样减少误判,因为每一个元素需要映射K个位置均已标记为1,才说明了这个元素存在于数据集合中。减少误判,并不能做到完全没有。在我们的数据结构或者算法中,往往是牺牲空间得到效率的提升,或者降低效率提高空间的利用率。而布隆过滤器给出了一个新的方法,就是引入了误判率,节省空间,并不降低效率。当数据量很大时,布隆过滤器的效率并不会因此降低,但误判率会提高。因此选取哈希函数的个数k,位数组的大小m以及字符串的量n很重要。
    官方文档中给出一个计算公式:K=ln2*(m/n)=0.7(m/n),此时的误判率最低。
    以下是使用三个哈希函数的布隆滤波器示意图
    这里写图片描述
    判重问题: 将查询的元素经过三个哈希函数映射后,如果三个标记位均为1,说明此元素在数据集合中存在(上面提到,是存在误判的)。

    展开全文
  • Bloom filter

    2019-07-25 22:02:58
    Bloom filter是一种空间效率很高的数据索引结构,它利用bit数组很简洁地表示一个集合,Bloom filter 的主要用来判断某个或某些元素是否属于某个集合,在判断是否属于某个集合时,有可能会把不属于这个集合的元素误...

    1. 概念

           Bloom filter是一种空间效率很高的数据索引结构,它利用bit数组很简洁地表示一个集合,Bloom filter 的主要用来判断某个或某些元素是否属于某个集合,在判断是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false  positive)。因此,Bloom filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom filter可以通过极少的错误换取存储空间的极大节省。

    2. 原理

           结合下图具体来看Bloom filter是如何通过使用位数组表示集合。

                                                               

    :初始状态,此时Bloom filter是一个新建的包含m位的位数组,每一位都置为0。

    :插入状态,为了将包含n个元素的集合S={x1, x2,…,xn}和Bloom filter建立关系,Bloom filter使用k个相互独立的哈希函数(Hash Function)(如图所示,使用了3个函数),k个哈希函数分别将集合中的每个元素映射到{1,…,m}的范围中(例如,对任意一个元素x,第i个哈希函数映射的位置Hashi(x)就会被置为1)。

    :查询状态,通过上述步骤,我们已将集合S={x1, x2,…,xn}和Bloom filter建立起映射关系,接下来就通过查询来判断某个元素是否属于集合S。如上图③所示,我们对待查询的元素y通过k次哈希函数找寻对应的k个bit位,如果k个位置都是1,那么我们就认为y是集合中的元素,否则就认为y不是集合中的元素(上图③中结果所示y1不属于当前集合,y2属于当前集合)。

    3. 与生俱来的错误率

           错误率(false positive rate):在判定某元素是否属于当前集合时,其结果有两种:属于或者不属于。对于“不属于”的判定结果,我们可以保证其正确性(false negative rate=0);但是对于“属于”的判定结果,我们无法保证其正确性(false positive rate\neq0)。

           错误率形成原因:哈希函数的冲突所致,即属于当前集合的元素a和不属于当前集合的元素通过哈希函数所共享的bit位(即图③中的y2的判定结果是属于当前集合的,但是也可能是误判)。

           量化错误率:量化错误率是一种估计,属于概率计算,用来评估当前Bloom filter 的质量。首先,Bloom filter具有m的bit位,k个hash函数,带插入集合有n个元素。然后是插入过程中产生错误率,即计算任意一个元素可能被Bloom filter误判的概率。

    (1)m位数组中某特定bit位,当一个元素经一次hash处理没有被置为1的概率为(1-1/m),则n个元素经过k次hash函数处理后仍然未被置位的概率:

                                                                                         

    (2)此特定bit位在n个元素经过k个hash函数处理后被置位为1的概率:

                                                                                     

    (3)经过插入阶段,我们可知,某一特定bit位被置为1的概率如上式所示,则在查询阶段,某一个待查询的元素的k个bit位均为1,可判定该元素在当前集合中,但是同时也存在误判的概率(错误率),且误判的概率为:

                                                                                     

    (4)由极限准则可知,可将误判率公式简化为:

                                       

    (5)求误判率最小值的参数,并且从上式可以看出,当m增大或者n减小时,都会使误判率更小:

                                                               

              即当k=ln2(m/n)时,此时的误判率最低。此时的Bloom filter的质量最好,优化后的误判率P(error)为:

                                                           

    4. 存在的问题及解决方法

           问题:Bloom filter作为一种数据索引结构,仅支持插入和查询,不支持删除操作。原因:仍旧是Bloom filter中hash的冲突(有hash函数的地方就一定有冲突的存在)。

           解决方法:目前解决Bloom filter删除问题有很多种方法,比如Bloom filter[1]的变种Counting Bloom filter[2]、d-left Counting Bloom filter[3],还有cuckoo filter[4]等,所列的这三项工作比较经典(参考文献见文章结尾),当然也有其它的工作,这里就不再进行延申了。

    5. Bloom filter与其变体的性能对比

           Bloom filter与其变体的性能对比:空间开销、查询性能、是否支持删除。

                                        

    6. Bloom filter的用法及应用场景

            用法:在应用Bloom filter时首先要确定两个参数,(1)即用户决定建立映射关系的元素集合的个数n;(2)用户希望的误判率大小P(error)。由上面我们第三步分析的结果可推导出此时Bloom filter所需bit的大小m:

                                                                  

    再由满足最小误判率的条件可推导出此时所需的hash函数的个数k:

                                                                                            

    以上,为一个优化的Bloom filter的完整求解过程。

            应用场景

            Bloom filter属于existence index,作为一种空间高效的数据索引结构,经常被数据库用于测试元素是否是某集合的成员。通常用于测试某些cold storage(例如disk)中是否存在某个元素,以减少cold storage的I/O次数。这里使用Bloom filter来提高查询性能,可以过滤掉一些“不必要的查询操作”,因为cold storage的一次I/O操作的性能开销非常大,(例如disk的一次I/O操作,包括寻道时间、旋转延迟和数据传输等三部分)。

     

    参考文献:

    [1] B. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors", http://www.dragonwins.com/domains/getteched/bbc/literature/Bloom70.pdf,  1970.

    [2] L. Fan, et. al, "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol", http://pages.cs.wisc.edu/~jussara/papers/00ton.pdf, Sep, 1998.

    [3] M. Mitzenmacher , et. al, "An Improved Construction for Counting Bloom Filters", http://www.eecs.harvard.edu/~michaelm/postscripts/esa2006b.pdf, 2006.

    [4] Bin Fan et. al, " Cuckoo Filter: Practically Better Than Bloom",                            https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf, Dec, 2014.

    展开全文
  • BloomFilter

    2018-02-27 14:40:27
    BloomFilter是通过“位(bit)”来保存元素的,是一个初始值全为0的位数组; 添加元素:使用K个Hash函数得到元素的K个Hash值,以这K个Hash值作为数组的索引,把位数组中位于该索引的值设为1。 查找元素:与添加...

    BloomFilter

    定义:二进制向量数据结构,具有很好的空间和时间效率,用来检测一个元素是否为集合的一个成员,一般使用BloomFilter来去重

    BloomFilter是通过“位(bit)”来保存元素的,是一个初始值全为0的位数组

    添加元素:使用K个Hash函数得到元素的K个Hash值,以这K个Hash值作为数组的索引,把位数组中位于该索引的值设为1。

    查找元素:与添加元素过程相似,使用K个Hash函数得到元素的K个Hash值,以这K个Hash值作为数组的索引,查找到索引位置的值,如有一个值为0,则代表该元素不存在于BloomFilter中;如果都为1,说明该元素存在于BloomFilter中,但有误判的概率

    举例:
    位数组bloom:0000000000000000

    • 存入元素x:
       元素x的三个Hash值为1、5和10,将x存入bloom中,bloom变为:0000010000100010
    • 存入元素y:
       元素y的三个Hash值为1、4和8,4和8所在的位为0,故y不存在于bloom中,将y存入bloom,bloom变为:0000010100110010
    • 存入元素z:
       元素z的三个Hash值为4、5和8,4、5和8所在的位为1,这时会判断为z已存在bloom中,为重复数据,但事实上z并不与x或y相同,故出现“误判”——将不是重复的数据判定为重复

    BloomFilter的优缺点:

    • 牺牲正确率来节省时间和空间,效率更高;
    • 往集合中插入的元素越多,错判“在集合内”的概率越大;
    • 不能删除集合中的元素,删除某个元素可能会将其他元素的位值也发生改变;

    相关值的设定

    1. 误判率f 的计算公式:
      f=(1(11m)kn)kmkHashn f = ( 1 − ( 1 − 1 m ) k n ) k , m 为 位 数 组 大 小 , k 为 H a s h 函 数 个 数 , n 为 预 计 存 入 的 最 大 数 据 量 ;

      m 趋向于无穷时,误判率f 的计算公式可变为:
      f=(1(11m)kn)k=(1(11m)mknm)k(1enkm)k f = ( 1 − ( 1 − 1 m ) k n ) k = ( 1 − ( 1 − 1 m ) − m − k n m ) k ≈ ( 1 − e n k m ) k
    2. 给定mn 值时,当 k=mnln20.7mn k = m n l n 2 ≈ 0.7 m n f 的值为最小,为 (12)k0.6185mn ( 1 2 ) k ≈ 0.6185 m n
    3. 位数组的大小m mlog2enlog2(1f) m ≥ l o g 2 e ∗ n l o g 2 ( 1 f )
      :具体算法公示计算参考中,在此处的计算出错,
      f=2kk=log21fmnln2=log21fm=log2enlog2(1f) f = 2 − k ⇒ k = l o g 2 1 f ⇒ m n l n 2 = l o g 2 1 f ⇒ m = l o g 2 e ∗ n l o g 2 ( 1 f ) ,
      (logaMn=nlogaM,logablogba=1) ( l o g a M n = n l o g a M , l o g a b ∗ l o g b a = 1 )

    如何获取更有用的BloomFilter?

    1. 选择合适的Hash函数,尽可能的返回范围更均匀的Hash值,减少误判率;
    2. 位数组的大小(m)非常重要,相对数据量,m太小的话,增加了误判的几率,m太大,又会浪费空间;
    3. Hash函数的个数(k)对索引值的均匀分配也很重要;

    具体算法公式计算参考:
    作者:Allen Sun
    链接:https://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html

    展开全文
  • Traditional bloomfilter实现 以及 动态增加/删除 字符串的counter bloomfilter实现。
  • Bloom Filter

    2018-11-02 15:48:40
    此时,可以考虑使用 Bloom Filter。 具体步骤: 申请足够的bit位,所有bit位置为0(如: int[]) 通过一定的Hash策略将集合元素映射到 int[] 的特定位上,并将对应 bit 置1 取待检测元素,进行相同的Hash,对应位上 ...
  • bloom filter

    2014-03-09 19:41:01
     在javaEyes上找到一篇挺有用的文章,希望能对大家理解Bloom filter有帮助    1 Overview  Bloom filter最早由 Burton Howard Bloom提出,是一种用于判断成员是否存在于某个集合中的数据结构。 Bloom ...
  • 通过前一篇文章的学习,对于 BloomFillter 通过前一篇文章的学习,对于 BloomFilter 的概念和原理,以及误报率等计算方法都一个理性的认识了。在这里,我们将用 Java'实现一个简单的 BloomFilter
  • 文章目录前言什么是缓冲穿透问题?...2.2 布隆过滤器内部的运行原理2.2.1 BloomFilter的成员变量。2.2.1.1 BloomFilterV18.0 的定义2.2.2 Bloom Filter构造2.2.3 哈希函数2.2.4 位数组具体实现2.3 添加元素的实现步骤2
  • php实现Bloom Filter

    万次阅读 2015-07-24 19:20:15
    Bloom Filter(BF) 是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法,用于**快速**查找某个元素是否属于集合, 但不要求百分百的准确率。 Bloom filter通常用于爬虫的url去重,即判断某个url是否已经被爬...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,318
精华内容 3,327
关键字:

bit数bloomfilter