# Bloom Filters

**URL:** <https://www.ruby-forum.com/t/bloom-filters/103679>\
**Category:** Ruby\
**Created:** [May 9, 2007, 7:16am UTC](https://www.ruby-forum.com/t/bloom-filters/103679 "2007-05-09T07:16:35Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![mfaine](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/b3f665/32.png) [@mfaine](https://www.ruby-forum.com/u/mfaine)\
**Post date:** [May 9, 2007, 7:16am UTC](https://www.ruby-forum.com/t/bloom-filters/103679/1 "2007-05-09T07:16:35Z")

</div>

I’ve been playing with Bloom Filters in Perl and found that there is a  
ruby  
module for them as well (perl inspired). I am trying to come up with a  
good  
way to serialize the filter post construction that would be compatible  
with  
perl, ruby, php and [asp.net](http://asp.net) (don’t ask). I am not sure what the best  
representation would be. Any ideas?

Mark

---

<div class="post-metadata">

**Author:** ![mfaine](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/b3f665/32.png) [@mfaine](https://www.ruby-forum.com/u/mfaine)\
**Post date:** [May 11, 2007, 4:49pm UTC](https://www.ruby-forum.com/t/bloom-filters/103679/2 "2007-05-11T16:49:41Z")

</div>

Text file?

---

<div class="post-metadata">

**Author:** ![mfaine](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/b3f665/32.png) [@mfaine](https://www.ruby-forum.com/u/mfaine)\
**Post date:** [May 11, 2007, 7:33pm UTC](https://www.ruby-forum.com/t/bloom-filters/103679/3 "2007-05-11T19:33:07Z")

</div>

“Mark Alexander F.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

> I’ve been playing with Bloom Filters in Perl and found that there is a ruby  
> module for them as well (perl inspired). I am trying to come up with a good  
> way to serialize the filter post construction that would be compatible with  
> perl, ruby, php and [asp.net](http://asp.net) (don’t ask). I am not sure what the best  
> representation would be. Any ideas?

Well, what do you need to encode? As I see it, you need to encode k  
(number of hashfunctions), m (number of bits in the filter), some  
knowledge of the k hashfunctions themselves, and the bitstring.

Now, both the perl and ruby implementation use hashfunctions that are  
done by:  
hash\_N(arg) = sha1(seed\_N + arg)

This has possibilities since the definition of sha1 is rigorously  
specified (i.e. two implementations fed the same byte string produce  
the same hash), sha1 libraries are available in all the potential  
target platforms, and the hash functions can be easily specified by  
giving the k seed strings.

So, you need a cross-language way to serialize two integers, a list of  
byte strings, and a huge bytestring. This looks like a job for  
bencoding! (the simple data serialization developed for bittorrent)

I’d serialize it as a bencoded dictionary with the keys “m”, “k”,  
“seeds” and “filter”. You should specify that the long bytestring  
“filter” is to be interpreted as a bit string, with the least  
signficant bit of byte 0 as bit 0. (This is what you get from  
BitSet.to\_bytes, and it’s what perl’s Bloom::Filter will give you for  
$self-\>{filter})

Actually, thinking about it a bit more, there’s one more thing you’ll  
want to add to the bencoded dictionary: “hashmethod”. For the current  
implementations of Bloom::Filter and pbloomfilter, I’d suggest the  
string “SHA1 32-bit XOR”, since if I were presented with the challenge  
of getting a 32-bit hash value out of an SHA1 hash, my inclination  
would be to just choose the first 4 bytes. SHA1 already mixes things  
so well that I don’t see any advantage in splitting the 20 bytes into  
five 4-byte chunks and XOR-ing them.