<jupyter_start><jupyter_text>A Bloom filter is a data structure that is used to check for membership of an element x in a set of m elements.http://prakhar.me/articles/bloom-filters-for-dummies/http://axiak.github.io/pybloomfiltermmap/Download from:https://pypi.python.org/pypi/pybloom/1.0.2pip install ez_setuppython setup.py install<jupyter_code>from pybloom import BloomFilter
f = BloomFilter(capacity=10000, error_rate=0.001)
for i in xrange(0, f.capacity):
    _ = f.add(i)
0 in f
f.capacity in f
len(f) <= f.capacity
 abs((len(f) / float(f.capacity)) - 1.0) <= f.error_rate
from pybloom import ScalableBloomFilter
sbf = ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)
count = 10000
for i in xrange(0, count):
     _ = sbf.add(i)
sbf.capacity > count



len(sbf) <= count
abs((len(sbf) / float(count)) - 1.0) <= sbf.error_rate<jupyter_output><empty_output><jupyter_text>Using a bloom filter on a set of postshttp://www.stavros.io/posts/bloom-filter-search-engine/<jupyter_code>from pybloom import BloomFilter
import os
import re

POST_DIR = 'data/posts/'
# Read all my posts.
posts = {post_name: open(POST_DIR + post_name).read() for post_name in os.listdir(POST_DIR)}
# Create a dictionary of {"post name": "lowercase word set"}.
split_posts = {name: set(re.split("\W+", contents.lower())) for name, contents in posts.items()}
filters = {}
for name, words in split_posts.items():
    filters[name] = BloomFilter(capacity=len(words), error_rate=0.1)
    for word in words:
        filters[name].add(word)
def search(search_string):
    search_terms = re.split("\W+", search_string)
    return [name for name, filter in filters.items() if all(term in filter for term in search_terms)]
search("nothing")
search("ice")
# %load data/posts/3.txt
Vacation Time

# %load data\posts\4.txt
Ice cream is always good
 sum(len(filter.bitarray.tobytes()) for filter in filters.values()) / len(filters)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.13267940113577698, 'fraction_numerical': 0.014455343314403717, 'mean_word_length': 5.0, 'pattern_counts': {'":': 1, '<': 13, '<?xml version=': 0, '>': 10, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '78886', 'license': 'MIT', 'n_tokens_mistral': 704, 'n_tokens_neox': 679, 'n_words': 175, 'path': 'Lectures/Lecture6-Streams/Bloom Filter Example.ipynb', 'repo_name': 'soumya8888/big-data-python-class', 'size': '1937'}