用纯python构建的高效、可扩展的bloom过滤模块。
bloom的Python项目详细描述
布鲁姆过滤器
\布鲁姆fil-ter\ 名词
- 空间有效的概率数据结构，用于测试元素是否是集合的成员。
- 一个有趣的项目！
关于布卢米
bloomy是一个bloom filter模块，设计为轻量级和可伸缩。Bloomy不使用任何外部库，并在内部扩展以匹配场景。Bloomy还旨在降低误报率。这是我应用md5散列和位旋转来生成k个唯一的8字节散列值，然后使用黄金比率压缩来实现均匀分布。
bloom过滤器的优点
- 使用位数组存储项的存在。这大大减少了内存中的存储空间。
- 实现二进制和位屏蔽操作。这减少了add的运行时间，并且包含的操作实际上是o（1）。
- 可以使用原始类型。
操作
___init__(m,[array of additional hash functions])
params: (optional) size of bit array, (optional) additional hash functions
return: bloomFilter object
创建位数组bits，其中m位清除为0，并保存k个哈希函数。m的默认值为1000，过滤器带有五个唯一的默认散列函数。
add(value)
params: object to add to the bloomFilter set
return: None
接受一个值并对其进行k次哈希运算以获得索引列表。对于由给定哈希函数获得的每个索引，将位数组bits中的值设置为1。
__contains__(value)
params: object to search for in the set
return: True/False indicating presence in the set
接受一个值并对其进行k次哈希运算，以获得唯一索引的列表。创建一个初始值为0的位掩码。对于哈希函数获得的每个索引，请在掩码1中设置该索引。执行下面的二进制运算^ {< CD6> }，如果该操作所执行的值等于掩码，则可以得出在Bloom过滤器中存在值{{EM1} $ ^ {STR 1 } $ < <强> > EEM>。
addHashFunction(fn)
params: additional hash function to add
return: None
将函数作为参数，并将此函数添加到Bloom过滤器所使用的哈希函数的现有列表中。函数fn必须采用fn(value)格式，其中value是要散列的项，函数必须返回一个介于0和索引上限之间的整数。以下所有其他参数都必须具有默认值。
函数还必须能够为给定的输入提供一致的值。不涉及随机化，而是一个纯键转换函数。可以使用任何压缩函数，只要它限制位数组上限内的键空间。
fingerprint(value)
params: value to inspect fingerprint
return: array (len = k) of hashed values
接受一个值并返回由哈希函数列表创建的哈希值数组。用于调试和检查哈希机制的行为。
mask([ints])
params: integer values to use to create bit mask
return: integer bit mask
在参数整数数组指定的索引中创建一个位屏蔽整数，其值为1。
示例（k=3，m=12）
0. constructor
bit array:
--- --- --- --- --- --- --- --- --- --- --- --- ---
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ...
--- --- --- --- --- --- --- --- --- --- --- --- ---
1. add("Hello world") => 00, 03, 04
bit array:
--- --- --- --- --- --- --- --- --- --- --- --- ---
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ...
--- --- --- --- --- --- --- --- --- --- --- --- ---
2. contains("Hello World") => 00,03,04
bit array:
--- --- --- --- --- --- --- --- --- --- --- --- ---
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ...
--- --- --- --- --- --- --- --- --- --- --- --- ---
|| || ||
||==========||==||=================> 1,1,1 = True
3. contains("java is the best") => 02,03,07
bit array:
--- --- --- --- --- --- --- --- --- --- --- --- ---
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ...
--- --- --- --- --- --- --- --- --- --- --- --- ---
|| || ||
||==||==============||=====> 0,1,0 = False
谢谢你！！
谢谢你检查这个！请随时通过电子邮件sdcroche@ncsu.edu，或Twitter @shmam_
欢迎加入QQ群-->： 979659372
