08.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Splitsville: Fun with the New **regex** Module\n",
    "\n",
    "## Rex Dwyer\n",
    "## TriPython Monthly Meeting\n",
    "## April 28, 2016\n",
    "\n",
    "The Python regular expression module **re** has a number of deficiencies.  There are several cases where its behavior differs from Perl, the gold standard for regular expressions. The **regex** module is intended to replace **re**. **regex** can be found at https://pypi.python.org/pypi/regex/2016.04.25 In addition to fixing some bugs, it adds a lot of new features. This notebook reviews a few 'advanced' features of regular expressions, then introduces some of the new features of **regex**.  It's not intended to be comprehensive.\n",
    "\n",
    "First, let's review a few things from the old **re** module that haven't changed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "from re import *\n",
    "\n",
    "t = 'The quick brown fox born on 1/23/2013 jumped over the lazy dog born on 10/6/10.'\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### match and search\n",
    "Use **r'...'** (raw strings) for patterns, because we like to use elements like **\\w**, and we don't want to have to type **\\\\\\\\w**.\n",
    "**match** looks for the pattern at the very beginning of the target string.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<_sre.SRE_Match object; span=(0, 3), match='The'>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "match(r'The',t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Normally if we were going to reuse a pattern, we'd compile it and use the **match** method of the resulting pattern like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<_sre.SRE_Match object; span=(0, 3), match='The'>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = compile(r'The')\n",
    "p.match(t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But in this tutorial, we will not compile.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one doesn't match, because **the** is not at the beginning of the target string.  It returns **None**, which of course doesn't print any output."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "match(r'the',t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**search** looks at the whole string.  It finds the **the** before **lazy dog**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<_sre.SRE_Match object; span=(50, 53), match='the'>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "search(r'the',t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**search** and **match** can be made case-insensitive."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<_sre.SRE_Match object; span=(0, 3), match='The'>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "search(r'the',t, IGNORECASE)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<_sre.SRE_Match object; span=(0, 3), match='The'>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "search(r'(?i)the',t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **findall** and **finditer**\n",
    "**findall** lists every match to the pattern, but doesn't give the position.  **I** is short for **IGNORECASE**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The', 'the']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'the',t, I)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**finditer** returns an iterator over all matches of the pattern in the string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<callable_iterator at 0x3ad8510>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "finditer(r'the',t, I)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<_sre.SRE_Match object; span=(0, 3), match='The'>,\n",
       " <_sre.SRE_Match object; span=(50, 53), match='the'>]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "list(finditer(r'the',t, I))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<_sre.SRE_Match object; span=(10, 19), match='brown fox'>,\n",
       " <_sre.SRE_Match object; span=(54, 62), match='lazy dog'>]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "list(finditer(r'(brown|lazy) (dog|fox)',t))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **X** option lets us add spaces to the pattern for readability -- but in this case, we wanted to match the space between the two words, so we need to escape it with **\\\\**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "list(finditer(r'(brown | lazy) (dog | fox)', t, X))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<_sre.SRE_Match object; span=(10, 19), match='brown fox'>,\n",
       " <_sre.SRE_Match object; span=(54, 62), match='lazy dog'>]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "list(finditer( r'(brown | lazy)\\ (dog | fox)', t, X ))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's find all the words with an internal **o**.  **\\\\w+** matches one or more 'word' characters: letters, digits, and underscore."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['brown', 'fox', 'born', 'dog', 'born']"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'\\w+o\\w+', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one also matches words that begin or end with **o**, because **\\\\w\\*** matches zero or more characters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['brown', 'fox', 'born', 'on', 'over', 'dog', 'born', 'on']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'\\w*o\\w*', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Substitution with **sub**\n",
    "Now a couple of substitutions... Note that (unlike in Perl) substitution returns a new string.  That's no surprise, because Python strings are immutable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The quick o-word o-word o-word o-word 1/23/2013 jumped o-word the lazy o-word o-word o-word 10/6/10.'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "sub(r'\\w*o\\w*', 'o-word', t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The quick brown fox born on 1/23/2013 jumped over the lazy dog born on 10/6/10.'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "t\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Capturing parts of the pattern match\n",
    "We can capture things with parentheses, then refer to the captured items by **\\1, \\2**, etc. in the substitution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The quick =brown= =fox= =born= =on= 1/23/2013 jumped =over= the lazy =dog= =born= =on= 10/6/10.'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "sub(r'(\\w*)o(\\w*)', r'=\\1o\\2=', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also give things names when we capture them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The quick =brown= =fox= =born= =on= 1/23/2013 jumped =over= the lazy =dog= =born= =on= 10/6/10.'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "sub(r'(?P<before>\\w*)o(?P<after>\\w*)', r'=\\g<before>o\\g<after>=', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can make the pattern, but apparently not the substitution, clearer by adding (?x) and spaces."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The quick =brown= =fox= =born= =on= 1/23/2013 jumped =over= the lazy =dog= =born= =on= 10/6/10.'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "sub(r'(?x) (?P<before> \\w*) o (?P<after> \\w*)', r'=\\g<before>o\\g<after>=', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yes, this would have been easier:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'The quick =brown= =fox= =born= =on= 1/23/2013 jumped =over= the lazy =dog= =born= =on= 10/6/10.'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "sub(r'(?x) (\\w*o\\w*)', r'=\\1=', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Greedy and lazy matching\n",
    "Let's try to get the \"day\" portion of each date. It is the first and only captured group in this pattern."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['23/2013 jumped over the lazy dog born on 10/6']"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "fi = finditer(r'(?x) / (.* ) /', t)\n",
    "\n",
    "[m.group(1) for m in fi]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What went wrong? By default, **\\*** is greedy.  We can make it lazy by adding **?**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['23', '6']"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "fi = finditer(r'(?x) / (.*? ) /', t)\n",
    "\n",
    "[m.group(1) for m in fi]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This works for the other quantifiers as well.  (**+, ?, {m,n}**)\n",
    "\n",
    "This one is eager and has an internal **e** in the first match and an internal **o** in the second match."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['e quick brown fox born on 1/23/2013 jumped over the', 'og born o']"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "fi = finditer(r'(?x) ([aeiou]) .* \\1', t)\n",
    "\n",
    "[m.group(0) for m in fi]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one is lazy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['e quick brown fox born on 1/23/2013 jumpe', 'over the lazy do', 'orn o']"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "fi = finditer(r'(?x) ([aeiou]) .*? \\1', t)\n",
    "\n",
    "[m.group(0) for m in fi]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### split\n",
    "**split** works differently in **regex**.  Let's start with **re**.\n",
    "This is a familiar split on whitespace."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The',\n",
       " 'quick',\n",
       " 'brown',\n",
       " 'fox',\n",
       " 'born',\n",
       " 'on',\n",
       " '1/23/2013',\n",
       " 'jumped',\n",
       " 'over',\n",
       " 'the',\n",
       " 'lazy',\n",
       " 'dog',\n",
       " 'born',\n",
       " 'on',\n",
       " '10/6/10.']"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'\\s+', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And this splits on the letter **o**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick br',\n",
       " 'wn f',\n",
       " 'x b',\n",
       " 'rn ',\n",
       " 'n 1/23/2013 jumped ',\n",
       " 'ver the lazy d',\n",
       " 'g b',\n",
       " 'rn ',\n",
       " 'n 10/6/10.']"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'o', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a gotcha:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick br',\n",
       " 'wn f',\n",
       " 'x born on 1/23/2013 jumped over the lazy dog born on 10/6/10.']"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'o', t, IGNORECASE)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The third argument to **split** does not give options.  It gives the maximum number of splits.  We unknowingly specified 2:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "IGNORECASE\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For split, it is better to use **(?i)** for case-insensitivity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['',\n",
       " ' quick brown fox born on 1/23/2013 jumped over ',\n",
       " ' lazy dog born on 10/6/10.']"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?i)the', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or you can use the **flags** keyword argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['',\n",
       " ' quick brown fox born on 1/23/2013 jumped over ',\n",
       " ' lazy dog born on 10/6/10.']"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'the', t, flags=IGNORECASE)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Capturing in the pattern for **split**\n",
    "\n",
    "This one splits on words with an internal **u**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The ',\n",
       " ' brown fox born on 1/23/2013 ',\n",
       " ' over the lazy dog born on 10/6/10.']"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'\\w+u\\w+', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But what if we wanted to save the **u**-words?  We can use parentheses to capture things inside the splitting pattern!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The ',\n",
       " 'quick',\n",
       " ' brown fox born on 1/23/2013 ',\n",
       " 'jumped',\n",
       " ' over the lazy dog born on 10/6/10.']"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(\\w+u\\w+)', t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick ',\n",
       " ' ',\n",
       " ' ',\n",
       " ' ',\n",
       " ' 1/23/2013 jumped ',\n",
       " ' the lazy ',\n",
       " ' ',\n",
       " ' ',\n",
       " ' 10/6/10.']"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'\\w*o\\w*', t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick ',\n",
       " 'brown',\n",
       " ' ',\n",
       " 'fox',\n",
       " ' ',\n",
       " 'born',\n",
       " ' ',\n",
       " 'on',\n",
       " ' 1/23/2013 jumped ',\n",
       " 'over',\n",
       " ' the lazy ',\n",
       " 'dog',\n",
       " ' ',\n",
       " 'born',\n",
       " ' ',\n",
       " 'on',\n",
       " ' 10/6/10.']"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(\\w*o\\w*)', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we split on 4-letter words.  Then we do it again and capture the 4-letter words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox ',\n",
       " ' on 1/23/',\n",
       " ' jumped ',\n",
       " ' the ',\n",
       " ' dog ',\n",
       " ' on 10/6/10.']"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'\\b\\w{4}\\b', t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox ',\n",
       " 'born',\n",
       " ' on 1/23/',\n",
       " '2013',\n",
       " ' jumped ',\n",
       " 'over',\n",
       " ' the ',\n",
       " 'lazy',\n",
       " ' dog ',\n",
       " 'born',\n",
       " ' on 10/6/10.']"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'\\b(\\w{4})\\b', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **split** and zero-width assertions.\n",
    "Here we split on word boundaries.  **\\\\b** is a zero-width assertion.  It requires that certain characters be present, but it doesn't \"consume\" them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox born on 1/23/2013 jumped over the lazy dog born on 10/6/10.']"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'\\b',t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So what went wrong?  Unlike **split** in Perl, the split function in **re** will not split on zero-width assertions. The new **regex** module gets this right."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox born on 1/23/2013 jumped over the lazy dog born on 10/6/10.']"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "from regex import *\n",
    "split(r'\\b',t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oops. To get the new behavior, we must add the \"Version 1\" option to the regular expression.  \"Version 0\" emulates **re**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['',\n",
       " 'The',\n",
       " ' ',\n",
       " 'quick',\n",
       " ' ',\n",
       " 'brown',\n",
       " ' ',\n",
       " 'fox',\n",
       " ' ',\n",
       " 'born',\n",
       " ' ',\n",
       " 'on',\n",
       " ' ',\n",
       " '1',\n",
       " '/',\n",
       " '23',\n",
       " '/',\n",
       " '2013',\n",
       " ' ',\n",
       " 'jumped',\n",
       " ' ',\n",
       " 'over',\n",
       " ' ',\n",
       " 'the',\n",
       " ' ',\n",
       " 'lazy',\n",
       " ' ',\n",
       " 'dog',\n",
       " ' ',\n",
       " 'born',\n",
       " ' ',\n",
       " 'on',\n",
       " ' ',\n",
       " '10',\n",
       " '/',\n",
       " '6',\n",
       " '/',\n",
       " '10',\n",
       " '.']"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "split(r'(?V1)\\b',t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can make life a little easier by setting the version globally."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['',\n",
       " 'The',\n",
       " ' ',\n",
       " 'quick',\n",
       " ' ',\n",
       " 'brown',\n",
       " ' ',\n",
       " 'fox',\n",
       " ' ',\n",
       " 'born',\n",
       " ' ',\n",
       " 'on',\n",
       " ' ',\n",
       " '1',\n",
       " '/',\n",
       " '23',\n",
       " '/',\n",
       " '2013',\n",
       " ' ',\n",
       " 'jumped',\n",
       " ' ',\n",
       " 'over',\n",
       " ' ',\n",
       " 'the',\n",
       " ' ',\n",
       " 'lazy',\n",
       " ' ',\n",
       " 'dog',\n",
       " ' ',\n",
       " 'born',\n",
       " ' ',\n",
       " 'on',\n",
       " ' ',\n",
       " '10',\n",
       " '/',\n",
       " '6',\n",
       " '/',\n",
       " '10',\n",
       " '.']"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import regex\n",
    "regex.DEFAULT_VERSION = VERSION1\n",
    "split(r'\\b',t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**\\\\m** and **\\\\M** are zero-width assertions that are true at the beginnings and ends of words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The',\n",
       " ' quick',\n",
       " ' brown',\n",
       " ' fox',\n",
       " ' born',\n",
       " ' on',\n",
       " ' 1',\n",
       " '/23',\n",
       " '/2013',\n",
       " ' jumped',\n",
       " ' over',\n",
       " ' the',\n",
       " ' lazy',\n",
       " ' dog',\n",
       " ' born',\n",
       " ' on',\n",
       " ' 10',\n",
       " '/6',\n",
       " '/10',\n",
       " '.']"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'\\M',t)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['',\n",
       " 'The ',\n",
       " 'quick ',\n",
       " 'brown ',\n",
       " 'fox ',\n",
       " 'born ',\n",
       " 'on ',\n",
       " '1/',\n",
       " '23/',\n",
       " '2013 ',\n",
       " 'jumped ',\n",
       " 'over ',\n",
       " 'the ',\n",
       " 'lazy ',\n",
       " 'dog ',\n",
       " 'born ',\n",
       " 'on ',\n",
       " '10/',\n",
       " '6/',\n",
       " '10.']"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'\\m',t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Look-arounds\n",
    "We can split on any 4-letter word."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox ',\n",
       " ' on 1/23/',\n",
       " ' jumped ',\n",
       " ' the ',\n",
       " ' dog ',\n",
       " ' on 10/6/10.']"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) \\b \\w{4} \\b', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But what if we want to split on any 4-letter word but **born**? We can use a look-ahead assertion.  Look-aheads and look-behinds come in two flavors: positive and negative.  All four are zero-width assertions.  They required certain characters to be present or absent, but don't consume the characters.  In this case, we need a negative assertion.  We could do a look-ahead:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox born on 1/23/',\n",
       " ' jumped ',\n",
       " ' the ',\n",
       " ' dog born on 10/6/10.']"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) \\b (?!born) \\w{4} \\b', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or a look-behind:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox born on 1/23/',\n",
       " ' jumped ',\n",
       " ' the ',\n",
       " ' dog born on 10/6/10.']"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) \\b \\w{4} (?<!born) \\b', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or, if we are feeling perverse, both:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox born on 1/23/',\n",
       " ' jumped ',\n",
       " ' the ',\n",
       " ' dog born on 10/6/10.']"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) \\b (?!bor) \\w{4} (?<!orn) \\b', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one splits on any 4-letter word that doesn't contain **o**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox born on 1/23/',\n",
       " ' jumped over the ',\n",
       " ' dog born on 10/6/10.']"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) \\b (?!\\w*o) \\w{4} \\b', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one splits on the letter **o**.  The **o** is consumed and lost."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick br',\n",
       " 'wn f',\n",
       " 'x b',\n",
       " 'rn ',\n",
       " 'n 1/23/2013 jumped ',\n",
       " 'ver the lazy d',\n",
       " 'g b',\n",
       " 'rn ',\n",
       " 'n 10/6/10.']"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) o', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one has a positive look-ahead assertion.  It splits before every **o**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick br',\n",
       " 'own f',\n",
       " 'ox b',\n",
       " 'orn ',\n",
       " 'on 1/23/2013 jumped ',\n",
       " 'over the lazy d',\n",
       " 'og b',\n",
       " 'orn ',\n",
       " 'on 10/6/10.']"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) (?=o)', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one has a positive look-behind assertion.  It splits after evey **o**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick bro',\n",
       " 'wn fo',\n",
       " 'x bo',\n",
       " 'rn o',\n",
       " 'n 1/23/2013 jumped o',\n",
       " 'ver the lazy do',\n",
       " 'g bo',\n",
       " 'rn o',\n",
       " 'n 10/6/10.']"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) (?<=o)', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one splits between  **o** and **r**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox bo',\n",
       " 'rn on 1/23/2013 jumped over the lazy dog bo',\n",
       " 'rn on 10/6/10.']"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) (?<=o) (?=r)', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The assertions could appear in either order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The quick brown fox bo',\n",
       " 'rn on 1/23/2013 jumped over the lazy dog bo',\n",
       " 'rn on 10/6/10.']"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) (?=r) (?<=o)', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one splits between any two consecutive vowels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['The qu',\n",
       " 'ick brown fox born on 1/23/2013 jumped over the lazy dog born on 10/6/10.']"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(r'(?x) (?<=[aeiou]) (?=[aeiou])', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fun with DNA: Open reading frames\n",
    "DNA is a sequence of bases, A, C, G, or T.  They are translated into proteins 3 bases at a time.  Each 3-base sequence is called a **codon**.  There is a special **start codon** ATG, and three **stop codons**, TGA, TAG, and TAA.  The start and stop codons are highlighted below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "dna = 'cgcgcATGcgcgcgTGAcgcgcgTAGcgcgcgcgc'\n",
    "\n",
    "dna = dna.lower()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An **opening reading frame** or **ORF** consists of a start codon, followed by some more codons, and ending with a stop codon.  (In real life, \"some more\" is usually hundreds or thousands.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<regex.Match object; span=(5, 26), match='atgcgcgcgtgacgcgcgtag'>"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "orfpat = r'(?x) atg (...)* (tga|tag|taa)'\n",
    "\n",
    "search(orfpat,dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Actually, that's not quite right.  The internal codons should not be stop codons. We can handle that with a negative lookahead assertion.  (Can you think of another way?)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<regex.Match object; span=(5, 17), match='atgcgcgcgtga'>"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "orfpat = r'(?x) atg  ( (?!tga|tag|taa) ... )*  (tga|tag|taa)'\n",
    "\n",
    "search(orfpat,dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We don't really want to capture the \"some more codons\" separately.  In a minute that will get in the way.  So we can use **(?:...)** to group without capturing:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['atgcgcgcgtga']"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "orfpat = r'(?x) ( atg  (?: (?!tga|tag|taa) ... )*  (?:tga|tag|taa) )'\n",
    "\n",
    "findall(orfpat,dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is another DNA sequence.  Note that this one has overlapping ORFs.  We would like a list of **all** orfs, specifically **ATGcATGcgTGA** and **ATGcgTGAcTAA**.  Our last pattern only finds the first ORF. Since it consumes the first ORF, it also consumes the beginning of the second ORF."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['atgcatgcgtga']"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "dna = 'cgcgcATGcATGcgTGAcTAAcgTAGcgcgcgcgc'\n",
    "\n",
    "dna = dna.lower()\n",
    "\n",
    "findall(orfpat,dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since we want to find something without consuming it, we can use a positive lookahead assertion.  We put the whole ORF pattern inside the lookahead.  We need to capture what is matched by the lookahead without consuming it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['atgcatgcgtga', 'atgcgtgactaa']"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "orfpat = r'(?x) (?= ( atg  (?: (?!tga|tag|taa) ... )*  (?:tga|tag|taa) ))'\n",
    "\n",
    "findall(orfpat,dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice the position of the capturing parentheses.  This doesn't work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['', '']"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "orfpat = r'(?x) ( (?= atg  (?: (?!tga|tag|taa) ... )*  (?:tga|tag|taa) ))'\n",
    "\n",
    "findall(orfpat,dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why? Because the look-ahead assertion has width 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### More fun with DNA: Restriction Digest Assays\n",
    "To perform certain assays, molecular biologists subject DNA sequences to enzymes known as restriction enzymes. There are several types; this is about Type II restriction endonucleases, to be precise. They are usually named with three letters, for the species of origin, and a Roman numeral; e.g., AfeI comes from Alcaligenes faecalis.  These enzymes typically recognize a specific sequence of 6-10 letters, and cut the DNA somewhere in the middle of that sequence.  For example, BgIII recognizes **AGATCT** and cuts between the first **A** and the **G**.\n",
    "\n",
    "For a typical assay, the DNA will be digested by a \"cocktail\" of 3-6 enzymes. The lengths of the resulting pieces will be measured by gel electrophoresis.  The lengths should match up with the lengths predicted by an in silico digestion. If not, something is wrong.\n",
    "Our task is to do the in silico digestion.\n",
    "\n",
    "For development, here is a dictionary of 4 enzymes, a DNA sequence to digest, and the string we would like to get out of the process. In real life, the DNA sequence would be thousands to ten-thousands of letters long. The researcher could be interested in knowing the cut-points for dozens of enzymes, even though a typical assay uses just a few."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "enzymes = {'A-GATCT': 'BgIII',\n",
    "           'AGC-GCT': 'AfeI',\n",
    "           'AGG-CCT': 'StuI',\n",
    "           'AT-CGAT': 'ClaI'}\n",
    "\n",
    "dna = 'AAAAGCGCTAAAATCGATAAAAAAGATCTAAAAAGCGCT'\n",
    "\n",
    "goal = 'AAAAGC <AfeI> GCTAAAAT <ClaI> CGATAAAAAA <BgIII> GATCTAAAAAGC <AfeI> GCT'\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are going to use positive look-aheads and look-behinds.  We will build a look ahead-look behind combination for each enzyme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['(?<=AT)(?=CGAT)', '(?<=A)(?=GATCT)', '(?<=AGC)(?=GCT)', '(?<=AGG)(?=CCT)']"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "pats = ['(?<=' + fore + ')(?=' + aft + ')' \n",
    "        \n",
    "        for (fore,aft) in [split(r'-',s) for s in enzymes.keys()]]\n",
    "\n",
    "pats\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(?<=AT)(?=CGAT) | (?<=A)(?=GATCT) | (?<=AGC)(?=GCT) | (?<=AGG)(?=CCT)'"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "pats = ' | '.join(pats)\n",
    "pats\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(?x) ( (?<=AT)(?=CGAT) | (?<=A)(?=GATCT) | (?<=AGC)(?=GCT) | (?<=AGG)(?=CCT) )'"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "pat = \"(?x) ( \" + pats + \" )\"\n",
    "pat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "AAAAGC <AfeI> GCTAAAAT <ClaI> CGATAAAAAA <BgIII> GATCTAAAAAGC <AfeI> GCT\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['AAAAGC', '', 'GCTAAAAT', '', 'CGATAAAAAA', '', 'GATCTAAAAAGC', '', 'GCT']"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(goal)\n",
    "\n",
    "split(pat,dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's a good start.  We split in the right places, but we didn't capture the recognition sequences, so we can't retrieve the name of the enzyme from the dictionary. In fact, we captured empty strings.  That's because we captured a zero-width assertion. So we will add some parentheses to capture the look-aheads and look-behinds."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(?x) (?: (?<=(AT)) (?=(CGAT))  |  (?<=(A)) (?=(GATCT))  |  (?<=(AGC)) (?=(GCT))  |  (?<=(AGG)) (?=(CCT)) )'"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "pats = ['(?<=(' + fore + ')) (?=(' + aft + '))' \n",
    "        \n",
    "        for (fore,aft) in [split(r'-',s) for s in enzymes.keys()]]\n",
    "\n",
    "pats = '  |  '.join(pats)\n",
    "pat = '(?x) (?: ' + pats + ' )'\n",
    "pat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['AAAAGC',\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " 'AGC',\n",
       " 'GCT',\n",
       " None,\n",
       " None,\n",
       " 'GCTAAAAT',\n",
       " 'AT',\n",
       " 'CGAT',\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " 'CGATAAAAAA',\n",
       " None,\n",
       " None,\n",
       " 'A',\n",
       " 'GATCT',\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " 'GATCTAAAAAGC',\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " None,\n",
       " 'AGC',\n",
       " 'GCT',\n",
       " None,\n",
       " None,\n",
       " 'GCT']"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(pat,dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What happened?  The pattern has eight sets of capturing parentheses. So, the match also returns eight groups when it's executed.  Only the parentheses from the successful alternative will capture anything.  The other six groups are set to **None**.\n",
    "\n",
    "Happily, **regex** provides a new \"branch reset\" feature. Briefly, it means that capturing occurs only on the successful branch."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(?x) (?| (?<=(AT)) (?=(CGAT))  |  (?<=(A)) (?=(GATCT))  |  (?<=(AGC)) (?=(GCT))  |  (?<=(AGG)) (?=(CCT)) )'"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "pat = '(?x) (?| ' + pats + ' )'\n",
    "pat\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['AAAAGC',\n",
       " 'AGC',\n",
       " 'GCT',\n",
       " 'GCTAAAAT',\n",
       " 'AT',\n",
       " 'CGAT',\n",
       " 'CGATAAAAAA',\n",
       " 'A',\n",
       " 'GATCT',\n",
       " 'GATCTAAAAAGC',\n",
       " 'AGC',\n",
       " 'GCT',\n",
       " 'GCT']"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "split(pat,dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hooray!  Now all we have to do it to map the recognition sequences into enzyme names:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'AAAAGC <AfeI> GCTAAAAT <ClaI> CGATAAAAAA <BgIII> GATCTAAAAAGC <AfeI> GCT'"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "L = split(pat,dna)\n",
    "\n",
    "LL = [ ' <' + enzymes[L[i]+'-'+L[i+1]] + '> '+ L[i+2] \n",
    "      \n",
    "                  for i in range(1,len(L),3) ]\n",
    "\n",
    "L[0] + ''.join(LL)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we can pull it all together into a nice class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "passed\n"
     ]
    }
   ],
   "source": [
    "\n",
    "import regex as re\n",
    "\n",
    "class EndonucleaseDigestor:\n",
    "    \n",
    "    def __init__(this,enzymeDict):\n",
    "        pats = ['(?<=(' + fore + '))(?=(' + aft + '))' \n",
    "                for (fore,aft) in [re.split(r'-',s) for s in enzymeDict.keys()]]\n",
    "        pat = ' | '.join(pats)\n",
    "        pat = '(?x) (?| ' + pat + ' )'\n",
    "        this.pat = re.compile(pat)\n",
    "        this.enzymes = enzymeDict\n",
    "        \n",
    "    def digest(this,dna):\n",
    "        L = this.pat.split(dna)\n",
    "        LL = [ ' <' + enzymes[L[i]+'-'+L[i+1]] + '> '+ L[i+2] for i in range(1,len(L),3) ]\n",
    "        return L[0] + ''.join(LL)\n",
    "        \n",
    "\n",
    "enzymes = {'A-GATCT': 'BgIII',\n",
    "           'AGC-GCT': 'AfeI',\n",
    "           'AGG-CCT': 'StuI',\n",
    "           'AT-CGAT': 'ClaI'}\n",
    "dna = 'AAAAGCGCTAAAATCGATAAAAAAGATCTAAAAAGCGCT'\n",
    "goal = 'AAAAGC <AfeI> GCTAAAAT <ClaI> CGATAAAAAA <BgIII> GATCTAAAAAGC <AfeI> GCT'\n",
    "\n",
    "digestor = EndonucleaseDigestor(enzymes)\n",
    "if digestor.digest(dna) == goal: print(\"passed\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### TMTOWTDT: **sub** with a function\n",
    "There's another way to solve the restriction digest problem. This time let's start by building a dictionary that maps the recognition sequences into versions with the enzyme name interposed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'AGATCT': 'A <BgIII> GATCT',\n",
       " 'AGCGCT': 'AGC <AfeI> GCT',\n",
       " 'AGGCCT': 'AGG <StuI> CCT',\n",
       " 'ATCGAT': 'AT <ClaI> CGAT'}"
      ]
     },
     "execution_count": 73,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "d = { sub('-','',k) : sub('-',\" <\"+v+\"> \", k) for k,v in enzymes.items()}\n",
    "d\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And let's build a pattern that matches all the recognition sequences:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(?x) (ATCGAT | AGATCT | AGCGCT | AGGCCT)'"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "p = ' | '.join( [ sub('-','',k) for k in enzymes.keys()])\n",
    "p = '(?x) (' + p + ')'\n",
    "p\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second argument to **sub** can be a function rather than a string.  If so, the function is called with a **match** object as its argument.  We are interested in the first (and only) thing captured in the match and we want to get the corresponding string out of dictionary **d**.  So we define a function to do that.  Then we call sub with that function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<regex.Match object; span=(3, 9), match='AGCGCT'>\n",
      "<regex.Match object; span=(12, 18), match='ATCGAT'>\n",
      "<regex.Match object; span=(23, 29), match='AGATCT'>\n",
      "<regex.Match object; span=(33, 39), match='AGCGCT'>\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'AAAAGC <AfeI> GCTAAAAT <ClaI> CGATAAAAAA <BgIII> GATCTAAAAAGC <AfeI> GCT'"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "def subber (m):\n",
    "    print(m)\n",
    "    return d[m.group(1)]\n",
    "\n",
    "sub(p, subber, dna)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So we can make a class like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "passed\n"
     ]
    }
   ],
   "source": [
    "\n",
    "import regex as re\n",
    "\n",
    "class AnotherEndonucleaseDigestor:\n",
    "    \n",
    "    def __init__(this,enzymeDict):\n",
    "        this.d = { re.sub('-','',k) : re.sub('-',\" <\"+v+\"> \", k) for k,v in enzymes.items()}\n",
    "        p = ' | '.join( [ re.sub('-','',k) for k in enzymes.keys()])\n",
    "        p = '(?x) (' + p + ')'\n",
    "        this.pat = re.compile(p)\n",
    "        this.enzymes = enzymeDict\n",
    "        \n",
    "    def digest(this,dna):\n",
    "        return this.pat.sub( lambda m: this.d[m.group(1)]  , dna)\n",
    "\n",
    "enzymes = {'A-GATCT': 'BgIII',\n",
    "           'AGC-GCT': 'AfeI',\n",
    "           'AGG-CCT': 'StuI',\n",
    "           'AT-CGAT': 'ClaI'}\n",
    "dna = 'AAAAGCGCTAAAATCGATAAAAAAGATCTAAAAAGCGCT'\n",
    "goal = 'AAAAGC <AfeI> GCTAAAAT <ClaI> CGATAAAAAA <BgIII> GATCTAAAAAGC <AfeI> GCT'\n",
    "\n",
    "digestor = AnotherEndonucleaseDigestor(enzymes)\n",
    "if digestor.digest(dna) == goal: print(\"passed\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That probably seems a lot simpler, but there is one problem.  What if two recognition sites are overlapping?  For the in silico simulation of a real digest, it doesn't much matter, because the resolution of gel electrophoresis is much less than the 5-10 bases that might be overlapping.  On the other hand, if the scientist actually wants a complete inventory of all the restriction sites for a large set of enzymes, overlaps matter, and this solution won't work."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Nested sets\n",
    "We have seen some character sets such as **[aeiou]** for all (lower-case) vowels.  Suppose we want all lower-case consonants.  One obvious way is to list them all.  We might also be tempted to use set negation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Th',\n",
       " ' q',\n",
       " 'ck br',\n",
       " 'wn f',\n",
       " 'x b',\n",
       " 'rn ',\n",
       " 'n 1/23/2013 j',\n",
       " 'mp',\n",
       " 'd ',\n",
       " 'v',\n",
       " 'r th',\n",
       " ' l',\n",
       " 'zy d',\n",
       " 'g b',\n",
       " 'rn ',\n",
       " 'n 10/6/10.']"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'[^aeiou]+',t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The problem is that we get not just consonants, but spaces, digits, etc.\n",
    "The new **regex** module allows us to do arithmetic on sets:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['h',\n",
       " 'q',\n",
       " 'ck',\n",
       " 'br',\n",
       " 'wn',\n",
       " 'f',\n",
       " 'x',\n",
       " 'b',\n",
       " 'rn',\n",
       " 'n',\n",
       " 'j',\n",
       " 'mp',\n",
       " 'd',\n",
       " 'v',\n",
       " 'r',\n",
       " 'th',\n",
       " 'l',\n",
       " 'zy',\n",
       " 'd',\n",
       " 'g',\n",
       " 'b',\n",
       " 'rn',\n",
       " 'n']"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'(?x) [[a-z]--[aeiou]]+', t)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fuzzy matching\n",
    "With **regex**, you can specify that patterns need only be satisfied approximately.  You can specify the number of insertions (**i**), number of deletions (**d**), and number of substitutions (**s**) as well as total number of errors (**e**).\n",
    "This example allows at most one insertion and at most one deletion for each pattern."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<regex.Match object; span=(10, 19), match='crown fax', fuzzy_counts=(0, 2, 2)>,\n",
       " <regex.Match object; span=(52, 61), match='leazy hog', fuzzy_counts=(0, 2, 1)>]"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "list(finditer(r'(brown|lazy){i<=1,d<=1} (dog|fox){i<=1,d<=1}',\n",
    "              \n",
    "              'The quick crown fax barn on Monday jumped over the sleazy hog bran on Tuesday.'))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can see that the match object reports the number of insertions, deletions, and substitutions as **fuzzy_counts**. \n",
    "\n",
    "You can even **require** a minimum number of errors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<regex.Match object; span=(8, 19), match='k crown fax', fuzzy_counts=(2, 2, 0)>,\n",
       " <regex.Match object; span=(20, 27), match='barn on', fuzzy_counts=(3, 0, 2)>,\n",
       " <regex.Match object; span=(50, 61), match=' sleazy hog', fuzzy_counts=(1, 3, 0)>,\n",
       " <regex.Match object; span=(62, 69), match='bran on', fuzzy_counts=(3, 0, 2)>]"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "list(finditer(r'(brown|lazy){1<=e<=3} (dog|fox){1<=e<=2}',\n",
    "                            \n",
    "              'The quick crown fax barn on Monday jumped over the sleazy hog bran on Tuesday.'))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What matched what?  We can find out by doing some more capturing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('k crown', '', '', 'fax'),\n",
       " ('barn', '', 'on', ''),\n",
       " ('', ' sleazy', 'hog', ''),\n",
       " ('bran', '', 'on', '')]"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'(?:(brown)|(lazy)){1<=e<=3} (?:(dog)|(fox)){1<=e<=2}',\n",
    "        \n",
    "        'The quick crown fax barn on Monday jumped over the sleazy hog bran on Tuesday.')\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What if we try our orginal correct string? We should get back no matches, because there are no errors, right?  Maybe not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('ck brown', '', 'fox', ''),\n",
       " (' born', '', 'on', ''),\n",
       " ('', 'he lazy', 'dog', ''),\n",
       " ('born', '', 'on', '')]"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'(?:(brown)|(lazy)){1<=e<=3} (?:(dog)|(fox)){1<=e<=2}',\n",
    "        \n",
    "        'The quick brown fox born on 1/23/2013 jumped over the lazy dog born on 10/6/10.')\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maybe it will work if we try the **BESTMATCH** option:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(' lazy', 'dog '), ('born', 'on')]"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'(brown|lazy){1<=e<=3} (dog|fox){1<=e<=2}',\n",
    "        'The quick brown fox born on 1/23/2013 jumped over the lazy dog born on 10/6/10.',\n",
    "        BESTMATCH)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hmm.  Maybe we need the **ENHANCEMATCH** option."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(' brown', 'fox'), ('born', 'on'), (' lazy', 'dog '), ('born', 'on')]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'(brown|lazy){1<=e<=3} (dog|fox){1<=e<=2}',\n",
    "        'The quick brown fox born on 1/23/2013 jumped over the lazy dog born on 10/6/10.',\n",
    "         ENHANCEMATCH)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maybe we should use both...."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(' lazy', 'dog '), ('born', 'on')]"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r'(brown|lazy){1<=e<=3} (dog|fox){1<=e<=2}',\n",
    "        'The quick brown fox born on 1/23/2013 jumped over the lazy dog born on 10/6/10.',\n",
    "         ENHANCEMATCH | BESTMATCH)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, now let's try a spelling corrector.  Here's a list of words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Aarhus\\n'"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = open('words.txt')\n",
    "\n",
    "f.readline()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Aaron\\n',\n",
       " 'Ababa\\n',\n",
       " 'aback\\n',\n",
       " 'abaft\\n',\n",
       " 'abandon\\n',\n",
       " 'abandoned\\n',\n",
       " 'abandoning\\n',\n",
       " 'abandonment\\n',\n",
       " 'abandons\\n',\n",
       " 'abase\\n']"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = f.readlines()\n",
    "words[:10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'zoom zooms zoos Zorn Zoroaster Zoroastrian Zulu Zulus Zurich'"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words =  ' '.join( [sub('\\n', '', w) for w in words] )\n",
    "words[-60:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's make a string with some misspelled (and correct) words. It might seem counterintuitive, but we will take the misspelled words and turn them into a pattern, and use the dictionary as the target sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(?x) \\\\m (?: (abrogatting){e<=2} | (baandoned){e<=2} | (abreviat){e<=2} | (astracted){e<=2} | (absinthe){e<=2} | (abussed){e<=2} | (abus){e<=2} | (zoan){e<=2} ) \\\\M'"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "misspelt = 'abrogatting baandoned abreviat astracted absinthe abussed abus zoan'\n",
    "\n",
    "misspelt = split('\\W+', misspelt)\n",
    "\n",
    "misspelt = [r\"(\" + s + r\"){e<=2}\" for s in misspelt]\n",
    "\n",
    "misspelt = r\"(?x) \\m (?: \" + \" | \".join(misspelt) + r\" ) \\M\"\n",
    "\n",
    "misspelt\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that this time we did not use the brach reset feature.  That's because the captured empty strings are going to tell us which misspelled word was matched."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('', 'abandoned', '', '', '', '', '', ''),\n",
       " ('', '', '', '', '', '', 'abase', ''),\n",
       " ('', '', '', '', '', 'abased', '', ''),\n",
       " ('', '', '', '', '', '', 'abash', ''),\n",
       " ('', '', '', '', '', 'abashed', '', ''),\n",
       " ('', '', '', '', '', '', 'abbe', ''),\n",
       " ('', '', 'abbreviate', '', '', '', '', ''),\n",
       " ('', '', '', '', '', '', 'abed', ''),\n",
       " ('', '', '', '', '', '', 'abet', ''),\n",
       " ('', '', '', '', '', '', 'abets', ''),\n",
       " ('', '', '', '', '', '', 'able', ''),\n",
       " ('', '', '', '', '', '', 'ably', ''),\n",
       " ('', '', '', '', '', '', 'Abos', ''),\n",
       " ('', '', '', '', '', '', 'about', ''),\n",
       " ('abrogating', '', '', '', '', '', '', ''),\n",
       " ('', '', '', '', 'absentee', '', '', ''),\n",
       " ('', '', '', '', 'absinthe', '', '', ''),\n",
       " ('', '', '', 'abstracted', '', '', '', ''),\n",
       " ('', '', '', '', '', '', 'Abu', ''),\n",
       " ('', '', '', '', '', '', 'abuse', ''),\n",
       " ('', '', '', '', '', 'abused', '', ''),\n",
       " ('', '', '', '', '', 'abuses', '', ''),\n",
       " ('', '', '', '', '', '', 'abut', ''),\n",
       " ('', '', '', '', '', '', 'abuts', ''),\n",
       " ('', '', '', '', '', 'abutted', '', ''),\n",
       " ('', '', '', '', '', '', 'abyss', ''),\n",
       " ('', '', '', '', '', 'abysses', '', ''),\n",
       " ('', '', '', '', '', '', 'aces', ''),\n",
       " ('', '', '', '', '', '', 'adds', ''),\n",
       " ('', '', '', '', '', '', 'ads', ''),\n",
       " ('', '', '', '', '', '', 'ages', ''),\n",
       " ('', '', '', '', '', '', 'ague', ''),\n",
       " ('', '', '', '', '', '', 'aids', ''),\n",
       " ('', '', '', '', '', '', 'aims', ''),\n",
       " ('', '', '', '', '', '', 'airs', ''),\n",
       " ('', '', '', '', '', '', '', 'Alan'),\n",
       " ('', '', '', '', '', '', 'alas', ''),\n",
       " ('', '', '', '', '', '', 'album', ''),\n",
       " ('', '', '', '', '', '', 'albums', ''),\n",
       " ('', '', '', '', '', '', 'alms', ''),\n",
       " ('', '', '', '', '', '', 'alum', ''),\n",
       " ('', '', '', '', '', 'amassed', '', ''),\n",
       " ('', '', '', '', '', '', 'ambush', ''),\n",
       " ('', '', '', '', '', 'ambushed', '', ''),\n",
       " ('', '', '', '', '', '', 'amuse', ''),\n",
       " ('', '', '', '', '', 'amused', '', ''),\n",
       " ('', '', '', '', '', '', '', 'an'),\n",
       " ('', '', '', '', '', '', 'ants', ''),\n",
       " ('', '', '', '', '', '', 'anus', ''),\n",
       " ('', '', '', '', '', '', 'apes', ''),\n",
       " ('', '', '', '', '', '', 'aqua', ''),\n",
       " ('', '', '', '', '', '', 'arcs', ''),\n",
       " ('', '', '', '', '', '', 'arms', ''),\n",
       " ('arrogating', '', '', '', '', '', '', ''),\n",
       " ('', '', '', '', '', '', 'arts', ''),\n",
       " ('', '', '', '', '', '', 'as', ''),\n",
       " ('', '', '', '', '', '', 'asks', ''),\n",
       " ('', '', '', '', '', '', 'ass', ''),\n",
       " ('', '', '', 'attracted', '', '', '', ''),\n",
       " ('', '', '', '', '', '', 'awls', ''),\n",
       " ('', '', '', '', '', '', 'axes', ''),\n",
       " ('', '', '', '', '', '', 'axis', ''),\n",
       " ('', '', '', '', '', '', 'ayes', ''),\n",
       " ('', '', '', '', '', '', 'babes', ''),\n",
       " ('', '', '', '', '', '', 'Babul', ''),\n",
       " ('', '', '', '', '', '', '', 'ban'),\n",
       " ('', '', '', '', '', '', '', 'bean'),\n",
       " ('', '', '', '', '', '', '', 'boa'),\n",
       " ('', '', '', '', '', '', '', 'boar'),\n",
       " ('', '', '', '', '', '', '', 'boat'),\n",
       " ('', '', '', '', '', '', '', 'Bonn'),\n",
       " ('', '', '', '', '', '', '', 'boon'),\n",
       " ('', '', '', '', '', '', '', 'born'),\n",
       " ('', '', '', '', '', 'bossed', '', ''),\n",
       " ('', '', '', '', '', '', '', 'bran'),\n",
       " ('', '', '', '', '', '', 'bud', ''),\n",
       " ('', '', '', '', '', '', 'buds', ''),\n",
       " ('', '', '', '', '', '', 'bug', ''),\n",
       " ('', '', '', '', '', '', 'bugs', ''),\n",
       " ('', '', '', '', '', '', 'bum', ''),\n",
       " ('', '', '', '', '', '', 'bums', ''),\n",
       " ('', '', '', '', '', '', 'bun', ''),\n",
       " ('', '', '', '', '', '', 'buns', ''),\n",
       " ('', '', '', '', '', '', 'bus', ''),\n",
       " ('', '', '', '', '', 'bused', '', ''),\n",
       " ('', '', '', '', '', '', 'bush', ''),\n",
       " ('', '', '', '', '', 'busied', '', ''),\n",
       " ('', '', '', '', '', '', 'buss', ''),\n",
       " ('', '', '', '', '', 'bussed', '', ''),\n",
       " ('', '', '', '', '', 'busses', '', ''),\n",
       " ('', '', '', '', '', '', 'bust', ''),\n",
       " ('', '', '', '', '', 'busted', '', ''),\n",
       " ('', '', '', '', '', '', 'busy', ''),\n",
       " ('', '', '', '', '', '', 'but', ''),\n",
       " ('', '', '', '', '', '', 'buy', ''),\n",
       " ('', '', '', '', '', '', 'buys', ''),\n",
       " ('', '', '', '', '', '', 'cabs', ''),\n",
       " ('', '', '', '', '', '', '', 'can'),\n",
       " ('', '', '', '', '', '', '', 'clan'),\n",
       " ('', '', '', '', '', '', '', 'coal'),\n",
       " ('', '', '', '', '', '', '', 'coat'),\n",
       " ('', '', '', '', '', '', '', 'coax'),\n",
       " ('', '', '', '', '', '', '', 'Cohn'),\n",
       " ('', '', '', '', '', '', '', 'coin'),\n",
       " ('', '', '', '', '', '', '', 'con'),\n",
       " ('', '', '', '', '', '', '', 'coon'),\n",
       " ('', '', '', '', '', '', '', 'corn'),\n",
       " ('', '', '', '', '', '', '', 'Cowan'),\n",
       " ('', '', '', '', '', '', '', 'Dan'),\n",
       " ('', '', '', '', '', '', '', 'dean'),\n",
       " ('', '', '', '', '', '', 'deus', ''),\n",
       " ('', '', '', 'distracted', '', '', '', ''),\n",
       " ('', '', '', '', '', '', '', 'Dolan'),\n",
       " ('', '', '', '', '', '', '', 'don'),\n",
       " ('', '', '', '', '', '', '', 'down'),\n",
       " ('', '', '', '', '', '', 'ebbs', ''),\n",
       " ('', '', '', '', '', '', '', 'Egan'),\n",
       " ('', '', '', 'extracted', '', '', '', ''),\n",
       " ('', '', '', '', '', '', '', 'fan'),\n",
       " ('', '', '', '', '', '', '', 'foal'),\n",
       " ('', '', '', '', '', '', '', 'foam'),\n",
       " ('', '', '', '', '', '', '', 'Fran'),\n",
       " ('', '', '', '', '', '', '', 'Goa'),\n",
       " ('', '', '', '', '', '', '', 'goad'),\n",
       " ('', '', '', '', '', '', '', 'goal'),\n",
       " ('', '', '', '', '', '', '', 'goat'),\n",
       " ('', '', '', '', '', '', '', 'gown'),\n",
       " ('', '', '', '', '', '', '', 'groan'),\n",
       " ('', '', '', '', '', '', 'Gus', ''),\n",
       " ('', '', '', '', '', '', '', 'Han'),\n",
       " ('', '', '', '', '', '', '', 'hoar'),\n",
       " ('', '', '', '', '', '', '', 'Hokan'),\n",
       " ('', '', '', '', '', '', '', 'horn'),\n",
       " ('', '', '', '', '', '', '', 'Ian'),\n",
       " ('', '', '', '', '', '', 'ibis', ''),\n",
       " ('', '', '', '', '', '', '', 'ion'),\n",
       " ('', '', '', '', '', '', '', 'Iran'),\n",
       " ('', '', '', '', '', '', '', 'Ivan'),\n",
       " ('', '', '', '', '', '', 'jabs', ''),\n",
       " ('', '', '', '', '', '', 'Janus', ''),\n",
       " ('', '', '', '', '', '', '', 'jean'),\n",
       " ('', '', '', '', '', '', '', 'Joan'),\n",
       " ('', '', '', '', '', '', '', 'John'),\n",
       " ('', '', '', '', '', '', '', 'join'),\n",
       " ('', '', '', '', '', '', '', 'Jon'),\n",
       " ('', '', '', '', '', '', '', 'Juan'),\n",
       " ('', '', '', '', '', '', 'Kabul', ''),\n",
       " ('', '', '', '', '', '', '', 'Klan'),\n",
       " ('', '', '', '', '', '', '', 'Koran'),\n",
       " ('', '', '', '', '', '', 'labs', ''),\n",
       " ('', '', '', '', '', '', '', 'lean'),\n",
       " ('', '', '', '', '', '', '', 'load'),\n",
       " ('', '', '', '', '', '', '', 'loaf'),\n",
       " ('', '', '', '', '', '', '', 'loan'),\n",
       " ('', '', '', '', '', '', '', 'loans'),\n",
       " ('', '', '', '', '', '', '', 'Logan'),\n",
       " ('', '', '', '', '', '', '', 'loin'),\n",
       " ('', '', '', '', '', '', '', 'loon'),\n",
       " ('', '', '', '', '', '', '', 'man'),\n",
       " ('', '', '', '', '', '', '', 'mean'),\n",
       " ('', '', '', '', '', '', '', 'moan'),\n",
       " ('', '', '', '', '', '', '', 'moans'),\n",
       " ('', '', '', '', '', '', '', 'moat'),\n",
       " ('', '', '', '', '', '', '', 'Moen'),\n",
       " ('', '', '', '', '', '', '', 'Moon'),\n",
       " ('', '', '', '', '', '', '', 'Moran'),\n",
       " ('', '', '', '', '', '', '', 'morn'),\n",
       " ('', '', '', '', '', '', '', 'Nan'),\n",
       " ('', '', '', '', '', '', '', 'Noah'),\n",
       " ('', '', '', '', '', '', '', 'Nolan'),\n",
       " ('', '', '', '', '', '', '', 'non'),\n",
       " ('', '', '', '', '', '', '', 'noon'),\n",
       " ('', '', '', '', '', '', '', 'noun'),\n",
       " ('', '', '', '', '', '', '', 'oaf'),\n",
       " ('', '', '', '', '', '', '', 'oak'),\n",
       " ('', '', '', '', '', '', '', 'oar'),\n",
       " ('', '', '', '', '', '', '', 'oat'),\n",
       " ('', '', '', '', '', '', '', 'Oman'),\n",
       " ('', '', '', '', '', '', '', 'on'),\n",
       " ('', '', '', '', '', '', 'onus', ''),\n",
       " ('', '', '', '', '', '', 'opus', ''),\n",
       " ('', '', '', '', '', '', '', 'own'),\n",
       " ('', '', '', '', '', '', '', 'pan'),\n",
       " ('', '', '', '', '', '', 'Pius', ''),\n",
       " ('', '', '', '', '', '', '', 'plan'),\n",
       " ('', '', '', '', '', '', 'plus', ''),\n",
       " ('', '', '', '', '', '', 'pus', ''),\n",
       " ('', '', '', '', '', '', '', 'ran'),\n",
       " ('', '', '', 'retracted', '', '', '', ''),\n",
       " ('', '', '', '', '', '', '', 'road'),\n",
       " ('', '', '', '', '', '', '', 'roam'),\n",
       " ('', '', '', '', '', '', '', 'roar'),\n",
       " ('', '', '', '', '', '', '', 'Roman'),\n",
       " ('', '', '', '', '', '', '', 'Ron'),\n",
       " ('', '', '', '', '', '', '', 'Ryan'),\n",
       " ('', '', '', '', '', '', '', 'San'),\n",
       " ('', '', '', '', '', '', '', 'scan'),\n",
       " ('', '', '', '', '', '', '', 'Sean'),\n",
       " ('', '', '', '', '', '', '', 'Sian'),\n",
       " ('', '', '', '', '', '', '', 'Sloan'),\n",
       " ('', '', '', '', '', '', '', 'soak'),\n",
       " ('', '', '', '', '', '', '', 'soap'),\n",
       " ('', '', '', '', '', '', '', 'soar'),\n",
       " ('', '', '', '', '', '', '', 'son'),\n",
       " ('', '', '', '', '', '', '', 'soon'),\n",
       " ('', '', '', '', '', '', '', 'sown'),\n",
       " ('', '', '', '', '', '', '', 'span'),\n",
       " ('', '', '', '', '', '', '', 'Stan'),\n",
       " ('', '', '', '', '', '', 'Sus', ''),\n",
       " ('', '', '', '', '', '', '', 'swan'),\n",
       " ('', '', '', '', '', '', 'tabs', ''),\n",
       " ('', '', '', '', '', '', '', 'tan'),\n",
       " ('', '', '', '', '', '', '', 'than'),\n",
       " ('', '', '', '', '', '', 'thus', ''),\n",
       " ('', '', '', '', '', '', '', 'toad'),\n",
       " ('', '', '', '', '', '', '', 'ton'),\n",
       " ('', '', '', '', '', '', '', 'torn'),\n",
       " ('', '', '', '', '', '', '', 'town'),\n",
       " ('', '', '', '', '', '', '', 'Ulan'),\n",
       " ('', '', '', '', '', '', 'us', ''),\n",
       " ('', '', '', '', '', '', '', 'van'),\n",
       " ('', '', '', '', '', '', '', 'wan'),\n",
       " ('', '', '', '', '', '', '', 'wean'),\n",
       " ('', '', '', '', '', '', '', 'woman'),\n",
       " ('', '', '', '', '', '', '', 'won'),\n",
       " ('', '', '', '', '', '', '', 'worn'),\n",
       " ('', '', '', '', '', '', '', 'Wotan'),\n",
       " ('', '', '', '', '', '', '', 'yon'),\n",
       " ('', '', '', '', '', '', '', 'Zan'),\n",
       " ('', '', '', '', '', '', '', 'zeal'),\n",
       " ('', '', '', '', '', '', 'Zeus', ''),\n",
       " ('', '', '', '', '', '', '', 'zonal'),\n",
       " ('', '', '', '', '', '', '', 'zone'),\n",
       " ('', '', '', '', '', '', '', 'zoo'),\n",
       " ('', '', '', '', '', '', '', 'zoom'),\n",
       " ('', '', '', '', '', '', '', 'zoos'),\n",
       " ('', '', '', '', '', '', '', 'Zorn')]"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "lis = findall(misspelt,words, ENHANCEMATCH)\n",
    "\n",
    "lis\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will transpose the matrix.  Every column will contain matches for a single misspelled word.  Most of the entries will be empty strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'abrogating',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'arrogating',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  ''),\n",
       " ('abandoned',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  ''),\n",
       " ('',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'abbreviate',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  ''),\n",
       " ('',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'abstracted',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'attracted',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'distracted',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'extracted',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'retracted',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  ''),\n",
       " ('',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'absentee',\n",
       "  'absinthe',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  ''),\n",
       " ('',\n",
       "  '',\n",
       "  'abased',\n",
       "  '',\n",
       "  'abashed',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'abused',\n",
       "  'abuses',\n",
       "  '',\n",
       "  '',\n",
       "  'abutted',\n",
       "  '',\n",
       "  'abysses',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'amassed',\n",
       "  '',\n",
       "  'ambushed',\n",
       "  '',\n",
       "  'amused',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'bossed',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'bused',\n",
       "  '',\n",
       "  'busied',\n",
       "  '',\n",
       "  'bussed',\n",
       "  'busses',\n",
       "  '',\n",
       "  'busted',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  ''),\n",
       " ('',\n",
       "  'abase',\n",
       "  '',\n",
       "  'abash',\n",
       "  '',\n",
       "  'abbe',\n",
       "  '',\n",
       "  'abed',\n",
       "  'abet',\n",
       "  'abets',\n",
       "  'able',\n",
       "  'ably',\n",
       "  'Abos',\n",
       "  'about',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'Abu',\n",
       "  'abuse',\n",
       "  '',\n",
       "  '',\n",
       "  'abut',\n",
       "  'abuts',\n",
       "  '',\n",
       "  'abyss',\n",
       "  '',\n",
       "  'aces',\n",
       "  'adds',\n",
       "  'ads',\n",
       "  'ages',\n",
       "  'ague',\n",
       "  'aids',\n",
       "  'aims',\n",
       "  'airs',\n",
       "  '',\n",
       "  'alas',\n",
       "  'album',\n",
       "  'albums',\n",
       "  'alms',\n",
       "  'alum',\n",
       "  '',\n",
       "  'ambush',\n",
       "  '',\n",
       "  'amuse',\n",
       "  '',\n",
       "  '',\n",
       "  'ants',\n",
       "  'anus',\n",
       "  'apes',\n",
       "  'aqua',\n",
       "  'arcs',\n",
       "  'arms',\n",
       "  '',\n",
       "  'arts',\n",
       "  'as',\n",
       "  'asks',\n",
       "  'ass',\n",
       "  '',\n",
       "  'awls',\n",
       "  'axes',\n",
       "  'axis',\n",
       "  'ayes',\n",
       "  'babes',\n",
       "  'Babul',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'bud',\n",
       "  'buds',\n",
       "  'bug',\n",
       "  'bugs',\n",
       "  'bum',\n",
       "  'bums',\n",
       "  'bun',\n",
       "  'buns',\n",
       "  'bus',\n",
       "  '',\n",
       "  'bush',\n",
       "  '',\n",
       "  'buss',\n",
       "  '',\n",
       "  '',\n",
       "  'bust',\n",
       "  '',\n",
       "  'busy',\n",
       "  'but',\n",
       "  'buy',\n",
       "  'buys',\n",
       "  'cabs',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'deus',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'ebbs',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'Gus',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'ibis',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'jabs',\n",
       "  'Janus',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'Kabul',\n",
       "  '',\n",
       "  '',\n",
       "  'labs',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'onus',\n",
       "  'opus',\n",
       "  '',\n",
       "  '',\n",
       "  'Pius',\n",
       "  '',\n",
       "  'plus',\n",
       "  'pus',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'Sus',\n",
       "  '',\n",
       "  'tabs',\n",
       "  '',\n",
       "  '',\n",
       "  'thus',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'us',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'Zeus',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  ''),\n",
       " ('',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'Alan',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'an',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'ban',\n",
       "  'bean',\n",
       "  'boa',\n",
       "  'boar',\n",
       "  'boat',\n",
       "  'Bonn',\n",
       "  'boon',\n",
       "  'born',\n",
       "  '',\n",
       "  'bran',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  '',\n",
       "  'can',\n",
       "  'clan',\n",
       "  'coal',\n",
       "  'coat',\n",
       "  'coax',\n",
       "  'Cohn',\n",
       "  'coin',\n",
       "  'con',\n",
       "  'coon',\n",
       "  'corn',\n",
       "  'Cowan',\n",
       "  'Dan',\n",
       "  'dean',\n",
       "  '',\n",
       "  '',\n",
       "  'Dolan',\n",
       "  'don',\n",
       "  'down',\n",
       "  '',\n",
       "  'Egan',\n",
       "  '',\n",
       "  'fan',\n",
       "  'foal',\n",
       "  'foam',\n",
       "  'Fran',\n",
       "  'Goa',\n",
       "  'goad',\n",
       "  'goal',\n",
       "  'goat',\n",
       "  'gown',\n",
       "  'groan',\n",
       "  '',\n",
       "  'Han',\n",
       "  'hoar',\n",
       "  'Hokan',\n",
       "  'horn',\n",
       "  'Ian',\n",
       "  '',\n",
       "  'ion',\n",
       "  'Iran',\n",
       "  'Ivan',\n",
       "  '',\n",
       "  '',\n",
       "  'jean',\n",
       "  'Joan',\n",
       "  'John',\n",
       "  'join',\n",
       "  'Jon',\n",
       "  'Juan',\n",
       "  '',\n",
       "  'Klan',\n",
       "  'Koran',\n",
       "  '',\n",
       "  'lean',\n",
       "  'load',\n",
       "  'loaf',\n",
       "  'loan',\n",
       "  'loans',\n",
       "  'Logan',\n",
       "  'loin',\n",
       "  'loon',\n",
       "  'man',\n",
       "  'mean',\n",
       "  'moan',\n",
       "  'moans',\n",
       "  'moat',\n",
       "  'Moen',\n",
       "  'Moon',\n",
       "  'Moran',\n",
       "  'morn',\n",
       "  'Nan',\n",
       "  'Noah',\n",
       "  'Nolan',\n",
       "  'non',\n",
       "  'noon',\n",
       "  'noun',\n",
       "  'oaf',\n",
       "  'oak',\n",
       "  'oar',\n",
       "  'oat',\n",
       "  'Oman',\n",
       "  'on',\n",
       "  '',\n",
       "  '',\n",
       "  'own',\n",
       "  'pan',\n",
       "  '',\n",
       "  'plan',\n",
       "  '',\n",
       "  '',\n",
       "  'ran',\n",
       "  '',\n",
       "  'road',\n",
       "  'roam',\n",
       "  'roar',\n",
       "  'Roman',\n",
       "  'Ron',\n",
       "  'Ryan',\n",
       "  'San',\n",
       "  'scan',\n",
       "  'Sean',\n",
       "  'Sian',\n",
       "  'Sloan',\n",
       "  'soak',\n",
       "  'soap',\n",
       "  'soar',\n",
       "  'son',\n",
       "  'soon',\n",
       "  'sown',\n",
       "  'span',\n",
       "  'Stan',\n",
       "  '',\n",
       "  'swan',\n",
       "  '',\n",
       "  'tan',\n",
       "  'than',\n",
       "  '',\n",
       "  'toad',\n",
       "  'ton',\n",
       "  'torn',\n",
       "  'town',\n",
       "  'Ulan',\n",
       "  '',\n",
       "  'van',\n",
       "  'wan',\n",
       "  'wean',\n",
       "  'woman',\n",
       "  'won',\n",
       "  'worn',\n",
       "  'Wotan',\n",
       "  'yon',\n",
       "  'Zan',\n",
       "  'zeal',\n",
       "  '',\n",
       "  'zonal',\n",
       "  'zone',\n",
       "  'zoo',\n",
       "  'zoom',\n",
       "  'zoos',\n",
       "  'Zorn')]"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "z = list(zip(*lis))\n",
    "\n",
    "z\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And now we can filter out the empty strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['abrogating', 'arrogating'],\n",
       " ['abandoned'],\n",
       " ['abbreviate'],\n",
       " ['abstracted', 'attracted', 'distracted', 'extracted', 'retracted'],\n",
       " ['absentee', 'absinthe'],\n",
       " ['abased',\n",
       "  'abashed',\n",
       "  'abused',\n",
       "  'abuses',\n",
       "  'abutted',\n",
       "  'abysses',\n",
       "  'amassed',\n",
       "  'ambushed',\n",
       "  'amused',\n",
       "  'bossed',\n",
       "  'bused',\n",
       "  'busied',\n",
       "  'bussed',\n",
       "  'busses',\n",
       "  'busted'],\n",
       " ['abase',\n",
       "  'abash',\n",
       "  'abbe',\n",
       "  'abed',\n",
       "  'abet',\n",
       "  'abets',\n",
       "  'able',\n",
       "  'ably',\n",
       "  'Abos',\n",
       "  'about',\n",
       "  'Abu',\n",
       "  'abuse',\n",
       "  'abut',\n",
       "  'abuts',\n",
       "  'abyss',\n",
       "  'aces',\n",
       "  'adds',\n",
       "  'ads',\n",
       "  'ages',\n",
       "  'ague',\n",
       "  'aids',\n",
       "  'aims',\n",
       "  'airs',\n",
       "  'alas',\n",
       "  'album',\n",
       "  'albums',\n",
       "  'alms',\n",
       "  'alum',\n",
       "  'ambush',\n",
       "  'amuse',\n",
       "  'ants',\n",
       "  'anus',\n",
       "  'apes',\n",
       "  'aqua',\n",
       "  'arcs',\n",
       "  'arms',\n",
       "  'arts',\n",
       "  'as',\n",
       "  'asks',\n",
       "  'ass',\n",
       "  'awls',\n",
       "  'axes',\n",
       "  'axis',\n",
       "  'ayes',\n",
       "  'babes',\n",
       "  'Babul',\n",
       "  'bud',\n",
       "  'buds',\n",
       "  'bug',\n",
       "  'bugs',\n",
       "  'bum',\n",
       "  'bums',\n",
       "  'bun',\n",
       "  'buns',\n",
       "  'bus',\n",
       "  'bush',\n",
       "  'buss',\n",
       "  'bust',\n",
       "  'busy',\n",
       "  'but',\n",
       "  'buy',\n",
       "  'buys',\n",
       "  'cabs',\n",
       "  'deus',\n",
       "  'ebbs',\n",
       "  'Gus',\n",
       "  'ibis',\n",
       "  'jabs',\n",
       "  'Janus',\n",
       "  'Kabul',\n",
       "  'labs',\n",
       "  'onus',\n",
       "  'opus',\n",
       "  'Pius',\n",
       "  'plus',\n",
       "  'pus',\n",
       "  'Sus',\n",
       "  'tabs',\n",
       "  'thus',\n",
       "  'us',\n",
       "  'Zeus'],\n",
       " ['Alan',\n",
       "  'an',\n",
       "  'ban',\n",
       "  'bean',\n",
       "  'boa',\n",
       "  'boar',\n",
       "  'boat',\n",
       "  'Bonn',\n",
       "  'boon',\n",
       "  'born',\n",
       "  'bran',\n",
       "  'can',\n",
       "  'clan',\n",
       "  'coal',\n",
       "  'coat',\n",
       "  'coax',\n",
       "  'Cohn',\n",
       "  'coin',\n",
       "  'con',\n",
       "  'coon',\n",
       "  'corn',\n",
       "  'Cowan',\n",
       "  'Dan',\n",
       "  'dean',\n",
       "  'Dolan',\n",
       "  'don',\n",
       "  'down',\n",
       "  'Egan',\n",
       "  'fan',\n",
       "  'foal',\n",
       "  'foam',\n",
       "  'Fran',\n",
       "  'Goa',\n",
       "  'goad',\n",
       "  'goal',\n",
       "  'goat',\n",
       "  'gown',\n",
       "  'groan',\n",
       "  'Han',\n",
       "  'hoar',\n",
       "  'Hokan',\n",
       "  'horn',\n",
       "  'Ian',\n",
       "  'ion',\n",
       "  'Iran',\n",
       "  'Ivan',\n",
       "  'jean',\n",
       "  'Joan',\n",
       "  'John',\n",
       "  'join',\n",
       "  'Jon',\n",
       "  'Juan',\n",
       "  'Klan',\n",
       "  'Koran',\n",
       "  'lean',\n",
       "  'load',\n",
       "  'loaf',\n",
       "  'loan',\n",
       "  'loans',\n",
       "  'Logan',\n",
       "  'loin',\n",
       "  'loon',\n",
       "  'man',\n",
       "  'mean',\n",
       "  'moan',\n",
       "  'moans',\n",
       "  'moat',\n",
       "  'Moen',\n",
       "  'Moon',\n",
       "  'Moran',\n",
       "  'morn',\n",
       "  'Nan',\n",
       "  'Noah',\n",
       "  'Nolan',\n",
       "  'non',\n",
       "  'noon',\n",
       "  'noun',\n",
       "  'oaf',\n",
       "  'oak',\n",
       "  'oar',\n",
       "  'oat',\n",
       "  'Oman',\n",
       "  'on',\n",
       "  'own',\n",
       "  'pan',\n",
       "  'plan',\n",
       "  'ran',\n",
       "  'road',\n",
       "  'roam',\n",
       "  'roar',\n",
       "  'Roman',\n",
       "  'Ron',\n",
       "  'Ryan',\n",
       "  'San',\n",
       "  'scan',\n",
       "  'Sean',\n",
       "  'Sian',\n",
       "  'Sloan',\n",
       "  'soak',\n",
       "  'soap',\n",
       "  'soar',\n",
       "  'son',\n",
       "  'soon',\n",
       "  'sown',\n",
       "  'span',\n",
       "  'Stan',\n",
       "  'swan',\n",
       "  'tan',\n",
       "  'than',\n",
       "  'toad',\n",
       "  'ton',\n",
       "  'torn',\n",
       "  'town',\n",
       "  'Ulan',\n",
       "  'van',\n",
       "  'wan',\n",
       "  'wean',\n",
       "  'woman',\n",
       "  'won',\n",
       "  'worn',\n",
       "  'Wotan',\n",
       "  'yon',\n",
       "  'Zan',\n",
       "  'zeal',\n",
       "  'zonal',\n",
       "  'zone',\n",
       "  'zoo',\n",
       "  'zoom',\n",
       "  'zoos',\n",
       "  'Zorn']]"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "z = [ list(filter(lambda s: s!= '', L)) for L in z]\n",
    "\n",
    "z\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It's not entirely satisfactory, but it might work well for correcting the spelling of small sets of words, for example, state names."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Multiple captures\n",
    "It's now possible to obtain information on all the successful matches of a repeated capture group, not just the last one.  Use **captures** instead of **group**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['cgc', 'att', 'cgg', 'gcg']"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "dna = 'cgcgcATGcgcattcgggcgTGAcgcgcgTAGcgcgcgcgc'\n",
    "dna = dna.lower()\n",
    "\n",
    "orfpat = r'(?x) (?= ( atg  ( (?!tga|tag|taa) ... )*  (?:tga|tag|taa) ))'\n",
    "\n",
    "search(orfpat,dna).captures(2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['atgcgcattcgggcgtga']"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "search(orfpat,dna).captures(1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also capture things by name.  The string **s** is an excerpt of a long file describing a gene network.  Each line contains two gene names, and the strength of the connection between them.  In this example, we are only interested in gathering the gene names."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'geneA': ['AT1G01280', 'AT1G01480', 'AT1G01600', 'AT1G01430', 'AT1G01150'],\n",
       " 'geneB': ['AT1G01450', 'AT1G01560', 'AT1G01610', 'AT1G01630', 'AT1G01700']}"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "s = \"\"\"AT1G01280\tAT1G01450\t5.1E-3\n",
    "AT1G01480\tAT1G01560\t2.3E-2\n",
    "AT1G01600\tAT1G01610\t1.6E-2\n",
    "AT1G01430\tAT1G01630\t2.1E-2\n",
    "AT1G01150\tAT1G01700\t1.1E-2\n",
    "\"\"\"\n",
    "\n",
    "m = match(\n",
    "    r'(?x) (?: (?P<geneA>\\w+) \\s+ (?P<geneB>\\w+) \\s+ \\S+ \\n )*',\n",
    "    s)\n",
    "\n",
    "m.capturesdict()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can even reuse a name;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'gene': ['AT1G01280',\n",
       "  'AT1G01450',\n",
       "  'AT1G01480',\n",
       "  'AT1G01560',\n",
       "  'AT1G01600',\n",
       "  'AT1G01610',\n",
       "  'AT1G01430',\n",
       "  'AT1G01630',\n",
       "  'AT1G01150',\n",
       "  'AT1G01700']}"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "m = match(\n",
    "    r'(?x) (?: (?P<gene>\\w+) \\s+ (?P<gene>\\w+) \\s+ \\S+ \\n )*',\n",
    "    s)\n",
    "\n",
    "m.capturesdict()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['AT1G01150',\n",
       " 'AT1G01280',\n",
       " 'AT1G01430',\n",
       " 'AT1G01450',\n",
       " 'AT1G01480',\n",
       " 'AT1G01560',\n",
       " 'AT1G01600',\n",
       " 'AT1G01610',\n",
       " 'AT1G01630',\n",
       " 'AT1G01700']"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(set(m.capturesdict()['gene']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Reverse searching\n",
    "\n",
    "Searches can now work backwards:\n",
    "\n",
    "Note: the result of a reverse search is not necessarily the reverse of a forward search:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['de', 'bc']"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "findall(r\"(?r)..\", \"abcde\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Who cares?  I thought of an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1 mile = 1,760 yards = 5,280 ft = 63,360 in = 1,609,344 mm = ,160,934.4 cm, more or less.  Pi = 3.14,159'"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sub(r'(?rx) (\\d\\d\\d)',\n",
    "    r',\\1',\n",
    "    '1 mile = 1760 yards = 5280 ft = 63360 in = 1609344 mm = 160934.4 cm, more or less.  Pi = 3.14159')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1 mile = 1,760 yards = 5,280 ft = 63,360 in = 1,609,344 mm = 160,934.4 cm, more or less.  Pi = 3.14,159'"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sub(r'(?rx)  (?<=\\d) (\\d\\d\\d)',\n",
    "    r',\\1',\n",
    "    '1 mile = 1760 yards = 5280 ft = 63360 in = 1609344 mm = 160934.4 cm, more or less.  Pi = 3.14159')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1 mile = 1,760 yards = 5,280 ft = 63,360 in = 1,609,344 mm = 160,934.4 cm, more or less.  Pi = 3.14159'"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sub(r'(?rx)  (?<! [.] \\d*) (?<=\\d) (\\d\\d\\d)',\n",
    "    r',\\1',\n",
    "    '1 mile = 1760 yards = 5280 ft = 63360 in = 1609344 mm = 160934.4 cm, more or less.  Pi = 3.14159')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### POSIX Matching (Leftmost Longest)\n",
    "\n",
    "The default matching method for alternations is to match the first alternative that will match. The POSIX standard is to find the leftmost longest match. This can be turned on using the POSIX flag **(?p)**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<regex.Match object; span=(4, 7), match='dog'>,\n",
       " <regex.Match object; span=(27, 30), match='dog'>]"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "list(finditer( r'(dog|doge|doggerel)', 'The doge wrote nothing but doggerel.'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<regex.Match object; span=(4, 8), match='doge'>,\n",
       " <regex.Match object; span=(27, 35), match='doggerel'>]"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "list(finditer( r'(?p)(dog|doge|doggerel)', 'The doge wrote nothing but doggerel.'))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### **fullmatch**\n",
    "The pattern must match the entire string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<regex.Match object; span=(0, 8), match='The doge'>"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "match(r'The doge', 'The doge wrote nothing but doggerel.')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "fullmatch(r'The doge', 'The doge wrote nothing but doggerel.')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nope, that one didn't match."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Partial matching\n",
    "Can the target string be extended to match the pattern?  The optional **partial** argument to **match**, **search**, and **fullmatch** can answer this question. This could be useful if you are validating input from the terminal, for example."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one is true, because the target can be extended to 'The doge wrote nothing but doggerel.' to match the pattern.  But, if you think about it, you will see that this one is true for any target string.  (It can be extended with 'dogdog'.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<regex.Match object; span=(0, 22), match='The doge wrote nothing', partial=True>"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "fullmatch(r'.*dog.*dog.*', 'The doge wrote nothing', partial=True)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one is more interesting: Can the string be extended to be a Social Security Number?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<regex.Match object; span=(0, 8), match='999-89-7', partial=True>"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "fullmatch(r'\\d\\d\\d-\\d\\d-\\d\\d\\d\\d',  \"999-89-7\", partial=True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<regex.Match object; span=(0, 8), match='999-89-7', partial=True>"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "match(r'\\d\\d\\d-\\d\\d-\\d\\d\\d\\d',  \"999-89-7\", partial=True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\n",
    "fullmatch(r'\\d\\d\\d-\\d\\d-\\d\\d\\d\\d',  \"My SSN is 999-89-7\", partial=True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "match(r'\\d\\d\\d-\\d\\d-\\d\\d\\d\\d',  \"My SSN is 999-89-7\", partial=True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<regex.Match object; span=(10, 18), match='999-89-7', partial=True>"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "search(r'\\d\\d\\d-\\d\\d-\\d\\d\\d\\d',  \"My SSN is 999-89-7\", partial=True)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that this one is a complete match, so the **partial** field is missing from the match object:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<regex.Match object; span=(10, 21), match='999-89-7654'>"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "search(r'\\d\\d\\d-\\d\\d-\\d\\d\\d\\d',  \"My SSN is 999-89-7654, but don't tell.\", partial=True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<regex.Match object; span=(33, 36), match='ll.', partial=True>"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "search(r'\\d\\d\\d-\\d\\d-\\d\\d\\d\\d',  \"My SSN is 999-89-76, but don't tell.\", partial=True)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Some functional programming fun"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'spam spam spam spam spam spam spam spam eggs and spam'"
      ]
     },
     "execution_count": 115,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "def twice(f):\n",
    "    return lambda x: f(f(x))\n",
    "\n",
    "def prepender(s):\n",
    "    return lambda t: s + t\n",
    "\n",
    "twice(twice)(twice(prepender('spam ')))('eggs and spam')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "53"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "twice(twice)(twice(prepender(len('spam '))))(len('eggs and spam'))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mark's puzzle\n",
    "Which character is most frequent in a string?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('2', 5)"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def most(s, care_about=r'\\w'):\n",
    "    t=''.join(sorted(s))\n",
    "    p = r'((' + care_about + r')\\2*)'\n",
    "    L = [ m.group(1) for m in finditer(p, t) ]\n",
    "    m = max(L, key=len)\n",
    "    return (m[0], len(m))\n",
    "\n",
    "most('123462232340997092')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('3', 3)"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "most('123462232340997092', care_about='[13579]')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('a', 10)"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "most(twice(twice)(twice(prepender('spam ')))('eggs and spam'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('s', 10)"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "most(twice(twice)(twice(prepender('spam ')))('eggs and spam'), r'[^aeiou\\s]')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}