[racket] Bloom filter?

From: Phil Bewig (pbewig at gmail.com)
Date: Mon Jun 6 11:43:48 EDT 2011

R5RS doesn't provide bit operations or bit vectors.  R6RS provides bit
operations but not bit vectors.  Thus, for my blog I used a vector of
booleans; I'm more interested in the concept of bloom filters than the
low-level implementation details.

I don't know if Racket provides bit vectors.  My Standard Prelude does
provide them, at
http://programmingpraxis.com/contents/standard-prelude/#bits.

On Mon, Jun 6, 2011 at 10:24 AM, Erich Rast <erich at snafu.de> wrote:

> 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
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20110606/a96b33a8/attachment.html>

Posted on the users mailing list.