from random import Random
class BloomFilter:
# http://en.wikipedia.org/wiki/Bloom_filter
def __init__(self, num_bytes, num_probes):
self.arr = bytearray([0]) * num_bytes
self.num_probes = num_probes
def get_probes(self, key):
random = Random(key).random
for _ in range(self.num_probes):
array_index = int(random() * len(self.arr))
bit_index = int(random() * 8)
yield array_index, 1 << bit_index
def add(self, key):
for i, mask in self.get_probes(key):
self.arr[i] |= mask
def __contains__(self, key):
return all(self.arr[i] & mask for i, mask in self.get_probes(key))
class SpellChecker(BloomFilter):
def __init__(self, wordlistfiles, estimated_number_of_words=125000):
num_probes = 14 # set higher for fewer false positives
num_bytes = estimated_number_of_words * num_probes * 3 // 2 // 8
BloomFilter.__init__(self, num_bytes, num_probes)
for filename in wordlistfiles:
for line in open(filename):
self.add(line.rstrip())
def spellcheck(self, text):
print('Misspellings:')
for word in text.lower().split():
if word not in self:
print(word)
if __name__ == '__main__':
## Compute effectiveness statistics for a 125 byte filter with 50 entries
from random import sample
from string import ascii_letters
states = '''Alabama Alaska Arizona Arkansas California Colorado Connecticut
Delaware Florida Georgia Hawaii Idaho Illinois Indiana Iowa Kansas
Kentucky Louisiana Maine Maryland Massachusetts Michigan Minnesota
Mississippi Missouri Montana Nebraska Nevada NewHampshire NewJersey
NewMexico NewYork NorthCarolina NorthDakota Ohio Oklahoma Oregon
Pennsylvania RhodeIsland SouthCarolina SouthDakota Tennessee Texas Utah
Vermont Virginia Washington WestVirginia Wisconsin Wyoming'''.split()
bf = BloomFilter(num_bytes=125, num_probes=14)
for state in states:
bf.add(state)
m = sum(state in bf for state in states)
print('%d true positives out of %d trials' % (m, len(states)))
trials = 100000
m = sum(''.join(sample(ascii_letters, 8)) in bf for i in range(trials))
print('%d true negatives and %d false positives out of %d trials'
% (trials-m, m, trials))
c = ''.join(bin(x).replace('Ob', '') for x in bf.arr)
print('Bit density:', c.count('1') / float(len(c)))
## Demonstrate a simple spell checker using a 125,000 word English wordlist
from glob import glob
# Use the GNU ispell wordlist found at http://bit.ly/english_dictionary
checker = SpellChecker(glob('/Users/raymondhettinger/dictionary/english.?'))
checker.spellcheck('''
All the werldz a stage
And all the mehn and wwomen merrely players
They have their exits and their entrances
And one man in his thaim pllays many parts
His actts being sevven ages
''')
Diff to Previous Revision
--- revision 4 2011-05-06 17:52:20
+++ revision 5 2011-05-07 01:50:32
@@ -8,10 +8,10 @@
self.num_probes = num_probes
def get_probes(self, key):
- hasher = Random(key).randrange
+ random = Random(key).random
for _ in range(self.num_probes):
- array_index = hasher(len(self.arr))
- bit_index = hasher(8)
+ array_index = int(random() * len(self.arr))
+ bit_index = int(random() * 8)
yield array_index, 1 << bit_index
def add(self, key):
