chapters/chap12.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1331faa1",
   "metadata": {},
   "source": [
    "You can order print and ebook versions of *Think Python 3e* from\n",
    "[Bookshop.org](https://bookshop.org/a/98697/9781098155438) and\n",
    "[Amazon](https://www.amazon.com/_/dp/1098155432?smid=ATVPDKIKX0DER&_encoding=UTF8&tag=oreilly20-20&_encoding=UTF8&tag=greenteapre01-20&linkCode=ur2&linkId=e2a529f94920295d27ec8a06e757dc7c&camp=1789&creative=9325)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6c6265de",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from os.path import basename, exists\n",
    "\n",
    "def download(url):\n",
    "    filename = basename(url)\n",
    "    if not exists(filename):\n",
    "        from urllib.request import urlretrieve\n",
    "\n",
    "        local, _ = urlretrieve(url, filename)\n",
    "        print(\"Downloaded \" + str(local))\n",
    "    return filename\n",
    "\n",
    "download('https://github.com/AllenDowney/ThinkPython/raw/v3/thinkpython.py');\n",
    "download('https://github.com/AllenDowney/ThinkPython/raw/v3/diagram.py');\n",
    "\n",
    "import thinkpython"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59a8621b",
   "metadata": {},
   "source": [
    "# Text Analysis and Generation\n",
    "\n",
    "At this point we have covered Python's core data structures -- lists, dictionaries, and tuples -- and and some algorithms that use them.\n",
    "In this chapter, we'll use them to explore text analysis and Markov generation:\n",
    "\n",
    "* Text analysis is a way to describe the statistical relationships between the words in a document, like the probability that one word is followed by another, and\n",
    "\n",
    "* Markov generation is a way to generate new text with words and phrases similar to the original text.\n",
    "\n",
    "These algorithms are similar to parts of a Large Language Model (LLM), which is the key component of a chatbot.\n",
    "\n",
    "We'll start by counting the number of times each word appears in a book.\n",
    "Then we'll look at pairs of words, and make a list of the words that can follow each word.\n",
    "We'll make a simple version of a Markov generator, and as an exercise, you'll have a chance to make a more general version."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e3811b8",
   "metadata": {},
   "source": [
    "## Unique words\n",
    "\n",
    "As a first step toward text analysis, let's read a book -- *The Strange Case Of Dr. Jekyll And Mr. Hyde* by Robert Louis Stevenson -- and count the number of unique words.\n",
    "Instructions for downloading the book are in the notebook for this chapter."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6567e1bf",
   "metadata": {
    "tags": []
   },
   "source": [
    "The following cell downloads the book from Project Gutenberg."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4cd1c980",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://www.gutenberg.org/cache/epub/43/pg43.txt');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5465ab1d",
   "metadata": {
    "tags": []
   },
   "source": [
    "The version available from Project Gutenberg includes information about the book at the beginning and license information at the end.\n",
    "We'll use `clean_file` from Chapter 8 to remove this material and write a \"clean\" file that contains only the text of the book."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "52ebfe94",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def is_special_line(line):\n",
    "    return line.strip().startswith('*** ')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "49cfc352",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "def clean_file(input_file, output_file):\n",
    "    reader = open(input_file, encoding='utf-8')\n",
    "    writer = open(output_file, 'w')\n",
    "\n",
    "    for line in reader:\n",
    "        if is_special_line(line):\n",
    "            break\n",
    "\n",
    "    for line in reader:\n",
    "        if is_special_line(line):\n",
    "            break\n",
    "        writer.write(line)\n",
    "        \n",
    "    reader.close()\n",
    "    writer.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "44e53ce6",
   "metadata": {},
   "outputs": [],
   "source": [
    "filename = 'dr_jekyll.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "50d1fafa",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "clean_file('pg43.txt', filename)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc66d7e2",
   "metadata": {},
   "source": [
    "We'll use a `for` loop to read lines from the file and `split` to divide the lines into words.\n",
    "Then, to keep track of unique words, we'll store each word as a key in a dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "16d24028",
   "metadata": {},
   "outputs": [],
   "source": [
    "unique_words = {}\n",
    "for line in open(filename):\n",
    "    seq = line.split()\n",
    "    for word in seq:\n",
    "        unique_words[word] = 1\n",
    "\n",
    "len(unique_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85171a3a",
   "metadata": {},
   "source": [
    "The length of the dictionary is the number of unique words -- about `6000` by this way of counting.\n",
    "But if we inspect them, we'll see that some are not valid words.\n",
    "\n",
    "For example, let's look at the longest words in `unique_words`.\n",
    "We can use `sorted` to sort the words, passing the `len` function as a keyword argument so the words are sorted by length."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "1668e6bd",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(unique_words, key=len)[-5:]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "795f5327",
   "metadata": {},
   "source": [
    "The slice index, `[-5:]`, selects the last `5` elements of the sorted list, which are the longest words. \n",
    "\n",
    "The list includes some legitimately long words, like \"circumscription\", and some hyphenated words, like \"chocolate-coloured\".\n",
    "But some of the longest \"words\" are actually two words separated by a dash.\n",
    "And other words include punctuation like periods, exclamation points, and quotation marks.\n",
    "\n",
    "So, before we move on, let's deal with dashes and other punctuation."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf89fafa",
   "metadata": {},
   "source": [
    "## Punctuation\n",
    "\n",
    "To identify the words in the text, we need to deal with two issues:\n",
    "\n",
    "* When a dash appears in a line, we should replace it with a space -- then when we use `split`, the words will be separated.\n",
    "\n",
    "* After splitting the words, we can use `strip` to remove punctuation.\n",
    "\n",
    "To handle the first issue, we can use the following function, which takes a string, replaces dashes with spaces, splits the string, and returns the resulting list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "ed5f0a43",
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_line(line):\n",
    "    return line.replace('—', ' ').split()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5decdec",
   "metadata": {},
   "source": [
    "Notice that `split_line` only replaces dashes, not hyphens.\n",
    "Here's an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "a9df2aeb",
   "metadata": {},
   "outputs": [],
   "source": [
    "split_line('coolness—frightened')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d9eb318",
   "metadata": {},
   "source": [
    "Now, to remove punctuation from the beginning and end of each word, we can use `strip`, but we need a list of characters that are considered punctuation.\n",
    "\n",
    "Characters in Python strings are in Unicode, which is an international standard used to represent letters in nearly every alphabet, numbers, symbols, punctuation marks, and more.\n",
    "The `unicodedata` module provides a `category` function we can use to tell which characters are punctuation.\n",
    "Given a letter, it returns a string with information about what category the letter is in."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "b138b123",
   "metadata": {},
   "outputs": [],
   "source": [
    "import unicodedata\n",
    "\n",
    "unicodedata.category('A')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "994835ea",
   "metadata": {},
   "source": [
    "The category string of `'A'` is `'Lu'` -- the `'L'` means it is a letter and the `'u'` means it is uppercase.\n",
    "\n",
    "The category string of `'.'` is `'Po'` -- the `'P'` means it is punctuation and the `'o'` means its subcategory is \"other\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "fe65df44",
   "metadata": {},
   "outputs": [],
   "source": [
    "unicodedata.category('.')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03773b9b",
   "metadata": {},
   "source": [
    "We can find the punctuation marks in the book by checking for characters with categories that begin with `'P'`.\n",
    "The following loop stores the unique punctuation marks in a dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "b47a87cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "punc_marks = {}\n",
    "for line in open(filename):\n",
    "    for char in line:\n",
    "        category = unicodedata.category(char)\n",
    "        if category.startswith('P'):\n",
    "            punc_marks[char] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6741dfa",
   "metadata": {},
   "source": [
    "To make a list of punctuation marks, we can join the keys of the dictionary into a string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "348949be",
   "metadata": {},
   "outputs": [],
   "source": [
    "punctuation = ''.join(punc_marks)\n",
    "print(punctuation)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6af8d5a2",
   "metadata": {},
   "source": [
    "Now that we know which characters in the book are punctuation, we can write a function that takes a word, strips punctuation from the beginning and end, and converts it to lower case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "06121901",
   "metadata": {},
   "outputs": [],
   "source": [
    "def clean_word(word):\n",
    "    return word.strip(punctuation).lower()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58a78cb1",
   "metadata": {},
   "source": [
    "Here's an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "881ed9f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "clean_word('“Behold!”')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "314e4fbd",
   "metadata": {},
   "source": [
    "Because `strip` removes characters from the beginning and end, it leaves hyphenated words alone."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "ab5d2fed",
   "metadata": {},
   "outputs": [],
   "source": [
    "clean_word('pocket-handkerchief')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99050f8a",
   "metadata": {},
   "source": [
    "Now here's a loop that uses `split_line` and `clean_word` to identify the unique words in the book."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "2fdfb936",
   "metadata": {},
   "outputs": [],
   "source": [
    "unique_words2 = {}\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        unique_words2[word] = 1\n",
    "\n",
    "len(unique_words2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "992e5466",
   "metadata": {},
   "source": [
    "With this stricter definition of what a word is, there are about 4000 unique words.\n",
    "And we can confirm that the list of longest words has been cleaned up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "3104d191",
   "metadata": {},
   "outputs": [],
   "source": [
    "sorted(unique_words2, key=len)[-5:]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8014c330",
   "metadata": {},
   "source": [
    "Now let's see how many times each word is used."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ef40180",
   "metadata": {},
   "source": [
    "## Word frequencies\n",
    "\n",
    "The following loop computes the frequency of each unique word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "4fba7d1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "word_counter = {}\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        if word not in word_counter:\n",
    "            word_counter[word] = 1\n",
    "        else:\n",
    "            word_counter[word] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd680b81",
   "metadata": {},
   "source": [
    "The first time we see a word, we initialize its frequency to `1`. If we see the same word again later, we increment its frequency.\n",
    "\n",
    "To see which words appear most often, we can use `items` to get the key-value pairs from `word_counter`, and sort them by the second element of the pair, which is the frequency.\n",
    "First we'll define a function that selects the second element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "4be34c95",
   "metadata": {},
   "outputs": [],
   "source": [
    "def second_element(t):\n",
    "    return t[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b15a5bd6",
   "metadata": {},
   "source": [
    "Now we can use `sorted` with two keyword arguments:\n",
    "\n",
    "* `key=second_element` means the items will be sorted according to the frequencies of the words.\n",
    "\n",
    "* `reverse=True` means they items will be sorted in reverse order, with the most frequent words first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "8efe7c4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "items = sorted(word_counter.items(), key=second_element, reverse=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db6812e2",
   "metadata": {},
   "source": [
    "Here are the five most frequent words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "79c17341",
   "metadata": {},
   "outputs": [],
   "source": [
    "for word, freq in items[:5]:\n",
    "    print(freq, word, sep='\\t')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "551e81bb",
   "metadata": {},
   "source": [
    "In the next section, we'll encapsulate this loop in a function.\n",
    "And we'll use it to demonstrate a new feature -- optional parameters."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45243ccc",
   "metadata": {},
   "source": [
    "## Optional parameters\n",
    "\n",
    "We've used built-in functions that take optional parameters.\n",
    "For example, `round` takes an optional parameters called `ndigits` that indicates how many decimal places to keep."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "838bcb4f",
   "metadata": {},
   "outputs": [],
   "source": [
    "round(3.141592653589793, ndigits=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ae60945",
   "metadata": {},
   "source": [
    "But it's not just built-in functions -- we can write functions with optional parameters, too.\n",
    "For example, the following function takes two parameters, `word_counter` and `num`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "90c45e7e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_most_common(word_counter, num=5):\n",
    "    items = sorted(word_counter.items(), key=second_element, reverse=True)\n",
    "\n",
    "    for word, freq in items[:num]:\n",
    "        print(freq, word, sep='\\t')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78cb1531",
   "metadata": {},
   "source": [
    "The second parameter looks like an assignment statement, but it's not -- it's an optional parameter.\n",
    "\n",
    "If you call this function with one argument, `num` gets the **default value**, which is `5`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "e106be95",
   "metadata": {},
   "outputs": [],
   "source": [
    "print_most_common(word_counter)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29753ad6",
   "metadata": {},
   "source": [
    "If you call this function with two arguments, the second argument gets assigned to `num` instead of the default value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "8101a510",
   "metadata": {},
   "outputs": [],
   "source": [
    "print_most_common(word_counter, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9bf907b",
   "metadata": {},
   "source": [
    "In that case, we would say the optional argument **overrides** the default value.\n",
    "\n",
    "If a function has both required and optional parameters, all of the required parameters have to come first, followed by the optional ones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "c046117b",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect SyntaxError\n",
    "\n",
    "def bad_function(n=5, word_counter):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f450df2",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Dictionary subtraction\n",
    "\n",
    "Suppose we want to spell-check a book -- that is, find a list of words that might be misspelled.\n",
    "One way to do that is to find words in the book that don't appear in a list of valid words.\n",
    "In previous chapters, we've used a list of words that are considered valid in word games like Scrabble.\n",
    "Now we'll use this list to spell-check Robert Louis Stevenson.\n",
    "\n",
    "We can think of this problem as set subtraction -- that is, we want to find all the words from one set (the words in the book) that are not in the other (the words in the list)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3804d82",
   "metadata": {
    "tags": []
   },
   "source": [
    "The following cell downloads the word list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "edd8ff1c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a46556c",
   "metadata": {},
   "source": [
    "As we've done before, we can read the contents of `words.txt` and split it into a list of strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "67ef3e08",
   "metadata": {},
   "outputs": [],
   "source": [
    "word_list = open('words.txt').read().split()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22becbab",
   "metadata": {},
   "source": [
    "The we'll store the words as keys in a dictionary so we can use the `in` operator to check quickly whether a word is valid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "471d58e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "valid_words = {}\n",
    "for word in word_list:\n",
    "    valid_words[word] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94cc7c61",
   "metadata": {},
   "source": [
    "Now, to identify words that appear in the book but not in the word list, we'll use `subtract`, which takes two dictionaries as parameters and returns a new dictionary that contains all the keys from one that are not in the other."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "4d4c3538",
   "metadata": {},
   "outputs": [],
   "source": [
    "def subtract(d1, d2):\n",
    "    res = {}\n",
    "    for key in d1:\n",
    "        if key not in d2:\n",
    "            res[key] = d1[key]\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e70c63b4",
   "metadata": {},
   "source": [
    "Here's how we use it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "8b42e014",
   "metadata": {},
   "outputs": [],
   "source": [
    "diff = subtract(word_counter, valid_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8ada7bd",
   "metadata": {},
   "source": [
    "To get a sample of words that might be misspelled, we can print the most common words in `diff`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "f48be152",
   "metadata": {},
   "outputs": [],
   "source": [
    "print_most_common(diff)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "deeec418",
   "metadata": {},
   "source": [
    "The most common \"misspelled\" words are mostly names and a few single-letter words (Mr. Utterson is Dr. Jekyll's friend and lawyer).\n",
    "\n",
    "If we select words that only appear once, they are more likely to be actual misspellings.\n",
    "We can do that by looping through the items and making a list of words with frequency `1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "5716f967",
   "metadata": {},
   "outputs": [],
   "source": [
    "singletons = []\n",
    "for word, freq in diff.items():\n",
    "    if freq == 1:\n",
    "        singletons.append(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98ae9281",
   "metadata": {},
   "source": [
    "Here are the last few elements of the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "b37219f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "singletons[-5:]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5040834",
   "metadata": {},
   "source": [
    "Most of them are valid words that are not in the word list.\n",
    "But `'reindue'` appears to be a misspelling of `'reinduce'`, so at least we found one legitimate error."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afcbbe19",
   "metadata": {},
   "source": [
    "## Random numbers\n",
    "\n",
    "As a step toward Markov text generation, next we'll choose a random sequence of words from `word_counter`.\n",
    "But first let's talk about randomness.\n",
    "\n",
    "Given the same inputs, most computer programs are **deterministic**, which means they generate the same outputs every time.\n",
    "Determinism is usually a good thing, since we expect the same calculation to yield the same result.\n",
    "For some applications, though, we want the computer to be unpredictable.\n",
    "Games are one example, but there are more.\n",
    "\n",
    "Making a program truly nondeterministic turns out to be difficult, but there are ways to fake it.\n",
    "One is to use algorithms that generate **pseudorandom** numbers.\n",
    "Pseudorandom numbers are not truly random because they are generated by a deterministic computation, but just by looking at the numbers it is all but impossible to distinguish them from random.\n",
    "\n",
    "The `random` module provides functions that generate pseudorandom numbers -- which I will simply call \"random\" from here on.\n",
    "We can import it like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "75b548a9",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "2bfa31ae",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# this cell initializes the random number generator so it \n",
    "# generates the same sequence each time the notebook runs.\n",
    "\n",
    "random.seed(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cbbd7f8",
   "metadata": {},
   "source": [
    "The `random` module provides a function called `choice` that chooses an element from a list at random, with every element having the same probability of being chosen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "6f5d5c1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "t = [1, 2, 3]\n",
    "random.choice(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57c15af2",
   "metadata": {},
   "source": [
    "If you call the function again, you might get the same element again, or a different one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "1445068b",
   "metadata": {},
   "outputs": [],
   "source": [
    "random.choice(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f0c2572",
   "metadata": {},
   "source": [
    "In the long run, we expect to get every element about the same number of times.\n",
    "\n",
    "If you use `choice` with a dictionary, you get a `KeyError`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "4fc47ecd",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "%%expect KeyError\n",
    "\n",
    "random.choice(word_counter)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "592722f3",
   "metadata": {},
   "source": [
    "To choose a random key, you have to put the keys in a list and then call `choice`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "91ae9d4c",
   "metadata": {},
   "outputs": [],
   "source": [
    "words = list(word_counter)\n",
    "random.choice(words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "172d72f6",
   "metadata": {},
   "source": [
    "If we generate a random sequence of words, it doesn't make much sense."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "8bf595c1",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(6):\n",
    "    word = random.choice(words)\n",
    "    print(word, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0e2fbc4",
   "metadata": {},
   "source": [
    "Part of the problem is that we are not taking into account that some words are more common than others.\n",
    "The results will be better if we choose words with different \"weights\", so that some are chosen more often than others.\n",
    "\n",
    "If we use the values from `word_counter` as weights, each word is chosen with a probability that depends on its frequency."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "22953b65",
   "metadata": {},
   "outputs": [],
   "source": [
    "weights = word_counter.values()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5098bf93",
   "metadata": {},
   "source": [
    "The `random` module provides another function called `choices` that takes weights as an optional argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "1c7cdf4d",
   "metadata": {},
   "outputs": [],
   "source": [
    "random.choices(words, weights=weights)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a3341e84",
   "metadata": {},
   "source": [
    "And it takes another optional argument, `k`, that specifies the number of words to select."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "a7a3aa42",
   "metadata": {},
   "outputs": [],
   "source": [
    "random_words = random.choices(words, weights=weights, k=6)\n",
    "random_words"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e57e6f3d",
   "metadata": {},
   "source": [
    "The result is a list of strings that we can join into something that's looks more like a sentence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "c4286fb3",
   "metadata": {},
   "outputs": [],
   "source": [
    "' '.join(random_words)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7a35dff",
   "metadata": {},
   "source": [
    "If you choose words from the book at random, you get a sense of the vocabulary, but a series of random words seldom makes sense because there is no relationship between successive words.\n",
    "For example, in a real sentence you expect an article like \"the\" to be followed by an adjective or a noun, and probably not a verb or adverb.\n",
    "So the next step is to look at these relationships between words."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0921dd53",
   "metadata": {},
   "source": [
    "## Bigrams\n",
    "\n",
    "Instead of looking at one word at a time, now we'll look at sequences of two words, which are called **bigrams**.\n",
    "A sequence of three words is called a **trigram**, and a sequence with some unspecified number of words is called an **n-gram**.\n",
    "\n",
    "Let's write a program that finds all of the bigrams in the book and the number of times each one appears.\n",
    "To store the results, we'll use a dictionary where\n",
    "\n",
    "* The keys are tuples of strings that represent bigrams, and \n",
    "\n",
    "* The values are integers that represent frequencies.\n",
    "\n",
    "Let's call it `bigram_counter`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "d8ee02f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "bigram_counter = {}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33f97a2a",
   "metadata": {},
   "source": [
    "The following function takes a list of two strings as a parameter.\n",
    "First it makes a tuple of the two strings, which can be used as a key in a dictionary.\n",
    "Then it adds the key to `bigram_counter`, if it doesn't exist, or increments the frequency if it does."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "bfdb1de1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_bigram(bigram):\n",
    "    key = tuple(bigram)\n",
    "    if key not in bigram_counter:\n",
    "        bigram_counter[key] = 1\n",
    "    else:\n",
    "        bigram_counter[key] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c30f429",
   "metadata": {},
   "source": [
    "As we go through the book, we have to keep track of each pair of consecutive words.\n",
    "So if we see the sequence \"man is not truly one\", we would add the bigrams \"man is\", \"is not\", \"not truly\", and so on.\n",
    "\n",
    "To keep track of these bigrams, we'll use a list called `window`, because it is like a window that slides over the pages of the book, showing only two words at a time.\n",
    "Initially, `window` is empty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "2e73df79",
   "metadata": {},
   "outputs": [],
   "source": [
    "window = []"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9376558c",
   "metadata": {},
   "source": [
    "We'll use the following function to process the words one at a time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "495ad429",
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_word(word):\n",
    "    window.append(word)\n",
    "    \n",
    "    if len(window) == 2:\n",
    "        count_bigram(window)\n",
    "        window.pop(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56895591",
   "metadata": {},
   "source": [
    "The first time this function is called, it appends the given word to `window`.\n",
    "Since there is only one word in the window, we don't have a bigram yet, so the function ends.\n",
    "\n",
    "The second time it's called -- and every time thereafter -- it appends a second word to `window`.\n",
    "Since there are two words in the window, it calls `count_bigram` to keep track of how many times each bigram appears.\n",
    "Then it uses `pop` to remove the first word from the window.\n",
    "\n",
    "The following program loops through the words in the book and processes them one at a time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "c1224061",
   "metadata": {},
   "outputs": [],
   "source": [
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        process_word(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "20c4627a",
   "metadata": {},
   "source": [
    "The result is a dictionary that maps from each bigram to the number of times it appears.\n",
    "We can use `print_most_common` to see the most common bigrams."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "4296485a",
   "metadata": {},
   "outputs": [],
   "source": [
    "print_most_common(bigram_counter)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "757bd309",
   "metadata": {},
   "source": [
    "Looking at these results, we can get a sense of which pairs of words are most likely to appear together.\n",
    "We can also use the results to generate random text, like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "e03fd803",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "random.seed(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "f6ee1840",
   "metadata": {},
   "outputs": [],
   "source": [
    "bigrams = list(bigram_counter)\n",
    "weights = bigram_counter.values()\n",
    "random_bigrams = random.choices(bigrams, weights=weights, k=6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eda80407",
   "metadata": {},
   "source": [
    "`bigrams` is a list of the bigrams that appear in the books.\n",
    "`weights` is a list of their frequencies, so `random_bigrams` is a sample where the probability a bigram is selected is proportional to its frequency. \n",
    "\n",
    "Here are the results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "d6c65d79",
   "metadata": {},
   "outputs": [],
   "source": [
    "for pair in random_bigrams:\n",
    "    print(' '.join(pair), end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f24c3b6",
   "metadata": {},
   "source": [
    "This way of generating text is better than choosing random words, but still doesn't make a lot of sense."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a13d93b5",
   "metadata": {},
   "source": [
    "## Markov analysis\n",
    "\n",
    "We can do better with Markov chain text analysis, which computes, for each word in a text, the list of words that come next.\n",
    "As an example, we'll analyze these lyrics from the Monty Python song *Eric, the Half a Bee*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "3171d592",
   "metadata": {},
   "outputs": [],
   "source": [
    "song = \"\"\"\n",
    "Half a bee, philosophically,\n",
    "Must, ipso facto, half not be.\n",
    "But half the bee has got to be\n",
    "Vis a vis, its entity. D'you see?\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "583ab9f0",
   "metadata": {},
   "source": [
    "To store the results, we'll use a dictionary that maps from each word to the list of words that follow it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "3321e6a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map = {}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5d85b09",
   "metadata": {},
   "source": [
    "As an example, let's start with the first two words of the song."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "e4e55c71",
   "metadata": {},
   "outputs": [],
   "source": [
    "first = 'half'\n",
    "second = 'a'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0349fe78",
   "metadata": {},
   "source": [
    "If the first word is not in `successor_map`, we have to add a new item that maps from the first word to a list containing the second word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "f25dcb5e",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map[first] = [second]\n",
    "successor_map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55bb8df9",
   "metadata": {},
   "source": [
    "If the first word is already in the dictionary, we can look it up to get the list of successors we've seen so far, and append the new one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "990354a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "first = 'half'\n",
    "second = 'not'\n",
    "\n",
    "successor_map[first].append(second)\n",
    "successor_map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6289cc32",
   "metadata": {},
   "source": [
    "The following function encapsulates these steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "b9371452",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_bigram(bigram):\n",
    "    first, second = bigram\n",
    "    \n",
    "    if first not in successor_map:\n",
    "        successor_map[first] = [second]\n",
    "    else:\n",
    "        successor_map[first].append(second)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74a51700",
   "metadata": {},
   "source": [
    "If the same bigram appears more that once, the second word is added to the list more than once.\n",
    "In this way, `successor_map` keeps track of how many times each successor appears.\n",
    "\n",
    "As we did in the previous section, we'll use a list called `window` to store pairs of consecutive words.\n",
    "And we'll use the following function to process the words one at a time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "8c3f45c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_word_bigram(word):\n",
    "    window.append(word)\n",
    "    \n",
    "    if len(window) == 2:\n",
    "        add_bigram(window)\n",
    "        window.pop(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "861a60d9",
   "metadata": {},
   "source": [
    "Here's how we use it to process the words in the song."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "641990a3",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map = {}\n",
    "window = []\n",
    "\n",
    "for word in song.split():\n",
    "    word = clean_word(word)\n",
    "    process_word_bigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf490d67",
   "metadata": {},
   "source": [
    "And here are the results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "9322a49a",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff7bad74",
   "metadata": {},
   "source": [
    "The word `'half'` can be followed by `'a'`, `'not'`, or `'the'`.\n",
    "The word `'a'` can be followed by `'bee'` or `'vis'`.\n",
    "Most of the other words appear only once, so they are followed by only a single word.\n",
    "\n",
    "Now let's analyze the book."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "45a60c52",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map = {}\n",
    "window = []\n",
    "\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        process_word_bigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2676e2fb",
   "metadata": {},
   "source": [
    "We can look up any word and find the words that can follow it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "3e86102c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# I used this cell to find a predecessor with a good number of possible successors\n",
    "# and at least one repeated word.\n",
    "\n",
    "def has_duplicates(t):\n",
    "    return len(set(t)) < len(t)\n",
    "\n",
    "for key, value in successor_map.items():\n",
    "    if len(value) == 7 and has_duplicates(value):\n",
    "        print(key, value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "e49d52f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map['going']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b777a9c",
   "metadata": {},
   "source": [
    "In this list of successors, notice that the word `'to'` appears three times -- the other successors only appear once."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8bf85fc",
   "metadata": {},
   "source": [
    "## Generating text\n",
    "\n",
    "We can use the results from the previous section to generate new text with the same relationships between consecutive words as in the original.\n",
    "Here's how it works:\n",
    "\n",
    "* Starting with any word that appears in the text, we look up its possible successors and choose one at random.\n",
    "\n",
    "* Then, using the chosen word, we look up its possible successors, and choose one at random.\n",
    "\n",
    "We can repeat this process to generate as many words as we want.\n",
    "As an example, let's start with the word `'although'`.\n",
    "Here are the words that can follow it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "15108884",
   "metadata": {},
   "outputs": [],
   "source": [
    "word = 'although'\n",
    "successors = successor_map[word]\n",
    "successors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "747a41be",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# this cell initializes the random number generator so it \n",
    "# starts at the same point in the sequence each time this\n",
    "# notebook runs.\n",
    "\n",
    "random.seed(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b26a2ead",
   "metadata": {},
   "source": [
    "We can use `choice` to choose from the list with equal probability."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "5a4682dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "word = random.choice(successors)\n",
    "word"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9741beca",
   "metadata": {},
   "source": [
    "If the same word appears more than once in the list, it is more likely to be selected.\n",
    "\n",
    "Repeating these steps, we can use the following loop to generate a longer series."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "36ee0f76",
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(10):\n",
    "    successors = successor_map[word]\n",
    "    word = random.choice(successors)\n",
    "    print(word, end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38a2d79a",
   "metadata": {},
   "source": [
    "The result sounds more like a real sentence, but it still doesn't make much sense.\n",
    "\n",
    "We can do better using more than one word as a key in `successor_map`.\n",
    "For example, we can make a dictionary that maps from each bigram -- or trigram -- to the list of words that come next.\n",
    "As an exercise, you'll have a chance to implement this analysis and see what the results look like."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c59dff45",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Debugging\n",
    "\n",
    "At this point we are writing more substantial programs, and you might find that you are spending more time debugging.\n",
    "If you are stuck on a difficult bug, here are a few things to try:\n",
    "\n",
    "* Reading: Examine your code, read it back to yourself, and check that it says what you meant to say.\n",
    "\n",
    "* Running: Experiment by making changes and running different versions. Often if you display the right thing at the right place in the program, the problem becomes obvious, but sometimes you have to build scaffolding.\n",
    "\n",
    "* Ruminating: Take some time to think! What kind of error is it: syntax, runtime,\n",
    "    or semantic? What information can you get from the error messages,\n",
    "    or from the output of the program? What kind of error could cause\n",
    "    the problem you're seeing? What did you change last, before the\n",
    "    problem appeared?\n",
    "\n",
    "* Rubberducking: If you explain the problem to someone else, you sometimes find the\n",
    "    answer before you finish asking the question. Often you don't need\n",
    "    the other person; you could just talk to a rubber duck. And that's\n",
    "    the origin of the well-known strategy called **rubber duck\n",
    "    debugging**. I am not making this up -- see\n",
    "    <https://en.wikipedia.org/wiki/Rubber_duck_debugging>.\n",
    "\n",
    "* Retreating: At some point, the best thing to do is back up -- undoing recent\n",
    "    changes -- until you get to a program that works. Then you can start rebuilding.\n",
    "    \n",
    "* Resting: If you give your brain a break, sometime it will find the problem for you."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "12c2cd32",
   "metadata": {},
   "source": [
    "Beginning programmers sometimes get stuck on one of these activities and forget the others. Each activity comes with its own failure mode.\n",
    "\n",
    "For example, reading your code works if the problem is a typographical error, but not if the problem is a conceptual misunderstanding.\n",
    "If you don't understand what your program does, you can read it 100 times and never see the error, because the error is in your head.\n",
    "\n",
    "Running experiments can work, especially if you run small, simple tests.\n",
    "But if you run experiments without thinking or reading your code, it can take a long time to figure out what's happening.\n",
    "\n",
    "You have to take time to think. Debugging is like an experimental science. You should have at least one hypothesis about what the problem is. If there are two or more possibilities, try to think of a test that would eliminate one of them."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a55036e1",
   "metadata": {},
   "source": [
    "But even the best debugging techniques will fail if there are too many\n",
    "errors, or if the code you are trying to fix is too big and complicated.\n",
    "Sometimes the best option is to retreat, simplifying the program until\n",
    "you get back to something that works.\n",
    "\n",
    "Beginning programmers are often reluctant to retreat because they can't\n",
    "stand to delete a line of code (even if it's wrong). If it makes you\n",
    "feel better, copy your program into another file before you start\n",
    "stripping it down. Then you can copy the pieces back one at a time.\n",
    "\n",
    "Finding a hard bug requires reading, running, ruminating, retreating, and sometimes resting.\n",
    "If you get stuck on one of these activities, try the others."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "25d091af",
   "metadata": {},
   "source": [
    "## Glossary\n",
    "\n",
    "**default value:**\n",
    "The value assigned to a parameter if no argument is provided.\n",
    "\n",
    "**override:**\n",
    " To replace a default value with an argument.\n",
    "\n",
    "**deterministic:**\n",
    " A deterministic program does the same thing each time it runs, given the same inputs.\n",
    "\n",
    "**pseudorandom:**\n",
    " A pseudorandom sequence of numbers appears to be random, but is generated by a deterministic program.\n",
    "\n",
    "**bigram:**\n",
    "A sequence of two elements, often words.\n",
    "\n",
    "**trigram:**\n",
    "A sequence of three elements.\n",
    "\n",
    "**n-gram:**\n",
    "A sequence of an unspecified number of elements.\n",
    "\n",
    "**rubber duck debugging:**\n",
    "A way of debugging by explaining a problem aloud to an inanimate object."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cde18229",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05752b6d",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# This cell tells Jupyter to provide detailed debugging information\n",
    "# when a runtime error occurs. Run it before working on the exercises.\n",
    "\n",
    "%xmode Verbose"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b0efab8",
   "metadata": {},
   "source": [
    "### Ask a virtual assistant\n",
    "\n",
    "In `add_bigram`, the `if` statement creates a new list or appends an element to an existing list, depending on whether the key is already in the dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "a4365ac0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_bigram(bigram):\n",
    "    first, second = bigram\n",
    "    \n",
    "    if first not in successor_map:\n",
    "        successor_map[first] = [second]\n",
    "    else:\n",
    "        successor_map[first].append(second)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30d9e549",
   "metadata": {},
   "source": [
    "Dictionaries provide a method called `setdefault` that we can use to do the same thing more concisely.\n",
    "Ask a virtual assistant how it works, or copy `add_word` into a virtual assistant and ask \"Can you rewrite this using `setdefault`?\"\n",
    "\n",
    "In this chapter we implemented Markov chain text analysis and generation.\n",
    "If you are curious, you can ask a virtual assistant for more information on the topic.\n",
    "One of the things you might learn is that virtual assistants use algorithms that are similar in many ways -- but also different in important ways.\n",
    "Ask a VA, \"What are the differences between large language models like GPT and Markov chain text analysis?\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "060c9ef6",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Write a function that counts the number of times each trigram (sequence of three words) appears. \n",
    "If you test your function with the text of _Dr. Jekyll and Mr. Hyde_, you should find that the most common trigram is \"said the lawyer\".\n",
    "\n",
    "Hint: Write a function called `count_trigram` that is similar to `count_bigram`. Then write a function called `process_word_trigram` that is similar to `process_word_bigram`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "f38a61ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "d047e546",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca1f8a79",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use the following loop to read the book and process the words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "6b8932ee",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "trigram_counter = {}\n",
    "window = []\n",
    "\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        process_word_trigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35d37fa1",
   "metadata": {
    "tags": []
   },
   "source": [
    "Then use `print_most_common` to find the most common trigrams in the book."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "44c3f0d8",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print_most_common(trigram_counter)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4bd07bb7",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Now let's implement Markov chain text analysis with a mapping from each bigram to a list of possible successors.\n",
    "\n",
    "Starting with `add_bigram`, write a function called `add_trigram` that takes a list of three words and either adds or updates an item in `successor_map`, using the first two words as the key and the third word as a possible successor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "id": "3fcf85f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "94d683fe",
   "metadata": {},
   "source": [
    "Here's a version of `process_word_trigram` that calls `add_trigram`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "d9e554e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_word_trigram(word):\n",
    "    window.append(word)\n",
    "    \n",
    "    if len(window) == 3:\n",
    "        add_trigram(window)\n",
    "        window.pop(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82eeed41",
   "metadata": {
    "tags": []
   },
   "source": [
    "You can use the following loop to test your function with the lyrics of \"Eric, the Half a Bee\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "8c2ee21c",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "successor_map = {}\n",
    "window = []\n",
    "\n",
    "for string in song.split():\n",
    "    word = string.strip(punctuation).lower()\n",
    "    process_word_trigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8829d4c2",
   "metadata": {
    "tags": []
   },
   "source": [
    "If your function works as intended, the predecessor `('half', 'a')` should map to a list with the single element `'bee'`.\n",
    "In fact, as it happens, each bigram in this song appear only once, so all of the values in `successor_map` have a single element."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "id": "b13384e3",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "successor_map"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "886212b5",
   "metadata": {},
   "source": [
    "You can use the following loop to test your function with the words from the book."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "62c2177f",
   "metadata": {},
   "outputs": [],
   "source": [
    "successor_map = {}\n",
    "window = []\n",
    "\n",
    "for line in open(filename):\n",
    "    for word in split_line(line):\n",
    "        word = clean_word(word)\n",
    "        process_word_trigram(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e1d073e",
   "metadata": {},
   "source": [
    "In the next exercise, you'll use the results to generate new random text."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04d7a6ee",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "For this exercise, we'll assume that `successor_map` is a dictionary that maps from each bigram to the list of words that follow it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "64e11f26",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# this cell initializes the random number generator so it \n",
    "# starts at the same point in the sequence each time this\n",
    "# notebook runs.\n",
    "\n",
    "random.seed(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb0f8f7d",
   "metadata": {},
   "source": [
    "To generate random text, we'll start by choosing a random key from `successor_map`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "id": "fe2d93fa",
   "metadata": {},
   "outputs": [],
   "source": [
    "successors = list(successor_map)\n",
    "bigram = random.choice(successors)\n",
    "bigram"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83ed6c7e",
   "metadata": {},
   "source": [
    "Now write a loop that generates 50 more words following these steps:\n",
    "\n",
    "1. In `successor_map`, look up the list of words that can follow `bigram`.\n",
    "\n",
    "2. Choose one of them at random and print it.\n",
    "\n",
    "3. For the next iteration, make a new bigram that contains the second word from `bigram` and the chosen successor.\n",
    "\n",
    "For example, if we start with the bigram `('doubted', 'if')` and choose `'from'` as its successor, the next bigram is `('if', 'from')`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "22210a5c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solution goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c71d8a89",
   "metadata": {},
   "source": [
    "If everything is working, you should find that the generated text is recognizably similar in style to the original, and some phrases make sense, but the text might wander from one topic to another.\n",
    "\n",
    "As a bonus exercise, modify your solution to the last two exercises to use trigrams as keys in `successor_map`, and see what effect it has on the results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3d4efda7",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "a7f4edf8",
   "metadata": {
    "tags": []
   },
   "source": [
    "[Think Python: 3rd Edition](https://allendowney.github.io/ThinkPython/index.html)\n",
    "\n",
    "Copyright 2024 [Allen B. Downey](https://allendowney.com)\n",
    "\n",
    "Code license: [MIT License](https://mit-license.org/)\n",
    "\n",
    "Text license: [Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-nc-sa/4.0/)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}