Lab 03_ Ngrams.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "# Lab 03: N-grams\n",
        "\n",
        "## Overview\n",
        "\n",
        "An *n-gram* -- in the context of parsing natural languages such as English -- is a sequence of *n* consecutive *tokens* (which we might define as characters separated by whitespace) from some passage of text. Based on the following passage:\n",
        "\n",
        "> I really really like cake.\n",
        "\n",
        "We have the following 2-grams:\n",
        "\n",
        "    [('I', 'really'), ('really', 'really'), ('really', 'like'), ('like', 'cake.')]\n",
        "\n",
        "And the following 3-grams:\n",
        "\n",
        "    [('I', 'really', 'really'),\n",
        "     ('really', 'really', 'like'),\n",
        "     ('really', 'like', 'cake.')]\n",
        "\n",
        "(I omit a 1-gram listing because it would merely be a list of all tokens in the original text.)\n",
        "\n",
        "Among other things, n-grams are useful for describing the vocabulary of and statistical correlation between tokens in a sample body of text (e.g., as taken from a book). We can use an n-gram model to determine the likelihood of finding\n",
        "a particular sequence of words after another. This information, in turn, can be used to generate passages of text that statistically mimic the sample.\n",
        "\n",
        "We can convert the above 3-gram list into the following lookup structure (i.e., a dictionary mapping strings to lists of 2-tuples), where the first token of each n-gram maps to all sequences that follow it in the text:\n",
        "\n",
        "    {'I': [('really', 'really')],\n",
        "     'really': [('really', 'like'), ('like', 'cake.')]}\n",
        "\n",
        "We can now generate passages of text using the following method:\n",
        "\n",
        "1. Select a random key and use it as the start token of the passage. It will also serve as the current token for the next step.\n",
        "2. Select a random tuple from the list associated with the current token and append the sequence to the passage. The last token of the selected sequence will be the new current token.\n",
        "3. If the current token is a key in the dictionary then simply repeat step 2, otherwise select another random key from the dictionary as the current token and append it to the passage before repeating step 2.\n",
        "\n",
        "E.g., we might start by selecting `'I'` in step (1), which gives us `('really', 'really')` as our only choice in (2). The second `'really'` in that tuple is the new current token (which is a valid key), which takes us back to (2) and gives us a choice between two tuples. If we choose `('like', 'cake.')`, then we have `'cake.'` as our new current token --- it is not a key in the map, however, so we'd have to choose a new random key if we wanted to generate a longer passage. Either way, the passage we've generated thus far is `'I really really like cake.'` (which also happens to be the original passage).\n",
        "\n",
        "Here's a lengthier passage that could be generated from the 3-gram dictionary above -- note that for clarity I've added `*`'s every time a new random key is selected (i.e., when the previous token isn't a key in the dictionary):\n",
        "\n",
        "> \\* really like cake. \\* I really really really like \\* really like cake. \\* I really really really like \\* really\n",
        "\n",
        "This gets more interesting when we build n-gram dictionaries from lengthier bodies of text. For instance, the following text was generated (with a little programmed embellishment for prettier capitalization and punctuation) from a 3-gram dictionary extracted from Romeo's famous balcony monologue:\n",
        "\n",
        "> Lamp her eyes were there they in their spheres till they in her eyes in all the fairest stars in all the heaven having some business do wear it is my love! O it is envious her cheek would through the heaven having some business do entreat her eyes were there they in their spheres till they in her eyes to.\n",
        "\n",
        "For reference, here is the dictionary entry for the token `'her'` used to generate the above:\n",
        "\n",
        "    'her': [('maid', 'art'),\n",
        "            ('maid', 'since'),\n",
        "            ('vestal', 'livery'),\n",
        "            ('eyes', 'to'),\n",
        "            ('eyes', 'were'),\n",
        "            ('head?', 'The'),\n",
        "            ('cheek', 'would'),\n",
        "            ('eyes', 'in'),\n",
        "            ('cheek', 'upon'),\n",
        "            ('hand!', 'O')],\n",
        "\n",
        "If you haven't already guessed it, your assignment is to implement a function that constructs an n-gram dictionary from a list of strings (tokens), and another that returns a passage of text generated from a given n-gram dictionary."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "## Implementation Details\n",
        "\n",
        "Before you start working on the aforementioned functions, it's important to consider how we'll be parsing passages for tokens.\n",
        "\n",
        "Here's the body of Romeo's balcony soliloquy:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "deletable": false,
        "editable": false,
        "id": "romeo",
        "nbgrader": {
          "grade": false,
          "grade_id": "romeo",
          "locked": true,
          "schema_version": 1,
          "solution": false
        },
        "state": "read_only",
        "trusted": true
      },
      "outputs": [],
      "source": [
        "ROMEO_SOLILOQUY = \"\"\"\n",
        "        But, soft! what light through yonder window breaks?\n",
        "        It is the east, and Juliet is the sun.\n",
        "        Arise, fair sun, and kill the envious moon,\n",
        "        who is already sick and pale with grief, \n",
        "        That thou her maid art far more fair than she:\n",
        "        be not her maid, since she is envious;\n",
        "        her vestal livery is but sick and green\n",
        "        and none but fools do wear it; cast it off.\n",
        "        It is my lady, O, it is my love! \n",
        "        O, that she knew she were!\n",
        "        She speaks yet she says nothing: what of that?\n",
        "        Her eye discourses; I will answer it.\n",
        "        I am too bold, 'tis not to me she speaks:\n",
        "        two of the fairest stars in all the heaven, \n",
        "        having some business, do entreat her eyes\n",
        "        to twinkle in their spheres till they return.\n",
        "        What if her eyes were there, they in her head?\n",
        "        The brightness of her cheek would shame those stars,\n",
        "        as daylight doth a lamp; her eyes in heaven \n",
        "        would through the airy region stream so bright\n",
        "        that birds would sing and think it were not night.\n",
        "        See, how she leans her cheek upon her hand!\n",
        "        O, that I were a glove upon that hand,\n",
        "        that I might touch that cheek!\"\"\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "Using the string's built-in `split` method --- previously mentioned in class --- along with `lower`, we can derive from the passage a list of tokens."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "state": "normal",
        "trusted": true
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "['but,', 'soft!', 'what', 'light', 'through', 'yonder', 'window', 'breaks?']"
            ]
          },
          "execution_count": 3,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "toks = [t.lower() for t in ROMEO_SOLILOQUY.split()]\n",
        "\n",
        "toks[0:8]"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "We could do more interesting things (such as separating out punctuation), but we'll keep our parser simple. For the sake of consistency, we'll rely on this fairly straighttforward approach to parsing. Onwards!\n",
        "\n",
        "### `compute_ngrams`\n",
        "\n",
        "Your first task is to write `compute_ngrams`, which will take a list of tokens, a value `n` indicating the n-gram length (e.g., 3 for 3-grams), and return an n-gram dictionary. The keys in the returned dictionary should all be strings, whose values will be lists of one or more tuples. Note that even in the case of `n`=2 (which would be the minimum value) the dictionary should map strings to lists of 1-tuples (i.e., instead of to lists of individual tokens)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "deletable": false,
        "id": "compute_ngrams",
        "nbgrader": {
          "grade": false,
          "grade_id": "compute_ngrams",
          "locked": false,
          "schema_version": 1,
          "solution": true
        },
        "starter_code": "def compute_ngrams(toks, n=2):\n    \"\"\"Returns an n-gram dictionary based on the provided list of tokens.\"\"\"\n    ",
        "state": "graded",
        "trusted": true
      },
      "outputs": [],
      "source": [
        "def compute_ngrams(toks, n=2):\n",
        "    \"\"\"Returns an n-gram dictionary based on the provided list of tokens.\"\"\"\n",
        "    ret = {}\n",
        "    lst = []\n",
        "    # trans to ngram lists\n",
        "    for i in range(len(toks)-n+1):\n",
        "        x = []  #to transfer to tuple\n",
        "        num = i\n",
        "        for _ in range(n):\n",
        "            x.append(toks[num])\n",
        "            num+=1\n",
        "        lst.append(tuple(x))\n",
        "    # trans to the dict\n",
        "    for j in lst:\n",
        "        y = []  #trans to tuple\n",
        "        for k in range(1,n):\n",
        "            y.append(j[k])\n",
        "\n",
        "        y = tuple(y)\n",
        "        lst1 = []\n",
        "        if j[0] in ret:\n",
        "            lst1 = ret[j[0]]\n",
        "        lst1.append(y)\n",
        "        ret[j[0]] = lst1\n",
        "\n",
        "    return ret\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "And now for some simple tests:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "deletable": false,
        "editable": false,
        "id": "test_compute_ngrams",
        "nbgrader": {
          "grade": true,
          "grade_id": "test_compute_ngrams",
          "locked": true,
          "points": 5,
          "schema_version": 1,
          "solution": false
        },
        "state": "read_only",
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "{'i': [('really',)], 'really': [('really',), ('like',)], 'like': [('cake.',)]}\n",
            "{'i': [('really', 'really')], 'really': [('really', 'like'), ('like', 'cake.')]}\n"
          ]
        }
      ],
      "source": [
        "# (5 points)\n",
        "\n",
        "from unittest import TestCase\n",
        "tc = TestCase()\n",
        "\n",
        "simple_toks = [t.lower() for t in 'I really really like cake.'.split()]\n",
        "#print(simple_toks)\n",
        "print(compute_ngrams(simple_toks))\n",
        "print(compute_ngrams(simple_toks, n=3))\n",
        "tc.assertEqual(compute_ngrams(simple_toks), \n",
        "               {'i': [('really',)], 'like': [('cake.',)], 'really': [('really',), ('like',)]})\n",
        "tc.assertEqual(compute_ngrams(simple_toks, n=3), \n",
        "               {'i': [('really', 'really')],\n",
        "                'really': [('really', 'like'), ('like', 'cake.')]})\n",
        "\n",
        "romeo_toks = [t.lower() for t in ROMEO_SOLILOQUY.split()]\n",
        "\n",
        "dct = compute_ngrams(romeo_toks, n=4)\n",
        "tc.assertEqual(dct['but'], [('sick', 'and', 'green'), ('fools', 'do', 'wear')])\n",
        "tc.assertEqual(dct['it'], \n",
        "              [('is', 'the', 'east,'),\n",
        "               ('off.', 'it', 'is'),\n",
        "               ('is', 'my', 'lady,'),\n",
        "               ('is', 'my', 'love!'),\n",
        "               ('were', 'not', 'night.')])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "I've also placed the entire text of Peter Pan (courtesy of [Project Gutenberg][]) on the server, to be used to stress test your function just a bit. Evaluate the following cell to read the text of the book into `peter_pan_text`.\n",
        "\n",
        "If you're not on the course server, you can uncomment the line to read the text directly from the Project Gutenberg website and comment out the lines which access the file for testing.\n",
        "\n",
        "[Project Gutenberg]: http://gutenberg.org"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "deletable": false,
        "editable": false,
        "id": "load_peter_pan",
        "state": "read_only",
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "All children, except one, grow up. They soon know that they will grow\n",
            "up, and the way Wendy knew was this. One day when she was two years old\n",
            "she was playing in a garden, and she plucked another flower and ran with\n",
            "it to her mother. I suppose she must have looked rather delightful, for\n",
            "Mrs. Darling put her hand to her heart and cried, “Oh, why can't you\n",
            "remain like this for ever!” This was all that passed between them on\n",
            "the subject, but henceforth Wendy knew that she must grow up. You always\n",
            "know after you are two. Two is the beginning of the end.\n",
            "\n",
            "Of course they lived at 14 [their house number on their street], and\n",
            "until Wendy came her mother was the chief one. She was a lovely lady,\n",
            "with a romantic mind and such a sweet mocking mouth. Her romantic\n",
            "mind was like the tiny boxes, one within the other, that come from the\n",
            "puzzling East, however many you discover there is always one more; and\n",
            "her sweet mocking mouth had one kiss on it that Wendy could never get,\n",
            "though ther\n"
          ]
        }
      ],
      "source": [
        "import urllib.request\n",
        "PETER_PAN_URL      = 'https://moss.cs.iit.edu/cs331/data/peterpan.txt'\n",
        "\n",
        "peter_pan_text = urllib.request.urlopen(PETER_PAN_URL).read().decode()\n",
        "chapt1_start = peter_pan_text.index('All children')\n",
        "print(peter_pan_text[chapt1_start:chapt1_start+1000])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "Time for some larger test cases!"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "deletable": false,
        "editable": false,
        "id": "test_compute_ngrams_2",
        "nbgrader": {
          "grade": true,
          "grade_id": "test_compute_ngrams_2",
          "locked": true,
          "points": 5,
          "schema_version": 1,
          "solution": false
        },
        "state": "read_only",
        "trusted": true
      },
      "outputs": [],
      "source": [
        "# (5 points)\n",
        "\n",
        "from unittest import TestCase\n",
        "tc = TestCase()\n",
        "\n",
        "pp_toks = [t.lower() for t in peter_pan_text.split()]\n",
        "dct = compute_ngrams(pp_toks, n=3)\n",
        "tc.assertEqual(dct['crocodile'], \n",
        "               [('passes,', 'but'),\n",
        "                ('that', 'happened'),\n",
        "                ('would', 'have'),\n",
        "                ('was', 'in'),\n",
        "                ('passed', 'him,'),\n",
        "                ('is', 'about'),\n",
        "                ('climbing', 'it.'),\n",
        "                ('that', 'was'),\n",
        "                ('pass', 'by'),\n",
        "                ('and', 'let'),\n",
        "                ('was', 'among'),\n",
        "                ('was', 'waiting')])\n",
        "tc.assertEqual(len(dct['wendy']), 202)\n",
        "tc.assertEqual(len(dct['peter']), 243)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "### Random selection"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "One more thing before you start work on generating passages from an n-gram dictionary: we need a way to choose a random item from a sequence.\n",
        "\n",
        "The [`random.choice` function](https://docs.python.org/3/library/random.html#random.choice) provides just this functionality. Consider (and feel free to play with) the following examples --- you should, at the very least, evaluate the cell a few separate times to see the results:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "state": "normal",
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "tigers\n",
            "78\n",
            "('like', 'cake')\n"
          ]
        }
      ],
      "source": [
        "import random\n",
        "print(random.choice(['lions', 'tigers', 'bears']))\n",
        "print(random.choice(range(100)))\n",
        "print(random.choice([('really', 'like'), ('like', 'cake')]))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "Note that a separate tutorial on random number generators (and other [`random` module](https://docs.python.org/3/library/random.html) APIs) will be posted separately, but for now just understanding how to use `random.choice` should be sufficient for this assignment."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "### `gen_passage`\n",
        "\n",
        "Finally, you're ready to implement `gen_passage`, which will take an n-gram dictionary and a length for the passage to generate (as a token count). \n",
        "\n",
        "As described earlier, it will work as follows:\n",
        "\n",
        "1. Select a random key from the dictionary and use it as the start token of the passage. It will also serve as the current token for the next step.\n",
        "2. Select a random tuple from the list associated with the current token and append the sequence to the passage. The last token of the selected sequence will be the new current token.\n",
        "3. If the current token is a key in the dictionary then simply repeat step 2, otherwise select another random key from the map as the current token and append it to the passage before repeating step 2.\n",
        "\n",
        "You will use `random.choice` whenever a random selection needs to be made. In order for your results to be reproduceable, be sure to sort the dictionary's keys (which, recall, are in no discernible order) before selecting a random one, like this (assuming `ngram_dict` is the dictionary):\n",
        "\n",
        "    random.choice(sorted(ngram_dict.keys()))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 53,
      "metadata": {
        "deletable": false,
        "id": "gen_passage",
        "nbgrader": {
          "grade": true,
          "grade_id": "gen_passage",
          "locked": false,
          "points": 5,
          "schema_version": 1,
          "solution": true
        },
        "starter_code": "import random\n\ndef gen_passage(ngram_dict, length=100):\n    ",
        "state": "graded",
        "trusted": true
      },
      "outputs": [],
      "source": [
        "import random\n",
        "\n",
        "\n",
        "def gen_passage(ngram_dict, length=100):\n",
        "    ret_lst = []\n",
        "    while len(ret_lst) < length:\n",
        "        m = random.choice(sorted(ngram_dict.keys()))\n",
        "        ret_lst.append(m)\n",
        "        print(m,1)\n",
        "        if len(ret_lst) < length:\n",
        "            n = random.choice(ngram_dict[m])\n",
        "            ret_lst.append(n[0])\n",
        "            p = n[0]\n",
        "            print(p,2)\n",
        "            while True:\n",
        "                if p in ngram_dict and len(ret_lst) < length:\n",
        "                    p = random.choice(ngram_dict[p])[0]\n",
        "                    ret_lst.append(p)\n",
        "                    print(p,3)\n",
        "                else:\n",
        "                    break\n",
        "\n",
        "    ret = ''\n",
        "    for i in range(len(ret_lst)):\n",
        "        ret += ret_lst[i]\n",
        "        if i != len(ret_lst)-1:\n",
        "            ret += ' '\n",
        "    return ret\n",
        "                    \n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "state": "normal"
      },
      "source": [
        "For the following test cases to work, it is *critical* that you do not invoke `random.choice` more than is absolutely necessary, and only as prescribed in the steps described above!\n",
        "\n",
        "Note that in addition to the automated test cases, we'll also be manually grading your code above."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 54,
      "metadata": {
        "deletable": false,
        "editable": false,
        "id": "gen_passage_test",
        "nbgrader": {
          "grade": true,
          "grade_id": "gen_passage_test",
          "locked": true,
          "points": 5,
          "schema_version": 1,
          "solution": false
        },
        "state": "read_only",
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "{'i': [('really',)], 'really': [('really',), ('like',)], 'like': [('cake.',)]}\n",
            "like 1\n",
            "cake. 2\n",
            "i 1\n",
            "really 2\n",
            "really 3\n",
            "really 3\n",
            "really 3\n",
            "like 3\n",
            "cake. 3\n",
            "i 1\n",
            "too 1\n",
            "bold, 2\n",
            "'tis 3\n",
            "not 3\n",
            "night. 3\n",
            "see, 3\n",
            "how 3\n",
            "she 3\n",
            "leans 3\n",
            "her 3\n"
          ]
        }
      ],
      "source": [
        "# (10 points)\n",
        "\n",
        "from unittest import TestCase\n",
        "tc = TestCase()\n",
        "\n",
        "random.seed(1234)\n",
        "simple_toks = [t.lower() for t in 'I really really like cake.'.split()]\n",
        "print(compute_ngrams(simple_toks))\n",
        "#print(gen_passage(compute_ngrams(simple_toks), 10))\n",
        "tc.assertEqual(gen_passage(compute_ngrams(simple_toks), 10),\n",
        "               'like cake. i really really really really like cake. i')\n",
        "\n",
        "random.seed(1234)\n",
        "romeo_toks = [t.lower() for t in ROMEO_SOLILOQUY.split()]\n",
        "tc.assertEqual(gen_passage(compute_ngrams(romeo_toks), 10),\n",
        "               'too bold, \\'tis not night. see, how she leans her')"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3.8.8 ('base')",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8.8"
    },
    "mimir": {
      "data": {},
      "last_submission_id": "",
      "project_id": "5900787b-23f6-4898-8bf1-1f613be7c3e7"
    },
    "varInspector": {
      "cols": {
        "lenName": 16,
        "lenType": 16,
        "lenVar": 40
      },
      "kernels_config": {
        "python": {
          "delete_cmd_postfix": "",
          "delete_cmd_prefix": "del ",
          "library": "var_list.py",
          "varRefreshCmd": "print(var_dic_list())"
        },
        "r": {
          "delete_cmd_postfix": ") ",
          "delete_cmd_prefix": "rm(",
          "library": "var_list.r",
          "varRefreshCmd": "cat(var_dic_list()) "
        }
      },
      "types_to_exclude": [
        "module",
        "function",
        "builtin_function_or_method",
        "instance",
        "_Feature"
      ],
      "window_display": false
    },
    "vscode": {
      "interpreter": {
        "hash": "ad2bdc8ecc057115af97d19610ffacc2b4e99fae6737bb82f5d7fb13d2f2c186"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}