I thought I'd try implementing a Bloom filter in Python, just for fun,
since Python does have a nice abstraction for large bit vectors: the
long int, or bignum.  Turns out it's grossly inefficient to use a single
long int for a Bloom filter because there's no way to set or clear bits
in it.

I wrote this on Beatrice's Mac with Python 2.3, which sucked, but was
better than not programming.

"""Bloom filters in Python, using SHA-1 and Python longs.

My first attempt stored the whole filter in a single arbitrary-size integer,
but for some reason that was 100x slower than storing it in a bunch of 256-bit

import sha

def nbits_required(n):
    """Bits required to represent any integer in [0, n)."""
    n -= 1
    rv = 0
    while n:
        n >>= 1
        rv += 1
    return rv

class Bloom:
    """Bloom filter: compact hash table for membership tests with false pos."""
    # default bits per bucket is 256 to cut down on pickle overhead
    def __init__(self, size, nhashes, bucketbits=256):
        """size: number of bits.  Should be a power of 2.
        nhashes: number of separate hashes to use.

        Making nhashes larger will make it slower.  There are also tradeoffs
        between size, performance, and false-positive rate, which you can look
        up elsewhere."""
        self.bucketbits = bucketbits
        self.filter = [0L] * int((size + bucketbits - 1) / bucketbits)
        self.size = size
        self.nhashes = nhashes
        self.hashbits = nbits_required(size)
        assert self.hashbits * nhashes <= 160  # 160's all we get with SHA1
    def add(self, astr):
        """Add a string to the membership of the filter."""
        for offset in self._hashes(astr):
            bucket, bit = divmod(offset, self.bucketbits)
            self.filter[bucket] |= (1L << bit)
    def __contains__(self, astr):
        """Returns true if the string is in the filter or it feels like it."""
        for offset in self._hashes(astr):
            bucket, bit = divmod(offset, self.bucketbits)
            if not self.filter[bucket] & (1L << bit): return 0
        return 1
    def _hashes(self, astr):
        """The hashes of a particular string."""
        digest = sha.sha(astr).digest()
        # is there no better way to convert a byte string into a long?!
        hashlong = 0L
        for ch in digest: hashlong = (hashlong << 8) | ord(ch)
        rv = []
        mask = (1L << self.hashbits) - 1
        for ii in range(self.nhashes):
            # Note that this will give substantially nonuniform results if
            # self.size is not a power of 2, in order to avoid wasting hash
            # bits or doing long division:
            rv.append((hashlong & mask) % self.size)
            hashlong >>= self.hashbits
        return rv

def test_bloom():
    """Very basic sanity test for Bloom filter implementation."""
    def ok(a, b): assert a == b, (a, b)
    ok(map(nbits_required, range(1, 10)), [0, 1, 2, 2, 3, 3, 3, 3, 4])
    ok(nbits_required(131072), 17)
    ok(nbits_required(131073), 18)

    b = Bloom(1024, 5)
    assert 'asdf' not in b
    assert 'fdsa' not in b
    assert 'asdf' in b
    assert 'fdsa' not in b

    # false positives (depends on hash function):
    x = Bloom(8, 3)
    x.add('asdf') # about a 5% chance of false positives
    assert 'asdf' in x
    assert 'fdsa' not in x
    ok(filter(x.__contains__, ['foo%d' % ii for ii in range(25)]), ['foo22'])


def misspellings(infile):
    """Demo: spell check."""
    import re, cPickle, sys
    try: bf = cPickle.load(file('dict.pck', 'rb'))
    except IOError:
        # /usr/share/dict/words has 234936 words on this Mac and is 2.4 megs
        sys.stderr.write("reading dictionary...\n")
        words = file('/usr/share/dict/words')
        # 2^21 bits, 8.9 per word, would give us 1.5% false positives with 5
        # hashes or 1.7% with 6, so we use 4194304 = 2^22 bits, or 17.8 per
        # word, for 0.09% false positives; that's still only half a mebibyte,
        # although pickle overhead pushes it up to 559K, 22% of the dictionary.
        bf = Bloom(4194304, 5)  
        lineno = 0
        for line in words: 
            lineno += 1
            if not lineno % 100:
                sys.stderr.write('%s%s\r' % (lineno, ' ' * 40))
        sys.stderr.write("done reading dictionary;\n")
        try: cPickle.dump(bf, file('dict.pck', 'wb'), 2)
        except: pass
    def candidates(word):
        """Words you might find in the dictionary in English."""
        yield word
        for suffix in ['s', 'ing', 'ed', 'es', 'er', 's', 'ly']:
            if word.endswith(suffix): yield word[:-len(suffix)]
        for suffix, repl in [('ed', 'e'), ('er', 'e'), ('ing', 'e'),
                             ('ies', 'y'), ('ied', 'y')]:
            if word.endswith(suffix): yield word[:-len(suffix)] + repl
    for line in infile:
        for word in re.findall(r"['\w]+", line):
            # we drop the "'" because our dictionary has "didnt" but not
            # "didn't"
            for chance in candidates(word.replace("'", '').lower()):
                if chance in bf: break
                sys.stdout.write(word + ' ')
                # to prevent repeating it...

if __name__ == '__main__': 
    import sys

Reply via email to