bloom_filter_mod module

Bloom Filter: Probabilistic set membership testing for large sets.

class bloom_filter_mod.Array_backend(num_bits)

Bases: object

Backend storage for our “array of bits” using a python array of integers.

clear(bitno)

Clear bit number bitno - set it to false.

close()

Noop for compatibility with the file+seek backend.

effs = 4294967295

is_set(bitno)

Return true iff bit number bitno is set.

set(bitno)

Set bit number bitno to true.

class bloom_filter_mod.Array_then_file_seek_backend(num_bits, filename, max_bytes_in_memory)

Bases: object

Backend storage for our “array of bits” using a python array of integers up to some maximum number of bytes…

…then spilling over to a file. This is -not- a cache; we instead save the leftmost bits in RAM, and the rightmost bits (if necessary) in a file. On open, we read from the file to RAM. On close, we write from RAM to the file.

clear(bitno)

Clear bit number bitno - set it to false.

close()

Write the in-memory portion to disk, leave the already-on-disk portion unchanged.

effs = 255

is_set(bitno)

Return true iff bit number bitno is set.

set(bitno)

Set bit number bitno to true.

class bloom_filter_mod.Bloom_filter(ideal_num_elements_n, error_rate_p, probe_bitnoer=<function get_bitno_lin_comb>, filename=None, start_fresh=False)

Bases: object

Probabilistic set membership testing for large sets.

add(key)

Add an element to the filter.

intersection(bloom_filter)

Compute the set intersection of two bloom filters.

union(bloom_filter)

Compute the set union of two bloom filters.

class bloom_filter_mod.File_seek_backend(num_bits, filename)

Bases: object

Backend storage for our “array of bits” using a file in which we seek.

clear(bitno)

Clear bit number bitno - set it to false.

close()

Close the file.

effs = 5

is_set(bitno)

Return true iff bit number bitno is set.

set(bitno)

Set bit number bitno to true.

class bloom_filter_mod.Mmap_backend(num_bits, filename)

Bases: object

Backend storage for our “array of bits” using an mmap’d file.

Please note that this has only been tested on Linux so far: 2 -11-01.

clear(bitno)

Clear bit number bitno - set it to false.

close()

Close the file.

effs = 5

is_set(bitno)

Return true iff bit number bitno is set.

set(bitno)

Set bit number bitno to true.

bloom_filter_mod.get_bitno_lin_comb(bloom_filter, key)

Apply num_probes_k hash functions to key. Generate the array index and bitmask corresponding to each result.

bloom_filter_mod.get_bitno_seed_rnd(bloom_filter, key)

Apply num_probes_k hash functions to key. Generate the array index and bitmask corresponding to each result.

bloom_filter_mod.hash1(int_list)

Hash input: function #1.

bloom_filter_mod.hash2(int_list)

Hash input: function #2.

bloom_filter_mod.simple_hash(int_list, prime1, prime2, prime3)

Compute a hash value from a list of integers and 3 primes.

bloom_filter_mod.try_unlink(filename)

Delete a file. Don’t complain if it’s not there.