asr_lab5.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lab 5  - WFST operations\n",
    "\n",
    "So far we've used WFSTs mainly as a usual structure for encoding and traversing HMMs.  In this lab we'll move away from HMM acoustic modelling and look at how WFST operations can be used to avoid the need for specialised algorithms in speech and language processing.  It is intended to give you insight into how these operations are used to construct HMMs encapsulating langauge model, pronunciation and acoustic modelling assumptions &ndash; the so-called \"HCLG\" WFST.\n",
    "\n",
    "This lab will focus on the lexicon transducer, $L$, and grammar transducer, $G$.\n",
    "\n",
    "We'll use some of the following operations, defined by Openfst:\n",
    "* `fst.determinize(f)` creates determinized version of `f`\n",
    "* `fst.compose(f1,f2)` composes FSTs `f1` and `f2`\n",
    "* `fst.shortestpath(f)` returns the shortest path (in terms of weight) through `f` from the start to a final state\n",
    "* `f.minimize()` creates minimized version of `f`\n",
    "* `f.project(project_output=False)` for every arc in `f`, copies the input label to the output label (or vice versa, if `project_output=True`).\n",
    "* `f.rmepsilon()` removes epsilon transitions &ndash; those arcs where both input and output labels are empty.\n",
    "\n",
    "For efficiency, the compostion of `f1` and `f2` requires either the output arcs of `f1` or input arcs of `f2` to be sorted prior to `compose()` being called.  You can do this by calling `f1.arcsort(sort_type='olabel')` or `f2.arcsort(sort_type='ilabel')`.\n",
    "\n",
    "Combining projection and removal of epsilon transitions will give you better visual clarity when looking at your FSTS.\n",
    "\n",
    "The functions above assume that `openfst_python` has been imported as `fst`.  Note that the first three functions above return a new WFST; the others modify the WFST *in place*, meaning that the original WFST is modified directly.\n",
    "\n",
    "For convenience, we've provided a python module `helper_functions` that provides the `parse_lexicon()` and `generate_symbol_tables()` from the [Lab 1 solutions](https://github.com/Ore-an/asr_lab1/blob/master/asr_lab1_solutions.ipynb).  And here is a function to generate an $L$ transducer:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "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.30.1 (20200930.0103)\n",
       " -->\n",
       "<!-- Title: FST Pages: 1 -->\n",
       "<svg width=\"612pt\" height=\"471pt\"\n",
       " viewBox=\"0.00 0.00 612.00 471.47\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(0.755556 0.755556) rotate(0) translate(4 620)\">\n",
       "<title>FST</title>\n",
       "<polygon fill=\"white\" stroke=\"white\" points=\"-4,5 -4,-620 807,-620 807,5 -4,5\"/>\n",
       "<!-- 0 -->\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" stroke-width=\"2\" cx=\"18\" cy=\"-316\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-312.3\" font-family=\"Times,serif\" font-size=\"14.00\">0</text>\n",
       "</g>\n",
       "<!-- 1 -->\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-594\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-594\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-590.3\" font-family=\"Times,serif\" font-size=\"14.00\">1</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;1 -->\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M19.5389,-334.011C21.2678,-381.504 27.9864,-508.836 51,-543 64.6719,-563.296 89.3306,-576.564 109.074,-584.465\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"107.991,-587.796 118.583,-588.018 110.441,-581.239 107.991,-587.796\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-584.8\" font-family=\"Times,serif\" font-size=\"14.00\">ey:a</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-536\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-532.3\" font-family=\"Times,serif\" font-size=\"14.00\">2</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;2 -->\n",
       "<g id=\"edge2\" class=\"edge\"><title>0&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M20.4418,-334.03C23.8459,-372.809 33.4444,-462.609 51,-487 66.0307,-507.883 92.8546,-520.948 112.949,-528.283\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"111.875,-531.614 122.469,-531.52 114.128,-524.987 111.875,-531.614\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-527.8\" font-family=\"Times,serif\" font-size=\"14.00\">k:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node4\" class=\"node\"><title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-482\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-478.3\" font-family=\"Times,serif\" font-size=\"14.00\">5</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;5 -->\n",
       "<g id=\"edge3\" class=\"edge\"><title>0&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M19.7707,-333.987C21.6807,-358.541 28.2809,-402.825 51,-432 66.721,-452.188 93.0299,-465.587 112.795,-473.389\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"111.851,-476.771 122.444,-476.965 114.283,-470.208 111.851,-476.771\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-471.8\" font-family=\"Times,serif\" font-size=\"14.00\">ah:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node5\" class=\"node\"><title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-428\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-424.3\" font-family=\"Times,serif\" font-size=\"14.00\">7</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;7 -->\n",
       "<g id=\"edge4\" class=\"edge\"><title>0&#45;&gt;7</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M24.6496,-332.89C29.8262,-346.369 38.581,-365.071 51,-378 68.6218,-396.345 94.4543,-409.931 113.576,-418.274\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"112.308,-421.538 122.885,-422.157 115.003,-415.077 112.308,-421.538\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-416.8\" font-family=\"Times,serif\" font-size=\"14.00\">p:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node6\" class=\"node\"><title>10</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-373\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-369.3\" font-family=\"Times,serif\" font-size=\"14.00\">10</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;10 -->\n",
       "<g id=\"edge5\" class=\"edge\"><title>0&#45;&gt;10</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.7547,-325.297C39.1028,-328.523 45.2446,-332.064 51,-335 70.9509,-345.178 94.2465,-355.157 111.856,-362.333\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.915,-365.727 121.499,-366.215 113.529,-359.234 110.915,-365.727\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-362.8\" font-family=\"Times,serif\" font-size=\"14.00\">p:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 15 -->\n",
       "<g id=\"node7\" class=\"node\"><title>15</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-316\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-312.3\" font-family=\"Times,serif\" font-size=\"14.00\">15</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;15 -->\n",
       "<g id=\"edge6\" class=\"edge\"><title>0&#45;&gt;15</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.1931,-316C55.4387,-316 86.945,-316 110.015,-316\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.258,-319.5 120.258,-316 110.258,-312.5 110.258,-319.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-319.8\" font-family=\"Times,serif\" font-size=\"14.00\">p:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 19 -->\n",
       "<g id=\"node8\" class=\"node\"><title>19</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-259\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-255.3\" font-family=\"Times,serif\" font-size=\"14.00\">19</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;19 -->\n",
       "<g id=\"edge7\" class=\"edge\"><title>0&#45;&gt;19</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M33.7547,-306.703C39.1028,-303.477 45.2446,-299.936 51,-297 70.9509,-286.822 94.2465,-276.843 111.856,-269.667\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"113.529,-272.766 121.499,-265.785 110.915,-266.273 113.529,-272.766\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-300.8\" font-family=\"Times,serif\" font-size=\"14.00\">p:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 23 -->\n",
       "<g id=\"node9\" class=\"node\"><title>23</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-202\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-198.3\" font-family=\"Times,serif\" font-size=\"14.00\">23</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;23 -->\n",
       "<g id=\"edge8\" class=\"edge\"><title>0&#45;&gt;23</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M24.9052,-299.198C30.1798,-286.006 38.9411,-267.792 51,-255 68.2936,-236.655 93.3206,-222.41 112.268,-213.33\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"113.928,-216.419 121.548,-209.058 111.001,-210.06 113.928,-216.419\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-258.8\" font-family=\"Times,serif\" font-size=\"14.00\">p:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 29 -->\n",
       "<g id=\"node10\" class=\"node\"><title>29</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-145\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-141.3\" font-family=\"Times,serif\" font-size=\"14.00\">29</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;29 -->\n",
       "<g id=\"edge9\" class=\"edge\"><title>0&#45;&gt;29</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M19.983,-297.731C22.1387,-273.251 29.022,-229.477 51,-200 66.4772,-179.242 92.3117,-164.457 111.996,-155.48\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"113.578,-158.609 121.367,-151.427 110.799,-152.185 113.578,-158.609\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-203.8\" font-family=\"Times,serif\" font-size=\"14.00\">p:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 33 -->\n",
       "<g id=\"node11\" class=\"node\"><title>33</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-87\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-83.3\" font-family=\"Times,serif\" font-size=\"14.00\">33</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;33 -->\n",
       "<g id=\"edge10\" class=\"edge\"><title>0&#45;&gt;33</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M20.4711,-298.017C23.9632,-258.855 33.7754,-167.338 51,-142 65.7103,-120.361 92.0528,-105.572 112.095,-96.8262\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"113.435,-100.059 121.348,-93.0145 110.769,-93.5869 113.435,-100.059\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-145.8\" font-family=\"Times,serif\" font-size=\"14.00\">dh:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 35 -->\n",
       "<g id=\"node12\" class=\"node\"><title>35</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"140\" cy=\"-28\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"140\" y=\"-24.3\" font-family=\"Times,serif\" font-size=\"14.00\">35</text>\n",
       "</g>\n",
       "<!-- 0&#45;&gt;35 -->\n",
       "<g id=\"edge11\" class=\"edge\"><title>0&#45;&gt;35</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M19.5323,-297.91C21.256,-249.554 27.9854,-118.565 51,-83 65.2154,-61.0325 91.6246,-46.2883 111.817,-37.6419\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"113.181,-40.8655 121.149,-33.8822 110.565,-34.3726 113.181,-40.8655\"/>\n",
       "<text text-anchor=\"middle\" x=\"77\" y=\"-86.8\" font-family=\"Times,serif\" font-size=\"14.00\">w:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node13\" class=\"node\"><title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-544\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-540.3\" font-family=\"Times,serif\" font-size=\"14.00\">3</text>\n",
       "</g>\n",
       "<!-- 2&#45;&gt;3 -->\n",
       "<g id=\"edge12\" class=\"edge\"><title>2&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M157.993,-537.079C178.941,-538.409 214.811,-540.686 239.654,-542.264\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"239.672,-545.772 249.874,-542.913 240.116,-538.786 239.672,-545.772\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-544.8\" font-family=\"Times,serif\" font-size=\"14.00\">ae:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node15\" class=\"node\"><title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-486\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-486\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-482.3\" font-family=\"Times,serif\" font-size=\"14.00\">6</text>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;6 -->\n",
       "<g id=\"edge14\" class=\"edge\"><title>5&#45;&gt;6</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M157.993,-482.539C177.771,-483.167 210.849,-484.217 235.391,-484.997\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"235.549,-488.503 245.655,-485.322 235.771,-481.507 235.549,-488.503\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-487.8\" font-family=\"Times,serif\" font-size=\"14.00\">v:of</text>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node16\" class=\"node\"><title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-428\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-424.3\" font-family=\"Times,serif\" font-size=\"14.00\">8</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;8 -->\n",
       "<g id=\"edge15\" class=\"edge\"><title>7&#45;&gt;8</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M158.256,-428C179.274,-428 215.031,-428 239.775,-428\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"239.953,-431.5 249.953,-428 239.953,-424.5 239.953,-431.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-431.8\" font-family=\"Times,serif\" font-size=\"14.00\">eh:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 11 -->\n",
       "<g id=\"node18\" class=\"node\"><title>11</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-373\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-369.3\" font-family=\"Times,serif\" font-size=\"14.00\">11</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;11 -->\n",
       "<g id=\"edge17\" class=\"edge\"><title>10&#45;&gt;11</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.592,-373C180.343,-373 214.174,-373 238.322,-373\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"238.332,-376.5 248.332,-373 238.332,-369.5 238.332,-376.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-376.8\" font-family=\"Times,serif\" font-size=\"14.00\">eh:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 16 -->\n",
       "<g id=\"node22\" class=\"node\"><title>16</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-316\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-312.3\" font-family=\"Times,serif\" font-size=\"14.00\">16</text>\n",
       "</g>\n",
       "<!-- 15&#45;&gt;16 -->\n",
       "<g id=\"edge21\" class=\"edge\"><title>15&#45;&gt;16</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.592,-316C180.343,-316 214.174,-316 238.322,-316\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"238.332,-319.5 248.332,-316 238.332,-312.5 238.332,-319.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-319.8\" font-family=\"Times,serif\" font-size=\"14.00\">iy:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 20 -->\n",
       "<g id=\"node25\" class=\"node\"><title>20</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-259\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-255.3\" font-family=\"Times,serif\" font-size=\"14.00\">20</text>\n",
       "</g>\n",
       "<!-- 19&#45;&gt;20 -->\n",
       "<g id=\"edge24\" class=\"edge\"><title>19&#45;&gt;20</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.592,-259C180.343,-259 214.174,-259 238.322,-259\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"238.332,-262.5 248.332,-259 238.332,-255.5 238.332,-262.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-262.8\" font-family=\"Times,serif\" font-size=\"14.00\">ih:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 24 -->\n",
       "<g id=\"node28\" class=\"node\"><title>24</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-202\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-198.3\" font-family=\"Times,serif\" font-size=\"14.00\">24</text>\n",
       "</g>\n",
       "<!-- 23&#45;&gt;24 -->\n",
       "<g id=\"edge27\" class=\"edge\"><title>23&#45;&gt;24</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.592,-202C180.343,-202 214.174,-202 238.322,-202\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"238.332,-205.5 248.332,-202 238.332,-198.5 238.332,-205.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-205.8\" font-family=\"Times,serif\" font-size=\"14.00\">ih:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 30 -->\n",
       "<g id=\"node33\" class=\"node\"><title>30</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-145\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-141.3\" font-family=\"Times,serif\" font-size=\"14.00\">30</text>\n",
       "</g>\n",
       "<!-- 29&#45;&gt;30 -->\n",
       "<g id=\"edge32\" class=\"edge\"><title>29&#45;&gt;30</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.592,-145C180.343,-145 214.174,-145 238.322,-145\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"238.332,-148.5 248.332,-145 238.332,-141.5 238.332,-148.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-148.8\" font-family=\"Times,serif\" font-size=\"14.00\">ay:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 34 -->\n",
       "<g id=\"node36\" class=\"node\"><title>34</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-84\" rx=\"19.4968\" ry=\"19.4968\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-84\" rx=\"23.4965\" ry=\"23.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-80.3\" font-family=\"Times,serif\" font-size=\"14.00\">34</text>\n",
       "</g>\n",
       "<!-- 33&#45;&gt;34 -->\n",
       "<g id=\"edge35\" class=\"edge\"><title>33&#45;&gt;34</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.592,-86.5573C179.182,-86.0909 210.427,-85.347 234.179,-84.7814\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"234.583,-88.2729 244.496,-84.5358 234.416,-81.2749 234.583,-88.2729\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-90.8\" font-family=\"Times,serif\" font-size=\"14.00\">iy:the</text>\n",
       "</g>\n",
       "<!-- 36 -->\n",
       "<g id=\"node37\" class=\"node\"><title>36</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"268\" cy=\"-23\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"268\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">36</text>\n",
       "</g>\n",
       "<!-- 35&#45;&gt;36 -->\n",
       "<g id=\"edge36\" class=\"edge\"><title>35&#45;&gt;36</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M159.592,-27.2622C180.343,-26.4388 214.174,-25.0963 238.322,-24.138\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"238.479,-27.6347 248.332,-23.7408 238.201,-20.6402 238.479,-27.6347\"/>\n",
       "<text text-anchor=\"middle\" x=\"203\" y=\"-30.8\" font-family=\"Times,serif\" font-size=\"14.00\">eh:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node14\" class=\"node\"><title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-544\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-544\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"390\" y=\"-540.3\" font-family=\"Times,serif\" font-size=\"14.00\">4</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;4 -->\n",
       "<g id=\"edge13\" class=\"edge\"><title>3&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M286.193,-544C304.767,-544 334.762,-544 357.57,-544\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"357.793,-547.5 367.792,-544 357.792,-540.5 357.793,-547.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"330\" y=\"-547.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:cat</text>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node17\" class=\"node\"><title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-432\" rx=\"18\" ry=\"18\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-432\" rx=\"22\" ry=\"22\"/>\n",
       "<text text-anchor=\"middle\" x=\"390\" y=\"-428.3\" font-family=\"Times,serif\" font-size=\"14.00\">9</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;9 -->\n",
       "<g id=\"edge16\" class=\"edge\"><title>8&#45;&gt;9</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M286.193,-428.573C304.767,-429.192 334.762,-430.192 357.57,-430.952\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"357.681,-434.458 367.792,-431.293 357.915,-427.462 357.681,-434.458\"/>\n",
       "<text text-anchor=\"middle\" x=\"330\" y=\"-433.8\" font-family=\"Times,serif\" font-size=\"14.00\">k:peck</text>\n",
       "</g>\n",
       "<!-- 12 -->\n",
       "<g id=\"node19\" class=\"node\"><title>12</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-373\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"390\" y=\"-369.3\" font-family=\"Times,serif\" font-size=\"14.00\">12</text>\n",
       "</g>\n",
       "<!-- 11&#45;&gt;12 -->\n",
       "<g id=\"edge18\" class=\"edge\"><title>11&#45;&gt;12</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M287.75,-373C307.124,-373 337.619,-373 360.083,-373\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"360.382,-376.5 370.382,-373 360.382,-369.5 360.382,-376.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"330\" y=\"-376.8\" font-family=\"Times,serif\" font-size=\"14.00\">p:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 13 -->\n",
       "<g id=\"node20\" class=\"node\"><title>13</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-385\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"518\" y=\"-381.3\" font-family=\"Times,serif\" font-size=\"14.00\">13</text>\n",
       "</g>\n",
       "<!-- 12&#45;&gt;13 -->\n",
       "<g id=\"edge19\" class=\"edge\"><title>12&#45;&gt;13</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M409.592,-374.771C430.343,-376.747 464.174,-379.969 488.322,-382.269\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"488.045,-385.758 498.332,-383.222 488.709,-378.79 488.045,-385.758\"/>\n",
       "<text text-anchor=\"middle\" x=\"453\" y=\"-385.8\" font-family=\"Times,serif\" font-size=\"14.00\">er:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 14 -->\n",
       "<g id=\"node21\" class=\"node\"><title>14</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"648\" cy=\"-385\" rx=\"19.4968\" ry=\"19.4968\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"648\" cy=\"-385\" rx=\"23.4965\" ry=\"23.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"648\" y=\"-381.3\" font-family=\"Times,serif\" font-size=\"14.00\">14</text>\n",
       "</g>\n",
       "<!-- 13&#45;&gt;14 -->\n",
       "<g id=\"edge20\" class=\"edge\"><title>13&#45;&gt;14</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M537.612,-385C557.665,-385 589.965,-385 614.278,-385\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"614.482,-388.5 624.482,-385 614.482,-381.5 614.482,-388.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"583\" y=\"-388.8\" font-family=\"Times,serif\" font-size=\"14.00\">z:peppers</text>\n",
       "</g>\n",
       "<!-- 17 -->\n",
       "<g id=\"node23\" class=\"node\"><title>17</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-316\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"390\" y=\"-312.3\" font-family=\"Times,serif\" font-size=\"14.00\">17</text>\n",
       "</g>\n",
       "<!-- 16&#45;&gt;17 -->\n",
       "<g id=\"edge22\" class=\"edge\"><title>16&#45;&gt;17</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M287.75,-316C307.124,-316 337.619,-316 360.083,-316\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"360.382,-319.5 370.382,-316 360.382,-312.5 360.382,-319.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"330\" y=\"-319.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 18 -->\n",
       "<g id=\"node24\" class=\"node\"><title>18</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-324\" rx=\"19.4968\" ry=\"19.4968\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-324\" rx=\"23.4965\" ry=\"23.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"518\" y=\"-320.3\" font-family=\"Times,serif\" font-size=\"14.00\">18</text>\n",
       "</g>\n",
       "<!-- 17&#45;&gt;18 -->\n",
       "<g id=\"edge23\" class=\"edge\"><title>17&#45;&gt;18</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M409.592,-317.18C429.27,-318.43 460.709,-320.426 484.5,-321.937\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"484.295,-325.43 494.496,-322.571 484.738,-318.444 484.295,-325.43\"/>\n",
       "<text text-anchor=\"middle\" x=\"453\" y=\"-325.8\" font-family=\"Times,serif\" font-size=\"14.00\">er:peter</text>\n",
       "</g>\n",
       "<!-- 21 -->\n",
       "<g id=\"node26\" class=\"node\"><title>21</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-259\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"390\" y=\"-255.3\" font-family=\"Times,serif\" font-size=\"14.00\">21</text>\n",
       "</g>\n",
       "<!-- 20&#45;&gt;21 -->\n",
       "<g id=\"edge25\" class=\"edge\"><title>20&#45;&gt;21</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M287.75,-259C307.124,-259 337.619,-259 360.083,-259\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"360.382,-262.5 370.382,-259 360.382,-255.5 360.382,-262.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"330\" y=\"-262.8\" font-family=\"Times,serif\" font-size=\"14.00\">k:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 22 -->\n",
       "<g id=\"node27\" class=\"node\"><title>22</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-259\" rx=\"19.4968\" ry=\"19.4968\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-259\" rx=\"23.4965\" ry=\"23.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"518\" y=\"-255.3\" font-family=\"Times,serif\" font-size=\"14.00\">22</text>\n",
       "</g>\n",
       "<!-- 21&#45;&gt;22 -->\n",
       "<g id=\"edge26\" class=\"edge\"><title>21&#45;&gt;22</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M409.592,-259C429.182,-259 460.427,-259 484.179,-259\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"484.496,-262.5 494.496,-259 484.496,-255.5 484.496,-262.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"453\" y=\"-262.8\" font-family=\"Times,serif\" font-size=\"14.00\">t:picked</text>\n",
       "</g>\n",
       "<!-- 25 -->\n",
       "<g id=\"node29\" class=\"node\"><title>25</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-201\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"390\" y=\"-197.3\" font-family=\"Times,serif\" font-size=\"14.00\">25</text>\n",
       "</g>\n",
       "<!-- 24&#45;&gt;25 -->\n",
       "<g id=\"edge28\" class=\"edge\"><title>24&#45;&gt;25</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M287.75,-201.844C307.124,-201.682 337.619,-201.428 360.083,-201.241\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"360.411,-204.738 370.382,-201.155 360.353,-197.739 360.411,-204.738\"/>\n",
       "<text text-anchor=\"middle\" x=\"330\" y=\"-205.8\" font-family=\"Times,serif\" font-size=\"14.00\">k:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 26 -->\n",
       "<g id=\"node30\" class=\"node\"><title>26</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-198\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"518\" y=\"-194.3\" font-family=\"Times,serif\" font-size=\"14.00\">26</text>\n",
       "</g>\n",
       "<!-- 25&#45;&gt;26 -->\n",
       "<g id=\"edge29\" class=\"edge\"><title>25&#45;&gt;26</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M409.592,-200.557C430.343,-200.063 464.174,-199.258 488.322,-198.683\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"488.418,-202.182 498.332,-198.444 488.251,-195.184 488.418,-202.182\"/>\n",
       "<text text-anchor=\"middle\" x=\"453\" y=\"-204.8\" font-family=\"Times,serif\" font-size=\"14.00\">ah:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 27 -->\n",
       "<g id=\"node31\" class=\"node\"><title>27</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"648\" cy=\"-198\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"648\" y=\"-194.3\" font-family=\"Times,serif\" font-size=\"14.00\">27</text>\n",
       "</g>\n",
       "<!-- 26&#45;&gt;27 -->\n",
       "<g id=\"edge30\" class=\"edge\"><title>26&#45;&gt;27</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M537.612,-198C558.752,-198 593.503,-198 618.159,-198\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"618.365,-201.5 628.365,-198 618.365,-194.5 618.365,-201.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"583\" y=\"-201.8\" font-family=\"Times,serif\" font-size=\"14.00\">l:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 28 -->\n",
       "<g id=\"node32\" class=\"node\"><title>28</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"778\" cy=\"-198\" rx=\"19.4968\" ry=\"19.4968\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"778\" cy=\"-198\" rx=\"23.4965\" ry=\"23.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"778\" y=\"-194.3\" font-family=\"Times,serif\" font-size=\"14.00\">28</text>\n",
       "</g>\n",
       "<!-- 27&#45;&gt;28 -->\n",
       "<g id=\"edge31\" class=\"edge\"><title>27&#45;&gt;28</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M667.612,-198C687.665,-198 719.965,-198 744.278,-198\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"744.482,-201.5 754.482,-198 744.482,-194.5 744.482,-201.5\"/>\n",
       "<text text-anchor=\"middle\" x=\"713\" y=\"-201.8\" font-family=\"Times,serif\" font-size=\"14.00\">d:pickled</text>\n",
       "</g>\n",
       "<!-- 31 -->\n",
       "<g id=\"node34\" class=\"node\"><title>31</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-139\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"390\" y=\"-135.3\" font-family=\"Times,serif\" font-size=\"14.00\">31</text>\n",
       "</g>\n",
       "<!-- 30&#45;&gt;31 -->\n",
       "<g id=\"edge33\" class=\"edge\"><title>30&#45;&gt;31</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M287.487,-144.076C306.897,-143.105 337.677,-141.566 360.26,-140.437\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"360.482,-143.93 370.294,-139.935 360.132,-136.939 360.482,-143.93\"/>\n",
       "<text text-anchor=\"middle\" x=\"330\" y=\"-147.8\" font-family=\"Times,serif\" font-size=\"14.00\">p:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 32 -->\n",
       "<g id=\"node35\" class=\"node\"><title>32</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-137\" rx=\"19.4968\" ry=\"19.4968\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-137\" rx=\"23.4965\" ry=\"23.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"518\" y=\"-133.3\" font-family=\"Times,serif\" font-size=\"14.00\">32</text>\n",
       "</g>\n",
       "<!-- 31&#45;&gt;32 -->\n",
       "<g id=\"edge34\" class=\"edge\"><title>31&#45;&gt;32</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M409.592,-138.705C429.182,-138.394 460.427,-137.898 484.179,-137.521\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"484.553,-141.016 494.496,-137.357 484.442,-134.016 484.553,-141.016\"/>\n",
       "<text text-anchor=\"middle\" x=\"453\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\">er:piper</text>\n",
       "</g>\n",
       "<!-- 37 -->\n",
       "<g id=\"node38\" class=\"node\"><title>37</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"390\" cy=\"-23\" rx=\"19.4965\" ry=\"19.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"390\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">37</text>\n",
       "</g>\n",
       "<!-- 36&#45;&gt;37 -->\n",
       "<g id=\"edge37\" class=\"edge\"><title>36&#45;&gt;37</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M287.75,-23C307.124,-23 337.619,-23 360.083,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"360.382,-26.5001 370.382,-23 360.382,-19.5001 360.382,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"330\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">r:&lt;eps&gt;</text>\n",
       "</g>\n",
       "<!-- 38 -->\n",
       "<g id=\"node39\" class=\"node\"><title>38</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-23\" rx=\"19.4968\" ry=\"19.4968\"/>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"518\" cy=\"-23\" rx=\"23.4965\" ry=\"23.4965\"/>\n",
       "<text text-anchor=\"middle\" x=\"518\" y=\"-19.3\" font-family=\"Times,serif\" font-size=\"14.00\">38</text>\n",
       "</g>\n",
       "<!-- 37&#45;&gt;38 -->\n",
       "<g id=\"edge38\" class=\"edge\"><title>37&#45;&gt;38</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M409.592,-23C429.182,-23 460.427,-23 484.179,-23\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"484.496,-26.5001 494.496,-23 484.496,-19.5001 484.496,-26.5001\"/>\n",
       "<text text-anchor=\"middle\" x=\"453\" y=\"-26.8\" font-family=\"Times,serif\" font-size=\"14.00\">z:where&#39;s</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<vector Fst at 0x7f9488615c70>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import openfst_python as fst\n",
    "from helper_functions import parse_lexicon, generate_symbol_tables\n",
    "\n",
    "lex = parse_lexicon('lexicon.txt')\n",
    "word_table, phone_table, state_table = generate_symbol_tables(lex)  # we won't use state_table in this lab\n",
    "\n",
    "def generate_L_wfst(lex):\n",
    "    \"\"\" Express the lexicon in WFST form\n",
    "    \n",
    "    Args:\n",
    "        lexicon (dict): lexicon to use, created from the parse_lexicon() function\n",
    "    \n",
    "    Returns:\n",
    "        the constructed lexicon WFST\n",
    "    \n",
    "    \"\"\"\n",
    "    L = fst.Fst()\n",
    "    \n",
    "    # create a single start state\n",
    "    start_state = L.add_state()\n",
    "    L.set_start(start_state)\n",
    "    \n",
    "    for (word, pron) in lex.items():\n",
    "        \n",
    "        current_state = start_state\n",
    "        for (i,phone) in enumerate(pron):\n",
    "            next_state = L.add_state()\n",
    "            \n",
    "            if i == len(pron)-1:\n",
    "                # add word output symbol on the final arc\n",
    "                L.add_arc(current_state, fst.Arc(phone_table.find(phone), \\\n",
    "                                                 word_table.find(word), None, next_state))\n",
    "            else:\n",
    "                L.add_arc(current_state, fst.Arc(phone_table.find(phone),0, None, next_state))\n",
    "            \n",
    "            current_state = next_state\n",
    "                          \n",
    "        L.set_final(current_state)\n",
    "        \n",
    "    L.set_input_symbols(phone_table)\n",
    "    L.set_output_symbols(word_table)                      \n",
    "    \n",
    "    return L\n",
    "\n",
    "L = generate_L_wfst(lex)\n",
    "L.arcsort()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the exercises, here are two functions to generate linear WFSTs for an arbitary sequence of phones or words.  (Yes, they are really just variants of the same function!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_linear_phone_wfst(phone_list):\n",
    "    \n",
    "    P = fst.Fst()\n",
    "    \n",
    "    current_state = P.add_state()\n",
    "    P.set_start(current_state)\n",
    "    \n",
    "    for p in phone_list:\n",
    "        \n",
    "        next_state = P.add_state()\n",
    "        P.add_arc(current_state, fst.Arc(phone_table.find(p), phone_table.find(p), None, next_state))\n",
    "        current_state = next_state\n",
    "        \n",
    "    P.set_final(current_state)\n",
    "    P.set_input_symbols(phone_table)\n",
    "    P.set_output_symbols(phone_table)\n",
    "    return P\n",
    "    \n",
    "def generate_linear_word_wfst(word_list):\n",
    "    \n",
    "    W = fst.Fst()\n",
    "    \n",
    "    current_state = W.add_state()\n",
    "    W.set_start(current_state)\n",
    "    \n",
    "    for w in word_list:\n",
    "        \n",
    "        next_state = W.add_state()\n",
    "        W.add_arc(current_state, fst.Arc(word_table.find(w), word_table.find(w), None, next_state))\n",
    "        current_state = next_state\n",
    "        \n",
    "    W.set_final(current_state)\n",
    "    W.set_input_symbols(word_table)\n",
    "    W.set_output_symbols(word_table)\n",
    "    return W"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises\n",
    "\n",
    "1. Suppose you are given a sequence of phones, in the form `['p','ih','k','t']`, and the $L$ transducer created above.  Write a function that returns the matching word from the lexicon for any given phone sequence, or else `None` if no matching word is found.   Write two functions:\n",
    "  1. That works for $L$ as provided by the code above\n",
    "  2. That works only on a determinized version of $L$ &ndash; and test it on the output of `fst.determinize(L)`\n",
    "  \n",
    " This should enable you to see why determinization is a very useful WFST operation!\n",
    "  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def transduce_sequence_nondet(f, in_seq):\n",
    "    \"\"\"Return transduced sequence given input sequence and non determinized FST.\n",
    "        Note that our skeleton code uses a queue to traverse the FST.\n",
    "        You can change this if you prefer, as long as you correctly output the list of trasduced words.\n",
    "    \n",
    "        Args:\n",
    "            f (fst.Fst()): a non determinized FST\n",
    "            in_seq (list[str]): the sequence of strings to transduce\n",
    "            \n",
    "        Returns:\n",
    "            out_seq (list[str]): the sequence of transduced symbols\n",
    "            \"\"\"\n",
    "    \n",
    "    seq_len = len(in_seq)\n",
    "    in_seq.append('<EOS>') # adding a padding symbol at the end for possible final eps traversal\n",
    "    queue = [(f.start(), 0, [])]  # the tuple is (state, index in input sequence, output)\n",
    "    outputs = []\n",
    "    \n",
    "    while queue:\n",
    "        curr_state, i, output = queue.pop(0) # pop first element in list\n",
    "        \n",
    "        if i <= seq_len:  # <= because we could traverse epsilons even when the input sequence ended\n",
    "            \n",
    "            # Your code here\n",
    "            \n",
    "        if i == seq_len:\n",
    "            final_weight = float(f.final(curr_state))\n",
    "            if final_weight != math.inf: # if this is a final state\n",
    "                out_seq = [f.output_symbols().find(w) for w in output if w != eps]  # find the labels in the table, remove epsilons\n",
    "                return out_seq\n",
    "            \n",
    "        \n",
    "    print(\"Can't transduce the sequence with provided FST\")  # return exits the function, so this is printed only when the stack is empty and we didn't find a path "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "seq = ['p','ih','k','t']\n",
    "print(transduce_sequence_nondet(L, seq))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#You should see the result below after running the last block\n",
    "# ['picked']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transduce_sequence_det(f, seq):\n",
    "    \"\"\"Return transduced sequence given input sequence and determinized FST\n",
    "    \n",
    "        Args:\n",
    "            f (fst.Fst()): a determinized FST\n",
    "            in_seq (list[str]): the sequence of strings to transduce\n",
    "            \n",
    "        Returns:\n",
    "            out_seq (list[str]): the sequence of transduced symbols\n",
    "            \"\"\"\n",
    "    \n",
    "    seq_len = len(seq)\n",
    "    curr_state = f.start()\n",
    "    output = []\n",
    "    \n",
    "    for i in range(seq_len):\n",
    "        # Your code here\n",
    "    final_weight = float(f.final(curr_state))\n",
    "    if final_weight != math.inf: # if this is a final state\n",
    "        out_seq = [f.output_symbols().find(w) for w in output if w != eps]  # find the labels in the table, remove epsilons\n",
    "        return out_seq\n",
    "    else:  \n",
    "        print(\"Can't transduce the sequence with provided FST\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "seq = ['p','ih','k','t']\n",
    "Ldet = fst.determinize(L)\n",
    "print(transduce_sequence_det(Ldet, seq))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# You should see the result below after running the last block\n",
    "# ['picked']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. WFST composition allows you to achieve the same result much more easily.  Create a linear WFST, $P$, corresponding to a string of phones, and compute $P \\circ L$.  Then use the projection and epsilon removal operations to display just the matching word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "seq = ['p','ih','k','t']\n",
    "P = generate_linear_phone_wfst(seq)\n",
    "\n",
    "def compose_phone_sequence_with_lexicon(P, L):\n",
    "\n",
    "    # Your code here for composition of P and L and other necessary FST operations\n",
    "    \n",
    "    return comp\n",
    "\n",
    "comp = compose_phone_sequence_with_lexicon(P, L)\n",
    "comp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should see this figure after running the last block\n",
    "![compose_phone_sequence_with_lexicon](figs/compose_phone_sequence_with_lexicon.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Modify your lexicon WFST slightly to allow a list of phones to be \"decoded\" to a sequence of multiple words from the lexicon. Then, compose the modified lexicon with a sequence of phones of multiple concatenated words.  Try it with `['p','eh','k','ah','v','p','iy','t','er']`.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# this modified the Lexicon WFST directly - you can also do it by adding\n",
    "# extra code to the generate_L_wfst() function above\n",
    "# The code below enables L to decode a sequence of phones corresponding to multiple words\n",
    "\n",
    "start_state = L.start()\n",
    "for state in L.states():\n",
    "    if float(L.final(state)) != math.inf:\n",
    "        L.add_arc(state, fst.Arc(0, 0, None, start_state))  # add arc to start\n",
    "Ldet = fst.determinize(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "seq = ['p','eh','k','ah','v','p','iy','t','er']\n",
    "P = generate_linear_phone_wfst(seq)\n",
    "\n",
    "def compose_phone_sequences_with_lexicon(P, L):\n",
    "    \n",
    "\n",
    "    # Your code here for composition of P and L and other necessary FST operations\n",
    "    \n",
    "    return comp\n",
    "\n",
    "comp = compose_phone_sequences_with_lexicon(P, L)\n",
    "comp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should see this figure after running the last block\n",
    "![compose_phone_sequences_with_lexicon](figs/compose_phone_sequences_with_lexicon.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Now solve the reverse problem: create a word-sequence WFST, $W$, and use composition to expand it into a sequence of phones. You'll need to sort by output labels this time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "seq = ['peck', 'of', 'peter']\n",
    "W = generate_linear_word_wfst(seq)\n",
    "\n",
    "def compose_lexicon_with_word_sequence(L, W):\n",
    "    \n",
    "    # Your code here\n",
    "    return comp\n",
    "\n",
    "comp = compose_lexicon_with_word_sequence(L, W)\n",
    "comp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should see this figure after running the last block\n",
    "![compose_lexicon_with_word_sequence](figs/compose_lexicon_with_word_sequence.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. Another advantage of WFST composition to solve these kind of problems are that it is easy to encode uncertainty in the input (a bit like in real ASR).  For example, consider this WFST, in which the multiple arcs denote alternative phone transcriptions from the acoustic model:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_alt_phone_wfst(phone_alternatives):\n",
    "    \n",
    "    P = fst.Fst()\n",
    "    \n",
    "    current_state = P.add_state()\n",
    "    P.set_start(current_state)\n",
    "    \n",
    "    for alt in phone_alternatives:\n",
    "        \n",
    "        next_state = P.add_state()\n",
    "        for p in alt:\n",
    "            if p=='*':\n",
    "                P.set_final(current_state)\n",
    "            else:\n",
    "                P.add_arc(current_state, fst.Arc(phone_table.find(p), phone_table.find(p), None, next_state))\n",
    "        current_state = next_state\n",
    "        \n",
    "    P.set_final(current_state)\n",
    "    P.set_input_symbols(phone_table)\n",
    "    P.set_output_symbols(phone_table)\n",
    "    return P    \n",
    "    \n",
    "altP = create_alt_phone_wfst([['p'],['ay'],['p'],['er'],['p'],['eh','ih'],['k'],['t','<eps>'],['ah','<eps>'],['l','v','*'],['d','*']])\n",
    "altP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "  Again, perform composition with your $L$ from Question 3, and observe the result.  (Notice particularly what happens to the `<eps>` transitions during composition.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "altP.arcsort()\n",
    "comp = # Please compose altP and L here \n",
    "comp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should see this figure after running the last block\n",
    "![compose_altP_lexicon](figs/compose_altP_lexicon.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "uncertainP = # Please project the output labels and remove epsilons here \n",
    "uncertainP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should see this figure after running the last block\n",
    "![project_output.png](figs/project_output.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. We could have added weights to the arcs of the WFST above to describe the probability of the phone alternatives given by the acoustic model &ndash; this would have enabled you to find the most likely sequence of words.  Without this information, let's instead use a $G$ WFST to find the most likely sequence.  Let's assume that a word sequence taken from the passage \"peter piper picked a peck of pickled peppers\" is most likely.  Design a $G$ WFST that accepts any sequence of words from the lexicon, but adds a cost of 1.0 to any word transition not in the passage.  Given $G$, use composition to recover the most likely word sequence from the uncertain $P$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_G_wfst(wseq):\n",
    "    \"\"\" Generate a grammar WFST that accepts any sequence of words for words in a sentence.\n",
    "        The bigrams not present in the sentence have a cost of 1, while those present have a cost of 0. \n",
    "        Args:\n",
    "            wseq (str): the sentence to use\n",
    "        Returns:\n",
    "            W (fst.Fst()): the grammar WFST \"\"\"\n",
    "    \n",
    "    G = fst.Fst()\n",
    "    start_state = G.add_state()\n",
    "    G.set_start(start_state)\n",
    "    \n",
    "    prev_state = None\n",
    "    \n",
    "    for w in wseq.split():\n",
    "        current_state = G.add_state()\n",
    "\n",
    "        # Your code here\n",
    "    \n",
    "    G.set_final(start_state)\n",
    "        \n",
    "    G.set_input_symbols(word_table)\n",
    "    G.set_output_symbols(word_table)  \n",
    " \n",
    "    return G\n",
    "\n",
    "string = \"peter piper picked a peck of pickled peppers\"\n",
    "G = generate_G_wfst(string)\n",
    "G\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now take the composition of the alternative pronunciation sequence and L you did in the exercise before and compose it with your new grammar. Check the output of the shortest path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Composition with your G wfst\n",
    "\n",
    "G.arcsort(sort_type='olabel')\n",
    "comp = fst.compose(uncertainP, G)\n",
    "comp.rmepsilon()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should see something similar to this\n",
    "![compose_with_G](figs/compose_with_G.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Get your result\n",
    "fst.shortestpath(comp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should see this figure after running the last block\n",
    "![results.png](figs/results.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## If you have more time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use WFST composition to implement a \"predictive text\"-style algorithm, that, given a partial phone sequence such as `['p']` or `['p','ih']`, returns a WFST giving all matching words.  You'll need to make some special modifications to $P$ or $L$, or both. On a determinized $L$ transducer this is a highly efficient way of solving this problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# There are very many ways this problem can be solved. Our skeleton code add extra arcs with \n",
    "# special <rho> symbol. This symbol will represent unterminated sequences, and will be transduced\n",
    "#  to words to be output at every intermediate state.\n",
    "# The same <rho> symbol is added the end of the partial pronunciation.\n",
    "\n",
    "def generate_predictive_L_wfst(lex):\n",
    "    \"\"\" express the lexicon in WFST form s.t. composition with partial sequence gives matching words\n",
    "    \n",
    "    Args:\n",
    "        lexicon (dict): lexicon to use, created from the parse_lexicon() function\n",
    "    \n",
    "    Returns:\n",
    "        the constructed WFST\n",
    "    \n",
    "    \"\"\"\n",
    "    Lpred = fst.Fst()\n",
    "    rho = phone_table.add_symbol('<rho>')\n",
    "    # create a single start state\n",
    "    start_state = Lpred.add_state()\n",
    "    Lpred.set_start(start_state)\n",
    "    \n",
    "    for (word, pron) in lex.items():\n",
    "        \n",
    "        # Your code here\n",
    "        \n",
    "    Lpred.set_input_symbols(phone_table)\n",
    "    Lpred.set_output_symbols(word_table)                      \n",
    "    \n",
    "    return Lpred\n",
    "\n",
    "Lpred = generate_predictive_L_wfst(lex)\n",
    "Lpred.arcsort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "seq = ['p']\n",
    "seq += ['<rho>']\n",
    "Ppred = generate_linear_phone_wfst(seq)\n",
    "Ppred.arcsort(sort_type='ilabel')\n",
    "comp = fst.compose(Ppred, Lpred)\n",
    "comp.project(True).rmepsilon()"
   ]
  }
 ],
 "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.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}