Sadly I'm no really into Bloom filter, so those aspects needs to be reviewed by someone else. However, there are some idiomatic stuff I would like to address in your code.
First let me mention some style issues (mostly my preferences, and not really large issues):
- Consider specifying imports – You are using limited parts of
bitarray and mmh3, so you could consider using from bitarray import bitarray and from mmh3 import hash. However, this is based on personal preferences, and using mmh3.hash() does clearly indicate which hash function you're using.
- Do you need the
hashlib import? – It doesn't seem like you using anything from it. Is it needed?
- Don't use more parentheses than needed – In
calc_optimal_hash_func() you use a lot of parentheses. Are really all of those needed? It seems a little too much, and I'd prefer not to use that many, as it kind of clutters up the formulas to some extent. This is still more of a general advice, though.
- Don't test for
== False – Use the not operator instead, and do if not bit_array[result]:. It simply make more sense.
- Variable naming – Naming a variable
result, or bit_array, or string doesn't convey anything about the purpose of the variable. These and some of the other could benefit from better naming.
- Comment on the non-obvious stuff – It would be nice to see some comments describing what actually happens in your code. What kind of a
lookup do you do?
- Mostly good spacing – Most of your code is reasonable easy to read, but I don't like the alignment at start of
get_bit_array(). I think it would be better to use the default way of words = load_words() and so on.
Code smells
In addition to the smaller style issues, there are some bigger code smells in your code which I would like to address:
load_words() hides a global constant – It always loads /usr/share/dict/words, which kind of removes the need for a function. It would make a little more sense if you had load_words(dictionary_file). load_words() reads the whole file into memory – If I'm not mistaken, part of the reason you're wanting to use a Bloom Filter is to verify membership within a really large data structure. When you load the entire thing into memory, there is no need for the filter, you'd be better off checking for membership in the array directly!- Why the
try...except around the mmh3.hash()? – This seems a little strange, as you pass the catch all the time. Does this serve some unknown purpose? If so, it should have been documented. And if not, it should be removed.
Consider making a class, instead of functions – Having get_bit_array() return two variables, which you need to shuffle around later on, makes me think that this would better be served with a class. Imaging something like the following main section:
bloom_filter = BloomFilter('/usr/share/dict/words')
print(bloom_filter.lookup('badwordforsure'))
print(bloom_filter.lookup('cat'))
print(bloom_filter.lookup('hello'))
print(bloom_filter.lookup('jsalj'))
This would also expose what you're filtering towards, and it would allow for better interface and handling in general. It does seem like most of the functions are only used once, with the exception of the lookup function.
Join load_words() and get_bit_array() – In order to avoid keeping the entire dictionary in memory, I would build the bit_array directly when reading the file. This would really ease the memory requirements of your code.
Alternative implementation
Here is an implementation were I've taken most of these advice into account:
import mmh3
import bitarray
import math
class BloomFilter:
"""By building a bit array based upon a dictionary, this class
allows for probable membership, and certain non-membership of
any lookups within the filter."""
def __init__(self, dictionary_file):
"""Based on the dictionary_file, builds a bit array to
be used for testing membership within the file for a given
percentage, and accurate non-membership."""
# Skip file to get number of words
number_words = sum(1 for line in open(dictionary_file))
# Initialize some variables
self.calc_optimal_hash(number_words)
self.bit_array = self.array_length * bitarray.bitarray('0')
# Reread file, and build bit array
with (open(dictionary_file, 'r')) as dict_file:
for word in dict_file.readlines():
for seed in range(self.seed_count):
hashIndex = mmh3.hash(word, seed) % self.array_length
self.bit_array[hashIndex] = True
def calc_optimal_hash(self, number_words):
"""Calculate array_length and seed_count."""
# If I'm mistaken in precedence, re-add parentheses :-)
m = -number_words * math.log(0.01) / math.log(2) ** 2
k = m / number_words * math.log(2)
self.array_length = int(m)
self.seed_count = int(math.ceil(k))
def probable_member(self, word):
"""Test whether word probably is in the dictionary, or
are surely not in the dictionary."""
for seed in range(self.seed_count):
candidateHash = mmh3.hash(word, seed) % self.array_length
if not self.bit_array[candidateHash]:
return False
return True
def lookup(self, word):
"""Test whether word probably is in the dictionary, or
are surely not in the dictionary."""
if self.probable_member(word):
return '"{}" is most likely in dictionary'.format(word)
else:
return '"{}" is not in dictionary'.format(word)
def main():
bloom_filter = BloomFilter('/usr/share/dict/words')
print(bloom_filter.lookup('badwordforsure'))
print(bloom_filter.lookup('cat'))
print(bloom_filter.lookup('hello'))
print(bloom_filter.lookup('jsalj'))
main()
If you're using Python 2.x, I would also consider using xrange(seed_count) if seed_count is somewhat large, to avoid creating that array in-memory. This is better handled by default in Python3.
In the suggested code I read the file twice in order to get the number of words. This would in a lot of cases be better than reading the entire file into memory, and reading is usually cheap. If not an exact number of words is needed, I would estimate this number by taking the file size, and dividing by the average word length.
Finally, I've also created the probable_member() to return a boolean regarding the membership, as this allows for other uses rather than just presenting a text.
Hopefully you'll see the benefit of packaging this into a class. This implementation should allow for a much smaller memory footprint, and it would also easier allow for multiple filter to be used in parallel by instantiating multiple filter simultaneously if that should be wanted.
