Bloom Filters.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "kPt5q27L5557"
   },
   "source": [
    "# Bloom Filters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "p0-YhEpP_Ds-"
   },
   "source": [
    "### Setup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Zsj5WYpR9QId"
   },
   "source": [
    "In this Pyhton code I am going to install a [bloom_filter](https://github.com/hiway/python-bloom-filter), a Python library which offers an implementations of Bloom filters.  Run the cell below!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "k-qHai2252mI"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting bloom_filter\n",
      "  Using cached bloom_filter-1.3.3-py3-none-any.whl (8.1 kB)\n",
      "Installing collected packages: bloom-filter\n",
      "Successfully installed bloom-filter-1.3.3\n"
     ]
    }
   ],
   "source": [
    "!pip install bloom_filter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "kAYRX2PMm0L6"
   },
   "source": [
    "### Data Loading"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "XO_IcxgquzhI"
   },
   "source": [
    "From the NLTK (Natural Language ToolKit) library, I am importing a large list of English dictionary words, commonly used by the very first spell-checking programs in Unix-like operating systems."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "-Xz3f79crEEb"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package words to\n",
      "[nltk_data]     /Users/rajeshidumalla/nltk_data...\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Dictionary length: 236736\n",
      "['A', 'a', 'aa', 'aal', 'aalii', 'aam', 'Aani', 'aardvark', 'aardwolf', 'Aaron', 'Aaronic', 'Aaronical', 'Aaronite', 'Aaronitic', 'Aaru']\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data]   Unzipping corpora/words.zip.\n"
     ]
    }
   ],
   "source": [
    "import nltk\n",
    "nltk.download('words')\n",
    "\n",
    "from nltk.corpus import words\n",
    "word_list = words.words()\n",
    "print(f'Dictionary length: {len(word_list)}')\n",
    "print(word_list[:15])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "csbQXPUFUMob"
   },
   "source": [
    "Then I am loading another dataset from the NLTK Corpora collection: ```movie_reviews```.\n",
    "\n",
    "The movie reviews are categorized between *positive* and *negative*, so I will construct a list of words (usually called **bag of words**) for each category."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "HwgRhMT1UNUt"
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package movie_reviews to\n",
      "[nltk_data]     /Users/rajeshidumalla/nltk_data...\n",
      "[nltk_data]   Unzipping corpora/movie_reviews.zip.\n"
     ]
    }
   ],
   "source": [
    "from nltk.corpus import movie_reviews\n",
    "nltk.download('movie_reviews')\n",
    "\n",
    "neg_reviews = []\n",
    "pos_reviews = []\n",
    "\n",
    "for fileid in movie_reviews.fileids('neg'):\n",
    "  neg_reviews.extend(movie_reviews.words(fileid))\n",
    "for fileid in movie_reviews.fileids('pos'):\n",
    "  pos_reviews.extend(movie_reviews.words(fileid))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "mrHJptH3Tb-3"
   },
   "source": [
    "And now I am going to develop a very simplistic spell-checker.  By no means I was first think of using it for a real-world use case, but it is an interesting exercise to highlight the strenghts and weaknesses of Bloom Filters!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "bK3WyXaPsa5q"
   },
   "outputs": [],
   "source": [
    "from bloom_filter import BloomFilter\n",
    "\n",
    "word_filter = BloomFilter(max_elements=236736)\n",
    "\n",
    "for word in word_list:\n",
    "  word_filter.add(word)\n",
    "\n",
    "word_set = set(word_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Ddqg0odiaSRg"
   },
   "source": [
    "If you executed the cell above, you now have 3 different variables in your scope:\n",
    "\n",
    "1.   ```word_list```, a Python list containing the English dictionary (in case insensitive order)\n",
    "2.   ```word_filter```, a Bloom filter where we have already added all the words in the English dictionary\n",
    "3.   ```word_set```, a [Python set](https://docs.python.org/3.6/library/stdtypes.html#set-types-set-frozenset) built from the same list of words in the English dictionary\n",
    "\n",
    "Let's inspect the size of each datastructure using the [getsizeof()](https://docs.python.org/3/library/sys.html#sys.getsizeof) method!\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "FVLxu20maRLf"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Size of word_list (in bytes): 2115944\n",
      "Size of word_filter (in bytes): 48\n",
      "Szie of word_set (in bytes): 8388824\n"
     ]
    }
   ],
   "source": [
    "from sys import getsizeof\n",
    "print(f'Size of word_list (in bytes): {getsizeof(word_list)}')\n",
    "\n",
    "print(f'Size of word_filter (in bytes): {getsizeof(word_filter)}')\n",
    "print(f'Szie of word_set (in bytes): {getsizeof(word_set)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "WbQzd4czlT3h"
   },
   "source": [
    "You should have noticed how efficient is the Bloom filter in terms of memory footprint!\n",
    "\n",
    "Now let's find out how fast is the main operation for which we construct Bloom filters: *membership testing*. To do so, we will use the ```%timeit``` IPython magic command, which times the repeated execution of a single Python statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "id": "xq7I6kJfwXy5"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "436 µs ± 36.9 µs per loop (mean ± std. dev. of 3 runs, 1000 loops each)\n",
      "15.2 µs ± 1.29 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -r 3 \"California\" in word_list\n",
    "\n",
    "\n",
    "%timeit \"California\" in word_filter\n",
    "#%timeit \"California\" in word_set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Qq2LVgEVnI_R"
   },
   "source": [
    "Notice the performance gap between linear search on a list, multiple hash computations in a Bloom filter, and a single hash computation in a native Python ```Set()```.\n",
    "\n",
    "I now have all the building blocks required to build our spell-checker, and we understand the performance tradeoffs of each datastructure we chose. Write a function that takes as arguments (1) a list of words, and (2) any of the 3 dictionary datastructures we constructed. The function must return the number of words which **do not appear** in the dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "id": "lTT-6rQcnibH"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.25797065181509365\n",
      "0.25797065181509365\n",
      "0.25797065181509365\n",
      "0.25797065181509365\n",
      "0.25797065181509365\n",
      "0.25797065181509365\n",
      "0.25797065181509365\n",
      "0.25797065181509365\n",
      "6.09 s ± 699 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "def func(a, ds):\n",
    "  cnt = 0\n",
    "  for x in a:\n",
    "    if x not in ds:\n",
    "      cnt += 1\n",
    "  \n",
    "  print(cnt / len(a))\n",
    "\n",
    "%timeit func(neg_reviews, word_filter)\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "CS246 - Colab 8.ipynb",
   "provenance": [],
   "toc_visible": true
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}