Bit_Map和Bloom Filter

在大规模的数据处理中，Bit_Map和Bloom Filter算法可以将内存空间的利用率提升到极致。在小规模的数据量中，可直接用哈希表。

Bit_Map

什么是Bit_Map

Bit_Map是一种紧凑的数据结构，可以用Bit标志位标记元素的state状态（可以用来判断某个元素是否在某个集合中），可以减少内存的使用，对空间的利用率有显著的提升。

Bit_Map的优点和缺点

优点

采用bit为单位存储数据，减少了内存的使用。采用了类Hash的映射的原理，减少了查询的时间，而且空间复杂度不随原始集合内元素的个数增加而增加。

缺点

只能用来判断数据是否出现过，不能记录数据出现的次数。对无重复的数据，可利用Bit_Map进行排序。但是有一个致命缺点是空间复杂度随集合内最大元素增大而线性增大。

Bit_Map C++简单实现

class BitMap {
  private:
    vector<int> arr;

  public:
    BitMap(int N = 1024) { arr.resize(N / 32 + 1); }
    void insert(int value) {
        int index = value >> 5;
        int num = value % 32;
        arr[index] |= (1 << num);
    }
    void retSetMap(int value) {
        int index = value >> 5;
        int num = value % 32;
        arr[index] &= ~(1 << num);
    }
    ~BitMap();
};

C++ 标准库头文件bitset

C++中STL中bitset头文件是对Bit_Map的完整的实现。

Bloom Filter（布隆过滤器）

在介绍Bloom Filter之前，首先介绍一下Hash函数的概念。
哈希函数的概念是：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。
哈希函数的输入域M中元素可能是非常大的范围，比如一个非常长的字符串。但是输出域S是一个固定的范围(经过Hash映射后)，在此基础上建立了一个映射，对于M里面每一个元素，输出域S里面都有唯一一个与之元素。M-->S
一般来说，典型的Hash函数有如下的性质。
1.有无限的输入值域。
2.当给Hash函数相同的输入值时，输出值是一样的。
3.不同的输入值可能对应到相同的输出值上，但是好的Hash函数会尽量避免这种情况。
4.不同的输入值经过Hash后的返回值会均匀的分布到S上。

image.png

原始的数据经过hash映射后成为了哈希编码，数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。

Bloom Filter介绍

巴顿.布隆于一九七零年提出
一个很长的二进制向量（位数组）
一系列随机函数 (哈希)
空间效率和查询效率高
有一定的误判率（哈希表是精确匹配）

Bloom Filter的原理

Bit_Map对于每一个可能的整型值，通过直接寻址的方式进行映射，相当于使用了一个哈希函数，那布隆过滤器就是引入了k(k>1)个相互独立的哈希函数，保证在给定的空间、误判率下，完成元素判重的过程。

image.png

x,y,z经由哈希函数映射将各自在Bitmap中的3个位置置为1，当w出现时，仅当3个标志位都为1时，才表示w在集合中。图中所示的情况，布隆过滤器将判定w不在集合中。

Bloom Filter过滤器添加元素

元素给K个哈希函数得到k个哈希值
根据K个哈希值把bit数组里面相应的K个位置置1

Bloom Filter过滤器查询元素

元素给K个哈希函数得到k个哈希值
根据K个哈希值得到bit数组的K个对应位置的数值
如果K个位置的数值都是1，可能在集合中。如果有一个为0，则元素肯定不在集合中。

布隆过滤器实现

python的实现，使用murmurhash算法

import mmh3
from bitarray import bitarray
"""
首先需要使用pip安装这两个依赖的包
"""


BIT_SIZE = 5000000

class BloomFilter:
    
    def __init__(self):
        # Initialize bloom filter, set size and all bits to 0
        bit_array = bitarray(BIT_SIZE)
        bit_array.setall(0)

        self.bit_array = bit_array
        
    def add(self, url):
        # Add a url, and set points in bitarray to 1 (Points count is equal to hash funcs count.)
        # Here use 7 hash functions.
        point_list = self.get_postions(url)

        for b in point_list:
            self.bit_array[b] = 1

    def contains(self, url):
        # Check if a url is in a collection
        point_list = self.get_postions(url)

        result = True
        for b in point_list:
            result = result and self.bit_array[b]
    
        return result

    def get_postions(self, url):
        # Get points positions in bit vector.
        point1 = mmh3.hash(url, 41) % BIT_SIZE
        point2 = mmh3.hash(url, 42) % BIT_SIZE
        point3 = mmh3.hash(url, 43) % BIT_SIZE
        point4 = mmh3.hash(url, 44) % BIT_SIZE
        point5 = mmh3.hash(url, 45) % BIT_SIZE
        point6 = mmh3.hash(url, 46) % BIT_SIZE
        point7 = mmh3.hash(url, 47) % BIT_SIZE


        return [point1, point2, point3, point4, point5, point6, point7]

# 测试一下
if __name__ == '__main__':
    bloom = BloomFilter()
    bloom.add("www.baidu.com")
    bloom.add("www.yahoo.com")
    bloom.add("www.tencen.com")
    flag = bloom.contains("www.baidu.com")
    print flag

总结

计算机领域内，为了达到某一方面的性能，常常需要牺牲某一方面。比如空间换时间或者时间换空间。布隆过滤器引入了错误率，极大的节省了空间。但是布隆过滤器不能100%正确的判断元素是否在集合中。
自从Burton Bloom在70年代提出Bloom Filter之后，Bloom Filter就被广泛用于拼写检查和数据库系统中。

参考：
https://www.jianshu.com/p/b0c0edf7686e
https://blog.csdn.net/zdxiq000/article/details/57626464