[racket] Bloom filter?

From: Erich Rast (erich at snafu.de)
Date: Mon Jun 6 11:24:08 EDT 2011

Thanks a lot, that's a very nice place to start (interesting blog, too).

I had something similar in mind but was wondering about the
space-efficiency of a vector of booleans. Does the compiler represent
this as a memory area where each boolean corresponds to a single bit?

That would be cool but my fear is that it doesn't.

For the record, this is for a function that checks user passphrases
against a *gigantic* dictionary of known ones. 

Best,

Erich


On Mon, 2011-06-06 at 09:56 -0500, Phil Bewig wrote:
> I implemented a spell checker using a Bloom filter
> at http://programmingpraxis.com/2009/04/21/probabilistic-spell-checking/.
> 
> On Mon, Jun 6, 2011 at 9:48 AM, Erich Rast <erich at snafu.de> wrote:
>         Hi,
>         
>         I need to check whether a given string already occurs in a
>         list of
>         several million strings, where occasional false positives are
>         acceptable.
>         
>         Before reinventing the wheel, has anybody already implemented
>         a
>         space-efficient Bloom filter in racket and would like to share
>         it?
>         
>         Or, what else would you recommend?
>         
>         Best,
>         
>         Erich
>         
>         
>         
>         _________________________________________________
>          For list-related administrative tasks:
>          http://lists.racket-lang.org/listinfo/users
> 
> _________________________________________________
>   For list-related administrative tasks:
>   http://lists.racket-lang.org/listinfo/users




Posted on the users mailing list.