4 ms·
OK, just as some code for you to play with, here's an explicit implementation. You shouldn't use md5, the hash functions aren't very good, and it's only a toy
by RiderOfGiraffes 16y ago
OK, just as some code for you to play with, here's an explicit implementation. You shouldn't use md5, the hash functions aren't very good, and it's only a toy example.
#!/usr/bin/python
import md5
def h0(obj): return ord(md5.md5(obj).digest()[0]) % size
def h1(obj): return ord(md5.md5(obj).digest()[1]) % size
def h2(obj): return ord(md5.md5(obj).digest()[2]) % size
def h3(obj): return ord(md5.md5(obj).digest()[3]) % size
def init_bloom(size): return size * [0]
def insert_item(vector,obj):
for fn in bloom_hash_fns:
vector[fn(obj)] = 1
def test_for_presence(vector,obj):
for fn in bloom_hash_fns:
if 0==vector[fn(obj)]:
return False
return True
# You decide what size your vector will be
size = 32
# The you create hash functions, each taking an
# object and return a value in the range 0 to size-1.
bloom_hash_fns = [ h0, h1, h2, h3 ]
vector = init_bloom(size)
print vector
insert_item(vector,'test')
print vector
insert_item(vector,'text')
print vector
insert_item(vector,'vext')
print vector
print 'Should be 1', test_for_presence(vector,'test')
print 'Should be 1', test_for_presence(vector,'text')
print 'Should be 1', test_for_presence(vector,'vext')
print 'Should be 0', test_for_presence(vector,'vest')
print 'Should be 0', test_for_presence(vector,'abcd')
print 'Should be 0', test_for_presence(vector,'wxyx')
- tocomment 16y agoThanks, this is perfect. (I wonder if you should add this to the Wikipedia article? It would make it a lot clearer.) I can definitely see how it works now. I'm still not sure on why it works. I guess it's just a probability thing? I.e., each hashed insertion is very unlikely to collide with another?
- RiderOfGiraffes 16y agoIt's really, really bad code, and although it serves its purpose of being explicit, I wouldn't put it on WikiPedia. By the way, if you really want to learn about learning, I strongly recommend that you return to the description in the wikipedia article and read it again, this time with your greater understanding. Ask youself: Why didn't I understand this first time round, and what should I have done differently to make sure I did? It's only by such self-reflection like that you will improve your independent learning abilities. Here's the section in question: An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with a uniform random distribution. To add an element, feed it to each of the k hash functions to get k array positions. Set the bits at all these positions to 1. To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions are 0, the element is not in the set - if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have been set to 1 during the insertion of other elements. That descriptions seems to me to be complete and clear. What did you not understand?