{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"provenance":[{"file_id":"13FoEodEA8M5fFYqJW9f2zj36cBhAvarZ","timestamp":1772160651119},{"file_id":"1NI01jwKnxSITvK-0RZYJr8THMOFgNBcj","timestamp":1684982683280}]},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"markdown","metadata":{"id":"kPt5q27L5557"},"source":["# CS246 - Colab 8 (Winter 2025)\n","## Bloom Filters"]},{"cell_type":"markdown","metadata":{"id":"p0-YhEpP_Ds-"},"source":["### Setup"]},{"cell_type":"markdown","metadata":{"id":"Zsj5WYpR9QId"},"source":["In this Colab, we need to install a [bloom_filter](https://github.com/hiway/python-bloom-filter), a Python library which offers an implementation of Bloom filters.  Run the cell below!"]},{"cell_type":"code","metadata":{"id":"k-qHai2252mI","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1772157690359,"user_tz":480,"elapsed":6072,"user":{"displayName":"Rishabh Ranjan","userId":"14643331064616738605"}},"outputId":"29ebd580-2488-437c-e905-a2494bd6d307"},"source":["!pip install bloom_filter"],"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["Collecting bloom_filter\n","  Downloading bloom_filter-1.3.3-py3-none-any.whl.metadata (1.7 kB)\n","Downloading 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"]}]},{"cell_type":"markdown","metadata":{"id":"kAYRX2PMm0L6"},"source":["### Data Loading"]},{"cell_type":"markdown","metadata":{"id":"XO_IcxgquzhI"},"source":["From the NLTK (Natural Language ToolKit) library, we import a large list of English dictionary words, commonly used by the very first spell-checking programs in Unix-like operating systems."]},{"cell_type":"code","metadata":{"id":"-Xz3f79crEEb","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1772157694762,"user_tz":480,"elapsed":4401,"user":{"displayName":"Rishabh Ranjan","userId":"14643331064616738605"}},"outputId":"ebd19dd9-c43f-4566-8e6d-d5e26fb4fab2"},"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])"],"execution_count":null,"outputs":[{"output_type":"stream","name":"stderr","text":["[nltk_data] Downloading package words to /root/nltk_data...\n"]},{"output_type":"stream","name":"stdout","text":["Dictionary length: 236736\n","['A', 'a', 'aa', 'aal', 'aalii', 'aam', 'Aani', 'aardvark', 'aardwolf', 'Aaron', 'Aaronic', 'Aaronical', 'Aaronite', 'Aaronitic', 'Aaru']\n"]},{"output_type":"stream","name":"stderr","text":["[nltk_data]   Unzipping corpora/words.zip.\n"]}]},{"cell_type":"markdown","metadata":{"id":"csbQXPUFUMob"},"source":["Then we load another dataset from the NLTK Corpora collection: ```movie_reviews```.\n","\n","The movie reviews are categorized between *positive* and *negative*, so we construct a list of words (usually called **bag of words**) for each category."]},{"cell_type":"code","metadata":{"id":"HwgRhMT1UNUt","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1772157698173,"user_tz":480,"elapsed":3410,"user":{"displayName":"Rishabh Ranjan","userId":"14643331064616738605"}},"outputId":"c103564a-6d63-4835-f614-dec76a782dcf"},"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))"],"execution_count":null,"outputs":[{"output_type":"stream","name":"stderr","text":["[nltk_data] Downloading package movie_reviews to /root/nltk_data...\n","[nltk_data]   Unzipping corpora/movie_reviews.zip.\n"]}]},{"cell_type":"markdown","metadata":{"id":"CRaF2A_j_nC7"},"source":["### Your task"]},{"cell_type":"markdown","metadata":{"id":"mrHJptH3Tb-3"},"source":["In this Colab, you will develop a very simplistic spell-checker.  By no means you should 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","metadata":{"id":"bK3WyXaPsa5q"},"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)"],"execution_count":null,"outputs":[]},{"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.11/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.11/library/sys.html#sys.getsizeof) method!\n","\n"]},{"cell_type":"code","metadata":{"id":"FVLxu20maRLf","executionInfo":{"status":"ok","timestamp":1772157701353,"user_tz":480,"elapsed":6,"user":{"displayName":"Rishabh Ranjan","userId":"14643331064616738605"}},"outputId":"f367b021-5b43-4cdc-a8a6-86e09e7c68fb","colab":{"base_uri":"https://localhost:8080/","height":52}},"source":["from sys import getsizeof\n","\n","print(f'Size of word_list (in bytes): {getsizeof(word_list)}')\n","\n","# YOUR CODE HERE\n","''' 1-2 lines of code in total expected but can differ based on your style. '''\n","''' For sub-parts of the question (if any), creating different cells of code would be recommended.'''\n"],"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["Size of word_list (in bytes): 2055512\n"]},{"output_type":"execute_result","data":{"text/plain":["' For sub-parts of the question (if any), creating different cells of code would be recommended.'"],"application/vnd.google.colaboratory.intrinsic+json":{"type":"string"}},"metadata":{},"execution_count":5}]},{"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","metadata":{"id":"xq7I6kJfwXy5","executionInfo":{"status":"ok","timestamp":1772157702376,"user_tz":480,"elapsed":1022,"user":{"displayName":"Rishabh Ranjan","userId":"14643331064616738605"}},"outputId":"78dd676b-0b45-4a76-814a-a3361a96b002","colab":{"base_uri":"https://localhost:8080/","height":52}},"source":["%timeit -r 3 \"California\" in word_list\n","\n","# YOUR CODE HERE\n","''' 2 lines of code in total expected but can differ based on your style. '''\n","\n"],"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["222 µs ± 2.69 µs per loop (mean ± std. dev. of 3 runs, 1000 loops each)\n"]},{"output_type":"execute_result","data":{"text/plain":["' 2 lines of code in total expected but can differ based on your style. '"],"application/vnd.google.colaboratory.intrinsic+json":{"type":"string"}},"metadata":{},"execution_count":6}]},{"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","We 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.\n"]},{"cell_type":"code","metadata":{"id":"lTT-6rQcnibH","executionInfo":{"status":"ok","timestamp":1772157702380,"user_tz":480,"elapsed":3,"user":{"displayName":"Rishabh Ranjan","userId":"14643331064616738605"}},"outputId":"c89bb800-e986-41d6-85ff-ce3bb773abe7","colab":{"base_uri":"https://localhost:8080/","height":35}},"source":["# YOUR CODE HERE\n","''' 5-7 lines of code in total expected for the function but can differ based on your style. '''\n","\n","''' 8-10 lines of code for the tests and errors identification (ref gradescope) '''\n","\n"],"execution_count":null,"outputs":[{"output_type":"execute_result","data":{"text/plain":["' 8-10 lines of code for the tests and errors identification (ref gradescope) '"],"application/vnd.google.colaboratory.intrinsic+json":{"type":"string"}},"metadata":{},"execution_count":7}]},{"cell_type":"markdown","metadata":{"id":"SIrXJyVNP2AI"},"source":["Once you have working code for each cell above, **head over to Gradescope, read carefully the questions, and submit your solution for this Colab**! The error rate should have `len(neg_reviews)` in its denominator. As a sanity check, your answers for 4.2 and 4.4 should be between 20 and 30."]}]}