HW1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Submission instructions\n",
    "\n",
    "In this programming assignment, you will create a simple search engine. More specifically, you will implement an index over a corpus of webpages, and also compress the index using variable length encoding. Both uncompressed and compressed indices will be tested on retrieval with Boolean conjunctive queries. The assignment is object-oriented and relies on python concepts such as functions, files and classes. Our TA, Makanjuola, has compiled a list of tutorials on these concepts:\n",
    "\n",
    "1. A short video: [Learn python in 1 hour](https://www.youtube.com/watch?v=kqtD5dpn9C8)\n",
    "2. [These docs](https://docs.python.org/3.7/reference/datamodel.html#special-method-names) describe special functions such as `__getitem__` , etc. \n",
    "3. This [short tutorial](https://www.omkarpathak.in/2018/04/11/python-getitem-and-setitem/) is also useful to get started with special functions.\n",
    "4. Here is a very helpful tutorial on Python [file handling](https://www.programiz.com/python-programming/file-operation).\n",
    "5. [This youtube video](https://www.youtube.com/watch?v=wfcWRAxRVBA) and [this article](https://www.w3schools.com/python/python_classes.asp) can help get you started with Classes in Python.\n",
    "6. All tutorials (and more) are categorized in this [Google doc](https://docs.google.com/document/d/1Q_aw1bW2Dx3eUMnlQLYl1p8iMyf4lXkBDjNfk688jHw/edit?usp=sharing).\n",
    "\n",
    "The HW is due **Wednesday, September 29, 2021 @ 11:59 pm**. You can form teams of two or work individually. Note that there exists no difference in terms of grading, i.e., we will grade the same for one and two person teams. Only one of the team members needs to submit the HW. \n",
    " \n",
    "\n",
    "Instructions on how to submit will be given soon. We will use an autograding system. Please do **NOT** change class and method names, otherwise autograding will fail. ONLY edit the parts with **\"### Begin your code\"** and **\"### End your code\"** comments. Note that all aspects of this assignment are covered by the [Honor Code](https://graduateschool.vt.edu/content/dam/graduateschool_vt_edu/graduate-honor-system/Constitution2021.pdf) and that the autograding system will also perform screening checks for code similarity. We will also inspect each student's code for implementation correctness. Finally, note that we will increase office hours before the HW deadline."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Declare your teammate here \n",
    "Include the name and email for your team member. If you are working independenty, write \"Myself\"\n",
    "> My teammate for this HW is: Vijay Balaji(dvijay25@vt.edu)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Grading breakdown\n",
    "\n",
    "**Autograder (60%)**: To ensure your indices are built correctly, both the uncompressed and compressed index versions of your implementations will be tested on 20 Boolean conjunctive queries of one or multiple terms. For those queries, you will get 1.5% of the final grade for each query you answer correctly, for a total of 60% of your grade (30% for the compressed index and 30% for the uncompressed index). \n",
    "\n",
    "**Code inspection (40%)**: We will also grade each function implementation individually. The grading breakdown is as follows:\n",
    "1. `IdMap` - 4%\n",
    "2. `BSBIIndex parse_block` - 4%\n",
    "3. `InvertedIndexWriter append` - 2%\n",
    "4. `BSBIIndex invert_write` - 4%\n",
    "5. `InvertedIndexIterator` - 2%\n",
    "6. `BSBIIndex merge` - 4%\n",
    "7. `InvertedIndexMapper _get_postings_list` - 2%\n",
    "8. `sorted_intersect` - 4%\n",
    "9. `BSBIIndex retrieve` - 4%\n",
    "10. `CompressedPostings` - 4%\n",
    "11. Index size & Performance Questions (Q1-Q4) - 1.5% each question, for a total for 6% (4 x 1.5)\n",
    "\n",
    "\n",
    "Finally note that in order to get full score:\n",
    "- The `retrieve` function should NOT load the whole index into memory  but rather load the postings lists of just the query terms.\n",
    "- The `merge` function should NOT load the complete intermediate indices or keep the whole merged index in memory.\n",
    "- The `retrieve` function should order the query terms by postings list length.\n",
    "- Both the `merge` function and the `sorted_intersect` function should NOT use the built in set operations  while merging postings lists or intersecting sorted lists.\n",
    "- Timings for the `retrieve` function should be within a time range. This will be ensured if you do NOT iterate through your index instead of seeking just the query terms, as this will significantly increase the time complexity. \n",
    "- Your compression algorithm should indeed achieve a compressed index, i.e., you should see a significant index size decrease."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's import a few necessary packages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import pickle as pkl\n",
    "import array\n",
    "import os\n",
    "import timeit\n",
    "import contextlib"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Corpus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The corpus you will be working with for this assignment contains webpages from the cs.vt.edu, vt.edu, illinois.edu and cs.illinois.edu domains. The data for this assignment are included as a .zip file. There are 4 sub-directories under the data directory. We will also remove HTML tags so that each webpage is a sequence of space-delimited words. Each consecutive span of non-space characters consists of a word token in the corpus. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0', '1', '2', '3', '4', '5', '6']"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import zipfile\n",
    "\n",
    "data_dir = 'hw1data'\n",
    "zip_ref = zipfile.ZipFile(data_dir+'.zip', 'r')\n",
    "zip_ref.extractall()\n",
    "zip_ref.close()\n",
    "sorted(os.listdir('hw1data'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "0it [00:00, ?it/s]\n",
      "  3%|██▍                                                                               | 3/100 [00:00<00:03, 27.85it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Going over hw1data ...\n",
      "Going over hw1data\\0 ...\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|████████████████████████████████████████████████████████████████████████████████| 100/100 [00:04<00:00, 23.46it/s]\n",
      "  4%|███▎                                                                              | 4/100 [00:00<00:02, 32.34it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Going over hw1data\\1 ...\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|████████████████████████████████████████████████████████████████████████████████| 100/100 [00:03<00:00, 26.98it/s]\n",
      "  4%|███▎                                                                              | 4/100 [00:00<00:02, 37.62it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Going over hw1data\\2 ...\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|████████████████████████████████████████████████████████████████████████████████| 100/100 [00:03<00:00, 28.40it/s]\n",
      "  3%|██▍                                                                               | 3/100 [00:00<00:03, 27.09it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Going over hw1data\\3 ...\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|████████████████████████████████████████████████████████████████████████████████| 100/100 [00:03<00:00, 27.31it/s]\n",
      "  3%|██▍                                                                               | 3/101 [00:00<00:03, 25.28it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Going over hw1data\\4 ...\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|████████████████████████████████████████████████████████████████████████████████| 101/101 [00:04<00:00, 21.05it/s]\n",
      "  4%|███▎                                                                              | 4/100 [00:00<00:03, 31.08it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Going over hw1data\\5 ...\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|████████████████████████████████████████████████████████████████████████████████| 100/100 [00:04<00:00, 23.32it/s]\n",
      "  3%|██▍                                                                               | 3/100 [00:00<00:03, 25.93it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Going over hw1data\\6 ...\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|████████████████████████████████████████████████████████████████████████████████| 100/100 [00:04<00:00, 24.56it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':\n",
      "new date().gettime(),event:'gtm.js'});var f=d.getelementsbytagname(s)[0],\n",
      "j=d.createelement(s),dl=l!='datalayer'?'&l='+l:'';j.async=true;j.src=\n",
      "'//www.googletagmanager.com/gtm.js?id='+i+dl;f.parentnode.insertbefore(j,f);\n",
      "})(window,document,'script','datalayer','gtm-3sqhdc'); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':\n",
      "      new date().gettime(),event:'gtm.js'});var f=d.getelementsbytagname(s)[0],\n",
      "      j=d.createelement(s),dl=l!='datalayer'?'&l='+l:'';j.async=true;j.src=\n",
      "      'https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentnode.insertbefore(j,f);\n",
      "      })(window,document,'script','datalayer','gtm-p6f85q5'); apply | virginia tech skip to main content skip to search virginia techâ® universal access universal access options report a barrier accessibility portal pause all background videos underline all links apply visit give shop hokie gear apparel, clothing, gear and merchandise hokie shop university bookstore, merchandise and gifts hokie license plates part of every virginia tech plate purchase funds scholarships resources for future students current students parents and families faculty and staff alumni industry and partners virginia tech menu virginia tech about facts about virginia tech campus locations university leadership arts@virginiatech history and traditions rankings academics colleges undergraduate majors undergraduate minors graduate school beyond boundaries online learning libraries continuing and professional education summer and winter sessions experiential learning living-learning programs study abroad admissions & aid cost & aid federal cares act reporting disclosure undergraduate admissions applying to virginia tech visit virginia tech transfer admissions international admissions veteran admissions graduate school admissions undergraduate admissions calendar first-generation students first-generation college institute black college institute tribal initiatives frequently asked questions online programs admissions staff site map campus life discover blacksburg housing dining career and professional development health and wellness corps of cadets clubs, organizations, and involvement cultural centers athletics inclusivevt engagement and outreach research apply visit give shop hokie gear apparel, clothing, gear and merchandise hokie shop university bookstore, merchandise and gifts hokie license plates part of every virginia tech plate purchase funds scholarships resources for future students current students parents and families faculty and staff alumni industry and partners search search submit home / apply / explore about academics admissions & aid campus life inclusivevt engagement and outreach research apply ready1 apply ready to apply? choose the experience that you're seeking. apply for undergraduate admission apply to the virginia-maryland college of veterinary medicine apply for graduate school apply to the virginia tech carilion school of medicine get directions see all locations contact virginia tech university status principles of community privacy statement acceptable use we remember university libraries accessibility consumer information stop abuse policies equal opportunity wvtf university bookstore jobs at virginia tech strategic plan â©â 2021 virginia polytechnic institute and state university. all rights reserved.\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "# Strip of HTML tags from all files and lowercase all words. This might take a while.\n",
    "from bs4 import BeautifulSoup\n",
    "from tqdm import tqdm #progress bars\n",
    "\n",
    "new_data_dir = 'hw1dataraw'\n",
    "os.makedirs(new_data_dir, exist_ok=True)\n",
    "\n",
    "def removeTags(soup):\n",
    "    for item in soup.find_all('span', 'sr-only'):\n",
    "        item.decompose()\n",
    "    return soup\n",
    "\n",
    "for (dirpath, dirnames, filenames) in os.walk(data_dir):\n",
    "    print(f'Going over {dirpath} ...')\n",
    "    for filename in tqdm(filenames, total=len(filenames)):\n",
    "        inF = open(os.sep.join([dirpath, filename]),'rb')\n",
    "        soup = BeautifulSoup(inF, features=\"html.parser\")\n",
    "        soup = removeTags(soup)\n",
    "        text = soup.get_text(strip=True, separator = \" \").lower()\n",
    "        newsubdir = dirpath.replace(data_dir, new_data_dir)\n",
    "        os.makedirs(newsubdir, exist_ok=True)\n",
    "        outF = open(os.sep.join([newsubdir, filename]), \"w\")\n",
    "        outF.write(text)\n",
    "        outF.close()\n",
    "        inF.close()\n",
    "\n",
    "data_dir = new_data_dir # point data_dir to the new dir.\n",
    "filename = 'hw1dataraw/6/apply.html'\n",
    "soup = BeautifulSoup(open(filename,'r'), features=\"html.parser\")\n",
    "soup = removeTags(soup)\n",
    "print(soup.get_text(strip=True, separator = \" \").lower()) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will create the directory for where the index will be stored (`index_dir`) and a separate folder `tmp` that will contain some temporary files. A small test corpus in subfolder `testdata` is included in the HW folder, which you can use for code testing purposes, and faster implementation cycles. The index for the `testdata` will be stored in `test_index_dir`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "try: \n",
    "    os.mkdir('index_dir')\n",
    "except FileExistsError:\n",
    "    pass\n",
    "try: \n",
    "    os.mkdir('tmp')\n",
    "except FileExistsError:\n",
    "    pass\n",
    "try: \n",
    "    os.mkdir('test_index_dir')\n",
    "except FileExistsError:\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Build an uncompressed index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first part of this assignment is to build an inverted index of this corpus, and implement Boolean conjunctive queries. **In particular, you need to implement the blocked sort-based indexing (BSBI) algorithm described in [Section 4.2](http://nlp.stanford.edu/IR-book/pdf/04const.pdf) of the textbook.** To fully understand the details of BSBI, we recommend that you read Section 4.2 .\n",
    "\n",
    "> Remember from lectures, to construct an index, first we assemble all term-docID pairs, where each document is represented with a unique serial numbers instead of strings. Then, we sort term-docID pairs by the term and docID. Finally, we organize docIDs for each term into a postings list and compute statistics like term and document frequency. To make the index more efficient, we can also represent terms as termIDs (unique serial numbers instead of strings). The dictionary that maps terms to termIDs can be built on the fly as we are processing the document collection. For small collections, the whole index construction can be done in memory. Here, we will implement large-scale methods that require use of secondary storage (disk)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## IdMap\n",
    "\n",
    "Let us first build a helper class `IdMap`, which maps strings to numeric ids (and vice-versa). This will be useful for mapping terms to termIDs and docs to docIDs. Data structures used include: i) dictionary (from strings to numeric ids) and ii) lists (from numeric ids to strings).\n",
    "\n",
    "\n",
    "In the following code, fill in the functions `_get_str` and `_get_id` . Notice that accessing items can be done by `__getitem__` which gets the correct mapping depending on the type of the key. We will later on incorporate functionality to add a string if it doesn't already exist in the map.   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "class IdMap:\n",
    "    \"\"\"Helper class to store a mapping from strings to ids.\"\"\"\n",
    "    def __init__(self):\n",
    "        self.str_to_id = {}\n",
    "        self.id_to_str = []\n",
    "        \n",
    "    def __len__(self):\n",
    "        \"\"\"Return number of terms stored in the IdMap\"\"\"\n",
    "        return len(self.id_to_str)\n",
    "        \n",
    "    def _get_str(self, i):\n",
    "        \"\"\"Returns the string corresponding to a given id (`i`).\"\"\"\n",
    "        ### Begin your code\n",
    "        return(self.id_to_str[i])\n",
    "        ### End your code\n",
    "        \n",
    "    def _get_id(self, s):\n",
    "        \"\"\"Returns the id corresponding to a string (`s`). \n",
    "        If `s` is not in the IdMap yet, then assigns a new id and returns the new id.\n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "        if(s not in self.str_to_id.keys()):\n",
    "            self.str_to_id[s] =  len(self)\n",
    "            self.id_to_str.append(s)\n",
    "            \n",
    "            \n",
    "        return(self.str_to_id[s])\n",
    "        ### End your code\n",
    "            \n",
    "    def __getitem__(self, key):\n",
    "        \"\"\"If `key` is a integer, use _get_str; \n",
    "           If `key` is a string, use _get_id;\"\"\"\n",
    "        if type(key) is int:\n",
    "            return self._get_str(key)\n",
    "        elif type(key) is str:\n",
    "            return self._get_id(key)\n",
    "        else:\n",
    "            raise TypeError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make sure your code passes the following test cases:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "testIdMap = IdMap()\n",
    "assert testIdMap['a'] == 0, \"Unable to add a new string to the IdMap\"\n",
    "assert testIdMap['bcd'] == 1, \"Unable to add a new string to the IdMap\"\n",
    "assert testIdMap['a'] == 0, \"Unable to retrieve the id of an existing string\"\n",
    "assert testIdMap[1] == 'bcd', \"Unable to retrive the string corresponding to a given id\"\n",
    "try:\n",
    "    testIdMap[2]\n",
    "except IndexError as e:\n",
    "    assert True, \"Doesn't throw an IndexError for out of range numeric ids\"\n",
    "assert len(testIdMap) == 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From now on you can use the `testdata` to write your own test cases, if you want to make sure that your code is working as expected. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Encoding Postings List as bytearrays\n",
    "\n",
    "In order to write and read lists of postings (docIDs) efficiently from the disk, we store them as bytearrays. The provided`UncompressedPostings` class which contains static encode and decode functions. In the next task you'll be required to implement compressed versions with the same inferface. \n",
    "\n",
    "Some links for reference:\n",
    "1. https://docs.python.org/3/library/array.html\n",
    "2. https://pymotw.com/3/array/#module-array\n",
    "3. https://realpython.com/instance-class-and-static-methods-demystified/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UncompressedPostings:\n",
    "    \n",
    "    @staticmethod\n",
    "    def encode(postings_list):\n",
    "        \"\"\"Encodes postings_list into a stream of bytes\n",
    "\n",
    "        Parameters\n",
    "        ----------\n",
    "        postings_list: List[int] of docIDs (postings)\n",
    "            \n",
    "        Returns\n",
    "        -------\n",
    "        bytes: bytearray representing integers in the postings_list\n",
    "        \"\"\"\n",
    "        return array.array('L', postings_list).tobytes()\n",
    "        \n",
    "    @staticmethod\n",
    "    def decode(encoded_postings_list):\n",
    "        \"\"\"Decodes postings_list from a stream of bytes\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        encoded_postings_list: bytearray representing encoded postings list as output by encode function\n",
    "            \n",
    "        Returns\n",
    "        -------\n",
    "        decoded_postings_list: Decoded List[int] of docIDs from encoded_postings_list\n",
    "        \"\"\"\n",
    "        decoded_postings_list = array.array('L')\n",
    "        decoded_postings_list.frombytes(encoded_postings_list)\n",
    "        return decoded_postings_list.tolist()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To illustrate how it works, run the following cell"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'\\x01\\x00\\x00\\x00\\x02\\x00\\x00\\x00\\x03\\x00\\x00\\x00'\n",
      "[1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "x = UncompressedPostings.encode([1,2,3])\n",
    "print(x)\n",
    "print(UncompressedPostings.decode(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Inverted Index on Disk\n",
    "\n",
    "As mentioned in lectures, inverted indices utilize external sorting algorithms (that uses disk). For efficiency, any such sorting algorithm needs to minize the number of random disks seeks, i.e., sequential disk reads are much faster than random seeks.\n",
    "\n",
    "In this section we provide a base class `InvertedIndex` which would be subsequently subclassed into `InvertedIndexWriter`, `InvertedIndexIterator` and `InvertedIndexMapper`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class InvertedIndex:\n",
    "    \"\"\"Implements efficient reads and writes of an inverted index to disk\n",
    "    \n",
    "    Attributes\n",
    "    ----------\n",
    "    postings_dict: Dictionary mapping: termID->(start_position_in_index_file, \n",
    "                                                number_of_postings_in_list,\n",
    "                                                length_in_bytes_of_postings_list)\n",
    "        \n",
    "        This is a dictionary that maps from termIDs to a 3-tuple of metadata that is helpful in reading \n",
    "        and writing the postings in the index file to/from disk. This mapping is supposed to be kept in memory. \n",
    "        \n",
    "        start_position_in_index_file is the position (in bytes) of the postings list in the index file\n",
    "        number_of_postings_in_list is the number of postings (docIDs) in the postings list\n",
    "        length_in_bytes_of_postings_list is the length of the byte encoding of the postings list\n",
    "    \n",
    "    terms: List[int]\n",
    "        A list of termIDs to remember the order in which terms and their postings lists were added to index. \n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self, index_name, postings_encoding=None, directory=''):\n",
    "        \"\"\"\n",
    "        Parameters\n",
    "        ----------\n",
    "        index_name (str): Name used to store files related to the index \n",
    "        postings_encoding: A class implementing static methods for encoding and decoding lists of integers. \n",
    "                           Default is None, which gets replaced with UncompressedPostings\n",
    "        directory (str): Directory where the index files will be stored\n",
    "        \"\"\"\n",
    "        self.index_file_path = os.path.join(directory, index_name+'.index')\n",
    "        self.metadata_file_path = os.path.join(directory, index_name+'.dict')\n",
    "        if postings_encoding is None:\n",
    "            self.postings_encoding = UncompressedPostings\n",
    "        else:\n",
    "            self.postings_encoding = postings_encoding\n",
    "        self.directory = directory\n",
    "        self.postings_dict = {}\n",
    "        self.terms = []         \n",
    "\n",
    "    def __enter__(self):\n",
    "        \"\"\"Opens the index_file and loads metadata upon entering the context\"\"\"\n",
    "        # Open the index file\n",
    "        self.index_file = open(self.index_file_path, 'rb+')\n",
    "        # Load the postings dict and terms from the metadata file\n",
    "        with open(self.metadata_file_path, 'rb') as f:\n",
    "            self.postings_dict, self.terms = pkl.load(f)\n",
    "            self.term_iter = self.terms.__iter__()                       \n",
    "        return self\n",
    "    \n",
    "    def __exit__(self, exception_type, exception_value, traceback):\n",
    "        \"\"\"Closes the index_file and saves metadata upon exiting the context\"\"\"\n",
    "        # Close the index file\n",
    "        self.index_file.close()\n",
    "        # Write the postings dict and terms to the metadata file\n",
    "        with open(self.metadata_file_path, 'wb') as f:\n",
    "            pkl.dump([self.postings_dict, self.terms], f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that `__enter__` and `__exit__` functions make `InvertedIndexWriter` a [context manager](https://docs.python.org/3/library/contextlib.html) that allows using the `with` statement just like native file I/O in python. \n",
    "\n",
    "```python\n",
    "with InvertedIndexWriter('test', directory='tmp/') as index:\n",
    "    # Some code here\n",
    "```\n",
    "\n",
    "Additional references on context managers in python (although thorough understanding is not neeed for this HW):\n",
    "1. https://jeffknupp.com/blog/2016/03/07/python-with-context-managers/\n",
    "2. http://arnavk.com/posts/python-context-managers/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Indexing\n",
    "\n",
    "BSBI segments the collection into blocks of equal size, sorts the termID-docID pairs of each part in memory, and stores intermediate sorted results on disk. Finally, all intermediate results are merged as the final index. \n",
    "\n",
    "Here, we treat each sub-directory as a block, i.e.,  small enough to be stored in memory, and only load one block in memory at a time when we build the index. We will build upon the `BSBIIndex` class. The `index` function provides the skeleton for BSBI. \n",
    "\n",
    "The next HW task is to implement `parse_block`, `invert_write` and `merge` functions in the subsequent sections."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSBIIndex:\n",
    "    \"\"\" \n",
    "    Attributes\n",
    "    ----------\n",
    "    term_id_map(IdMap): For mapping terms to termIDs\n",
    "    doc_id_map(IdMap): For mapping relative paths of documents to docIDs\n",
    "    data_dir(str): Path to data\n",
    "    output_dir(str): Path to output index files\n",
    "    index_name(str): Name assigned to index\n",
    "    postings_encoding: Encoding used for storing the postings. The default (None) implies UncompressedPostings\n",
    "    \"\"\"\n",
    "    def __init__(self, data_dir, output_dir, index_name = \"BSBI\", postings_encoding = None):\n",
    "        self.term_id_map = IdMap()\n",
    "        self.doc_id_map = IdMap()\n",
    "        self.data_dir = data_dir\n",
    "        self.output_dir = output_dir\n",
    "        self.index_name = index_name\n",
    "        self.postings_encoding = postings_encoding\n",
    "        # Stores names of intermediate indices\n",
    "        self.intermediate_indices = []\n",
    "        \n",
    "    def save(self):\n",
    "        \"\"\"Dumps doc_id_map and term_id_map into output directory\"\"\"\n",
    "        with open(os.path.join(self.output_dir, 'terms.dict'), 'wb') as f:\n",
    "            pkl.dump(self.term_id_map, f)\n",
    "        with open(os.path.join(self.output_dir, 'docs.dict'), 'wb') as f:\n",
    "            pkl.dump(self.doc_id_map, f)\n",
    "    \n",
    "    def load(self):\n",
    "        \"\"\"Loads doc_id_map and term_id_map from output directory\"\"\"\n",
    "        with open(os.path.join(self.output_dir, 'terms.dict'), 'rb') as f:\n",
    "            self.term_id_map = pkl.load(f)\n",
    "        with open(os.path.join(self.output_dir, 'docs.dict'), 'rb') as f:\n",
    "            self.doc_id_map = pkl.load(f)\n",
    "            \n",
    "    def index(self):\n",
    "        \"\"\"\n",
    "        This function loops through the data directories, calls parse_block to parse the documents, \n",
    "        calls invert_write, which inverts each block and writes to a new index and then saves the \n",
    "        id maps and calls merge on the intermediate indices.\n",
    "        \"\"\"\n",
    "        for block_dir_relative in sorted(next(os.walk(self.data_dir))[1]):\n",
    "            td_pairs = self.parse_block(str(block_dir_relative))\n",
    "            index_id = 'index_'+block_dir_relative\n",
    "            self.intermediate_indices.append(index_id)\n",
    "            with InvertedIndexWriter(index_id, directory=self.output_dir, \n",
    "                                     postings_encoding=self.postings_encoding) as index:\n",
    "                self.invert_write(td_pairs, index)\n",
    "                td_pairs = None\n",
    "        self.save()\n",
    "        with InvertedIndexWriter(self.index_name, directory=self.output_dir, \n",
    "                                 postings_encoding=self.postings_encoding) as merged_index:\n",
    "            with contextlib.ExitStack() as stack:\n",
    "                indices = [stack.enter_context(InvertedIndexIterator(index_id, directory=self.output_dir, \n",
    "                                          postings_encoding=self.postings_encoding)) \n",
    "                 for index_id in self.intermediate_indices]\n",
    "                self.merge(indices, merged_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Parsing\n",
    "\n",
    "The function `parse_block` parses documents into termID-docID pairs and accumulates the pairs in memory until a block of a fixed size is full. Here, we treat each sub-directory as a block (`parse_block` expects the path to the sub-directory). You can assume that the full path of the files are unique. That means that while the individual file names are unique within each sub-directory, this may not necessarily be the case across sub-directories. \n",
    "\n",
    "*Disclaimer: it may seem that `BSBIIndex` inherits `BSBIIndex` (same class), but this is just a convenient way to split class definitions into two parts, such that we can add a new method to an existing class. This note is to avoid confusion on how we used the same name for two classes.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSBIIndex(BSBIIndex):            \n",
    "    def parse_block(self, block_dir_relative):\n",
    "        \"\"\"Parses a tokenized text file into termID-docID pairs\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        block_dir_relative : str Relative Path to the directory that contains the files for the block\n",
    "        \n",
    "        Returns\n",
    "        -------\n",
    "        parseLst: List[Tuple[Int, Int]] \n",
    "        Returns all the termID-docID pairs extracted from the block\n",
    "        Should use self.term_id_map and self.doc_id_map to get termIDs and docIDs.\n",
    "        These persist across calls to parse_block\n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "#         self.parseLst = []\n",
    "#         self.save()\n",
    "#         self.load()\n",
    "#         path = self.data_dir+'/'+block_dir_relative\n",
    "#         for file in os.listdir(path):\n",
    "#             f = open(path+\"/\"+file,'r')\n",
    "#             docId = self.doc_id_map[file]\n",
    "#             print(f)\n",
    "#             for line in f:\n",
    "#                 arr = line.split()\n",
    "#                 for i in range(len(arr)):\n",
    "#                     termId = self.term_id_map[arr[i]]\n",
    "#                     self.parseLst.append((termId,docId))\n",
    "#         return(self.parseLst)\n",
    "    \n",
    "        self.parseLst = []\n",
    "        lis = sorted(os.listdir(os.path.join(self.data_dir, block_dir_relative)))\n",
    "        for file_dir in lis:\n",
    "            with open(os.path.join(self.data_dir, block_dir_relative, file_dir), 'r',encoding=\"utf-8\") as f:\n",
    "                content = f.read()\n",
    "                content = content.strip().split() \n",
    "                file = os.path.join(block_dir_relative, file_dir)\n",
    "                doc_id = self.doc_id_map[file]\n",
    "                for token in content:\n",
    "                    term_id = self.term_id_map[token]\n",
    "                    self.parseLst.append([term_id, doc_id])\n",
    "        return self.parseLst\n",
    "        ### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See if the function works as expected on the toy data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i'm fine , thank you\n",
      "\n",
      "hi hi\n",
      "how are you ?\n",
      "\n"
     ]
    }
   ],
   "source": [
    "with open('testdata/0/fine.txt', 'r') as f:\n",
    "    print(f.read())\n",
    "with open('testdata/0/hello.txt', 'r') as f:\n",
    "    print(f.read())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [5, 1], [5, 1], [6, 1], [7, 1], [4, 1], [8, 1]]\n",
      "[[0, 0], [1, 0], [2, 0], [3, 0], [4, 0], [5, 1], [5, 1], [6, 1], [7, 1], [4, 1], [8, 1]]\n"
     ]
    }
   ],
   "source": [
    "BSBI_instance = BSBIIndex(data_dir='testdata', output_dir = 'tmp/', index_name = 'test')\n",
    "print(BSBI_instance.parse_block('0'))\n",
    "print(BSBI_instance.parseLst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Does `parse_block` work as expected on a block of the `testdata`? \n",
    "Write a test to make sure that a given word gets the same id each time it appears."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "### Begin your code\n",
    "assert BSBI_instance.parse_block('0') == BSBI_instance.parse_block('0')\n",
    "assert BSBI_instance.parseLst == BSBI_instance.parse_block('0')\n",
    "### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Inversion\n",
    "\n",
    "However, we first implement the class `InvertedIndexWriter`, which provides an append function, just like appending to a list, with the difference that the postings_list isn't stored in memory but is directly written to disk. Next, we will add a function `invert_write` that inverts a block and writes it to disk. Inversion involves first sorting the termID-docID pairs and then collect all of pairs with the same termID into a postings list, where a posting is simply a docID. The result is an inverted index for the block, which is finally written to disk. You might find it helpful to read the [Python I/O docs](https://docs.python.org/3/tutorial/inputoutput.html) for information about appending to the end of a file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "class InvertedIndexWriter(InvertedIndex):\n",
    "    \"\"\"\"\"\"\n",
    "    def __enter__(self):\n",
    "        self.index_file = open(self.index_file_path, 'wb+')\n",
    "        return self\n",
    "\n",
    "    def append(self, term, postings_list):\n",
    "        \"\"\"Appends the term and postings_list to end of the index file.\n",
    "        \n",
    "        This function should:\n",
    "        1. Encode the postings_list using self.postings_encoding\n",
    "        2. Store metadata in the form of self.terms and self.postings_dict\n",
    "           Note that self.postings_dict maps termID to a tuple of \n",
    "           (start_position_in_index_file, number_of_postings_in_list, length_in_bytes_of_postings_list)\n",
    "        3. Appends the bytestream to the index file on disk\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        term: term or termID is the unique identifier for the term\n",
    "        postings_list: List[Int] of docIDs where the term appears\n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "        b = self.postings_encoding.encode(postings_list)\n",
    "        self.terms.append(term)\n",
    "        x = len(self.index_file.read())\n",
    "        y = len(postings_list)\n",
    "        z = len(b)\n",
    "        self.postings_dict[term] = (x,y,z)\n",
    "        self.index_file.write(b)\n",
    "        self.index_file.flush()\n",
    "        self.index_file.seek(0)\n",
    "        #print(self.postings_dict)\n",
    "        ### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make sure you pass the following asserts before moving forward:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "with InvertedIndexWriter('test', directory='tmp/') as index:\n",
    "    index.append(1, [2, 3, 4])\n",
    "    index.append(2, [3, 4, 5])\n",
    "    index.index_file.seek(0)\n",
    "    assert index.terms == [1,2], \"terms sequence incorrect\"\n",
    "    assert index.postings_dict == {1: (0, 3, len(UncompressedPostings.encode([2,3,4]))), \n",
    "                                   2: (len(UncompressedPostings.encode([2,3,4])), 3, \n",
    "                                       len(UncompressedPostings.encode([3,4,5])))}, \"postings_dict incorrect\"\n",
    "    assert UncompressedPostings.decode(index.index_file.read()) == [2, 3, 4, 3, 4, 5], \"postings on disk incorrect\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will implement `invert_write`, which takes as input the termID-docID pairs created with parse_block and writes them to the given index directory, by using `InvertedIndexWriter` to write to disk."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b''\n"
     ]
    }
   ],
   "source": [
    "with InvertedIndexWriter('test', directory='tmp/') as index:\n",
    "    print((index.index_file.read()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "class BSBIIndex(BSBIIndex):\n",
    "    def invert_write(self, td_pairs, index):\n",
    "        \"\"\"Inverts termID-docID pairs into postings_lists and writes them to the given index\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        td_pairs: List[Tuple[Int, Int]]  (List of termID-docID pairs)\n",
    "        index: InvertedIndexWriter  (Inverted index on disk corresponding to the block)   \n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "        td_dict = defaultdict(list)\n",
    "        for t, d in td_pairs:\n",
    "            td_dict[t].append(d)\n",
    "        for t in sorted(td_dict.keys()):\n",
    "            lis = sorted(td_dict[t])\n",
    "            index.append(t, lis)\n",
    "        ### End your code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write some tests as you did for the `InvertedIndexWriter`, to test this on a block of the `testdata` (using the `tmp` directory) and see what the inverted index contains. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Begin your code\n",
    "BSBI_instance = BSBIIndex(data_dir='testdata', output_dir = 'tmp/', index_name = 'toy_2')\n",
    "with InvertedIndexWriter('toy_2', directory='tmp/') as index:\n",
    "    test_pair = [[2,3], [2,5], [1,2], [1,4], [1,3], [2,4]]\n",
    "    BSBI_instance.invert_write(test_pair, index)\n",
    "    index.index_file.seek(0)\n",
    "    assert index.terms == [1,2], \"terms sequence incorrect\"\n",
    "    assert index.postings_dict == {1: (0, 3, len(UncompressedPostings.encode([2,3,4]))), \n",
    "                                   2: (len(UncompressedPostings.encode([2,3,4])), 3, \n",
    "                                       len(UncompressedPostings.encode([3,4,5])))}, \"postings_dict incorrect\"\n",
    "    assert UncompressedPostings.decode(index.index_file.read()) == [2, 3, 4, 3, 4, 5], \"postings on disk incorrect\"\n",
    "### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Merging\n",
    "\n",
    "Now we need to merge the ten blocks into one large merged index. We open all block files simultaneously, and maintain small read buffers for the ten blocks we are reading and a write buffer for the final merged index we are writing. We can iterate through the file while reading just one postings list at a time from the disk. We subclass `InvertedIndex` into `InvertedIndexIterator` to construct this iterator. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "class InvertedIndexIterator(InvertedIndex):\n",
    "    \"\"\"\"\"\"\n",
    "    def __enter__(self):\n",
    "        \"\"\"Adds an initialization_hook to the __enter__ function of super class\n",
    "        \"\"\"\n",
    "        super().__enter__()\n",
    "        self._initialization_hook()\n",
    "        return self\n",
    "\n",
    "    def _initialization_hook(self):\n",
    "        \"\"\"Use this function to initialize the iterator\n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "        self.curr_term_pos = 0\n",
    "        ### End your code\n",
    "\n",
    "    def __iter__(self): \n",
    "        return self\n",
    "    \n",
    "    def __next__(self):\n",
    "        \"\"\"Returns the next (term, postings_list) pair in the index.\n",
    "        Note: This function should only read a small amount of data from the index file. \n",
    "        In particular, you should not try to maintain the full index file in memory.\n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "        if self.curr_term_pos < len(self.terms):\n",
    "            term = self.terms[self.curr_term_pos]\n",
    "            self.curr_term_pos += 1\n",
    "            start_position, n_postings, length_in_bytes = self.postings_dict[term]\n",
    "            self.index_file.seek(start_position)\n",
    "            postings_list = self.postings_encoding.decode(self.index_file.read(length_in_bytes))\n",
    "            return term, postings_list\n",
    "        else:\n",
    "            raise StopIteration\n",
    "        ### End your code\n",
    "\n",
    "    def delete_from_disk(self):\n",
    "        \"\"\"Marks the index for deletion upon exit. Useful for temporary indices\n",
    "        \"\"\"\n",
    "        self.delete_upon_exit = True\n",
    "\n",
    "    def __exit__(self, exception_type, exception_value, traceback):\n",
    "        \"\"\"Delete the index file upon exiting the context along with the \n",
    "        functions of the super class __exit__ function\"\"\"\n",
    "        self.index_file.close()\n",
    "        if hasattr(self, 'delete_upon_exit') and self.delete_upon_exit:\n",
    "            os.remove(self.index_file_path)\n",
    "            os.remove(self.metadata_file_path)\n",
    "        else:\n",
    "            with open(self.metadata_file_path, 'wb') as f:\n",
    "                pkl.dump([self.postings_dict, self.terms], f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's test this. Write a test that constructs a small inverted index, writes them to disk (in `tmp` folder) with an `InvertedIndexWriter`, then uses an `InvertedIndexIterator` to iterate over the inverted index."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Begin your code\n",
    "with InvertedIndexWriter('a3', directory='tmp/') as index:\n",
    "    index.append(1, [2, 3, 4])\n",
    "    index.append(2, [3, 4, 5])\n",
    "with InvertedIndexIterator('a3', directory='tmp/') as index:\n",
    "    assert next(index) == (1, [2, 3, 4])\n",
    "    assert next(index) == (2, [3, 4, 5])\n",
    "### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "During merging, in each iteration, we select the lowest termID that has not been processed yet (using a priority queue or a similar data structure). All postings lists for this termID are read and merged, and the merged list is written back to disk. Each read buffer is refilled from its file when necessary. We'll use the `InvertedIndexIterator` to do the reading part and `InvertedIndexWriter` to write the merged postings list. \n",
    "\n",
    "Your task is to write the logic for merging *opened* `InvertedIndexIterator` objects and writing one postings list at a time into into a single `InvertedIndexWriter` object. \n",
    "\n",
    "Since we know that the postings are sorted, we can appropriately merge them in sorted order in linear time. In fact `heapq` ([documentation](https://docs.python.org/3.0/library/heapq.html)) is a standard python module that provides an implementation of the heap queue algorithm. In particular it contains a `heapq.merge` utility function which merges multiple sorted inputs into a single sorted output and returns an iterator over the sorted values. Not only can this be handy with merging postings lists, but also with merging the inverted indices. To get you started on using the `heapq.merge` function, we've provided a sample usage of the function. The two lists contain animals/birds sorted by their average life span. We want to merge the two lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('Giraffe', 28)\n",
      "('Rhinoceros', 40)\n",
      "('Gray Birch', 50)\n",
      "('Indian Elephant', 70)\n",
      "('Black Willow', 70)\n",
      "('Golden Eagle', 80)\n",
      "('Basswood', 100)\n",
      "('Bald Cypress', 600)\n"
     ]
    }
   ],
   "source": [
    "import heapq\n",
    "animal_lifespans = [('Giraffe', 28), ('Rhinoceros', 40), ('Indian Elephant', 70), ('Golden Eagle', 80)]\n",
    "tree_lifespans = [('Gray Birch', 50), ('Black Willow', 70), ('Basswood', 100), ('Bald Cypress', 600)]\n",
    "lifespan_lists = [animal_lifespans, tree_lifespans]\n",
    "for merged_item in heapq.merge(*lifespan_lists, key=lambda x: x[1]):\n",
    "    print(merged_item)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice the use of `*` to unpack `lifespan_lists` as arguments and the `lambda` function to represent the key based on which sorting is performed. \n",
    "\n",
    "We list here some references and tutorials:\n",
    "1. Unpacking lists [python documentation](https://docs.python.org/3/tutorial/controlflow.html#unpacking-argument-lists) and a [tutorial](https://www.geeksforgeeks.org/packing-and-unpacking-arguments-in-python/)\n",
    "2. Lambda expressions [python documentation](https://docs.python.org/3/tutorial/controlflow.html#lambda-expressions) and a [tutorial](https://www.afternerd.com/blog/python-lambdas/)\n",
    "\n",
    "Now complete the `merge` function below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "class BSBIIndex(BSBIIndex):\n",
    "    def merge(self, indices, merged_index):\n",
    "        \"\"\"Merges multiple inverted indices into a single index\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        indices: List[InvertedIndexIterator]\n",
    "            A list of InvertedIndexIterator objects, each representing an iterable inverted index for a block\n",
    "        merged_index: InvertedIndexWriter\n",
    "            An instance of InvertedIndexWriter into which each merged postings list is written out one at a time\n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "        last_term = last_posting = None\n",
    "        for current, currentP in heapq.merge(*indices):\n",
    "            if(current != last_term):\n",
    "                if last_term:\n",
    "                    last_posting = list(sorted(set(last_posting)))\n",
    "                    merged_index.append(last_term, last_posting)\n",
    "                last_term = current\n",
    "                last_posting = currentP\n",
    "            else:\n",
    "                last_posting += currentP\n",
    "        if(last_term):\n",
    "            last_posting = list(sorted(set(last_posting)))\n",
    "            merged_index.append(last_term, last_posting) \n",
    "        ### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Make sure it works without errors on `testdata` (using `test_index_dir` as output directory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "BSBI_instance = BSBIIndex(data_dir='testdata', output_dir = 'test_index_dir/' , index_name = 'test')\n",
    "BSBI_instance.index()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now lets index the full corpus (using `index_dir` as output directory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "BSBI_instance = BSBIIndex(data_dir=data_dir, output_dir = 'index_dir', )\n",
    "BSBI_instance.index()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you face any issues or errors with the merging part, use the following code to debug it. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "BSBI_instance = BSBIIndex(data_dir=data_dir, output_dir = 'index_dir', )\n",
    "BSBI_instance.intermediate_indices = [f'index_{i}' for i in os.listdir(data_dir)]\n",
    "with InvertedIndexWriter(BSBI_instance.index_name, directory=BSBI_instance.output_dir, postings_encoding=BSBI_instance.postings_encoding) as merged_index:\n",
    "    with contextlib.ExitStack() as stack:\n",
    "        indices = [stack.enter_context(InvertedIndexIterator(index_id, directory=BSBI_instance.output_dir, postings_encoding=BSBI_instance.postings_encoding)) for index_id in BSBI_instance.intermediate_indices]\n",
    "        BSBI_instance.merge(indices, merged_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Boolean conjunctive retrieval\n",
    "\n",
    "Your task here is to implement a function `retrieve` to BSBIIndex, which given a query string consisting of space-delimited tokens, returns a list of documents that contain each of the tokens in the query. However, note that we do not want to be iterating through the index, nor loading the entire index to find the relevant terms. First we'll implement `InvertedIndexMapper` which subclasses `InvertedIndex` to add functionality for retrieving postings corresponding to a particular term by seeking to that location in the file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "class InvertedIndexMapper(InvertedIndex):\n",
    "    def __getitem__(self, key):\n",
    "        return self._get_postings_list(key)\n",
    "    \n",
    "    def _get_postings_list(self, term):\n",
    "        \"\"\"Gets a postings list (of docIds) for `term`. This function SHOULD NOT iterate through the index file, \n",
    "        but instead read only the bytes from the index file corresponding to the postings list for the requested term.\n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "        start_position, n_postings, length_in_bytes = self.postings_dict[term]\n",
    "        self.index_file.seek(start_position)\n",
    "        return self.postings_encoding.decode(self.index_file.read(length_in_bytes))\n",
    "        ### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a few tests to check your `_get_postings_list` implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Begin your code\n",
    "with InvertedIndexMapper('a3', directory='tmp/') as mapper:\n",
    "    assert mapper[1] == [2,3,4]\n",
    "### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now obtain postings lists corresponding to the query terms, but to create a boolean query, we need to intersect them. We can use the fact that these lists are pre-sorted to intersect them efficiently. \n",
    "\n",
    "Your next task is to implement the `sorted_intersect` function that takes two sorted lists and returns a sorted intersection of the elements.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sorted_intersect(list1, list2):\n",
    "    \"\"\"Intersects two (ascending) sorted lists and returns the sorted result\n",
    "    \n",
    "    Parameters\n",
    "    ----------\n",
    "    list1: List[Comparable]\n",
    "    list2: List[Comparable]\n",
    "    Sorted lists to be intersected\n",
    "        \n",
    "    Returns\n",
    "    -------\n",
    "    List[Comparable] Sorted intersection        \n",
    "    \"\"\"\n",
    "    ### Begin your code\n",
    "    i,j = 0,0\n",
    "    intersect = []\n",
    "    while i < len(list1) and j < len(list2):\n",
    "        if list1[i] < list2[j]:\n",
    "            i += 1\n",
    "        elif list2[j] < list1[i]:\n",
    "            j += 1\n",
    "        else:\n",
    "            intersect.append(list1[i])\n",
    "            i += 1\n",
    "            j += 1\n",
    "    return intersect\n",
    "    ### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also write a few test cases to check that it works properly"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Begin your code\n",
    "l1 = [2,3,4,5,6,7,9]\n",
    "l2 = [1,2,5,6,8,10]\n",
    "assert sorted_intersect(l1, l2) == [2,5,6]\n",
    "### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, the task is to write the `retrieve` function using `InvertedIndexMapper` and `sorted_intersect`.\n",
    "Note that `retrieve` should NOT throw errors for terms not in corpus. You can take a look at exception handling in python [here](https://docs.python.org/3/tutorial/errors.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSBIIndex(BSBIIndex):\n",
    "    def retrieve(self, query):\n",
    "        \"\"\"Retrieves the documents corresponding to the conjunctive query\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        query: str  Space separated list of query tokens\n",
    "            \n",
    "        Result\n",
    "        ------\n",
    "        List[str] Sorted list of documents which contains each of the query tokens. \n",
    "        Should be empty if no documents are found. Should NOT throw errors for terms not in corpus\n",
    "        \"\"\"\n",
    "        if len(self.term_id_map) == 0 or len(self.doc_id_map) == 0:\n",
    "            self.load()\n",
    "\n",
    "        ### Begin your code\n",
    "        with InvertedIndexMapper(self.index_name, directory=self.output_dir, \n",
    "                                 postings_encoding=\n",
    "                                 self.postings_encoding) as mapper:\n",
    "            result = None\n",
    "            for term in query.split():\n",
    "                term_id = self.term_id_map.str_to_id.get(term)\n",
    "                if not term_id:\n",
    "                    return []\n",
    "                r = mapper[term_id]\n",
    "                if result is None:\n",
    "                    result = r\n",
    "                else:\n",
    "                    result = sorted_intersect(result, r)\n",
    "        return [self.doc_id_map[r] for r in result]\n",
    "        ### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us test if our index works on the real corpus with a simple query"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0\\\\CI-Fellowships-2021-support-postdoc-research',\n",
       " '0\\\\Chowdhary-2021-Illinois-Innovtion-Network-Award',\n",
       " '0\\\\andreask',\n",
       " '0\\\\angrave',\n",
       " '0\\\\application-checklist',\n",
       " '0\\\\application-deadlines',\n",
       " '0\\\\application-fee-waivers',\n",
       " '0\\\\architecture-compilers-and-parallel-computing',\n",
       " '0\\\\arindamb',\n",
       " '0\\\\artificial-intelligence',\n",
       " '0\\\\batesa',\n",
       " '0\\\\bcosman',\n",
       " '0\\\\best-papers-roundup-August-2021',\n",
       " '0\\\\bigdog',\n",
       " '0\\\\bioinformatics-and-computational-biology',\n",
       " '0\\\\bpbailey',\n",
       " '0\\\\bs-computer-science',\n",
       " '0\\\\bs-mathematics-computer-science',\n",
       " '0\\\\bs-statistics-computer-science',\n",
       " '0\\\\business-office',\n",
       " '0\\\\c-gear',\n",
       " '0\\\\ca-training',\n",
       " '0\\\\caesar',\n",
       " '0\\\\camillec',\n",
       " '0\\\\campus-master-computer-science',\n",
       " '0\\\\career-services',\n",
       " '0\\\\celebration',\n",
       " '0\\\\cgunter',\n",
       " '0\\\\chackoge',\n",
       " '0\\\\chairs-and-professorships',\n",
       " '0\\\\challen',\n",
       " '0\\\\charithm',\n",
       " '0\\\\chekuri',\n",
       " '0\\\\choose-illinois-computer-science',\n",
       " '0\\\\clblake',\n",
       " '0\\\\colleenl',\n",
       " '0\\\\communications-engagement-team',\n",
       " '0\\\\computer-science-advertising',\n",
       " '0\\\\computer-science-animal-sciences',\n",
       " '0\\\\computer-science-anthropology',\n",
       " '0\\\\computer-science-astronomy',\n",
       " '0\\\\computer-science-chemistry',\n",
       " '0\\\\computer-science-crop-sciences',\n",
       " '0\\\\computer-science-economics',\n",
       " '0\\\\computer-science-geography',\n",
       " '0\\\\computer-science-linguistics',\n",
       " '0\\\\computer-science-music',\n",
       " '0\\\\computer-science-philosophy',\n",
       " '0\\\\computer-science-visionary-scholarship-donors',\n",
       " '0\\\\computers-and-education',\n",
       " '0\\\\conferences-workshops',\n",
       " '0\\\\contact',\n",
       " '0\\\\contact-us',\n",
       " '0\\\\course-hero-acquires-iconic-study-guides-cliffsnotes',\n",
       " '0\\\\courses',\n",
       " '0\\\\covid-19-projects',\n",
       " '0\\\\cs-student-opportunity-series-cs-sos',\n",
       " '0\\\\cs-undergraduate-degree-options-faq',\n",
       " '0\\\\cs-x-degree-requirements',\n",
       " '0\\\\csambassadors',\n",
       " '0\\\\cskickstart',\n",
       " '0\\\\daf',\n",
       " '0\\\\dakshita',\n",
       " '0\\\\data-and-information-systems',\n",
       " '0\\\\data-structures-proficiency-exam',\n",
       " '0\\\\davis68',\n",
       " '0\\\\dchen',\n",
       " '0\\\\delgosha',\n",
       " '0\\\\department-college-and-campus-events',\n",
       " '0\\\\department-faculty',\n",
       " '0\\\\department-news',\n",
       " '0\\\\dhoiem',\n",
       " '0\\\\dmnicol',\n",
       " '0\\\\donnacox',\n",
       " '0\\\\donor-profiles',\n",
       " '0\\\\dskatz',\n",
       " '0\\\\e-news',\n",
       " '0\\\\egunter',\n",
       " '0\\\\emer-kuck',\n",
       " '0\\\\emeritus-faculty',\n",
       " '0\\\\epi-exam-requirements',\n",
       " '0\\\\eshwar',\n",
       " '0\\\\facebooks-northwest-lead-envisions-big-future-in-virtual-reality',\n",
       " '0\\\\facilities-shipping-and-receiving',\n",
       " '0\\\\faculty-positions',\n",
       " '0\\\\faculty-support-contacts',\n",
       " '0\\\\featured-lectures',\n",
       " '0\\\\features',\n",
       " '0\\\\final-exam-thesis-defense',\n",
       " '0\\\\financial-aid',\n",
       " '0\\\\friedman',\n",
       " '0\\\\gdallen',\n",
       " '0\\\\gerard-salton-award-provides-opportunity-for-zhai-to-reflect-before-looking-forward-again',\n",
       " '0\\\\ghose',\n",
       " '0\\\\girishc',\n",
       " '0\\\\girju',\n",
       " '0\\\\give-now',\n",
       " '0\\\\glherman',\n",
       " '0\\\\governance',\n",
       " '0\\\\graduate-advising-contacts',\n",
       " '1\\\\5-year-bs-mcs-program',\n",
       " '1\\\\5-year-bs-ms-program',\n",
       " '1\\\\abdelzaher-leading-DARPA-effort-understand-how-people-respond-influence-messaging',\n",
       " '1\\\\accreditation',\n",
       " '1\\\\additional-required-application-materials',\n",
       " '1\\\\adjunct-faculty',\n",
       " '1\\\\affiliate-faculty',\n",
       " '1\\\\agha',\n",
       " '1\\\\ai4all',\n",
       " '1\\\\alawini',\n",
       " '1\\\\alumni-awards-past-recipients',\n",
       " '1\\\\kkhauser',\n",
       " '1\\\\klara',\n",
       " '1\\\\klevchen',\n",
       " '1\\\\lavalle',\n",
       " '1\\\\lawrie',\n",
       " '1\\\\lbo',\n",
       " '1\\\\lgui',\n",
       " '1\\\\loars-passion-for-expanding-possibilities-in-computing-leads-to-support-of-ican',\n",
       " '1\\\\ludaesch',\n",
       " '1\\\\lukeo',\n",
       " '1\\\\lumetta',\n",
       " '1\\\\maa',\n",
       " '1\\\\marinov',\n",
       " '1\\\\mattox',\n",
       " '1\\\\mchenry',\n",
       " '1\\\\mcs-campus',\n",
       " '1\\\\mdbailey',\n",
       " '1\\\\media-coverage',\n",
       " '1\\\\members',\n",
       " '1\\\\meseguer',\n",
       " '1\\\\mgolpar',\n",
       " '1\\\\mickunas',\n",
       " '1\\\\miforbes',\n",
       " '1\\\\milenkov',\n",
       " '1\\\\minhdo',\n",
       " '1\\\\minor-computer-science',\n",
       " '1\\\\misailo',\n",
       " '1\\\\mitras',\n",
       " '1\\\\mnowak1',\n",
       " '1\\\\moralesa',\n",
       " '1\\\\mrebl',\n",
       " '1\\\\ms-bioinformatics-program',\n",
       " '1\\\\ms-general',\n",
       " '1\\\\ms-program',\n",
       " '1\\\\nagi',\n",
       " '1\\\\namato',\n",
       " '1\\\\nanjiang',\n",
       " '1\\\\national-international-awards',\n",
       " '1\\\\new-grant-helps-illinois-cs-develop-programs-to-support-undergraduate-women-in-cs',\n",
       " '1\\\\nikita',\n",
       " '1\\\\nskim',\n",
       " '1\\\\office-department-head',\n",
       " '1\\\\official-forms',\n",
       " '1\\\\online-master-computer-science',\n",
       " '1\\\\online-master-computer-science-data-science',\n",
       " '1\\\\online-mcs-faqs',\n",
       " '1\\\\overview-cs-student-life',\n",
       " '1\\\\padua',\n",
       " '1\\\\pbg',\n",
       " '1\\\\phd-general',\n",
       " '1\\\\phd-ms-thesis-format-review-guidelines',\n",
       " '1\\\\phd-program-study-process',\n",
       " '1\\\\phd-requirements',\n",
       " '1\\\\phd-time-limits-milestones',\n",
       " '1\\\\policies-and-procedures',\n",
       " '1\\\\postdocs',\n",
       " '1\\\\postdoctoral',\n",
       " '1\\\\preliminary-exam',\n",
       " '1\\\\professional-master-computer-science-mcs-program',\n",
       " '1\\\\programming-languages-formal-methods-and-software-engineering',\n",
       " '1\\\\qualifying-exam',\n",
       " '1\\\\radhikam',\n",
       " '1\\\\rakeshk',\n",
       " '1\\\\ranjitha',\n",
       " '1\\\\rcunnin2',\n",
       " '1\\\\recent-phd-alumni',\n",
       " '1\\\\reconstruct-raises-series-b-advance-construction-management',\n",
       " '1\\\\resources',\n",
       " '1\\\\reyhaneh',\n",
       " '1\\\\rhc',\n",
       " '1\\\\rhk',\n",
       " '1\\\\rkiyer',\n",
       " '1\\\\rutameht',\n",
       " '1\\\\sadve',\n",
       " '1\\\\salesforces-codet5-system-can-understand-and-generate-code',\n",
       " '1\\\\sanmi',\n",
       " '1\\\\sariel',\n",
       " '1\\\\values',\n",
       " '1\\\\w-hwu',\n",
       " '1\\\\ways-give',\n",
       " '1\\\\wendycho',\n",
       " '1\\\\wgropp',\n",
       " '1\\\\wtkramer',\n",
       " '1\\\\ygertner',\n",
       " '1\\\\yihchun',\n",
       " '1\\\\ymn',\n",
       " '1\\\\yongjoo',\n",
       " '1\\\\yunhuang',\n",
       " '1\\\\zaher',\n",
       " '2\\\\academics.html',\n",
       " '2\\\\accessibility.html',\n",
       " '2\\\\almacam.html',\n",
       " '2\\\\awards.html',\n",
       " '2\\\\calendars.html',\n",
       " '2\\\\calendars_process.html',\n",
       " '2\\\\contact.html',\n",
       " '2\\\\copyright.html',\n",
       " '2\\\\emergency.html',\n",
       " '2\\\\employment.html',\n",
       " '2\\\\facts.html',\n",
       " '2\\\\graduate-advising-office',\n",
       " '2\\\\graduate-fellowships-awards',\n",
       " '2\\\\graduate-student-annual-evaluation-process',\n",
       " '2\\\\graduating-phd-students',\n",
       " '2\\\\guidelines-forming-phd-committee',\n",
       " '2\\\\haitham',\n",
       " '2\\\\hanj',\n",
       " '2\\\\harandi',\n",
       " '2\\\\hclane',\n",
       " '2\\\\heath',\n",
       " '2\\\\hengji',\n",
       " '2\\\\history-timeline',\n",
       " '2\\\\hl314',\n",
       " '2\\\\honor-code',\n",
       " '2\\\\honors',\n",
       " '2\\\\honors.html',\n",
       " '2\\\\ican',\n",
       " '2\\\\ican-faqs',\n",
       " '2\\\\idoia',\n",
       " '2\\\\impact-illinois-cs-degree',\n",
       " '2\\\\impact-report-publications',\n",
       " '2\\\\index.html',\n",
       " '2\\\\indexs.html',\n",
       " '2\\\\indy',\n",
       " '2\\\\instructional-development-team',\n",
       " '2\\\\interactive-computing',\n",
       " '2\\\\j-liu1',\n",
       " '2\\\\jch',\n",
       " '2\\\\jdiesner',\n",
       " '2\\\\jhasegaw',\n",
       " '2\\\\jianh',\n",
       " '2\\\\jianpeng',\n",
       " '2\\\\jingrui',\n",
       " '2\\\\jugal',\n",
       " '2\\\\juliahmr',\n",
       " '2\\\\k-12-outreach',\n",
       " '2\\\\k-12-resources',\n",
       " '2\\\\kale',\n",
       " '2\\\\kamin',\n",
       " '2\\\\karthe',\n",
       " '2\\\\kcchang',\n",
       " '2\\\\kesh',\n",
       " '2\\\\kindrtnk',\n",
       " '2\\\\kingli',\n",
       " '2\\\\kirlik',\n",
       " '2\\\\kkarahal',\n",
       " '2\\\\landmarks.html',\n",
       " '2\\\\leadership.html',\n",
       " '2\\\\prospective.html',\n",
       " '2\\\\quadcam.html',\n",
       " '2\\\\rankings.html',\n",
       " '2\\\\rankings_grad.html',\n",
       " '2\\\\rankings_ug.html',\n",
       " '2\\\\research.html',\n",
       " '2\\\\saurabhg',\n",
       " '2\\\\scientific-computing',\n",
       " '2\\\\security-and-privacy',\n",
       " '2\\\\senior-design',\n",
       " '2\\\\shieh-li-scholarship',\n",
       " '2\\\\shj',\n",
       " '2\\\\silva-leads-team-studying-interconnections-between-online-learning-equity-access',\n",
       " '2\\\\sjp',\n",
       " '2\\\\slazebni',\n",
       " '2\\\\soc1024',\n",
       " '2\\\\spbhat2',\n",
       " '2\\\\staff-awards',\n",
       " '2\\\\staff-positions',\n",
       " '2\\\\statistics',\n",
       " '2\\\\student-organizations',\n",
       " '2\\\\student-resources',\n",
       " '2\\\\systems-and-networking',\n",
       " '2\\\\tbretl',\n",
       " '2\\\\technical-conferences-workshops',\n",
       " '2\\\\theory-and-algorithms',\n",
       " '2\\\\this-ai-startup-aims-to-be-a-one-stop-writing-platform',\n",
       " '2\\\\tmc',\n",
       " '2\\\\tours.html',\n",
       " '2\\\\traditions.html',\n",
       " '2\\\\transfer-students',\n",
       " '2\\\\transfer.html',\n",
       " '2\\\\tribal-initatives.html',\n",
       " '2\\\\undergraduate-advising',\n",
       " '2\\\\undergraduate-advising-office',\n",
       " '2\\\\undergraduate-forms',\n",
       " '2\\\\undergraduate.html',\n",
       " '2\\\\university-illinois-awards',\n",
       " '2\\\\vadve',\n",
       " '2\\\\wildlife-conservation.html',\n",
       " '2\\\\xj-meng.html',\n",
       " '3\\\\Administrivia.html',\n",
       " '3\\\\ApplicationDeadlines.html',\n",
       " '3\\\\Assistantships.html',\n",
       " '3\\\\BSMS.html',\n",
       " '3\\\\COVID19.html',\n",
       " '3\\\\CS1014.html',\n",
       " '3\\\\CS1044.html',\n",
       " '3\\\\CS1054.html',\n",
       " '3\\\\CS1064.html',\n",
       " '3\\\\CS1114.html',\n",
       " '3\\\\CS1124.html',\n",
       " '3\\\\CS1604.html',\n",
       " '3\\\\CS1944.html',\n",
       " '3\\\\CS2104.html',\n",
       " '3\\\\CS2114.html',\n",
       " '3\\\\CS2304.html',\n",
       " '3\\\\CS2505.html',\n",
       " '3\\\\CS2506.html',\n",
       " '3\\\\CS2974.html',\n",
       " '3\\\\CS3114.html',\n",
       " '3\\\\CS3214.html',\n",
       " '3\\\\CS3304.html',\n",
       " '3\\\\CS3414.html',\n",
       " '3\\\\CS3604.html',\n",
       " '3\\\\CS3634.html',\n",
       " '3\\\\CS3654.html',\n",
       " '3\\\\CS3704.html',\n",
       " '3\\\\CS3714.html',\n",
       " '3\\\\CS3724.html',\n",
       " '3\\\\CS3744.html',\n",
       " '3\\\\CS3754.html',\n",
       " '3\\\\CS3824.html',\n",
       " '3\\\\CS3984.html',\n",
       " '3\\\\CS4104.html',\n",
       " '3\\\\CS4114.html',\n",
       " '3\\\\CS4124.html',\n",
       " '3\\\\CS4204.html',\n",
       " '3\\\\CS4214.html',\n",
       " '3\\\\CS4234.html',\n",
       " '3\\\\CS4254.html',\n",
       " '3\\\\CS4264.html',\n",
       " '3\\\\CS4284.html',\n",
       " '3\\\\CS4304.html',\n",
       " '3\\\\CS4414.html',\n",
       " '3\\\\CS4504.html',\n",
       " '3\\\\CS4570.html',\n",
       " '3\\\\CS4604.html',\n",
       " '3\\\\CS4624.html',\n",
       " '3\\\\CS4634.html',\n",
       " '3\\\\CS4644.html',\n",
       " '3\\\\CS4654.html',\n",
       " '3\\\\CS4704.html',\n",
       " '3\\\\CS4784.html',\n",
       " '3\\\\CS4804.html',\n",
       " '3\\\\CS4824.html',\n",
       " '3\\\\CS4884.html',\n",
       " '3\\\\CS4944.html',\n",
       " '3\\\\CS4974.html',\n",
       " '3\\\\CS4994.html',\n",
       " '3\\\\Computer-Science-Press-Releases.html',\n",
       " '3\\\\ContactsRoles.html',\n",
       " '3\\\\Courses2.html',\n",
       " '3\\\\Degrees.html',\n",
       " '3\\\\FAQs.html',\n",
       " '3\\\\ForceAdd.html',\n",
       " '3\\\\Forms.html',\n",
       " '3\\\\Funding.html',\n",
       " '3\\\\Giving.html',\n",
       " '3\\\\MSThesis.html',\n",
       " '3\\\\NewStudentFAQ.html',\n",
       " '3\\\\OptionsCertificates.html',\n",
       " '3\\\\Prospective.html',\n",
       " '3\\\\ProspectiveStudents.html',\n",
       " '3\\\\Scholarships.html',\n",
       " '3\\\\StudentServices..html',\n",
       " '3\\\\StudentServices.html',\n",
       " '3\\\\Undergradhandbook.html',\n",
       " '3\\\\Undergraduate.html',\n",
       " '3\\\\courses.html',\n",
       " '3\\\\cs-source-events.html',\n",
       " '3\\\\cs-source-membership.html',\n",
       " '3\\\\cs-source.html',\n",
       " '3\\\\fall-career-fair.html',\n",
       " '3\\\\featured-spotlight.html',\n",
       " '3\\\\index.html',\n",
       " '3\\\\phd-recipients.html',\n",
       " '3\\\\sp22grforceadd.html',\n",
       " '3\\\\university-leadership.html',\n",
       " '3\\\\university-studies-undecided.html',\n",
       " '3\\\\venture_opportunities.html',\n",
       " '3\\\\veterans.html',\n",
       " '3\\\\virtual-vt-visit.html',\n",
       " '3\\\\visit.html',\n",
       " '3\\\\vt-i-corps-program.html',\n",
       " '3\\\\vt-icorps.html',\n",
       " '3\\\\vtip.html',\n",
       " '3\\\\water-resources-policy-and-management.html',\n",
       " '3\\\\webster-santos.html',\n",
       " '4\\\\COVID19.html',\n",
       " '4\\\\agribusiness-management-and-entrepreneurship.html',\n",
       " '4\\\\agribusiness.html',\n",
       " '4\\\\agricultural-and-applied-economics.html',\n",
       " '4\\\\agricultural-sciences.html',\n",
       " '4\\\\agricultural-technology.html',\n",
       " '4\\\\aluminate.html',\n",
       " '4\\\\italian.html',\n",
       " '4\\\\japanese-studies.html',\n",
       " '4\\\\job-opportunities.html',\n",
       " '4\\\\judaic-studies.html',\n",
       " '4\\\\landscape-architecture.html',\n",
       " '4\\\\landscape-horticulture-and-design.html',\n",
       " '4\\\\language-sciences.html',\n",
       " '4\\\\latin.html',\n",
       " '4\\\\launch-of-new-hokie-owned-business-directory.html',\n",
       " '4\\\\launch.html',\n",
       " '4\\\\liberal-arts-and-human-sciences-undecided.html',\n",
       " '4\\\\libraries.html',\n",
       " '4\\\\license-launch.html',\n",
       " '4\\\\license.html',\n",
       " '4\\\\link.html',\n",
       " '4\\\\living-learning-communities.html',\n",
       " '4\\\\locations.html',\n",
       " '4\\\\majors.html',\n",
       " '4\\\\management.html',\n",
       " '4\\\\maps.html',\n",
       " '4\\\\marketing-management.html',\n",
       " '4\\\\marketing.html',\n",
       " '4\\\\materials-science-and-engineering.html',\n",
       " '4\\\\mathematics-education.html',\n",
       " '4\\\\mathematics.html',\n",
       " '4\\\\mechanical-engineering.html',\n",
       " '4\\\\medicinal-chemistry.html',\n",
       " '4\\\\mentoring.html',\n",
       " '4\\\\meteorology.html',\n",
       " '4\\\\microbiology.html',\n",
       " '4\\\\mining-and-mineral-engineering.html',\n",
       " '4\\\\minors.html',\n",
       " '4\\\\multimedia-journalism.html',\n",
       " '4\\\\music.html',\n",
       " '4\\\\nanomedicine.html',\n",
       " '4\\\\nanoscience.html',\n",
       " '4\\\\national-security-and-foreign-affairs.html',\n",
       " '4\\\\news.html',\n",
       " '4\\\\ocean-engineering.html',\n",
       " '4\\\\office-hours.html',\n",
       " '4\\\\online-learning.html',\n",
       " '4\\\\online-redir.html',\n",
       " '4\\\\open-house.html',\n",
       " '4\\\\packaging-systems-and-design.html',\n",
       " '4\\\\parents-and-families.html',\n",
       " '4\\\\philosophy-politics-and-economics.html',\n",
       " '4\\\\philosophy.html',\n",
       " '4\\\\physics.html',\n",
       " '4\\\\poc-grant-program.html',\n",
       " '4\\\\political-science.html',\n",
       " '4\\\\polymer-chemistry.html',\n",
       " '4\\\\pre-education.html',\n",
       " '4\\\\pre-health-professions.html',\n",
       " '4\\\\pre-law.html',\n",
       " '4\\\\pre-medicine.html',\n",
       " '4\\\\pre-veterinary-medicine.html',\n",
       " '4\\\\principles-of-community.html',\n",
       " '4\\\\privacy.html',\n",
       " '4\\\\professional-and-technical-writing.html',\n",
       " '4\\\\profiles.html',\n",
       " '4\\\\property-management.html',\n",
       " '4\\\\psychology.html',\n",
       " '4\\\\public-health.html',\n",
       " '4\\\\public-relations.html',\n",
       " '4\\\\quantum.html',\n",
       " '4\\\\rafael-davalos.html',\n",
       " '4\\\\rankings.html',\n",
       " '4\\\\raytheon-vt-ai-research.html',\n",
       " '4\\\\real-estate.html',\n",
       " '4\\\\religion-and-culture.html',\n",
       " '4\\\\research.html',\n",
       " '4\\\\residential-environments-and-design.html',\n",
       " '4\\\\resources.html',\n",
       " '4\\\\robert-gourdie.html',\n",
       " '4\\\\russian.html',\n",
       " '4\\\\science-technology-and-society.html',\n",
       " '4\\\\site-map.html',\n",
       " '4\\\\smart-and-sustainable-cities.html',\n",
       " '4\\\\sociology.html',\n",
       " '4\\\\space-event-registration.html',\n",
       " '4\\\\space.html',\n",
       " '4\\\\spanish.html',\n",
       " '4\\\\sports-media-and-analytics.html',\n",
       " '4\\\\staff.html',\n",
       " '4\\\\statistics.html',\n",
       " '4\\\\status.html',\n",
       " '4\\\\strategic-plan.html',\n",
       " '4\\\\studio-art.html',\n",
       " '4\\\\study-abroad.html',\n",
       " '4\\\\summer-winter-programs.html',\n",
       " '4\\\\sustainable-biomaterials.html',\n",
       " '4\\\\systems-biology.html',\n",
       " '4\\\\team.html',\n",
       " '4\\\\theatre-arts.html',\n",
       " '5\\\\awards.html',\n",
       " '5\\\\biology.html',\n",
       " '5\\\\board-of-directors-ex-officio.html',\n",
       " '5\\\\economics.html',\n",
       " '5\\\\electrical-engineering.html',\n",
       " '5\\\\elementary-education-pk-6.html',\n",
       " '5\\\\emergency-contacts.html',\n",
       " '5\\\\engagement-outreach.html',\n",
       " '5\\\\engineering-science-and-mechanics.html',\n",
       " '5\\\\english-creative-writing.html',\n",
       " '5\\\\english-language-arts-education.html',\n",
       " '5\\\\english-language-sciences.html',\n",
       " '5\\\\english-literature.html',\n",
       " '5\\\\english.html',\n",
       " '5\\\\entomology.html',\n",
       " '5\\\\entrepreneurship-new-venture-growth.html',\n",
       " '5\\\\environmental-conservation-and-society.html',\n",
       " '5\\\\environmental-economics-management-and-policy.html',\n",
       " '5\\\\environmental-economics.html',\n",
       " '5\\\\environmental-horticulture.html',\n",
       " '5\\\\environmental-informatics.html',\n",
       " '5\\\\environmental-policy-and-planning.html',\n",
       " '5\\\\environmental-resources-management.html',\n",
       " '5\\\\environmental-science.html',\n",
       " '5\\\\equal-opportunity.html',\n",
       " '5\\\\equine-science.html',\n",
       " '5\\\\european-and-transatlantic-studies.html',\n",
       " '5\\\\event-and-experience-management.html',\n",
       " '5\\\\experiential-learning.html',\n",
       " '5\\\\experimental-neuroscience.html',\n",
       " '5\\\\explore-science-undecided.html',\n",
       " '5\\\\exploring-architecture-and-urban-studies-undecided.html',\n",
       " '5\\\\exploring-life-sciences.html',\n",
       " '5\\\\exploring-natural-resources.html',\n",
       " '5\\\\facts-about-virginia-tech.html',\n",
       " '5\\\\faculty-and-staff.html',\n",
       " '5\\\\faculty-inventors.html',\n",
       " '5\\\\family-and-consumer-sciences.html',\n",
       " '5\\\\fashion-merchandising-and-design.html',\n",
       " '5\\\\finaid-cares-act-disclosure.html',\n",
       " '5\\\\finance.html',\n",
       " '5\\\\first-generation-college-institute.html',\n",
       " '5\\\\first-generation-students.html',\n",
       " '5\\\\fish-conservation.html',\n",
       " '5\\\\food-and-health-systems-economics.html',\n",
       " '5\\\\food-science-and-technology.html',\n",
       " '5\\\\forestry.html',\n",
       " '5\\\\foundation-relations.html',\n",
       " '5\\\\french-for-business-advanced.html',\n",
       " '5\\\\french-for-business.html',\n",
       " '5\\\\french.html',\n",
       " '5\\\\frequently-asked-questions.html',\n",
       " '5\\\\future-students.html',\n",
       " '5\\\\gender-science-and-technology.html',\n",
       " '5\\\\general-engineering.html',\n",
       " '5\\\\geographic-information-systems.html',\n",
       " '5\\\\geography.html',\n",
       " '5\\\\geosciences.html',\n",
       " '5\\\\german.html',\n",
       " '5\\\\global-business-practices-to-improve-the-human-condition.html',\n",
       " '5\\\\global-engagement.html',\n",
       " '5\\\\global-food-security-and-health.html',\n",
       " '5\\\\graduate-school.html',\n",
       " '5\\\\graduate.html',\n",
       " '5\\\\graphic-design.html',\n",
       " '5\\\\green-engineering.html',\n",
       " '5\\\\health-wellness.html',\n",
       " '5\\\\history-and-social-sciences-education.html',\n",
       " '5\\\\history.html',\n",
       " '5\\\\hokie-stone.html',\n",
       " '5\\\\horticulture.html',\n",
       " '5\\\\hospitality-and-tourism-management.html',\n",
       " '5\\\\housing copy.html',\n",
       " '5\\\\housing.html',\n",
       " '5\\\\human-computer-interaction.html',\n",
       " '5\\\\human-development.html',\n",
       " '5\\\\human-nutrition-foods-and-exercise.html',\n",
       " '5\\\\humanities-for-public-service.html',\n",
       " '5\\\\humanities-science-and-environment.html',\n",
       " '5\\\\immigration.html',\n",
       " '5\\\\inclusion-diversity.html',\n",
       " '5\\\\inclusive-vt-rdr.html',\n",
       " '5\\\\index.html',\n",
       " '5\\\\industrial-and-systems-engineering.html',\n",
       " '5\\\\industrial-design.html',\n",
       " '5\\\\industry-and-partners.html',\n",
       " '5\\\\industrynetworks.html',\n",
       " '5\\\\innovation.html',\n",
       " '5\\\\integrated-security.html',\n",
       " '5\\\\integrative-health-and-wellness.html',\n",
       " '5\\\\interdisciplinary-engineering-and-science.html',\n",
       " '5\\\\interior-design.html',\n",
       " '5\\\\international-agriculture-and-life-sciences.html',\n",
       " '5\\\\international-business.html',\n",
       " '5\\\\international-public-policy.html',\n",
       " '5\\\\international-relations.html',\n",
       " '5\\\\international-studies.html',\n",
       " '5\\\\international-trade-and-development.html',\n",
       " '5\\\\italian.html',\n",
       " '6\\\\about-us.html',\n",
       " '6\\\\about.html',\n",
       " '6\\\\academics.html',\n",
       " '6\\\\acceptable-use.html',\n",
       " '6\\\\accessibility.html',\n",
       " '6\\\\accounting-and-information-systems.html',\n",
       " '6\\\\actuarial-science.html',\n",
       " '6\\\\adaptive-brain-and-behavior.html',\n",
       " '6\\\\admissions.html',\n",
       " '6\\\\advertising.html',\n",
       " '6\\\\aerospace-engineering.html',\n",
       " '6\\\\africana-studies.html',\n",
       " '6\\\\alumni.html',\n",
       " '6\\\\american-indian-studies.html',\n",
       " '6\\\\american-studies.html',\n",
       " '6\\\\animal-and-poultry-sciences.html',\n",
       " '6\\\\applachian-culture-and-environment.html',\n",
       " '6\\\\apply.html',\n",
       " '6\\\\arabic.html',\n",
       " '6\\\\architecture.html',\n",
       " '6\\\\art-history.html',\n",
       " '6\\\\arts.html',\n",
       " '6\\\\asian-area-studies.html',\n",
       " '6\\\\astronomy.html',\n",
       " '6\\\\athletics.html',\n",
       " '6\\\\beyond-boundaries.html',\n",
       " '6\\\\big-ideas.html',\n",
       " '6\\\\biochemistry.html',\n",
       " '6\\\\biodiversity-conservation.html',\n",
       " '6\\\\biological-physics.html',\n",
       " '6\\\\biological-sciences.html',\n",
       " '6\\\\biological-systems-engineering.html',\n",
       " '6\\\\biology.html',\n",
       " '6\\\\biomedical-engineering.html',\n",
       " '6\\\\black-college-institute.html',\n",
       " '6\\\\blocksburg2021.html',\n",
       " '6\\\\blue-planet.html',\n",
       " '6\\\\board-of-directors-ex-officio.html',\n",
       " '6\\\\board.html',\n",
       " '6\\\\building-construction.html',\n",
       " '6\\\\buildings.html',\n",
       " '6\\\\business-information-technology.html',\n",
       " '6\\\\business-undecided.html',\n",
       " '6\\\\business.html',\n",
       " '6\\\\calendar.html',\n",
       " '6\\\\campus-highlights.html',\n",
       " '6\\\\campus-life.html',\n",
       " '6\\\\career-and-technical-education-agriculture-education.html',\n",
       " '6\\\\career-professional-development.html',\n",
       " '6\\\\chemical-engineering.html',\n",
       " '6\\\\chemistry.html',\n",
       " '6\\\\childhood-pre-education.html',\n",
       " '6\\\\chinese-studies.html',\n",
       " '6\\\\cinema.html',\n",
       " '6\\\\civic-agriculture-and-food-systems.html',\n",
       " '6\\\\civil-engineering.html',\n",
       " '6\\\\classical-languages.html',\n",
       " '6\\\\classical-studies.html',\n",
       " '6\\\\clinical-neuroscience.html',\n",
       " '6\\\\clubs-organizations-involvement.html',\n",
       " '6\\\\cognitive-and-behavioral-neuroscience.html',\n",
       " '6\\\\commencement.html',\n",
       " '6\\\\communication.html',\n",
       " '6\\\\community-economic-development.html',\n",
       " '6\\\\community-systems-and-engagement.html',\n",
       " '6\\\\computational-and-systems-neuroscience.html',\n",
       " '6\\\\computational-modeling-and-data-analytics.html',\n",
       " '6\\\\computer-engineering.html',\n",
       " '6\\\\computer-science.html',\n",
       " '6\\\\construction-engineering-and-management.html',\n",
       " '6\\\\consumer-info.html',\n",
       " '6\\\\consumer-studies.html',\n",
       " '6\\\\contact.html',\n",
       " '6\\\\contacts.html',\n",
       " '6\\\\continuing-professional-education.html',\n",
       " '6\\\\corporate-chapters.html',\n",
       " '6\\\\corporate_venture_arms.html',\n",
       " '6\\\\corps-cadets.html',\n",
       " '6\\\\cost-and-aid.html',\n",
       " '6\\\\creative-technologies.html',\n",
       " '6\\\\creative-writing.html',\n",
       " '6\\\\criminology.html',\n",
       " '6\\\\crop-and-soil-environmental-sciences.html',\n",
       " '6\\\\crop-and-soil-sciences.html',\n",
       " '6\\\\cultural-centers.html',\n",
       " '6\\\\current-students.html',\n",
       " '6\\\\cyber-security.html',\n",
       " '6\\\\daily-campus-visit.html',\n",
       " '6\\\\dairy-science.html',\n",
       " '6\\\\data-and-decisions.html',\n",
       " '6\\\\dei-series.html',\n",
       " '6\\\\depts-colleges.html',\n",
       " '6\\\\development-and-international-trade.html',\n",
       " '6\\\\digital-marketing-strategy.html',\n",
       " '6\\\\dining.html',\n",
       " '6\\\\disabilities-studies.html',\n",
       " '6\\\\discover-blacksburg.html',\n",
       " '6\\\\diversity-and-community-engagement.html',\n",
       " '6\\\\ecological-cities.html',\n",
       " '6\\\\engineering-science-and-mechanics.html']"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "BSBI_instance = BSBIIndex(data_dir=data_dir, output_dir = 'index_dir', )\n",
    "BSBI_instance.retrieve('the the')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also check if indeed one of the retrieved pages contains the query terms, by reading a file as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':\n",
      "      new date().gettime(),event:'gtm.js'});var f=d.getelementsbytagname(s)[0],\n",
      "      j=d.createelement(s),dl=l!='datalayer'?'&l='+l:'';j.async=true;j.src=\n",
      "      'https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentnode.insertbefore(j,f);\n",
      "      })(window,document,'script','datalayer','gtm-p6f85q5'); cs|source offers in-person and virtual connections with companies   | computer science | virginia tech skip to main content skip to search virginia techÂ® universal access universal access options report a barrier accessibility portal pause all background videos underline all links apply visit give shop hokie gear apparel, clothing, gear and merchandise hokie shop university bookstore, merchandise and gifts hokie license plates part of every virginia tech plate purchase funds scholarships resources for future students current students parents and families faculty and staff alumni industry and partners computer science menu college of engineeringÂ Â / department of computer science home about giving to cs contact us press releases undergraduate programs majors and minors courses undergraduate advising force add procedures undergraduate handbook prospective students transfer students computer science ambassadors graduate programs contacts and roles degrees and certificates administrivia graduate courses cs graduate advising compact cs grad council for prospective students funding opportunities faqs past phd recipients northern virginia programs forms new student faq covid-19 faq graduate fellowships spring 22 csa graduate force add page northern virginia center people department leadership research centers and institutes blockchain blockchain challenge 2020 blockchain boot camp blockchain challenge winners 2020 blockchain boot camp 2020 agenda blocksburg summit 2019 contact us blockchain resource portal blockchain adjunct blocksburg 2021 blockchain webinar series blockchain certificate program news and events news from computer science department spotlights the network newsletter seminars and distinguished lectures prospective student information sessions commencement spring 2020 2020 virtual awards banquet recognitions virtual town hall commencement spring 2021 2021 virtual awards banquet recognitions community diversity in computer science student groups tributes to beloved academic advisor terry arthur cs|source membership events portal student success alumni engagement alumni events alumni advisory board alumni in the news alumni awards 50 years of computer science network newsletter students in distress apply visit give shop hokie gear apparel, clothing, gear and merchandise hokie shop university bookstore, merchandise and gifts hokie license plates part of every virginia tech plate purchase funds scholarships resources for future students current students parents and families faculty and staff alumni industry and partners search search submit college of engineering / department of computer science / news and events / department spotlights / cs|source offers in-person and virtual connections with companies / explore news from computer science department spotlights chapman pendery embraces questions to create community vt international collegiate programming contest team advances to national championship cs|source stakeholder spotlight: reinventing geospatial, inc. (rgi) faculty answer the covid-19 research call a convergence of computer science talent leads to development of coronavirus tracking website living his best grad life: kobla setor zilevu ut prosim is the foundation of  emma menoâ€™s passion for cybersecurity a successful mission for senior sam imamov cs|source stakeholder spotlight: peraton department of computer science hosts virtual town hall congratulations to 2020 dean's award recipients computer science welcomes eight new faculty members advisory board of national leaders will guide virginia tech innovation campus virtual showcase of creative computing studio 2020 fall meet fall 2020 hokie grad: samie amriui meet fall 2020 hokie grad: allison desantis stephen edwards recognized for outstanding contribution to computer science education cs|source stakeholder spotlight: caci student creativity shines in computing studio virtual showcase works of wonder student virtual showcase grady booch meets with software engineering capstone students cs|source stakeholder spotlight: mitre hoda eldardiry receives early career science award from purdue university kirk cameron named 2021 ieee computer society fellow jared cooper has a knack for making lasting impressions mostafa mohammed says the joy he receives from teaching is beyond any description chapman pendery named outstanding senior in computer science 2021 virtual awards banquet recognitions tanvi haldankar's receives undergraduate research excellence awards bethlehem teshome shines as an undergraduate teaching assistant sai gurrapu's curiosity continues to fuel his entrepreneurial drive daphne yao recognized for pioneering contributions to the cybersecurity industry alumna jamika burge receives richard a. tapia award roxanne paul honored with virginia louise \"jenny\" frank award for outstanding contributions a summer internship to remember department welcomes 11 new faculty members for academic year student apps that make the grade cs|source stakeholder spotlight: costar group cs|source offers in-person and virtual connections with companies the network newsletter seminars and distinguished lectures prospective student information sessions commencement spring 2020 2020 virtual awards banquet recognitions virtual town hall commencement spring 2021 2021 virtual awards banquet recognitions cs|source offers in-person and virtual connections with companies august 9, 2021 theÂ department of computer scienceÂ atÂ virginia tech, through its tech-talent community, cs|source , provides a pathway for department-industry partnerships, including its career fairs held during the fall and spring semesters. the department benefits through investments of funding toward student scholarships, groups, and activities; development of students leading to internships and careers; and research opportunities to address and advance technological solutions. this year, 48 students received scholarships through the cs|source totaling $100k, all made possible through this partnership. a total of 42 companies are participating in the cs|source fall career fair, with 12 companies in person and 27 virtual, which kicked off its activities this week with a virtual career fair prep networking event on september 8. the in-person and virtual career fair will be held on september 13. the cs|source also welcomes five new companies this year, including cgi, drt strategies, kentik, mosaic learning, inc., and west creek financial. tags blacksburg main campus 1160 torgersen hall 620 drillfield drive blacksburg, va 24061 united states (540) 231-6931 blacksburg corporate research center 2202 kraft drive blacksburg, va 24060 united states (540) 231-9195 national capital region 7054 haycock road falls church, va 22043 united states (703) 538-8370 csundergrad@cs.vt.edu (undergraduate program) gradinfo@cs.vt.edu (graduate program) webmaster@cs.vt.edu (webmaster) cs intranet $(\"a\").each(function() {\n",
      "\n",
      "    $(this).attr(\"href\", $(this).attr(\"href\").replace(\"website.cs.vt.edu\", \"cs.vt.edu\")); }); var _gaq = _gaq || [];\n",
      "  _gaq.push(['_setaccount', 'ua-47559051-3']);\n",
      "  _gaq.push(['_trackpageview']);\n",
      "  (function() {\n",
      "    var ga = document.createelement('script'); ga.type = 'text/javascript'; ga.async = true;\n",
      "    ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';\n",
      "    var s = document.getelementsbytagname('script')[0]; s.parentnode.insertbefore(ga, s);\n",
      "  })(); get directions see all locations contact virginia tech university status principles of community privacy statement acceptable use we remember university libraries accessibility consumer information stop abuse policies equal opportunity wvtf university bookstore jobs at virginia tech strategic plan Â©Â 2021 virginia polytechnic institute and state university. all rights reserved.\n"
     ]
    }
   ],
   "source": [
    "with open(\"hw1dataraw/3/fall-career-fair.html\", 'r') as f:\n",
    "    print(f.read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Building a compressed index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section, we will build a compressed index using gap encoding with variable byte encoding for each gap.\n",
    "\n",
    "First, let's take a look at some useful python math operations: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 % 2 =  0\n",
      "10 % 3 =  1\n",
      "10 / 3 =  3.3333333333333335\n",
      "10 // 3 =  3\n"
     ]
    }
   ],
   "source": [
    "# Remainder (modulo) operator %\n",
    "print(\"10 % 2 = \", 10 % 2)\n",
    "print(\"10 % 3 = \", 10 % 3)\n",
    "\n",
    "# Integer division in Python 3 is done by using two slash signs\n",
    "print(\"10 / 3 = \", 10 / 3)\n",
    "print(\"10 // 3 = \", 10 // 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Your taks is to fill in the following `CompressedPostings` class which we'll use as a drop-in replacement for `UncompressedPostings`. To understand in detail gap encoding (with variable byte encoding for each gap), we suggest that you revisit the corresponding lecture video and [Chapter 5](https://nlp.stanford.edu/IR-book/pdf/05comp.pdf) of the textbook. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CompressedPostings:\n",
    "    #If you need any extra helper methods you can add them here \n",
    "    ### Begin your code\n",
    "    @staticmethod\n",
    "    def VBEncodeNum(n):\n",
    "        byte = []\n",
    "        while True:\n",
    "            byte.append(n % 128)\n",
    "            if n < 128:\n",
    "                break\n",
    "            n //= 128\n",
    "        byte[0] += 128\n",
    "        return byte[::-1]\n",
    "\n",
    "    @staticmethod\n",
    "    def VBEncode(n_list):\n",
    "        b = []\n",
    "        for n in n_list:\n",
    "            b.extend(CompressedPostings.VBEncodeNum(n))\n",
    "        return b\n",
    "\n",
    "    @staticmethod\n",
    "    def VBDecode(bs):\n",
    "        n_list = []\n",
    "        n = 0\n",
    "        for b in bs:\n",
    "            if b < 128:\n",
    "                n = 128*n + b\n",
    "            else:\n",
    "                n = 128*n + b - 128\n",
    "                n_list.append(n)\n",
    "                n = 0\n",
    "        return n_list\n",
    "    ### End your code\n",
    "    \n",
    "    @staticmethod\n",
    "    def encode(postings_list):\n",
    "        \"\"\"Encodes `postings_list` using gap encoding with variable byte encoding for each gap\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        postings_list: List[int]  The postings list to be encoded\n",
    "        \n",
    "        Returns\n",
    "        -------\n",
    "        bytes: Bytes reprsentation of the compressed postings list (as produced by `array.tobytes` function)\n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "        p = postings_list.copy()\n",
    "        for i in range(1, len(p))[::-1]:\n",
    "            p[i] -= p[i-1]\n",
    "        vb = CompressedPostings.VBEncode(p)\n",
    "        return array.array('B', vb).tobytes()\n",
    "        ### End your code\n",
    "\n",
    "    @staticmethod\n",
    "    def decode(encoded_postings_list):\n",
    "        \"\"\"Decodes a byte representation of compressed postings list\n",
    "        \n",
    "        Parameters\n",
    "        ----------\n",
    "        encoded_postings_list: Bytes representation as produced by `CompressedPostings.encode` \n",
    "            \n",
    "        Returns\n",
    "        -------\n",
    "        List[int] Decoded postings list (each posting is a docIds)\n",
    "        \"\"\"\n",
    "        ### Begin your code\n",
    "        vb = array.array('B')\n",
    "        vb.frombytes(encoded_postings_list)\n",
    "        postings_list = CompressedPostings.VBDecode(vb.tolist())\n",
    "        for i in range(1, len(postings_list)):\n",
    "            postings_list[i] += postings_list[i-1]\n",
    "        return postings_list\n",
    "        ### End your code\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can write test cases for any helper methods implemented"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Begin your code\n",
    "assert CompressedPostings.VBEncodeNum(656) == [5,144]\n",
    "assert CompressedPostings.VBEncode([144, 5]) == [1,144,133]\n",
    "assert CompressedPostings.VBDecode([1,144,133]) == [144, 5]\n",
    "### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have provided a helper function for testing whether an encoded postings list is decoded correctly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_encode_decode(l):\n",
    "    e = CompressedPostings.encode(l)\n",
    "    d = CompressedPostings.decode(e)\n",
    "    assert d == l\n",
    "    print(l, e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a few test cases to make sure the postings list compression and decompression is being done correctly."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[25, 36, 12345] b'\\x99\\x8b`\\x95'\n"
     ]
    }
   ],
   "source": [
    "### Begin your code\n",
    "test_encode_decode([25, 36, 12345])\n",
    "### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's create a new folder to store the compressed index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "try: \n",
    "    os.mkdir('index_dir_compressed')\n",
    "except FileExistsError:\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "BSBI_instance_compressed = BSBIIndex(data_dir=data_dir, output_dir='index_dir_compressed', postings_encoding=CompressedPostings)\n",
    "BSBI_instance_compressed.index()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0\\\\celebration',\n",
       " '0\\\\department-college-and-campus-events',\n",
       " '0\\\\dskatz',\n",
       " '0\\\\featured-lectures',\n",
       " '1\\\\nskim',\n",
       " '1\\\\rutameht',\n",
       " '1\\\\values',\n",
       " '2\\\\honor-code',\n",
       " '2\\\\jugal',\n",
       " '2\\\\theory-and-algorithms',\n",
       " '3\\\\cs-source-events.html',\n",
       " '3\\\\fall-career-fair.html',\n",
       " '3\\\\featured-spotlight.html',\n",
       " '3\\\\index.html',\n",
       " '4\\\\property-management.html',\n",
       " '4\\\\site-map.html',\n",
       " '5\\\\graduate.html',\n",
       " '6\\\\construction-engineering-and-management.html']"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "BSBI_instance_compressed.retrieve('career fair')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And we are done with our search engine implementation!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Running time analysis (Optional, NOT graded)\n",
    "\n",
    "In this section you can write queries to evaluate the running time characteristics of `retrieve` and use it to for in-practice understanding of the key optimizations decisions when designing a retrieval algorithm. Note that, due to the very small data collection size, timings may not be perfect (and sometimes results may vary). However, you should still be able to see some timing differences often. Also, note that the following code cells assume there exists an indexed BSBIIndex object.\n",
    "\n",
    "Python offers a convenient timing module `%timeit` ([documentation](https://docs.python.org/3/library/timeit.html))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit BSBI_instance.retrieve('virginia tech')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Can you **replace or add** a term in the query so that it runs slower? Time your query to see if indeed is slower."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit BSBI_instance.retrieve('virginia tech')\n",
    "### Begin your code\n",
    "\n",
    "### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Why did the retrieve function get slower?**\n",
    "> *Type your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Construct a new query by adding a term to the previous query that makes it go faster."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Begin your code \n",
    "\n",
    "### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Where does the increase in speed come from?** \n",
    "\n",
    "> *Type your answer here*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Index size\n",
    "\n",
    "In this section we will look at the size of index on disk.\n",
    "\n",
    "### Uncompressed index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us look at the size of the merged index (`.index`) file "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Size of index\", os.path.getsize(\"index_dir/BSBI.index\"), 'bytes')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code above queries the file system to compute the size of the index. \n",
    "\n",
    "Show that you can compute the same answer by looking at the `postings_dict` object directly. Your code should compute the size of the index file (in bytes) using the postings dict. You should use the word size (in bytes) and size information stored in the `postings_dict`. The resulting number should match the byte number above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 'pkl' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-1-b7b8d9e9550b>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mwith\u001b[0m \u001b[0mopen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'index_dir/BSBI.dict'\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m'rb'\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m     \u001b[0mpostings_dict\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mterms\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mpkl\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mload\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m     \u001b[1;31m### Begin your code\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m     \u001b[0mmax\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mj\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0m_\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mj\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mpostings_dict\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mvalues\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[1;31m### End your code\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mNameError\u001b[0m: name 'pkl' is not defined"
     ]
    }
   ],
   "source": [
    "with open('index_dir/BSBI.dict', 'rb') as f:\n",
    "    postings_dict, terms = pkl.load(f)\n",
    "    ### Begin your code\n",
    "    max([i+j for i, _, j in postings_dict.values()])\n",
    "    ### End your code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q1: Describe how you have computed the expected size based on the information stored in the postings dictionary.**\n",
    "\n",
    "> *Your answer here*\n",
    "\n",
    "The size is based on the maximum starting position added to the size of postings list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compressed Index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us look at the size of the compressed index (`.index`) file "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Size of compressed index\", os.path.getsize(\"index_dir_compressed/BSBI.index\"), 'bytes')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q2: How would the size of the compressed index change if variable byte encoding was used on the docIDs instead of the gaps?**\n",
    "\n",
    "> \n",
    "By applying variable byte encoding on docIDs the size would be larger than gaps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Improving performance\n",
    "\n",
    "Let's take a deeper look into improving performance. Think about your answers to the following questions. Note that some questions are subjective and may have multiple correct answers. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**In this HW you useD each sub-directory as a block and build an index for one block at a time. Can you discuss the trade-off of different sizes of blocks? Is there a better way to work with limited memory when we want to minimize indexing time?**\n",
    "\n",
    "> Your answer here\n",
    "\n",
    "Using larger sized blocks can enable us to process more at a time. This also reduces the final merge task, thus less time to form the index. The optimal way would be to keep the block size that maximum fits the memory."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q3: Is there a part of your indexing program that limits its scalability to larger datasets?**\n",
    "\n",
    "> Your answer here\n",
    "\n",
    "Ys, I believe the dictionary for the terms will be in memory and will be the bottleneck for this program."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Q4: Describe other parts of the indexing process that you could optimize for indexing scalability and faster retrieval time.**\n",
    "\n",
    "> Using better hardware can improve the process. \n",
    "\n",
    "For boolean retrieval, we can start working on the less frequent term and thus reduce the merge operation needed."
   ]
  }
 ],
 "metadata": {
  "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.7.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {
    "height": "66px",
    "width": "252px"
   },
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}