homework/HW1/assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# NLP Assignment 1\n",
    "Created by Prof. [Mohammad M. Ghassemi](https://ghassemi.xyz)\n",
    "\n",
    "Submitted by: <span style=\"color:red\"> INSERT YOUR NAME HERE </span>\n",
    "\n",
    "In collaboration with: <span style=\"color:red\"> INSERT YOUR HOMEWORK PARTNER'S GRADE HERE </span>\n",
    "\n",
    "\n",
    "<hr> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Assignment Goals\n",
    "The goal of this assignment is to familiarize yourself with:\n",
    "1. Regular expressions, \n",
    "2. Text normalization, \n",
    "3. Edit distance, \n",
    "4. N-gram language models and smoothing \n",
    "\n",
    "This assignment combines tutorial components, with learning exercises that you must complete and submit. The learning exercise sections are clearly demarcated within the assignments.\n",
    "\n",
    "## Assumptions\n",
    "BEFORE YOU START\n",
    "\n",
    "1. PULL THE LATEST VERSION OF THE `course-materials` REPOSITORY, AND COPY `homework/HW1/` INTO THE CORRESPONDING DIRECTORY. \n",
    "2. CREATE AND ATTACHED TO A VIRTUAL ENVIRONMENT, AND INSTALLED THE REQUIREMENTS IN `requirements.txt`\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from materials.code import class_utils"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "\n",
    "# Part 0: Collecting Data\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before we can perform any text analysis, we will need to collect some text to apply our analysis to! One excellent resource for free text data is [Project Gutenburg](https://www.gutenberg.org/) (PG); PG contains ~60,000 free eBooks in a variety of formats including the very easy to use `.txt` format. Let's start by pulling [Bertrand Russell's](https://plato.stanford.edu/entries/russell/) book on [The Problems of Philosophy](http://www.gutenberg.org/cache/epub/5827/pg5827.txt) directly from the internet to our machines using [Python's requests library](https://requests.readthedocs.io/en/master/). The requests library is a powerful tool for extracting text data from the internet. Given that most contemporary text data is on the web, it's a tool you should become familiar with:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "import requests\n",
    "website = 'http://www.gutenberg.org/cache/epub/5827/pg5827.txt'\n",
    "site    = requests.get(website)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--------------------------------------------------------\n",
      "Server status code: 200\n",
      "--------------------------------------------------------\n",
      "Here is a 250 character sample of your text:\n",
      "- - - - - - - - - - - - - - - - - - - - - - - - - - - - \n",
      "wledge in the world which is so certain that no\n",
      "reasonable man could doubt it? This question, which at first sight might\n",
      "not seem difficult, is really one of the most difficult that can\n",
      "be asked. When we have realized the obstacles in the way of a\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('\\n')\n",
    "print('--------------------------------------------------------')\n",
    "print('Server status code: ' + str(site.status_code))\n",
    "print('--------------------------------------------------------')\n",
    "print('Here is a 250 character sample of your text:')\n",
    "print('- - - - - - - - - - - - - - - - - - - - - - - - - - - - ')\n",
    "print(site.text[1500:1750])\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The requests object returned a server status code of `200`, and placed the text we requested in `r.text`. The status code is the server's way of telling us `OK` but note that servers can also refuse to serve us; If we request another resources that doesn't exist from Guttenburg for example, it will respond differently. Let's ask for a new book called `idontthinkyouhavethisbook.txt`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "website = 'http://www.gutenberg.org/cache/epub/5827/idontthinkyouhavethisbook.txt'\n",
    "r = requests.get(website)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--------------------------------------------------------\n",
      "Server status code: 404\n",
      "--------------------------------------------------------\n",
      "Here is a 250 character sample of your text:\n",
      "- - - - - - - - - - - - - - - - - - - - - - - - - - - - \n",
      "_logo\"> -->\n",
      "  <a id=\"main_logo\" href=\"/\" class=\"no-hover\">\n",
      "    <img src=\"/gutenberg/pg-logo-129x80.png\" alt=\"Project Gutenberg\" draggable=\"false\" />\n",
      "  </a>\n",
      "  <!--\t</div>-->\n",
      "  <div id=\"menu\">\n",
      "    <label for=\"tm\" id=\"toggle-menu\">Menu<span class=\"drop-\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('\\n')\n",
    "print('--------------------------------------------------------')\n",
    "print('Server status code: ' + str(r.status_code))\n",
    "print('--------------------------------------------------------')\n",
    "print('Here is a 250 character sample of your text:')\n",
    "print('- - - - - - - - - - - - - - - - - - - - - - - - - - - - ')\n",
    "print(r.text[1500:1750])\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the server returned a `404` status code, which is it's way of telling us `Not Found`. Sure enough, the content that was returned in `r.text` is the error page of Project Guttenburg, not the book we requested. I point this out because when you collect your own data from the internet, especially large volumes of data, you will want to pay attention to those server status codes to make sure what you requested is what you obtained. To learn more about server codes, you can see this [this page](https://developer.mozilla.org/en-US/docs/Web/HTTP/Status)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr> \n",
    "\n",
    "# Part 1: Regular Expressions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A regular expression is a compact programming language that is specialized for enhanced text search. We can import the `re` library, which comes standard with the Python programming language, to analyze the book we pulled from Project Guttenburg in part 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "regular_expression = 'philosophy'\n",
    "text               = site.text\n",
    "results            = re.search(regular_expression,text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--------------------------------------------------------\n",
      "Results\n",
      "--------------------------------------------------------\n",
      "A match for the search query: \"philosophy\"\n",
      "was found at the following character span: (764, 774)\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('\\n')\n",
    "print('--------------------------------------------------------')\n",
    "print('Results')\n",
    "print('--------------------------------------------------------')\n",
    "print('A match for the search query: \"' + results.group() + '\"\\nwas found at the following character span: ' + str(results.span()))\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above example finds the first instance of the word `philosophy` in the book. For some purposes, we may want to capture *every instance* where the search term was mentioned in a text. We can accomplish that using the `re.finditer` function, and packaging our results in a neat list of dictionaries that contain the matching string and the location of the match:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "# collect all the mentions of the search term\n",
    "regular_expression = 'philosophy'\n",
    "results            = [ {\"indicies\":m.span(), \"match\":m.group() } for m in re.finditer(regular_expression,text)];\n",
    "matches            = []; [matches.append(m['match']) for m in results];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--------------------------------------------------------\n",
      "Results\n",
      "--------------------------------------------------------\n",
      "We found 72 matches...\n",
      "\n",
      "[{'indicies': (764, 774), 'match': 'philosophy'}, {'indicies': (1833, 1843), 'match': 'philosophy'}, {'indicies': (1849, 1859), 'match': 'philosophy'}, {'indicies': (5109, 5119), 'match': 'philosophy'}, {'indicies': (19891, 19901), 'match': 'philosophy'}, {'indicies': (21170, 21180), 'match': 'philosophy'}, {'indicies': (33483, 33493), 'match': 'philosophy'}, {'indicies': (33560, 33570), 'match': 'philosophy'}, {'indicies': (33849, 33859), 'match': 'philosophy'}, {'indicies': (50321, 50331), 'match': 'philosophy'}, {'indicies': (54760, 54770), 'match': 'philosophy'}, {'indicies': (103297, 103307), 'match': 'philosophy'}, {'indicies': (109118, 109128), 'match': 'philosophy'}, {'indicies': (122400, 122410), 'match': 'philosophy'}, {'indicies': (122529, 122539), 'match': 'philosophy'}, {'indicies': (125952, 125962), 'match': 'philosophy'}, {'indicies': (126061, 126071), 'match': 'philosophy'}, {'indicies': (130439, 130449), 'match': 'philosophy'}, {'indicies': (137039, 137049), 'match': 'philosophy'}, {'indicies': (137797, 137807), 'match': 'philosophy'}, {'indicies': (141982, 141992), 'match': 'philosophy'}, {'indicies': (142856, 142866), 'match': 'philosophy'}, {'indicies': (143182, 143192), 'match': 'philosophy'}, {'indicies': (187623, 187633), 'match': 'philosophy'}, {'indicies': (217060, 217070), 'match': 'philosophy'}, {'indicies': (217606, 217616), 'match': 'philosophy'}, {'indicies': (218230, 218240), 'match': 'philosophy'}, {'indicies': (218493, 218503), 'match': 'philosophy'}, {'indicies': (231308, 231318), 'match': 'philosophy'}, {'indicies': (231368, 231378), 'match': 'philosophy'}, {'indicies': (231474, 231484), 'match': 'philosophy'}, {'indicies': (232593, 232603), 'match': 'philosophy'}, {'indicies': (233131, 233141), 'match': 'philosophy'}, {'indicies': (233425, 233435), 'match': 'philosophy'}, {'indicies': (233545, 233555), 'match': 'philosophy'}, {'indicies': (233816, 233826), 'match': 'philosophy'}, {'indicies': (234323, 234333), 'match': 'philosophy'}, {'indicies': (234555, 234565), 'match': 'philosophy'}, {'indicies': (235193, 235203), 'match': 'philosophy'}, {'indicies': (235369, 235379), 'match': 'philosophy'}, {'indicies': (235447, 235457), 'match': 'philosophy'}, {'indicies': (235666, 235676), 'match': 'philosophy'}, {'indicies': (235850, 235860), 'match': 'philosophy'}, {'indicies': (235992, 236002), 'match': 'philosophy'}, {'indicies': (236350, 236360), 'match': 'philosophy'}, {'indicies': (236378, 236388), 'match': 'philosophy'}, {'indicies': (236439, 236449), 'match': 'philosophy'}, {'indicies': (236606, 236616), 'match': 'philosophy'}, {'indicies': (236725, 236735), 'match': 'philosophy'}, {'indicies': (237387, 237397), 'match': 'philosophy'}, {'indicies': (237505, 237515), 'match': 'philosophy'}, {'indicies': (237868, 237878), 'match': 'philosophy'}, {'indicies': (238560, 238570), 'match': 'philosophy'}, {'indicies': (238691, 238701), 'match': 'philosophy'}, {'indicies': (238775, 238785), 'match': 'philosophy'}, {'indicies': (238849, 238859), 'match': 'philosophy'}, {'indicies': (238890, 238900), 'match': 'philosophy'}, {'indicies': (238988, 238998), 'match': 'philosophy'}, {'indicies': (239235, 239245), 'match': 'philosophy'}, {'indicies': (239324, 239334), 'match': 'philosophy'}, {'indicies': (239976, 239986), 'match': 'philosophy'}, {'indicies': (240137, 240147), 'match': 'philosophy'}, {'indicies': (240278, 240288), 'match': 'philosophy'}, {'indicies': (240616, 240626), 'match': 'philosophy'}, {'indicies': (241278, 241288), 'match': 'philosophy'}, {'indicies': (241368, 241378), 'match': 'philosophy'}, {'indicies': (241511, 241521), 'match': 'philosophy'}, {'indicies': (241613, 241623), 'match': 'philosophy'}, {'indicies': (242858, 242868), 'match': 'philosophy'}, {'indicies': (249062, 249072), 'match': 'philosophy'}, {'indicies': (249535, 249545), 'match': 'philosophy'}, {'indicies': (249777, 249787), 'match': 'philosophy'}]\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('\\n')\n",
    "print('--------------------------------------------------------')\n",
    "print('Results')\n",
    "print('--------------------------------------------------------')\n",
    "print('We found ' +  str(len(matches)) + ' matches...\\n')\n",
    "print(str(results))\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We found `72` matches for the search term. That seems a bit low for a book with the word philosophy in it's name! Let's update our regular expression so that it's not sensitive to capitalization of the letter `p`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "# collect all the mentions of the search term\n",
    "regular_expression = '(p|P)hilosophy'\n",
    "results            = [ {\"indicies\":m.span(), \"match\":m.group() } for m in re.finditer(regular_expression,text)];\n",
    "matches            = []; [matches.append(m['match']) for m in results];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--------------------------------------------------------\n",
      "Results\n",
      "--------------------------------------------------------\n",
      "We found 81 matches...\n",
      "\n",
      "['Philosophy', 'Philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'Philosophy']\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('\\n')\n",
    "print('--------------------------------------------------------')\n",
    "print('Results')\n",
    "print('--------------------------------------------------------')\n",
    "print('We found ' +  str(len(results)) + ' matches...\\n')\n",
    "print(str(matches))\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We found `81` matches; that is not much better than before. Let's make the search even more general by seeking out terms that start with the word `philo`, followed by an arbitrary number of [a-z] characters thereafter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "regular_expression = '(P|p)hilo[a-z]+'\n",
    "results            = [ {\"indicies\":m.span(), \"match\":m.group() } for m in re.finditer(regular_expression,text)];\n",
    "matches            = []; [matches.append(m['match']) for m in results];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--------------------------------------------------------\n",
      "Results\n",
      "--------------------------------------------------------\n",
      "We found 154 matches...\n",
      "\n",
      "['Philosophy', 'Philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophy', 'philosophy', 'philosopher', 'philosopher', 'philosopher', 'Philonous', 'Philonous', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'Philosophy', 'philosophy', 'philosophy', 'philosopher', 'philosophical', 'Philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophy', 'philosophical', 'philosopher', 'philosophical', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'philosophy', 'philosophical', 'philosopher', 'philosophy', 'philosopher', 'philosophy', 'philosopher', 'philosophy', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'philosopher', 'philosophers', 'philosophy', 'philosophy', 'philosophical', 'philosophers', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophers', 'philosophers', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophers', 'philosophies', 'philosophers', 'philosophical', 'philosopher', 'philosophers', 'philosophers', 'philosophers', 'philosophy', 'philosophical', 'philosophy', 'philosophers', 'philosophers', 'philosophy', 'philosophy', 'philosophy', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'Philosophical', 'philosophy', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophical', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosopher', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophical', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophize', 'Philosophy', 'philosophy', 'philosophic', 'philosophic', 'Philosophic', 'Philosophic', 'philosophic', 'philosophies', 'philosophical', 'philosophic', 'philosophic', 'philosophic', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'philosophers', 'Philonous', 'Philosophy']\n",
      "--------------------------------------------------------\n",
      "We found 11 distinct terms...\n",
      "\n",
      "{'Philosophy': 9, 'philosophy': 72, 'philosophers': 37, 'philosopher': 11, 'Philonous': 3, 'philosophical': 10, 'philosophies': 2, 'Philosophical': 1, 'philosophize': 1, 'philosophic': 6, 'Philosophic': 2}\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('\\n')\n",
    "print('--------------------------------------------------------')\n",
    "print('Results')\n",
    "print('--------------------------------------------------------')\n",
    "print('We found ' +  str(len(matches)) + ' matches...\\n')\n",
    "print(str(matches))\n",
    "print('--------------------------------------------------------')\n",
    "print('We found ' +  str(len(set(matches))) + ' distinct terms...\\n')\n",
    "print(class_utils.CountFrequency(matches))\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks better! But now we have a new problem. It seems that an inconveniently named philosopher, `Philonous`, has made his way into our results. Let's modify our regular expression to use a `negative lookahead` `(?!nous)` to remove him."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "regular_expression = '(P|p)hilo(?!nous)[a-z]+'\n",
    "results            = [ {\"indicies\":m.span(), \"match\":m.group() } for m in re.finditer(regular_expression,text)];\n",
    "matches            = []; [matches.append(m['match']) for m in results];"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--------------------------------------------------------\n",
      "Results\n",
      "--------------------------------------------------------\n",
      "We found 151 matches...\n",
      "\n",
      "['Philosophy', 'Philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophy', 'philosophy', 'philosopher', 'philosopher', 'philosopher', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'Philosophy', 'philosophy', 'philosophy', 'philosopher', 'philosophical', 'Philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophy', 'philosophical', 'philosopher', 'philosophical', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'philosophy', 'philosophical', 'philosopher', 'philosophy', 'philosopher', 'philosophy', 'philosopher', 'philosophy', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'philosopher', 'philosophers', 'philosophy', 'philosophy', 'philosophical', 'philosophers', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophers', 'philosophers', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophers', 'philosophies', 'philosophers', 'philosophical', 'philosopher', 'philosophers', 'philosophers', 'philosophers', 'philosophy', 'philosophical', 'philosophy', 'philosophers', 'philosophers', 'philosophy', 'philosophy', 'philosophy', 'philosophers', 'philosophers', 'philosophers', 'philosophers', 'Philosophical', 'philosophy', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophical', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'Philosophy', 'philosophy', 'philosopher', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophy', 'philosophers', 'philosophy', 'philosophical', 'philosophy', 'philosophy', 'philosophy', 'philosophy', 'philosophize', 'Philosophy', 'philosophy', 'philosophic', 'philosophic', 'Philosophic', 'Philosophic', 'philosophic', 'philosophies', 'philosophical', 'philosophic', 'philosophic', 'philosophic', 'philosophy', 'Philosophy', 'philosophy', 'philosophy', 'philosophers', 'Philosophy']\n",
      "--------------------------------------------------------\n",
      "We found 10 distinct terms...\n",
      "\n",
      "{'Philosophy': 9, 'philosophy': 72, 'philosophers': 37, 'philosopher': 11, 'philosophical': 10, 'philosophies': 2, 'Philosophical': 1, 'philosophize': 1, 'philosophic': 6, 'Philosophic': 2}\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('\\n')\n",
    "print('--------------------------------------------------------')\n",
    "print('Results')\n",
    "print('--------------------------------------------------------')\n",
    "print('We found ' +  str(len(matches)) + ' matches...\\n')\n",
    "print(str(matches))\n",
    "print('--------------------------------------------------------')\n",
    "print('We found ' +  str(len(set(matches))) + ' distinct terms...\\n')\n",
    "print(class_utils.CountFrequency(matches))\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr> \n",
    "\n",
    "## Learning Exercise 1: \n",
    "#### Worth 1/5 Points\n",
    "Now I'm curious how Bertrand used these various philosophical terms in his sentences, and how Bertrand's language, more generally, compares to [Friedrich Nietzsche](https://en.wikipedia.org/wiki/Friedrich_Nietzsche) and other philosophers. You're going to help me with that!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A. Download Data\n",
    "Use Python's `requests` library to collect Friedrich Nietzsche's book, [Beyond Good and Evil](http://www.gutenberg.org/cache/epub/4363/pg4363.txt) into Python. Collect one additional work of philosophy (of your choice) and import it as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "################################################################################\n",
    "# INSERT YOUR CODE HERE\n",
    "# DO NOT FORGET TO PRINT YOUR MEANINGFUL RESULTS TO THE SCREEN.\n",
    "################################################################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\"> INSERT AN INTERPRETATION OF YOUR RESULTS HERE </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### B. Basic Text Cleansing\n",
    "Use `re.sub` to do some basic text cleansing on books you downloaded. More specifically: \n",
    "\n",
    "1. replace the various forms of whitespace that appear (`\\n`,`\\r`,`\\t` etc.) with a single whitespace character. \n",
    "2. cast all text to lower case\n",
    "3. replace common abbreviations with their full form, for instance: `it's` with `it is`\n",
    "\n",
    "Note that item #3 does not have to be comprehensive, just do a couple common abbreviations to illustrate that you know how to do this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "################################################################################\n",
    "# INSERT YOUR CODE HERE\n",
    "# DO NOT FORGET TO PRINT YOUR MEANINGFUL RESULTS TO THE SCREEN.\n",
    "################################################################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\"> INSERT AN INTERPRETATION OF YOUR RESULTS HERE </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### C. Sentence Extractor\n",
    "Write a regular expression that will extract the complete sentences containing any matches of the following regex we wrote together earlier: `(P|p)hilo(?!nous)[a-z]+`. Apply this regular expression to \"Beyond Good and Evil\", \"The Problems of Philosophy\", and the work of philosophy you chose. Show a couple of example sentences from each work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "################################################################################\n",
    "# INSERT YOUR CODE HERE\n",
    "# DO NOT FORGET TO PRINT YOUR RESULTS TO THE SCREEN.\n",
    "################################################################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\"> INSERT AN INTERPRETATION OF YOUR RESULTS HERE </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### D. Sentence Tokenizer\n",
    "Write another regular expression that tokenizes the text in your collected sentences by splitting the sentences into a list of individual words. Tokenize the entire text of all three books using this regular expression. For each book, store your result as a list of lists and print the last word of the last sentence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "################################################################################\n",
    "# INSERT YOUR CODE HERE\n",
    "# DO NOT FORGET TO PRINT YOUR RESULTS TO THE SCREEN.\n",
    "################################################################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\"> INSERT AN INTERPRETATION OF YOUR RESULTS HERE </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### E. Compare Works\n",
    "Use Python's `matplotlib` library, to compare the distribution of the most common words that show up in each book. Compare the distributions and comment on any important statistical similarities or differences between the distributions. Do the distributions of the word frequency follow Zipf's law? Ignoring common words (`the`,`and`,`in`, etc.) what are the top 10 words that each book used most frequently? Are there any words that showed up more frequently in one work than they did in another?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "################################################################################\n",
    "# INSERT YOUR CODE HERE\n",
    "# DO NOT FORGET TO PRINT YOUR MEANINGFUL RESULTS TO THE SCREEN.\n",
    "################################################################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\"> INSERT AN INTERPRETATION OF YOUR RESULTS HERE </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr> \n",
    "\n",
    "# Part 2: Text normalization \n",
    "Text normalization is an essential preliminary step to any natural language processing pipeline. To begin, let's re-import `The Problems of Philosophy`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "website  = 'http://www.gutenberg.org/cache/epub/5827/pg5827.txt'\n",
    "text     = requests.get(website).text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tokenization\n",
    "As you saw in `Learning Exercise 1`, tokenization of text can be performed through the use of Regular Expressions. Familiarity with Regular Expressions is an important part of any NLP apprentice's toolkit but fortunately, it's not the only (or even the best) tool that exists for text normalization tasks! Indeed, for basic text normalization and cleansing, Python has a number of functions that operate on strings directly - no libraries required! \n",
    "\n",
    "Let's begin this section of the tutorial by taking a look at some of these functions, starting with the `replace` function to remove the whitespace characters in our text data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Replace \\r\\n with whitespace, then replace \\n with whitespace, then replace \\r with whitespace\n",
    "clean_text = text.replace('\\r\\n',' ').replace('\\n',' ').replace('\\r',' ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--------------------------------------------------------\n",
      "Results\n",
      "--------------------------------------------------------\n",
      "Before:\n",
      "\n",
      "\n",
      "I have derived valuable assistance from unpublished writings of G. E.\n",
      "Moore and J. M. Keynes: from the former, as regards ...\n",
      "--------------------------------------------------------\n",
      "After:\n",
      "I have derived valuable assistance from unpublished writings of G. E. Moore and J. M. Keynes: from the former, as regards ...\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('\\n')\n",
    "print('--------------------------------------------------------')\n",
    "print('Results')\n",
    "print('--------------------------------------------------------')\n",
    "print('Before:\\n' + text[1101:1227] + ' ...')\n",
    "print('--------------------------------------------------------')\n",
    "print('After:\\n' + clean_text[1056:1177] + ' ...')\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That seems to have worked! Notice that `replace` is a method that is built into Python strings. That's the reason that we write `text.replace(...)` and not something like `replace(text,...)`.  \n",
    "\n",
    "Python has other many [other useful string manipulation methods](https://www.programiz.com/python-programming/methods/string), but for the rest of the basic pre-processing we'll be used in this tutorial, we'll only need `split`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Split the sentences when we see a '.' character\n",
    "clean_text = clean_text.split('.')\n",
    "\n",
    "# Split each sentence further - when there are no arguments provided to split, it defaults to whitespace (tabs, newlines, spaces, etc)\n",
    "textmat = []\n",
    "for c in clean_text:\n",
    "    textmat.append(c.split())    \n",
    "#re.split(r'\\w+|\\$[\\d\\.]+|\\S+',\"text\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--------------------------------------------------------\n",
      "Results (showing sentence 10)\n",
      "--------------------------------------------------------\n",
      "['I', 'have', 'also', 'profited', 'greatly', 'by', 'the', 'criticisms', 'and', 'suggestions', 'of', 'Professor', 'Gilbert', 'Murray']\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Printing the tenth sentence:\n",
    "print('--------------------------------------------------------')\n",
    "print('Results (showing sentence 10)')\n",
    "print('--------------------------------------------------------')\n",
    "print(textmat[10])\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The pre-processing shown above is mostly for illustrative purposes. If we'd like to do anything serious, we'll need a more sophisticated approach to sentence segmentation and text tokenization. Fortunately, there are many existing tools in Python that assist with the Sentence segmentation and word tokenization. One of the most popular tools for this is the [Natural Langauge Toolkit](https://www.nltk.org/). Let's import the tool into python and explore some of it's functionality together:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[nltk_data] Downloading package punkt to /Users/ghamut/nltk_data...\n",
      "[nltk_data]   Package punkt is already up-to-date!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Importing the NLTK Package\n",
    "import nltk\n",
    "\n",
    "# Importing the `punkt` data, used by the NLTK tokenizer\n",
    "import ssl\n",
    "try:\n",
    "    _create_unverified_https_context = ssl._create_unverified_context\n",
    "except AttributeError:\n",
    "    pass\n",
    "else:\n",
    "    ssl._create_default_https_context = _create_unverified_https_context\n",
    "\n",
    "nltk.download('punkt')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's test out the NLTK tokenizer with a tricky sentence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "['At', 'eight', \"o'clock\", 'on', 'Thursday', 'morning', 'Arthur', 'did', \"n't\", 'feel', 'very', 'good', '.', 'He', 'drove', 'to', 'the', 'store', 'in', 'New', 'York', 'at', '100', 'm.p.h.', '!', 'He', 'wanted', 'to', 'obtain', 'some', 'Kool-Aid', '!', 'It', 'cost', '$', '10.89', '.']\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "sentences = \"\"\"At eight o'clock on Thursday morning Arthur didn't feel very good. He drove to the store in New York at 100 m.p.h.! He wanted to obtain some Kool-Aid! It cost $10.89.\"\"\"\n",
    "tokens    = nltk.word_tokenize(sentences)\n",
    "print('\\n')\n",
    "print(tokens)\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, the tokenization is pretty good for something out-of-the box, but it could be better! In an ideal world, we would want the Tokenizer to understand that `New York` is actually a single token, not two. Furthermore, depending on our use case, we may want the `$` sign to be attached to the `10.89` token. So, if you wanted to use the NLTK tool out-of-the-box, you may need to do some additional pre-processing. Let's try the sentence splitting functionality next:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "[\"At eight o'clock on Thursday morning Arthur didn't feel very good.\", 'He drove to the store in New York at 100 m.p.h.!', 'He wanted to obtain some Kool-Aid!', 'It cost $10.89.']\n",
      "\n"
     ]
    }
   ],
   "source": [
    "result = nltk.sent_tokenize(sentences)\n",
    "print('\\n' + str(result) + '\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one also works rather nicely. Indeed, NLTK does a lot to make Natural Language Processing accessible. In fact, NLTK has several other tools that we will cover in subsequent lectures, but one of the tools that is not yet available in NLTK (at the time this tutorial was written) is Byte Pair Encoding, the tokenization approaches with some relation to many of today's NLP powerhouses (Yes, I'm talking about [BERT](https://en.wikipedia.org/wiki/BERT_(language_model))). I think I'm going to need some help with that..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr> \n",
    "\n",
    "## Learning Exercise 2:\n",
    "#### Worth 1/5 Points\n",
    "\n",
    "For this learning exercise, you will implement the Byte Pair Encoding (BPE) algorithm and use it to Tokenize `The Problems of Philosophy`. If you can't recall how the BPE algorithm works, you can refer back to the lectures, or see Section 2.4.3 of [Daniel Jurafsky & James H. Martin's NLP book](https://web.stanford.edu/~jurafsky/slp3/2.pdf). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### A. Download Books to Create a Larger Corpus\n",
    "Given that the BPE algorithm is data-driven, we'll first need to gather a training data corpus. For your training data, you will choose at least 10 books from [Project Gutenburg](https://www.gutenberg.org/): \n",
    "* Choose at least 5 books that were authored by Bertrand Russell, not including `The Problems of Philosophy`\n",
    "* Choose at least 5 books that were authored by Friedrich Nietzsche\n",
    "\n",
    "You'll be using these training data later with BPE to identify the token `vocabularies`, which you will then use to tokenize `The problems of Philosophy`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "################################################################################\n",
    "# INSERT YOUR CODE HERE\n",
    "# DO NOT FORGET TO PRINT YOUR MEANINGFUL RESULTS TO THE SCREEN.\n",
    "################################################################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\"> INSERT AN INTERPRETATION OF YOUR RESULTS HERE </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### B. Implement Byte Pair Encoding\n",
    "Implement the Byte Pair Encoding algorithm by filling out the function skeleton below. The function should take three inputs:\n",
    "\n",
    "* `text` : an unprocessed text file that we wish to tokenize using BPE\n",
    "* `k`    : the number of merges to perform\n",
    "* `training_corpus` : a python list of complete texts we wish to use for training. The formatting should look like: `['blah blah blah ...', 'the rain in spain ...', 'do pickles count as vegetables? ...']`\n",
    "\n",
    "The function should output a tokenized version of the `text` based on the `k` vocabulary units learned by BPE using the `training_corpus`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BytePairEncoding(text, k, training_corpus):\n",
    "    tokenized_text = []\n",
    "    vocabulary = []\n",
    "    # INSERT YOUR CODE HERE\n",
    "    return vocabulary, tokenized_text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### C. Evaluate Byte Pair Encoding\n",
    "Because BPE is data-driven, we might expect there to be some differences in the tokenization based on the training corpus, as well as your choice of `k`! To evaluate BPE, you will now experiment with how the tokenization performs for various settings of `k`, and when using different training . More specifically, you will compare the `vocabulary` and `tokenized_text` of Bertrand Russell's `The Problem's of Philosophy` for:\n",
    "\n",
    "* values of `k` ranging from 1,000 to 10,000 in steps of 1,000 and\n",
    "    *  `training_corpus` sets that include: (1) only Bertrand Russell books, (2) only Friedrich Nietzsche books, and (3) all books from groups (1) and (2).\n",
    "\n",
    "For the above conditions, please generate one or more plots using Python's `matplotlib` that compare:\n",
    "* The total number of unique tokens in the tokenized text\n",
    "* The median size of tokens in the tokenized text\n",
    "* The % overlap in the number of distinct unique tokens generated by BPE and NLTK's word tokenizer.\n",
    "\n",
    "Compare the plots, and note any interesting observations about the results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "################################################################################\n",
    "# INSERT YOUR CODE HERE\n",
    "# DO NOT FORGET TO PRINT YOUR MEANINGFUL RESULTS TO THE SCREEN.\n",
    "################################################################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\"> INSERT AN INTERPRETATION OF YOUR RESULTS HERE </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr> \n",
    "\n",
    "# Part 3: Edit Distance\n",
    "#### Character Level Distance\n",
    "As we discussed in the lectures, Edit Distance is a way to measure the similarity between different sequences of text. Our goal in this section will be to compare and contrast some of the different measures of edit distance that exist so that you'll have a better intuition for how to use them, depending on the problem you're trying to solve. To start, let's import the [`textdistance` library](https://github.com/life4/textdistance), written by [Gram Voronov](https://orsinium.dev/)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "import textdistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `textdistance` library contains python implementations of about 30 edit distance algorithms. Let's begin by trying out the edit distance tool we discussed in class, the [Levenshtein Distance](https://en.wikipedia.org/wiki/Levenshtein_distance): "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "levenshtein distance:\n",
      "--------------------------------------------------------\n",
      "\"test\" and \"test\" is: 0\n",
      "\"test\" and \"texts\" is: 2\n",
      "\"test\" and \"   test\" is: 3\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def GetDistance(string1, string2, method):\n",
    "    # Compute the distance and print the results\n",
    "    distance = eval(\"textdistance.\" + method + \"(string1, string2)\")\n",
    "    print('\"' + string1 + '\" and \"' + string2 + '\" is: ' + str(distance))  \n",
    "    \n",
    "print('\\n')\n",
    "print('levenshtein' + \" distance:\")\n",
    "print('--------------------------------------------------------')\n",
    "GetDistance('test','test'      ,'levenshtein')\n",
    "GetDistance('test','texts'     ,'levenshtein')\n",
    "GetDistance('test','   test'   ,'levenshtein')\n",
    "print('--------------------------------------------------------')\n",
    "print('\\n')\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall from the lecture that the Levenshtein distance counts the total number of `insertion`, `deletion`, and `substitution` actions that a required to transform one string into another and the cost of each edit is always 1. So, as shown in the above example, moving from `\"test\"` to `\"test\"` requires no edits, and therefore has a distance of 0, moving from `\"test\"` to `\"texts\"` requires 1 substitution and one addition and therefore has a distance of 2, moving from `\"test\"` to `\"   test\"`   has a distance of 3 becasue we must remove the  three whitespace characters to the left of the word `\"   test\"` to create a match.\n",
    "\n",
    "The above example is intentionally meant to highlight that the assumptions of the edit distance measures can have consequence for their estimates; Indeed, depending on the problem we are trying to solve, we may want `\"   test\"` and `\"test\"` to be closer than the distance between `\"test\"` and `\"texts\"`. On that note, let's explore the performance of three other edit distance measures: the [Hamming Distance](https://en.wikipedia.org/wiki/Hamming_distance), [Needleman Wunsch](https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm), and [Smith Waterman](https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hamming distance:\n",
      "--------------------------------------------------------\n",
      "\"test\" and \"test\" is: 0\n",
      "\"test\" and \"texts\" is: 2\n",
      "\"test\" and \"   test\" is: 6\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n",
      "levenshtein distance:\n",
      "--------------------------------------------------------\n",
      "\"test\" and \"test\" is: 0\n",
      "\"test\" and \"texts\" is: 2\n",
      "\"test\" and \"   test\" is: 3\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n",
      "needleman_wunsch distance:\n",
      "--------------------------------------------------------\n",
      "\"test\" and \"test\" is: 4.0\n",
      "\"test\" and \"texts\" is: 2.0\n",
      "\"test\" and \"   test\" is: 1.0\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n",
      "smith_waterman distance:\n",
      "--------------------------------------------------------\n",
      "\"test\" and \"test\" is: 4\n",
      "\"test\" and \"texts\" is: 2.0\n",
      "\"test\" and \"   test\" is: 4.0\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "distance_measures = ['hamming',  'levenshtein', 'needleman_wunsch', 'smith_waterman']\n",
    "\n",
    "for method in distance_measures:\n",
    "    print(method + \" distance:\")\n",
    "    print('--------------------------------------------------------')\n",
    "    GetDistance('test'      ,'test'      ,method)\n",
    "    GetDistance('test'      ,'texts'     ,method)\n",
    "    GetDistance('test'      ,'   test'   ,method)\n",
    "    print('--------------------------------------------------------')\n",
    "    print('\\n')\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's step through these results together. First, we notice that the Hamming distance between `\"test\"` and `\"   test\"` is 6, which is even higher than what we observed for the Levenshtein distance! To understand why, we can refer to the definition of the [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance): \"The Hamming distance between two strings is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other.\" Given that there are so many white space characters, and that Hamming is only concerned with substitutions, it makes sense that the hamming distance would be higher than the levenshtein distance!\n",
    "\n",
    "At first glance, the results of the [Needleman Wunch](https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm) and [Smith Waterman](https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm) methods seem suprising. Why is the distance between \"test\" and \"test\" 4? Shouldn't it be 0? Once again, the answer here resides in understanding the definition of the \"distance\" metric. Both of these algorithms are actually providing an **alignment score** between the two sequences. \n",
    "\n",
    "Of course, we may also notice that the scores between the two alignment methods are quite different; the reason for this difference has to do with what these alignment scores are exactly measuring: the Smith–Waterman algorithm is designed to find the *segments* in two sequences that have maximal similarities while the Needleman–Wunsch algorithm is designed for alignment between two complete sequences. Let's explore these two methods to make this distinction a little more clear:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "needleman_wunsch distance:\n",
      "--------------------------------------------------------\n",
      "\"test\" and \"test\" is: 4.0\n",
      "\"test\" and \" test\" is: 3.0\n",
      "\"test\" and \"  test\" is: 2.0\n",
      "\"test\" and \"   test\" is: 1.0\n",
      "\"test\" and \"    test\" is: 0.0\n",
      "\"test\" and \"     test\" is: -1.0\n",
      "\"test\" and \"      test\" is: -2.0\n",
      "\"test\" and \"       test\" is: -3.0\n",
      "\n",
      "\n",
      "smith_waterman distance:\n",
      "--------------------------------------------------------\n",
      "\"test\" and \"test\" is: 4\n",
      "\"test\" and \" test\" is: 4.0\n",
      "\"test\" and \"  test\" is: 4.0\n",
      "\"test\" and \"   test\" is: 4.0\n",
      "\"test\" and \"    test\" is: 4.0\n",
      "\"test\" and \"     test\" is: 4.0\n",
      "\"test\" and \"      test\" is: 4.0\n",
      "\"test\" and \"       test\" is: 4.0\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "distance_measures = ['needleman_wunsch', 'smith_waterman']\n",
    "for method in distance_measures:\n",
    "    print(method + \" distance:\")\n",
    "    print('--------------------------------------------------------')\n",
    "    GetDistance('test','test',method)\n",
    "    GetDistance('test',' test',method)\n",
    "    GetDistance('test','  test',method)\n",
    "    GetDistance('test','   test',method)\n",
    "    GetDistance('test','    test',method)\n",
    "    GetDistance('test','     test',method)\n",
    "    GetDistance('test','      test',method)\n",
    "    GetDistance('test','       test',method)\n",
    "    print('\\n')\n",
    "   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see above, the Needleman Wunsh method grows more negative as the absolute difference between the two strings increases. In this sense, the Needleman-Wunsch algorithm is similar to the Levenshtein distance algorithm; the difference being that Levenshtein uses a static penalty cost to any mismatched letters while the Needleman-Wunsch algorithm gives weights to matches and mismatches differently. The Smith Waterman method distance remains 4 because the substring `test` overlaps in both strings regardless of the whitespace."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Token-Level distance\n",
    "All of our edit distance work up until now has focused on character-level distances and alignment but depending on the problem we want to solve, we may care more about distance at the token level. Fortunately, there are several distance metrics that measure similarity between strings at the token level. One such measure is the [Jaccard Index](https://en.wikipedia.org/wiki/Jaccard_index), which is the size of the intersection of the token sets divided by the size of the union of the sample sets. Here's an example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "jaccard distance:\n",
      "--------------------------------------------------------\n",
      "\"The fish was delish, and it made quite a dish\" and \"The fish on the dish was made quite delicious!\" is: 0.7843137254901961\n",
      "\"The fish was delish, and it made quite a dish\" and \"Joe eats crabs, crabs do not taste good.\" is: 0.39344262295081966\n",
      "--------------------------------------------------------\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "distance_measures = ['jaccard']\n",
    "text1 = \"The fish was delish, and it made quite a dish\"\n",
    "text2 = \"The fish on the dish was made quite delicious!\"\n",
    "text3 = \"Joe eats crabs, crabs do not taste good.\"\n",
    "for method in distance_measures:\n",
    "    print(method + \" distance:\")\n",
    "    print('--------------------------------------------------------')\n",
    "    GetDistance(text1      ,text2      ,method)\n",
    "    GetDistance(text1      ,text3      ,method)\n",
    "    print('--------------------------------------------------------')\n",
    "    print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We won't be covering all the edit distance functions of the NLP community in great detail, but hopefully this is enough to whet your appetite, and allow you to dig into some of the methods on your own."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr> \n",
    "\n",
    "## Learning Exercise 3:\n",
    "#### Worth 1/5 Points\n",
    "#### A. Towards a More Nuanced Edit Distance Cost Metric\n",
    "As we've eluded to here and in the lectures, one deficiency of the Levenshtein cost metric is the assumption that substitutions, edit, and deletion costs are all equal. Your goal for this learning exercise is to modify the cost structure of the `LevenshteinDistanceDP` method shown below so that is assigns 1/2 of the normal penalty for any edits that involve whitespace characters (FYI, the implementation shown below was originally written by [Ahmed Gad](https://blog.paperspace.com/author/ahmed/), [here](https://blog.paperspace.com/implementing-levenshtein-distance-word-autocomplete-autocorrect/#:~:text=The%20Levenshtein%20distance%20is%20a,representing%20the%20distance%20between%20them.&text=In%20this%20tutorial%20the%20Levenshtein,using%20the%20dynamic%20programming%20approach.)). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 631,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 631,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "################################################################################\n",
    "# INSERT YOUR CODE HERE\n",
    "# DO NOT FORGET TO PRINT YOUR MEANINGFUL RESULTS TO THE SCREEN.\n",
    "################################################################################\n",
    "\n",
    "import numpy as np\n",
    "def levenshteinDistanceDP(token1, token2):\n",
    "    distances = np.zeros((len(token1) + 1, len(token2) + 1))\n",
    "\n",
    "    for t1 in range(len(token1) + 1):\n",
    "        distances[t1][0] = t1\n",
    "\n",
    "    for t2 in range(len(token2) + 1):\n",
    "        distances[0][t2] = t2\n",
    "        \n",
    "    a = 0\n",
    "    b = 0\n",
    "    c = 0\n",
    "    \n",
    "    for t1 in range(1, len(token1) + 1):\n",
    "        for t2 in range(1, len(token2) + 1):\n",
    "            if (token1[t1-1] == token2[t2-1]):\n",
    "                distances[t1][t2] = distances[t1 - 1][t2 - 1]\n",
    "            else:\n",
    "                a = distances[t1][t2 - 1]\n",
    "                b = distances[t1 - 1][t2]\n",
    "                c = distances[t1 - 1][t2 - 1]\n",
    "                \n",
    "                if (a <= b and a <= c):\n",
    "                    distances[t1][t2] = a + 1\n",
    "                elif (b <= a and b <= c):\n",
    "                    distances[t1][t2] = b + 1\n",
    "                else:\n",
    "                    distances[t1][t2] = c + 1\n",
    "\n",
    "    return distances[len(token1)][len(token2)]\n",
    "\n",
    "#\n",
    "\n",
    "levenshteinDistanceDP('test  ', 'test')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\"> INSERT AN INTERPRETATION OF YOUR RESULTS HERE </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr> \n",
    "\n",
    "# Part 4: N-Gram language Models\n",
    "In this section, we'll be covering n-gram language models which, as the name implies, are language models that use n-grams!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### N-grams\n",
    "An n-gram is a contiguous sequence of n items from a given sample of text or speech. Let's begin this section by defining a function that generates n-grams from our text data using the `nltk` library and using it to extract n-grams for n ranging from 1-5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Word-Level:\n",
      "1-gram:  ['a', 'fish', 'keeps', 'for', 'a']\n",
      "2-gram:  ['a fish', 'fish keeps', 'keeps for', 'for a', 'a day']\n",
      "3-gram:  ['a fish keeps', 'fish keeps for', 'keeps for a', 'for a day', 'a day ;']\n",
      "4-gram:  ['a fish keeps for', 'fish keeps for a', 'keeps for a day', 'for a day ;', 'a day ; a']\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import nltk\n",
    "from nltk.util import ngrams\n",
    "\n",
    "# an ngram extractor \n",
    "def extract_word_ngrams(data, num):\n",
    "    n_grams = ngrams(nltk.word_tokenize(data), num)\n",
    "    return [ ' '.join(grams) for grams in n_grams]\n",
    "\n",
    "# some example text\n",
    "data = \"\"\"a fish keeps for a day; a fish keeps well if you put it in a cold place. \n",
    "          a fish keeps best if you put it in the fridge. If you’ll be having fish, \n",
    "          have it with an apple because one apple a day keeps the doctor away! \n",
    "          You know they also say that a day keeps coming.\"\"\"\n",
    "\n",
    "# printing the first 5 tokens after gramification\n",
    "print(\"\\nWord-Level:\")\n",
    "print(\"1-gram: \", extract_word_ngrams(data, 1)[0:5])\n",
    "print(\"2-gram: \", extract_word_ngrams(data, 2)[0:5])\n",
    "print(\"3-gram: \", extract_word_ngrams(data, 3)[0:5])\n",
    "print(\"4-gram: \", extract_word_ngrams(data, 4)[0:5])\n",
    "print(\"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that the n-gram extractor I use above leverages the `nltk` tokenizer that we discussed earlier in this assignment. Also, that sample data I showed above should look familiar... As we discussed in the lectures, n-grams can be generated at whatever level of resolution we need for the task at hand; we also don't need any fancy libraries to generate them! If we were interested in extracting n-grams at the character level for instance, we could do that in one line:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Character-Level:\n",
      "1-gram:  ['a', ' ', 'f', 'i', 's']\n",
      "2-gram:  ['a ', ' f', 'fi', 'is', 'sh']\n",
      "3-gram:  ['a f', ' fi', 'fis', 'ish', 'sh ']\n",
      "4-gram:  ['a fi', ' fis', 'fish', 'ish ', 'sh k']\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# some example text\n",
    "data = \"\"\"a fish keeps for a day; a fish keeps well if you put it in a cold place. \n",
    "          a fish keeps best if you put it in the fridge. If you’ll be having fish, \n",
    "          have it with an apple because one apple a day keeps the doctor away! \n",
    "          You know they also say that a day keeps coming.\"\"\"\n",
    "\n",
    "def extract_char_ngrams(data, num):\n",
    "    return [data[i:i+num] for i in range(len(data))][:(-num-1)]\n",
    "\n",
    "# printing the first 5 tokens after gramification\n",
    "print(\"\\nCharacter-Level:\")\n",
    "print(\"1-gram: \", extract_char_ngrams(data, 1)[0:5])\n",
    "print(\"2-gram: \", extract_char_ngrams(data, 2)[0:5])\n",
    "print(\"3-gram: \", extract_char_ngrams(data, 3)[0:5])\n",
    "print(\"4-gram: \", extract_char_ngrams(data, 4)[0:5])\n",
    "print(\"\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Skip-Grams\n",
    "While n-grams bring together contiguous sequences of words, skip-grams include grams that skip over certain terms!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a', 'fish'),\n",
       " ('a', 'keeps'),\n",
       " ('a', 'for'),\n",
       " ('fish', 'keeps'),\n",
       " ('fish', 'for')]"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# some example text\n",
    "data = \"\"\"a fish keeps for a day; a fish keeps well if you put it in a cold place. \n",
    "          a fish keeps best if you put it in the fridge. If you’ll be having fish, \n",
    "          have it with an apple because one apple a day keeps the doctor away! \n",
    "          You know they also say that a day keeps coming.\"\"\"\n",
    "\n",
    "# Creating skip-grams using the NLTK library\n",
    "skip_gram = list(nltk.skipgrams(nltk.word_tokenize(data),n=2,k=2))\n",
    "skip_gram[0:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Language Models \n",
    "A language model refers to any method that assign probabilities to strings. Let's try to develop a more concrete understanding of language models by building a simple one together. More specifically, let's build a model that tries to predict the next word in a sentence, given the last word we saw. One approach to accomplish this is to simply count, for each unique word, what words tend to follow it. To do that, let's start by using the `extract_word_ngrams` tool we showed earlier, and collect all the unique words in the corpus:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---------------------------------------\n",
      "Vocabulary (n = 40)\n",
      "---------------------------------------\n",
      "['also', 'the', '.', 'with', ';', 'because', 'it', 'a', 'for', 'place', 'keeps', '!', 'cold', 'apple', 'in', 'if', 'fridge', 'that', 'well', 'put', 'If', 'having', 'one', 'day', 'fish', 'have', 'know', 'll', 'best', 'away', 'say', 'an', 'You', 'coming', 'you', 'they', ',', 'be', 'doctor', '’']\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# some example text\n",
    "data = \"\"\"a fish keeps for a day; a fish keeps well if you put it in a cold place. \n",
    "          a fish keeps best if you put it in the fridge. If you’ll be having fish, \n",
    "          have it with an apple because one apple a day keeps the doctor away! \n",
    "          You know they also say that a day keeps coming.\"\"\"\n",
    "\n",
    "unigrams = extract_word_ngrams(data,1)\n",
    "\n",
    "# get the unique words:\n",
    "vocabulary = list(set(unigrams))\n",
    "print('---------------------------------------')\n",
    "print('Vocabulary (n = ' + str(len(vocabulary)) +')')\n",
    "print('---------------------------------------')\n",
    "print(str(vocabulary) + '\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have a list of the words, lets initialize a `JSON` object called `counts` that will keep track of the next word, given the current word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "counts = {}\n",
    "for given_word in vocabulary:\n",
    "    counts[given_word] = {}\n",
    "    for next_word in vocabulary:\n",
    "        counts[given_word][next_word] = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `counts` object is a dictionary of dictionaries. It's convenient to store the count data this way because we can see the counts of the next word, given the current word, by simply providing the count object the current word. Let's take a look at the count of all possible next words, given that the current word is `fish`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------------------------------------------------\n",
      "Count of next words, given that current word is \"fish\"\n",
      "------------------------------------------------------\n",
      "{'also': 0, 'the': 0, '.': 0, 'with': 0, ';': 0, 'because': 0, 'it': 0, 'a': 0, 'for': 0, 'place': 0, 'keeps': 0, '!': 0, 'cold': 0, 'apple': 0, 'in': 0, 'if': 0, 'fridge': 0, 'that': 0, 'well': 0, 'put': 0, 'If': 0, 'having': 0, 'one': 0, 'day': 0, 'fish': 0, 'have': 0, 'know': 0, 'll': 0, 'best': 0, 'away': 0, 'say': 0, 'an': 0, 'You': 0, 'coming': 0, 'you': 0, 'they': 0, ',': 0, 'be': 0, 'doctor': 0, '’': 0}\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('------------------------------------------------------')\n",
    "print('Count of next words, given that current word is \"fish\"')\n",
    "print('------------------------------------------------------')\n",
    "print(counts['fish'])\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see, the counts are currently empty; that's because we've only just initialized this object and haven't actually counted anything yet! Let's do that now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(len(unigrams)-1):\n",
    "    counts[unigrams[i]][unigrams[i+1]] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's take a look at that `fish` count again!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------------------------------------------------\n",
      "Count of next words, given that current word is \"fish\"\n",
      "------------------------------------------------------\n",
      "{'also': 0, 'the': 0, '.': 0, 'with': 0, ';': 0, 'because': 0, 'it': 0, 'a': 0, 'for': 0, 'place': 0, 'keeps': 3, '!': 0, 'cold': 0, 'apple': 0, 'in': 0, 'if': 0, 'fridge': 0, 'that': 0, 'well': 0, 'put': 0, 'If': 0, 'having': 0, 'one': 0, 'day': 0, 'fish': 0, 'have': 0, 'know': 0, 'll': 0, 'best': 0, 'away': 0, 'say': 0, 'an': 0, 'You': 0, 'coming': 0, 'you': 0, 'they': 0, ',': 1, 'be': 0, 'doctor': 0, '’': 0}\n",
      "\n",
      "\n",
      "------------------------------------------------------\n",
      "Count of next word \"keeps\", given that current word is \"fish\"\n",
      "------------------------------------------------------\n",
      "3\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('------------------------------------------------------')\n",
    "print('Count of next words, given that current word is \"fish\"')\n",
    "print('------------------------------------------------------')\n",
    "print(counts['fish'])\n",
    "\n",
    "print('\\n')\n",
    "print('------------------------------------------------------')\n",
    "print('Count of next word \"keeps\", given that current word is \"fish\"')\n",
    "print('------------------------------------------------------')\n",
    "print(counts['fish']['keeps'])\n",
    "\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have a count of the words, we can convert these to probabilities by simply dividing by the total incidence of next words, for a given current word:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [],
   "source": [
    "# initialize the probabilites JSON object\n",
    "probs = {}\n",
    "for given_word in vocabulary:\n",
    "    probs[given_word] = {}\n",
    "    for next_word in vocabulary:\n",
    "        probs[given_word][next_word] = 0\n",
    "\n",
    "# convert the counts to probabilites\n",
    "for key, value in counts.items():\n",
    "    denominator = 0\n",
    "    for key2, value2 in counts[key].items():\n",
    "        denominator += value2\n",
    "\n",
    "    for key2, value2 in counts[key].items():\n",
    "        probs[key][key2] = value2 / denominator\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's check the probability of the next word being `keeps`, given that the current word is `fish` "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------------------------------------------------\n",
      "The probability of the next word being keeps,\n",
      "given that the current word is fish:\n",
      "------------------------------------------------------\n",
      "75.0%\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('------------------------------------------------------')\n",
    "print('The probability of the next word being keeps,') \n",
    "print('given that the current word is fish:')\n",
    "print('------------------------------------------------------')\n",
    "print(str(100*probs['fish']['keeps']) + '%')\n",
    "print('\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And there you have it! You have built your first data-driven language model. Congratulations! Now let's get to work doing some fun things with the language model, like simulating new sentences. Let's do that by choosing a word, and then selecting the next word in accordance to the probability given by our language model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Given the token :  a\n",
      " The next token is :  day\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def sample_next_gram_from_language_model(probs, given_token):\n",
    "    distribution            = list(probs[given_token].values())\n",
    "    sample_from_multinomial = np.random.multinomial(1,distribution)\n",
    "    sample_index            = np.where(sample_from_multinomial==1)[0][0]\n",
    "    word_keys               = list(probs[given_token].keys())\n",
    "    next_word               = word_keys[sample_index]\n",
    "    return(next_word)\n",
    "    \n",
    "given_token = \"a\"\n",
    "next_token  = sample_next_gram_from_language_model(probs,given_token)\n",
    "\n",
    "print(' Given the token :  ' + given_token)\n",
    "print(' The next token is :  ' + next_token)\n",
    "print('\\n')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have a language model built, we can do all sorts of useful things. Including running our model to generate new sentences we've never seen before:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---------------------------------------\n",
      "a cold place . a fish keeps for a cold place\n",
      "a day keeps best if you put it with an apple\n",
      "a fish keeps best if you ’ ll be having fish\n"
     ]
    }
   ],
   "source": [
    "def create_new_sentence(length, seed_token):\n",
    "    tokens = [seed_token]\n",
    "    for i in range(length):\n",
    "        tokens.append(sample_next_gram_from_language_model(probs,tokens[-1]))  \n",
    "    return tokens\n",
    "      \n",
    "print('---------------------------------------')\n",
    "print(' '.join(create_new_sentence(10, 'a')))\n",
    "print(' '.join(create_new_sentence(10, 'a')))\n",
    "print(' '.join(create_new_sentence(10, 'a')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr> \n",
    "\n",
    "## Learning Exercise 4:\n",
    "#### Worth 2/5 Points\n",
    "Now that you have built your first language model, let's turn our attention back to the philosophers. For this final learning exercise, you will be building a tri-gram `Nietzsche language model`, and a tri-gram `Russel Language Model` using the 5 books from each of the philosophers you collected from Project Gutenburg earlier. \n",
    "\n",
    "Generate a conversation between your philosophers models by seeding one of the models with a tri-gram and allow it to run until it generates a terminating character (a '.', '?' or '!'). Then, have the other model generate a response by providing the ending tri-gram of the the first model as the seed tri-gram for the other model. Iterate like this for 15 sentences and print the text.\n",
    "\n",
    "**Note:** You probably learned from the earlier components of this assignment that Nietzsche and Russel have slightly different writing styles (yes, that was an understatement). For this reason, there are likely to be instances where the ending tri-gram from your Nietzsche model does not show up in the Russel language model and vice-versa. Use Laplace smoothing to handle this problem.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "################################################################################\n",
    "# INSERT YOUR CODE HERE\n",
    "# DO NOT FORGET TO PRINT YOUR MEANINGFUL RESULTS TO THE SCREEN.\n",
    "################################################################################"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<span style=\"color:red\"> INSERT AN INTERPRETATION OF YOUR RESULTS HERE </span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1><span style=\"color:red\"> Self Assessment </span></h1>\n",
    "Please provide an assessment of how successfully you accomplished the learning exercises in this assignment according to the instruction provided; do not assign yourself points for effort. This self assessment will be used as a starting point when I grade your assignments. Please note that if you over-estimate your grade on a given learning exercise, you will face a 50% penalty on the total points granted for that exercise. If you underestimate your grade, there will be no penalty.\n",
    "\n",
    "* Learning Exercise 1: \n",
    "    * <span style=\"color:red\">X</span>/1 points\n",
    "* Learning Exercise 2: \n",
    "    * <span style=\"color:red\">X</span>/1 points\n",
    "* Learning Exercise 3:\n",
    "    * <span style=\"color:red\">X</span>/1 points\n",
    "* Learning Exercise 4:\n",
    "    * <span style=\"color:red\">X</span>/2 points\n",
    "\n",
    "#### Total Grade: \n",
    "<span style=\"color:red\">X</span>/5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}