asr_lab1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "\n",
    "In these labs we will work with HMMs in the form of Weighted Finite State Transducers.    We will use the Python interface to the [OpenFst toolkit](http://openfst.org). Examples were given at the start of Lecture 5, but if you need a refresh, read this [introduction](https://github.com/yiwang454/asr_labs/blob/main/introduction.pdf).\n",
    "\n",
    "Although most of the lab instructions are self-contained, this year we have started to create our [own documentation](https://openfst-python-documentation.readthedocs.io/en/latest/index.html) to the Python interface to OpenFst, following feedback that the [official documentation](https://www.openfst.org/twiki/bin/view/FST/PythonExtension) is incomplete and hard to follow.  We intend the documentation to be useful as reference material, and will add to it as labs progress.\n",
    "\n",
    "See [README.md](https://github.com/yiwang454/asr_labs/blob/main/README.md) for setup instructions.\n",
    "\n",
    "# Getting started\n",
    "\n",
    "We start by importing the OpenFst Python wrapper:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import openfst_python as fst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OpenFst internally stores FST labels in integer format. This means we need a _symbol table_ to map from the text form of the labels to their integer IDs.  We create now tables for our symbols.\n",
    "\n",
    "A **SymbolTable()** is simply a table associating symbols and indexes. We add symbols to the table with the method **add_symbol()**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Create two symbol tables: one for the input labels, one for the output labels\n",
    "input_sym = fst.SymbolTable()\n",
    "output_sym = fst.SymbolTable()\n",
    "\n",
    "# input symbols\n",
    "input_sym.add_symbol('<eps>') # by convention, <eps> always\n",
    "                              # has symbol zero\n",
    "input_sym.add_symbol('a')     \n",
    "input_sym.add_symbol('b')\n",
    "\n",
    "# output symbols\n",
    "output_sym.add_symbol('<eps>') \n",
    "output_sym.add_symbol('d')\n",
    "output_sym.add_symbol('c')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we've got our symbol tables, we will build the FST itself:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": "",
      "text/plain": [
       "<vector Fst at 0x7f8cac6c11f0>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = fst.Fst()\n",
    "\n",
    "f.set_input_symbols(input_sym)\n",
    "f.set_output_symbols(output_sym)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's add some states:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "s0 = f.add_state()\n",
    "s1 = f.add_state()\n",
    "s2 = f.add_state()\n",
    "s3 = f.add_state()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output of the **add_state()** method is just the index assigned to the state.  It's not necessary to stroe this, but in this example, we assign each state index to a variable name so that it can be easily used later.\n",
    "\n",
    "To create arcs between states, we do:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": "",
      "text/plain": [
       "<vector Fst at 0x7f8cac6c11f0>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Get IDs for labels 'a', 'b', 'c', 'd' in integer form\n",
    "a = input_sym.find('a')\n",
    "b = input_sym.find('b')\n",
    "c = output_sym.find('c')\n",
    "d = output_sym.find('d')\n",
    "\n",
    "# Add arcs\n",
    "f.add_arc(s0, fst.Arc(a, c, None, s1))\n",
    "f.add_arc(s0, fst.Arc(b, d, None, s2))\n",
    "f.add_arc(s1, fst.Arc(a, c, None, s3))\n",
    "f.add_arc(s2, fst.Arc(b, d, None, s3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The syntax for the method **add_arc** is:\n",
    "\n",
    "**add_arc(*source state*, *arc to add*)**\n",
    "\n",
    "while the syntax for initializing a class **Arc()** is:\n",
    "\n",
    "**Arc(*input symbol index*, *output symbol index*, *weight*, *destination state*)**\n",
    "\n",
    "We use the **find()** method of the symbol tables to get the index of a label in the state table.\n",
    "\n",
    "To finish constructing the FST we just add start and end states:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n<!-- Generated by graphviz version 2.50.0 (0)\n -->\n<!-- Title: FST Pages: 1 -->\n<svg width=\"220pt\" height=\"98pt\"\n viewBox=\"0.00 0.00 220.00 98.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 94)\">\n<title>FST</title>\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-94 216,-94 216,4 -4,4\"/>\n<!-- 0 -->\n<g id=\"node1\" class=\"node\">\n<title>0</title>\n<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"18\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"18\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n</g>\n<!-- 1 -->\n<g id=\"node2\" class=\"node\">\n<title>1</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"102\" cy=\"-72\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"102\" y=\"-68.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n</g>\n<!-- 0&#45;&gt;1 -->\n<g id=\"edge1\" class=\"edge\">\n<title>0&#45;&gt;1</title>\n<path fill=\"none\" stroke=\"black\" d=\"M35.2,-50.33C46.47,-54.05 61.74,-59.07 74.74,-63.35\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"73.96,-66.78 84.55,-66.58 76.15,-60.13 73.96,-66.78\"/>\n<text text-anchor=\"middle\" x=\"60\" y=\"-63.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:c</text>\n</g>\n<!-- 2 -->\n<g id=\"node3\" class=\"node\">\n<title>2</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"102\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n<text text-anchor=\"middle\" x=\"102\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n</g>\n<!-- 0&#45;&gt;2 -->\n<g id=\"edge2\" class=\"edge\">\n<title>0&#45;&gt;2</title>\n<path fill=\"none\" stroke=\"black\" d=\"M35.2,-39.67C46.47,-35.95 61.74,-30.93 74.74,-26.65\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"76.15,-29.87 84.55,-23.42 73.96,-23.22 76.15,-29.87\"/>\n<text text-anchor=\"middle\" x=\"60\" y=\"-36.8\" font-family=\"Times,serif\" font-size=\"14.00\">b:d</text>\n</g>\n<!-- 3 -->\n<g id=\"node4\" class=\"node\">\n<title>3</title>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"190\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\n<ellipse fill=\"none\" stroke=\"black\" cx=\"190\" cy=\"-45\" rx=\"22\" ry=\"22\"/>\n<text text-anchor=\"middle\" x=\"190\" y=\"-41.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n</g>\n<!-- 1&#45;&gt;3 -->\n<g id=\"edge3\" class=\"edge\">\n<title>1&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M119.58,-66.79C130.78,-63.28 145.89,-58.53 159.15,-54.37\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"160.34,-57.67 168.84,-51.33 158.25,-50.99 160.34,-57.67\"/>\n<text text-anchor=\"middle\" x=\"144\" y=\"-64.8\" font-family=\"Times,serif\" font-size=\"14.00\">a:c</text>\n</g>\n<!-- 2&#45;&gt;3 -->\n<g id=\"edge4\" class=\"edge\">\n<title>2&#45;&gt;3</title>\n<path fill=\"none\" stroke=\"black\" d=\"M119.58,-23.21C130.78,-26.72 145.89,-31.47 159.15,-35.63\"/>\n<polygon fill=\"black\" stroke=\"black\" points=\"158.25,-39.01 168.84,-38.67 160.34,-32.33 158.25,-39.01\"/>\n<text text-anchor=\"middle\" x=\"144\" y=\"-36.8\" font-family=\"Times,serif\" font-size=\"14.00\">b:d</text>\n</g>\n</g>\n</svg>\n",
      "text/plain": [
       "<vector Fst at 0x7f8cac6c11f0>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f.set_start(s0)\n",
    "f.set_final(s3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And our first FST, shown in the example above, is done!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercises\n",
    "\n",
    "In this lab you will build some simple FSTs.  Some of these will be related to words or phones, as described in lectures.  For these examples, we'll use a short _lexicon_ (a dictionary of pronunciations).  We load this from the provided text file with this helper function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_lexicon(lex_file):\n",
    "    \"\"\"\n",
    "    Parse the lexicon file and return it in dictionary form.\n",
    "    \n",
    "    Args:\n",
    "        lex_file (str): filename of lexicon file with structure '<word> <phone1> <phone2>...'\n",
    "                        eg. peppers p eh p er z\n",
    "\n",
    "    Returns:\n",
    "        lex (dict): dictionary mapping words to list of phones\n",
    "    \"\"\"\n",
    "    \n",
    "    lex = {}  # create a dictionary for the lexicon entries\n",
    "    with open(lex_file, 'r') as f:\n",
    "        for line in f:\n",
    "            line = line.split()  # split at each space\n",
    "            lex[line[0]] = line[1:]  # first field the word, the rest is the phones\n",
    "    return lex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': ['ey'],\n",
       " 'cat': ['k', 'ae', 't'],\n",
       " 'of': ['ah', 'v'],\n",
       " 'peck': ['p', 'eh', 'k'],\n",
       " 'peppers': ['p', 'eh', 'p', 'er', 'z'],\n",
       " 'peter': ['p', 'iy', 't', 'er'],\n",
       " 'picked': ['p', 'ih', 'k', 't'],\n",
       " 'pickled': ['p', 'ih', 'k', 'ah', 'l', 'd'],\n",
       " 'piper': ['p', 'ay', 'p', 'er'],\n",
       " 'the': ['dh', 'iy'],\n",
       " \"where's\": ['w', 'eh', 'r', 'z']}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lex = parse_lexicon('lexicon.txt')\n",
    "lex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Complete the following function that generates symbol tables from a lexicon, using the provided phonetic dictionary in **lexicon.txt** and the helper function *parse_lexicon* in cells above. Use p_1, p_2, ..., eh_1, ... to denote the phone state labels. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_symbol_tables(lexicon, n=3):\n",
    "    '''\n",
    "    Return word, phone and state symbol tables based on the supplied lexicon\n",
    "    \n",
    "    Args:\n",
    "        lexicon (dict): lexicon to use, created from the parse_lexicon() function\n",
    "        n (int): number of states for each phone HMM\n",
    "        \n",
    "    Returns:\n",
    "        word_table (fst.SymbolTable): table of words\n",
    "        phone_table (fst.SymbolTable): table of phones\n",
    "        state_table (fst.SymbolTable): table of HMM phone-state IDs\n",
    "    '''\n",
    "    state_table = fst.SymbolTable()\n",
    "    phone_table = fst.SymbolTable()\n",
    "    word_table = fst.SymbolTable()\n",
    "    \n",
    "    # your code here\n",
    "\n",
    "    return word_table, phone_table, state_table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**You may check your answer with the codes below, where you can see the expected results and change your codes accordingly.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "word_table, phone_table, state_table = generate_symbol_tables(lex)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Checking word_table\n",
    "word_table.write_text('tmp.txt')\n",
    "print(open('tmp.txt').read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should get a result as below after running the above cell,\n",
    "```\n",
    "<eps>\t0\n",
    "a\t1\n",
    "cat\t2\n",
    "of\t3\n",
    "peck\t4\n",
    "peppers\t5\n",
    "peter\t6\n",
    "picked\t7\n",
    "pickled\t8\n",
    "piper\t9\n",
    "the\t10\n",
    "where's\t11\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Checking phone_table\n",
    "phone_table.write_text('tmp.txt')\n",
    "print(open('tmp.txt').read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should get a result as below after running the above cell,\n",
    "```\n",
    "<eps>\t0\n",
    "ey\t1\n",
    "k\t2\n",
    "ae\t3\n",
    "t\t4\n",
    "ah\t5\n",
    "v\t6\n",
    "p\t7\n",
    "eh\t8\n",
    "er\t9\n",
    "z\t10\n",
    "iy\t11\n",
    "ih\t12\n",
    "l\t13\n",
    "d\t14\n",
    "ay\t15\n",
    "dh\t16\n",
    "w\t17\n",
    "r\t18\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Checking state_table\n",
    "state_table.write_text('tmp.txt')\n",
    "print(open('tmp.txt').read())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should get a result as below after running the above cell,\n",
    "```\n",
    "<eps>\t0\n",
    "ey_1\t1\n",
    "ey_2\t2\n",
    "ey_3\t3\n",
    "k_1\t4\n",
    "k_2\t5\n",
    "k_3\t6\n",
    "ae_1\t7\n",
    "ae_2\t8\n",
    "ae_3\t9\n",
    "t_1\t10\n",
    "t_2\t11\n",
    "t_3\t12\n",
    "ah_1\t13\n",
    "ah_2\t14\n",
    "ah_3\t15\n",
    "v_1\t16\n",
    "v_2\t17\n",
    "v_3\t18\n",
    "p_1\t19\n",
    "p_2\t20\n",
    "p_3\t21\n",
    "eh_1\t22\n",
    "eh_2\t23\n",
    "eh_3\t24\n",
    "er_1\t25\n",
    "er_2\t26\n",
    "er_3\t27\n",
    "z_1\t28\n",
    "z_2\t29\n",
    "z_3\t30\n",
    "iy_1\t31\n",
    "iy_2\t32\n",
    "iy_3\t33\n",
    "ih_1\t34\n",
    "ih_2\t35\n",
    "ih_3\t36\n",
    "l_1\t37\n",
    "l_2\t38\n",
    "l_3\t39\n",
    "d_1\t40\n",
    "d_2\t41\n",
    "d_3\t42\n",
    "ay_1\t43\n",
    "ay_2\t44\n",
    "ay_3\t45\n",
    "dh_1\t46\n",
    "dh_2\t47\n",
    "dh_3\t48\n",
    "w_1\t49\n",
    "w_2\t50\n",
    "w_3\t51\n",
    "r_1\t52\n",
    "r_2\t53\n",
    "r_3\t54\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Create functions generating WFSTs representing the following HMMs (illustrated in Lecture 4, slide 11)\n",
    "\n",
    "    1. A 3-state left-to-right phone HMM with self-loops\n",
    "    2. A 5-state parallel-path left-to-right HMM\n",
    "    3. An ergodic HMM with $n$ states (you will need to think about how to handle initial and final states)\n",
    "    \n",
    "Don't worry about the arc labels for the second two WFSTs.   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_phone_wfst(f, start_state, phone, n):\n",
    "    \"\"\"\n",
    "    Generate a WFST representing an n-state left-to-right phone HMM.\n",
    "    \n",
    "    Args:\n",
    "        f (fst.Fst()): an FST object, assumed to exist already\n",
    "        start_state (int): the index of the first state, assumed to exist already\n",
    "        phone (str): the phone label \n",
    "        n (int): number of emitting states of the HMM\n",
    "        \n",
    "    Returns:\n",
    "        the final state of the FST\n",
    "    \"\"\"\n",
    "    \n",
    "    current_state = start_state\n",
    "    \n",
    "    for i in range(1, n+1):\n",
    "    \n",
    "        in_label = state_table.find('{}_{}'.format(phone, i))\n",
    "    # your code here\n",
    "    \n",
    "    return current_state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Here is the code to help you debug your solutions\n",
    "f = fst.Fst()\n",
    "start = f.add_state()\n",
    "f.set_start(start)\n",
    "\n",
    "last_state = generate_phone_wfst(f, start, 'p', 3)\n",
    "f.set_final(last_state)\n",
    "\n",
    "f.set_input_symbols(state_table)\n",
    "f.set_output_symbols(phone_table)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**You should get a result looks like this**\n",
    "![phone_wfst](figs/generate_phone_wfst.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_parallel_path_wfst(f, start_state, n):\n",
    "    \"\"\"\n",
    "    Generate a WFST representing an n-state parallel-path left-to-right HMM\n",
    "    \n",
    "    Args:\n",
    "        f (fst.Fst()): an FST object, assumed to exist already\n",
    "        start_state (int): the index of the first state, assumed to exist already\n",
    "        n (int): number of emitting states of the HMM\n",
    "        \n",
    "    Returns:\n",
    "        the final state of the FST\n",
    "    \"\"\"\n",
    "    \n",
    "    current_state = start_state\n",
    "    \n",
    "    for i in range(n):\n",
    "    \n",
    "        # your code here\n",
    "    \n",
    "    return current_state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Here is the code to help you debug your solutions\n",
    "f = fst.Fst()\n",
    "start = f.add_state()\n",
    "f.set_start(start)\n",
    "\n",
    "last_state = generate_parallel_path_wfst(f, start, 5)\n",
    "f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**You should get a result looks like this**\n",
    "![parallel_path_wfst](figs/generate_parallel_path_wfst.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_ergodic_wfst(f, start_state, n):\n",
    "    \"\"\"\n",
    "    Generate a WFST representing an n-state ergodic HMM\n",
    "    \n",
    "    Args:\n",
    "        f (fst.Fst()): an FST object, assumed to exist already\n",
    "        start_state (int): the index of the first state, assumed to exist already\n",
    "        n (int): number of emitting states of the HMM\n",
    "        \n",
    "    Returns:\n",
    "        the final state of the FST\n",
    "    \"\"\"    \n",
    "    \n",
    "    current_state = start_state\n",
    "    \n",
    "    for i in range(n):\n",
    "        \n",
    "        # your code here\n",
    "\n",
    "    return current_state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Here is the code to help you debug your solutions\n",
    "f = fst.Fst()\n",
    "start = f.add_state()\n",
    "f.set_start(start)\n",
    "\n",
    "last_state = generate_ergodic_wfst(f, start, 5)\n",
    "f"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**You should get a result looks like this**\n",
    "![ergodic_wfst](figs/generate_ergodic_wfst.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Write a function to generate an HMM for any word in the lexicon using $n$ states per phone by concatenating $n$-state phone HMMs. Make use of your *generate_phone_wfst()* function. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_word_wfst(f, start_state, word, n):\n",
    "    \"\"\" Generate a WFST for any word in the lexicon, composed of n-state phone WFSTs.\n",
    "        This will currently output phone labels.  \n",
    "    \n",
    "    Args:\n",
    "        f (fst.Fst()): an FST object, assumed to exist already\n",
    "        start_state (int): the index of the first state, assumed to exist already\n",
    "        word (str): the word to generate\n",
    "        n (int): states per phone HMM\n",
    "        \n",
    "    Returns:\n",
    "        the constructed WFST\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "    current_state = start_state\n",
    "    \n",
    "    # your code here\n",
    "    \n",
    "    return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Here is the code to help you debug your solutions\n",
    "f = fst.Fst()\n",
    "start = f.add_state()\n",
    "f.set_start(start)\n",
    "\n",
    "generate_word_wfst(f, start, 'peppers', 3)\n",
    "f.set_input_symbols(state_table)\n",
    "f.set_output_symbols(phone_table)\n",
    "\n",
    "# We need special code to display the higher-resolution WFSTs inside Jupyter notebook\n",
    "# (you don't need to look at this)\n",
    "from subprocess import check_call\n",
    "from IPython.display import Image\n",
    "f.draw('tmp.dot', portrait=True)\n",
    "check_call(['dot','-Tpng','-Gdpi=200','tmp.dot','-o','tmp.png'])\n",
    "Image(filename='tmp.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**You should get a result looks like this**\n",
    "![word_wfst](figs/generate_word_wfst.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Generate an HMM that can recognise:\n",
    "\n",
    "    1. any phone contained in the lexicon\n",
    "    2. any sequence of phones contained in the lexicon\n",
    "    \n",
    "Think of the difference between the first and the second HMM. Again, previous functions should help in the task. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_phone_recognition_wfst(n):\n",
    "    \"\"\" generate a HMM to recognise any single phone in the lexicon\n",
    "    \n",
    "    Args:\n",
    "        n (int): states per phone HMM\n",
    "\n",
    "    Returns:\n",
    "        the constructed WFST\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    f = fst.Fst()\n",
    "    \n",
    "    # create a single start state\n",
    "    start_state = f.add_state()\n",
    "    f.set_start(start_state)\n",
    "    \n",
    "    # your code here\n",
    "            \n",
    "    return f\n",
    "\n",
    "f = generate_phone_recognition_wfst(3)\n",
    "f.set_input_symbols(state_table)\n",
    "f.set_output_symbols(phone_table)\n",
    "\n",
    "f.draw('tmp.dot', portrait=True)\n",
    "check_call(['dot','-Tpng','-Gdpi=200','tmp.dot','-o','tmp.png'])\n",
    "Image(filename='tmp.png')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Here is the code to help you debug your solutions\n",
    "f = generate_phone_recognition_wfst(3)\n",
    "f.set_input_symbols(state_table)\n",
    "f.set_output_symbols(phone_table)\n",
    "\n",
    "from subprocess import check_call\n",
    "from IPython.display import Image\n",
    "f.draw('tmp.dot', portrait=True)\n",
    "check_call(['dot','-Tpng','-Gdpi=200','tmp.dot','-o','tmp.png'])\n",
    "Image(filename='tmp.png')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_phone_sequence_recognition_wfst(n):\n",
    "    \"\"\" generate a HMM to recognise any single phone sequence in the lexicon\n",
    "    \n",
    "    Args:\n",
    "        n (int): states per phone HMM\n",
    "\n",
    "    Returns:\n",
    "        the constructed WFST\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    f = fst.Fst()\n",
    "    \n",
    "    # create a single start state\n",
    "    start_state = f.add_state()\n",
    "    f.set_start(start_state)\n",
    "    \n",
    "    # your code here\n",
    "            \n",
    "    return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Here is the code to help you debug your solutions\n",
    "f = generate_phone_sequence_recognition_wfst(3)\n",
    "f.set_input_symbols(state_table)\n",
    "f.set_output_symbols(phone_table)\n",
    "\n",
    "from subprocess import check_call\n",
    "from IPython.display import Image\n",
    "f.draw('tmp.dot', portrait=True)\n",
    "check_call(['dot','-Tpng','-Gdpi=200','tmp.dot','-o','tmp.png'])\n",
    "Image(filename='tmp.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. You have decided that the best way to start teaching a friend English is to have them learn the notorious tongue-twister *peter piper picked a peck of pickled peppers*.  Write a function that creates an HMM that can recognize any sequence of these words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_word_sequence_recognition_wfst(n):\n",
    "    \"\"\" generate a HMM to recognise any sequence of words in the lexicon\n",
    "    \n",
    "    Args:\n",
    "        n (int): states per phone HMM\n",
    "\n",
    "    Returns:\n",
    "        the constructed WFST\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    f = fst.Fst()\n",
    "    \n",
    "    # create a single start state\n",
    "    start_state = f.add_state()\n",
    "    f.set_start(start_state)\n",
    "    \n",
    "    for word in lex.keys():\n",
    "        # your code here\n",
    "        \n",
    "    return f\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "f = generate_word_sequence_recognition_wfst(3)\n",
    "f.set_input_symbols(state_table)\n",
    "f.set_output_symbols(phone_table)\n",
    "\n",
    "from subprocess import check_call\n",
    "from IPython.display import Image\n",
    "f.draw('tmp.dot', portrait=True)\n",
    "check_call(['dot','-Tpng','-Gdpi=200','tmp.dot','-o','tmp.png'])\n",
    "Image(filename='tmp.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# If you have more time (optional)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Probabilities in WFSTs are traditionally expressed in negative log format, that is, the weight $w$ on an arc transitioning between states $i$ and $j$ is given by $w=-\\log a_{ij}$, where $a_{ij}$ is the HMM transition probability.\n",
    "\n",
    "6. Add weights to your WFSTs corresponding to transition probabilities.  Assume that the probability of a self-loop is $0.1$, and that when transitioning *between* separate phones or words, the probabilities are uniform over all transitions."
   ]
  }
 ],
 "metadata": {
  "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.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}