7.Parsing_with_CFG_and_PCFG.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "nbpresent": {
     "id": "70894730-f4d6-4a45-8e3d-1dc5c282bca3"
    }
   },
   "source": [
    "<h1 align=\"center\">Parsing with Context Free Grammars(CFG) and PCFG (Probabilistic CFG)</h1> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "0c213053-41a5-475b-8311-ac785dca697f"
    }
   },
   "source": [
    "<h3>1. Context Free Grammars</h3>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "f15f2986-d737-40ba-ad12-dd255069807c"
    }
   },
   "source": [
    "- Let's consider a simple grammar. By convention, the left-hand-side of the first production is the start-symbol of the grammar, typically S, and all well-formed trees must have this symbol as their root label.\n",
    "-  In NLTK, context-free grammars are defined in the nltk.grammar module.[4]\n",
    "- Steps\n",
    "    - Import ntk\n",
    "    - Create grammar\n",
    "    - Parse the string\n",
    "    - Print the parse tree\n",
    "- Following is an example taken from NLTK-book"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2016-10-24T14:08:33.632141",
     "start_time": "2016-10-24T14:08:33.510328"
    },
    "collapsed": false,
    "nbpresent": {
     "id": "1b38753f-f5a8-427d-a3da-d613c19576fc"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 'Parse trees : ')\n",
      "(S (NP Mary) (VP (V saw) (NP Bob)))\n"
     ]
    }
   ],
   "source": [
    "#code snippet taken from http://www.nltk.org/book/\n",
    "\n",
    "import nltk\n",
    "import io\n",
    "import IPython\n",
    "import PIL.Image\n",
    "from nltk import Tree\n",
    "from nltk.draw.util import CanvasFrame\n",
    "from nltk.draw import TreeWidget\n",
    "from IPython.display import Image\n",
    "from IPython.display import display\n",
    "from IPython.display import HTML\n",
    "\n",
    "#specify the grammar\n",
    "grammar1 = nltk.CFG.fromstring(\"\"\"\n",
    "S -> NP VP\n",
    "VP -> V NP | V NP PP\n",
    "PP -> P NP\n",
    "V -> \"saw\" | \"ate\" | \"walked\"\n",
    "NP -> \"John\" | \"Mary\" | \"Bob\" | Det N | Det N PP\n",
    "Det -> \"a\" | \"an\" | \"the\" | \"my\"\n",
    "N -> \"man\" | \"dog\" | \"cat\" | \"telescope\" | \"park\"\n",
    "P -> \"in\" | \"on\" | \"by\" | \"with\"\n",
    "\"\"\")\n",
    "sent = \"Mary saw Bob\".split()\n",
    "parser = nltk.ChartParser(grammar1) #parse it using chart parser\n",
    "\n",
    "#showing parsed trees\n",
    "\n",
    "num_of_parse = len(list(parser.parse(sent)))\n",
    "\n",
    "print (num_of_parse,\"Parse trees : \")\n",
    "\n",
    "c =0\n",
    "for tree in parser.parse(sent):\n",
    "    print(tree)\n",
    "    #tree.draw()     #Try out this too"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "85e969e1-b3ef-4de3-977e-d9afc42b7011"
    }
   },
   "source": [
    "<h3>Another example with address parsing</h3>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "1dad07fe-8456-4bc0-bc11-a6efad0b7b91"
    }
   },
   "source": [
    "- We want to parse home addresses using CFG. Address consists of 2 lines of addresses containing house number, street/road/avenue,floor number, region (north,east,south,west), and other details.\n",
    "- Here we have used a regular expression-tagger to tag the sequence of words in the address lines with tags such as 'NUM', 'STREET', etc.\n",
    "- For example,\n",
    "                'suite' and 'Suite' are tagged to 'SUITE'\n",
    "                'floor' and 'Floor' are tagged to 'FLOOR'\n",
    "                 sequence of number is tagged as 'NUM'\n",
    "- Note: You should have downloaded 'punct' package from nltk downloader. If not then type on python command line\n",
    "                import nltk\n",
    "                nltk.download()\n",
    "  and select 'punct' package form dialog box and download it.\n",
    "- A CFG can be formed as follows, for the address \"525 N. Main Street , Suite 28\" as input:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2016-10-24T14:19:24.645573",
     "start_time": "2016-10-24T14:19:24.444118"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('Parse trees : ', 1)\n",
      "(S\n",
      "  (ADD1 (N NUM) (DIR N.) (ST STREET (ST STREET (ST STREET))))\n",
      "  (ADD2 (SUI (SU Suite) (N NUM))))\n"
     ]
    }
   ],
   "source": [
    "import pprint\n",
    "\n",
    "#specify the grammar\n",
    "grammar1 = nltk.CFG.fromstring(\"\"\"\n",
    "S -> ADD1 ADD2 | ADD1\n",
    "ADD1 -> N DIR ST | ST | N DIR\n",
    "ADD2 -> FL ST | FL | SUI | SUI FL | SUI FL ST | FL SUI \n",
    "N -> 'NUM'\n",
    "DIR -> 'N.' | 'S.' | 'W.'|'E.'|'North'|'South'|'West'|'East'|'N'|'S'|'E'|'W'\n",
    "ST -> 'STREET' ST | 'STREET'\n",
    "SUI -> SU N\n",
    "FL -> N SS F | N F\n",
    "F -> 'FLOOR'\n",
    "SU -> 'SUITE' | 'Suite'\n",
    "SS -> 'SUP'\n",
    "\"\"\")\n",
    "\n",
    "#specify the regular expression pattern pattern\n",
    "pattern = [(r'[0-9]+','NUM'),(r'^(?!(N|W|E|S|N.|S.|W.|E.|West|North|East|,\\\n",
    "           |South|Suite|Floor|floor|nd|st|th)$).*','STREET'),\n",
    "           (r'(Suite,suite)+','SUITE'),(r'(nd|st|th)','SUP'),\n",
    "           (r'(floor|Floor)','FLOOR'),(r',','COM')]\n",
    "tagger = nltk.RegexpTagger(pattern) #regular expression tagger from nltk\n",
    "\n",
    "t=[]\n",
    "#print(tagger.tag(nltk.word_tokenize('525 N. Main Street , Suite 28')))\n",
    "\n",
    "#tag the address with the previous regular expression pattern\n",
    "for (y,x) in (tagger.tag(nltk.word_tokenize('525 N. Main Street , Suite 28'))):\n",
    "    if x is not None and x != 'COM':\n",
    "        t.append(x)\n",
    "    elif x is None :\n",
    "        t.append(y)\n",
    "#print (t)\n",
    "parser = nltk.ChartParser(grammar1)\n",
    "\n",
    "#showing parsed trees\n",
    "\n",
    "num_of_parse = len(list(parser.parse(t)))\n",
    "\n",
    "print (\"Parse trees : \", num_of_parse)\n",
    "c =0\n",
    "for tree in parser.parse(t):\n",
    "    print(tree)\n",
    "    #tree.draw()     #Try out this too    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "556fa1de-6b47-45b2-aba2-4e5ef374e054"
    }
   },
   "source": [
    "- Parsing is performed using this tagged sequence only."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "ea9422e8-9a34-4071-a25f-fc41f9f5b4fa"
    }
   },
   "source": [
    "<h3>2.1 A modified cfg</h3>\n",
    "<pre>\n",
    "Following grammar is the extension of the above grammer having fields: name, address_line_1, address_line_2,  city, state, country and zip.\n",
    "Regex Tagger is also updated accordingly.\n",
    "Out of 13078 addresses, 7541 are being parsed properly.\n",
    "Strings like \"<b>773-702-7034 Carl Sandburg Middle School , 855 W. Hawley Street , LOCATED IN THE GYM ,Mundelein, IL , us , 60060</b>\" is not parsed by the following grammar because \"<b>773-702-7034</b>\" format is not taken in number tag.\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# %%time\n",
    "grammar1 = nltk.CFG.fromstring(\"\"\"\n",
    "S ->  N NM ADD1 ADD2 CT STATE COUNTRY Z |NM ADD1 ADD2 CT STATE COUNTRY Z| NM ADD1 CT STATE COUNTRY Z\n",
    "NM -> 'NAME' NM | 'NAME' 'NUM' NM | 'NAME' 'NUM' | 'NAME'\n",
    "ADD1 -> N DIR ST | ST | N DIR | N DIR AVE | AVE | N AVE | N ST |AVE N| ST N | AVE DIR |ST DIR | AVE DIR AVE| AVE DIR AVE |ST DIR ST |AVE N AVE | ST N ST | N DIR N SS AVE |N DIR N SS ST | N DIR N SS AVE |N DIR N SS ST |  DIR AVE |DIR ST\n",
    "ADD2 -> FL ST1 | FL | SUI | SUI FL | SUI FL ST1 | FL SUI | DIR ST1 |N DIR ST1 | ST1 | N DIR | N ST1 | N SS ST1 | ST1 N |ST1 DIR ST1 | 'NUM'\n",
    "N -> 'NUM' \n",
    "CT -> 'CITY' | 'CITY' 'CITY' | 'CITY' 'CITY' 'CITY'\n",
    "STATE -> 'STATE' | STATE 'STATE'\n",
    "Z -> 'ZIP'\n",
    "COUNTRY -> 'COUNTRY'| COUNTRY 'COUNTRY'|'us'|'US'\n",
    "DIR -> 'N.' | 'S.' | 'W.'|'E.'|'North'|'South'|'West'|'East'|'N'|'S'|'E'|'W'|'w.'|'s.'|'n.'|'e.'\n",
    "ST -> 'STREET1' ST | 'STREET1' 'NUM' | 'STREET1' 'NUM' ST| 'STREET1'\n",
    "AVE -> 'AVENUE' AVE | 'AVENUE'\n",
    "ST1 -> 'STREET2' ST1 | 'STREET2'\n",
    "SUI -> SU N\n",
    "FL -> N SS F | N F | OTH F | F N SS\n",
    "OTH -> 'Top' | 'Main'\n",
    "F -> 'FLOOR'\n",
    "SU -> 'SUITE'\n",
    "SS -> 'SUP'\n",
    "\"\"\")\n",
    "\n",
    "pattern = [(r'^(?!(?:^[0-9][0-9][0-9][0-9][0-9]+$)$)\\d+','NUM'),(r'^(?!(?:^[0-9][0-9][0-9][0-9][0-9]+$)|(\\(|\\)|us|US|N\\.|W\\.|E\\.|S\\.|N|W|E|S|n\\.|w\\.|e\\.|s\\.|Ave|Ave\\.|ave|avenue|Avenue|AVENUE|ave\\.|,|Suite|suite|SUITE|Floor|Fl.|Fl|floor|nd|th)$).*','STREET1'),(r'(Suite|suite|SUITE)','SUITE'),(r'(nd|th)','SUP'),(r'(floor|Fl.|Fl|Floor)','FLOOR'),(r',','COM'),(r'\\(|\\)','BRAC'),(r'Ave|Ave.|ave|avenue|Avenue|AVENUE|ave.','AVENUE'),(r'^[0-9][0-9][0-9][0-9][0-9]+$','ZIP')]\n",
    "\n",
    "f = io.open(\"Data/ParsingWithCFGandPCFG/all_addr.csv\",encoding=\"utf-8\")\n",
    "\n",
    "count = 0\n",
    "total_count = 0\n",
    "for line in f:\n",
    "    adr1 = line\n",
    "    #print(adr1)\n",
    "    tagger = nltk.RegexpTagger(pattern)\n",
    "    #adr1 = 'Miguel , private location , details to be emailed to those attending , Evanston , IL , us , 60202'\n",
    "    t=[]\n",
    "    f=0\n",
    "    p=0\n",
    "    start=0\n",
    "    end=0\n",
    "    for (y,x) in (tagger.tag(nltk.word_tokenize(adr1))):\n",
    "        if x is not None and x != 'COM' and x != 'BRAC' and f==0:\t\n",
    "            if x is 'STREET1' :\n",
    "                x='NAME'\n",
    "            t.append(x)\n",
    "        elif x is not None and x != 'COM' and x != 'BRAC' and f==1:\n",
    "            t.append(x)\n",
    "        elif x is not None and x != 'COM' and x != 'BRAC' and f==2:\t\n",
    "            if x is 'STREET1' :\n",
    "                x='STREET2'\n",
    "            t.append(x)\n",
    "        elif x is not None and x != 'COM' and x != 'BRAC' and f==3:\t\n",
    "            if x is 'STREET1' :\n",
    "                x='CITY'\n",
    "            t.append(x)\n",
    "        elif x is not None and x != 'COM' and x != 'BRAC' and f==4:\t\n",
    "            if x is 'STREET1' :\n",
    "                x='STATE'\n",
    "            t.append(x)\n",
    "        elif x is not None and x != 'COM' and x != 'BRAC' and f==5:\t\n",
    "            if x is 'STREET1' :\n",
    "                x='COUNTRY'\n",
    "            t.append(x)     \n",
    "        elif x is not None and x != 'COM' and x != 'BRAC' and f==6:\t\n",
    "            t.append(x)\t\t\n",
    "        elif x == 'COM' :\n",
    "            f+=1\n",
    "        elif x is None  :\n",
    "            t.append(y)\n",
    "    if 'AVENUE' in t :\n",
    "        p=1\n",
    "    if p==1:\n",
    "        for index, item in enumerate(t):\n",
    "            if 'STREET1' in item :\n",
    "                start=index\n",
    "                break\n",
    "        for index, item in enumerate(t):\n",
    "            if 'AVENUE' in item :\n",
    "                end=index\n",
    "                break\n",
    "        for i in range(start,end) :\n",
    "            t[i]='AVENUE'\n",
    "\n",
    "\n",
    "\n",
    "    #print(t)\n",
    "\n",
    "    parser = nltk.ChartParser(grammar1)\n",
    "    num_of_parse = len(list(parser.parse(t)))\n",
    "\n",
    "    #print(num_of_parse)\n",
    "\n",
    "    if num_of_parse>0:\n",
    "        count += 1\n",
    "    total_count += 1\n",
    "\n",
    "    #for tree in parser.parse(t):\n",
    "        #tree.draw()\n",
    "\n",
    "print \"Parsed : \",count,\"/\",total_count\n",
    "print \"Accuracy : %.3f\"%((float(count)*100.0)/float(total_count))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h3>Ambiguity in Grammar</h3>\n",
    "<pre>\n",
    "There are several addresses which lead to more than one parse tree, after being parsed by the above grammar.\n",
    "Here is an example of an ambiguity taking \"<b>Harold Washington Library Center , 400 S. State Street , Cindy Pritzker Auditorium , Chicago , IL , us , 60605</b>\" as input.\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2016-10-24T14:34:58.472561",
     "start_time": "2016-10-24T14:34:57.580848"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2, 'Parse trees : ')\n",
      "(S\n",
      "  (NM NAME (NM NAME (NM NAME (NM NAME))))\n",
      "  (ADD1 (N NUM) (DIR S.) (ST STREET1 (ST STREET1)))\n",
      "  (ADD2 (ST1 STREET2 (ST1 STREET2 (ST1 STREET2))))\n",
      "  (CT CITY)\n",
      "  (STATE STATE)\n",
      "  (COUNTRY us)\n",
      "  (Z ZIP))\n",
      "(S\n",
      "  (NM NAME (NM NAME (NM NAME (NM NAME NUM))))\n",
      "  (ADD1 (DIR S.) (ST STREET1 (ST STREET1)))\n",
      "  (ADD2 (ST1 STREET2 (ST1 STREET2 (ST1 STREET2))))\n",
      "  (CT CITY)\n",
      "  (STATE STATE)\n",
      "  (COUNTRY us)\n",
      "  (Z ZIP))\n"
     ]
    }
   ],
   "source": [
    "adr1 = 'Harold Washington Library Center , 400 S. State Street , Cindy Pritzker Auditorium , Chicago , IL , us , 60605'\n",
    "grammar1 = nltk.CFG.fromstring(\"\"\"\n",
    "S ->  N NM ADD1 ADD2 CT STATE COUNTRY Z |NM ADD1 ADD2 CT STATE COUNTRY Z| NM ADD1 CT STATE COUNTRY Z\n",
    "NM -> 'NAME' NM | 'NAME' 'NUM' NM | 'NAME' 'NUM' | 'NAME'\n",
    "ADD1 -> N DIR ST | ST | N DIR | N DIR AVE | AVE | N AVE | N ST |AVE N| ST N | AVE DIR |ST DIR | AVE DIR AVE| AVE DIR AVE |ST DIR ST |AVE N AVE | ST N ST | N DIR N SS AVE |N DIR N SS ST | N DIR N SS AVE |N DIR N SS ST |  DIR AVE |DIR ST\n",
    "ADD2 -> FL ST1 | FL | SUI | SUI FL | SUI FL ST1 | FL SUI | DIR ST1 |N DIR ST1 | ST1 | N DIR | N ST1 | N SS ST1 | ST1 N |ST1 DIR ST1 | 'NUM'\n",
    "N -> 'NUM' \n",
    "CT -> 'CITY' | 'CITY' 'CITY' | 'CITY' 'CITY' 'CITY'\n",
    "STATE -> 'STATE' | STATE 'STATE'\n",
    "Z -> 'ZIP'\n",
    "COUNTRY -> 'COUNTRY'| COUNTRY 'COUNTRY'|'us'|'US'\n",
    "DIR -> 'N.' | 'S.' | 'W.'|'E.'|'North'|'South'|'West'|'East'|'N'|'S'|'E'|'W'|'w.'|'s.'|'n.'|'e.'\n",
    "ST -> 'STREET1' ST | 'STREET1' 'NUM' | 'STREET1' 'NUM' ST| 'STREET1'\n",
    "AVE -> 'AVENUE' AVE | 'AVENUE'\n",
    "ST1 -> 'STREET2' ST1 | 'STREET2'\n",
    "SUI -> SU N\n",
    "FL -> N SS F | N F | OTH F | F N SS\n",
    "OTH -> 'Top' | 'Main'\n",
    "F -> 'FLOOR'\n",
    "SU -> 'SUITE'\n",
    "SS -> 'SUP'\n",
    "\"\"\")\n",
    "\t\n",
    "pattern = [(r'^(?!(?:^[0-9][0-9][0-9][0-9][0-9]+$)$)\\d+','NUM'),(r'^(?!(?:^[0-9][0-9][0-9][0-9][0-9]+$)|(\\(|\\)|us|US|N\\.|W\\.|E\\.|S\\.|N|W|E|S|n\\.|w\\.|e\\.|s\\.|Ave|Ave\\.|ave|avenue|Avenue|AVENUE|ave\\.|,|Suite|suite|SUITE|Floor|Fl.|Fl|floor|nd|th)$).*','STREET1'),(r'(Suite|suite|SUITE)','SUITE'),(r'(nd|th)','SUP'),(r'(floor|Fl.|Fl|Floor)','FLOOR'),(r',','COM'),(r'\\(|\\)','BRAC'),(r'Ave|Ave.|ave|avenue|Avenue|AVENUE|ave.','AVENUE'),(r'^[0-9][0-9][0-9][0-9][0-9]+$','ZIP')]\n",
    "tagger = nltk.RegexpTagger(pattern)\n",
    "\n",
    "t=[]\n",
    "f=0\n",
    "p=0\n",
    "start=0\n",
    "end=0\n",
    "for (y,x) in (tagger.tag(nltk.word_tokenize(adr1))):\n",
    "    if x is not None and x != 'COM' and x != 'BRAC' and f==0:\t\n",
    "        if x is 'STREET1' :\n",
    "            x='NAME'\n",
    "        t.append(x)\n",
    "    elif x is not None and x != 'COM' and x != 'BRAC' and f==1:\n",
    "        t.append(x)\n",
    "    elif x is not None and x != 'COM' and x != 'BRAC' and f==2:\t\n",
    "        if x is 'STREET1' :\n",
    "            x='STREET2'\n",
    "        t.append(x)\n",
    "    elif x is not None and x != 'COM' and x != 'BRAC' and f==3:\t\n",
    "        if x is 'STREET1' :\n",
    "            x='CITY'\n",
    "        t.append(x)\n",
    "    elif x is not None and x != 'COM' and x != 'BRAC' and f==4:\t\n",
    "        if x is 'STREET1' :\n",
    "            x='STATE'\n",
    "        t.append(x)\n",
    "    elif x is not None and x != 'COM' and x != 'BRAC' and f==5:\t\n",
    "        if x is 'STREET1' :\n",
    "            x='COUNTRY'\n",
    "        t.append(x)     \n",
    "    elif x is not None and x != 'COM' and x != 'BRAC' and f==6:\t\n",
    "        t.append(x)\t\t\n",
    "    elif x == 'COM' :\n",
    "        f+=1\n",
    "    elif x is None  :\n",
    "        t.append(y)\n",
    "if 'AVENUE' in t :\n",
    "    p=1\n",
    "if p==1:\n",
    "    for index, item in enumerate(t):\n",
    "        if 'STREET1' in item :\n",
    "            start=index\n",
    "            break\n",
    "    for index, item in enumerate(t):\n",
    "        if 'AVENUE' in item :\n",
    "            end=index\n",
    "            break\n",
    "    for i in range(start,end) :\n",
    "        t[i]='AVENUE'\n",
    "\n",
    "parser = nltk.ChartParser(grammar1) #parsing using chart parser\n",
    "\n",
    "\n",
    "num_of_parse = len(list(parser.parse(t)))\n",
    "\n",
    "#printing parse trees\n",
    "print(num_of_parse,\"Parse trees : \")\n",
    "c =0\n",
    "for tree in parser.parse(t):\n",
    "    print tree\n",
    "    #tree.draw()     #Try out this too"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "15d55141-ecc5-493d-82c1-7d6381d45518"
    }
   },
   "source": [
    "<h3>3. CYK algorithm</h3>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "0807e5aa-1601-4cb1-8831-fc8e3bf4d156"
    }
   },
   "source": [
    "- CYK is a parsing algorithm for context-free grammars which employs bottom-up parsing and dynamic programming.\n",
    "- The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be transformed to a CNF grammar expressing the same language.[3]\n",
    "- In formal language theory, a grammar is said to be in Chomsky Norma Form(CNF) if all of its productions are of the form:\n",
    "    - A -> BC\n",
    "    - A -> a\n",
    "    - S -> null\n",
    "    where, where A, B, and C are nonterminal symbols, a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε denotes the empty string.\n",
    "- The importance of the CYK algorithm stems from its high efficiency in certain situations. The worst case running time of CYK is O((n^3)*|G|), where n is the length of the parsed string and |G| is the size of the CNF grammar G (Hopcroft & Ullman 1979, p. 140). This makes it one of the most efficient parsing algorithms in terms of worst-case asymptotic complexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "f407e8d7-d830-477d-9c43-2343db128138"
    }
   },
   "source": [
    "<a href=\"http://www.tutorialspoint.com/automata_theory/chomsky_normal_form.htm\">Useful resource on CNF conversion</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "4c4270ad-cc10-4438-a67f-d5a5dd4032f3"
    }
   },
   "source": [
    "<h3>3.1 Example</h3>\n",
    "<p>The example shows implementation of a CYK algorithm.<br>\n",
    "Parsing is performed on simple string: \"the kids opened the box on the floor\".<br>\n",
    "Parsing is also peformed using Prbabilistic CFG in which each prouction is assigned a probability. So in case of unambiguous grammars in which more then one productions with same darivations are possible, probability is given to the highest production.[2]</p>\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "c67923a2-c477-4448-9b5b-3d105ddde603"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[Det -> 'the' [1.0]]\n",
      "[N -> 'kids' [0.4], X -> 'kids' [1.0]]\n",
      "[V -> 'opened' [1.0]]\n",
      "[Det -> 'the' [1.0]]\n",
      "[N -> 'box' [0.3]]\n",
      "[P -> 'on' [1.0]]\n",
      "[Det -> 'the' [1.0]]\n",
      "[N -> 'floor' [0.3]]\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table><tr><td>TABLE</td><td>the[1]</td><td>kids[2]</td><td>opened[3]</td><td>the[4]</td><td>box[5]</td><td>on[6]</td><td>the[7]</td><td>floor[8]</td></tr><tr><td>0</td><td>Det [1.0 ]</br></td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>1</td><td>-</td><td>N [0.4 ]</br>X [1.0 ]</br></td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>2</td><td>-</td><td>-</td><td>V [1.0 ]</br></td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>3</td><td>-</td><td>-</td><td>-</td><td>Det [1.0 ]</br></td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>4</td><td>-</td><td>-</td><td>-</td><td>-</td><td>N [0.3 ]</br></td><td>-</td><td>-</td><td>-</td></tr><tr><td>5</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>P [1.0 ]</br></td><td>-</td><td>-</td></tr><tr><td>6</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>Det [1.0 ]</br></td><td>-</td></tr><tr><td>7</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>N [0.3 ]</br></td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# code snippet taken from http://www.cs.pomona.edu/classes/cs181NLP/lectures/Lec11/Lec11.pdf\n",
    "\n",
    "\n",
    "tokens = [\"the\", \"kids\", \"opened\", \"the\", \"box\", \"on\", \"the\", \"floor\"]\n",
    "# grammar is in CNF form for CYK algorithm\n",
    "grammar = nltk.PCFG.fromstring(\"\"\"\n",
    "S -> NP VP [1.0]\n",
    "PP -> P NP [1.0]\n",
    "NP -> Det N [0.4] | NP PP [0.6]\n",
    "VP -> V NP [0.5] | VP PP [0.5]\n",
    "Det -> 'the' [1.0]\n",
    "N -> 'kids' [0.4] | 'box' [0.3] | 'floor' [0.3]\n",
    "V -> 'opened' [1.0]\n",
    "P -> 'on' [1.0]\n",
    "X -> 'kids' [1.0]\n",
    "\"\"\")\n",
    "                               \n",
    "def init_wfst(tokens, grammar):\n",
    "    numtokens = len(tokens)    \n",
    "    \n",
    "    wfst = [[\"-\" for i in range(numtokens+1)] for j in range(numtokens+1)]\n",
    "    \n",
    "    # fill in diagonal\n",
    "    for i in range(numtokens):\n",
    "        productions = grammar.productions(rhs=tokens[i])\n",
    "        print(productions)\n",
    "        temp = \"\"\n",
    "        for prod in productions:\n",
    "            temp += str(prod.lhs()) + ' ['+ str(prod.prob()) +' ]</br>'\n",
    "        wfst[i][i+1] = temp\n",
    "    \n",
    "    return wfst\n",
    "\n",
    "def complete_wfst(wfst, tokens, trace=False):\n",
    "    index = {}\n",
    "    for prod in grammar.productions(): #make reverse lookup\n",
    "        index[prod.rhs()] = prod.lhs()\n",
    "    numtokens = len(tokens)\n",
    "    for span in range(2, numtokens+1):\n",
    "        for start in range(numtokens+1-span): #go down diagonal\n",
    "            end = start + span\n",
    "            for mid in range(start+1, end):\n",
    "                nt1, nt2 = wfst[start][mid], wfst[mid][end]\n",
    "                if (nt1,nt2) in index:\n",
    "                    if trace:\n",
    "                        '''\n",
    "                        format : \n",
    "                            [ i ] NT_RHS1 [ k ] NT_RHS2 [ j ] ==> [ PROD_NUM ] NT_LHS [ j ]\n",
    "                        \n",
    "                            It means\n",
    "                                NT_RHS1 can derive string (i,k]\n",
    "                                NT_RHS2 can derive string (k,j]\n",
    "                                \n",
    "                                Using NT_RHS1 and NT_RHS2 procuction number PROD_NUM can derive NT_LHS and string (i,j] which is of the form\n",
    "                                    NT_LHS -> NT_RHS1 NT_RHS2\n",
    "                            \n",
    "                        '''\n",
    "                        print( \"[%s] %3s [%s] %3s [%s] ==> [%s] %3s [%s]\" %(start, nt1, mid, nt2, end, start, index[(nt1,nt2)], end))\n",
    "                    wfst[start][end] = index[(nt1,nt2)]\n",
    "    return wfst \n",
    "\n",
    "def display(wfst, tokens):\n",
    "    print '\\nWFST\\t' , '\\t'.join([(\"%-4d\" % i) for i in range(1, len(wfst))])\n",
    "    for i in range(len(wfst)-1):\n",
    "        print \"%d\\t\" % i,\n",
    "        for j in range(1, len(wfst)):\n",
    "            print \"%-4s\\t\" % wfst[i][j],\n",
    "        print \"\\n\"\n",
    "\n",
    "wfst = init_wfst(tokens, grammar)\n",
    "wfst = complete_wfst(wfst, tokens, trace=False)\n",
    "#display(wfst, tokens)\n",
    "\n",
    "wfst[0][0] = \"TABLE :P\"\n",
    "for x in range(0,len(wfst)):\n",
    "    wfst[x][0] = str(x)\n",
    "    \n",
    "wfst = wfst[:-1]\n",
    "temp = []\n",
    "for i in range(len(tokens)):\n",
    "    temp.append(tokens[i]+\"[%d]\"%(i+1))\n",
    "temp.insert(0,'TABLE')\n",
    "\n",
    "wfst.insert(0,temp)\n",
    "        \n",
    "\n",
    "IPython.display.display(HTML(\n",
    "    '<table><tr>{}</tr></table>'.format(\n",
    "        '</tr><tr>'.join(\n",
    "            '<td>{}</td>'.format('</td><td>'.join(str(_) for _ in row)) for row in wfst)\n",
    "        )\n",
    " ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "84d2d19b-abee-4913-97ff-d63f59307eb2"
    }
   },
   "source": [
    "<h3>3.2 Applying above CYK algorithm to parse address:</h3>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "2391da40-4267-48c7-a87c-7e392443f87f"
    }
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><td>[NM, X7]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[S]</td></tr><tr><td>[]</td><td>[ADD1, STREET1, ST]</td><td>[ST, ADD1]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[X1]</td></tr><tr><td>[]</td><td>[]</td><td>[ADD1, STREET1, ST]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[X1]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[ADD2, STREET2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[]</td><td>[]</td><td>[]</td><td>[X2]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[ADD2, STREET2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[]</td><td>[]</td><td>[]</td><td>[X2]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[ADD2, STREET2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[]</td><td>[]</td><td>[]</td><td>[X2]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[ADD2, STREET2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[]</td><td>[]</td><td>[]</td><td>[X2]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[ADD2, STREET2, ST1]</td><td>[ADD2, ST1]</td><td>[ADD2, ST1]</td><td>[]</td><td>[]</td><td>[]</td><td>[X2]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[ADD2, STREET2, ST1]</td><td>[ADD2, ST1]</td><td>[]</td><td>[]</td><td>[]</td><td>[X2]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[ADD2, STREET2, ST1]</td><td>[]</td><td>[]</td><td>[]</td><td>[X2]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[CITY, CT]</td><td>[]</td><td>[]</td><td>[X3]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[STATE]</td><td>[]</td><td>[X4]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[COUNTRY]</td><td>[X5]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[Z]</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "adr1 = \"Miguel , private location , details to be emailed to those attending , Evanston , IL , us , 60202\"\n",
    "\n",
    "grammar1 = \\\n",
    "    nltk.CFG.fromstring(\"\"\"\n",
    "S -> NM X1 | NM X6\n",
    "X6 -> ADD1 X3\n",
    "X1 -> ADD1 X2\n",
    "X2 -> ADD2 X3\n",
    "X3 -> CT X4\n",
    "X4 -> STATE X5\n",
    "X5 -> COUNTRY Z\n",
    "NM -> X7 NM | X7 X8 | X7 N | 'NAME'\n",
    "X7 -> 'NAME'\n",
    "X8 -> N NM \n",
    "ADD1 -> X9 ST | ST STREET1 | 'STREET1' | N DIR | X9 AVE | AVENUE AVE | 'AVENUE' | N ST\n",
    "X9 -> N DIR\n",
    "ADD2 -> FL ST1 | X11 F | N F | OTH F | F X11 | SU N | SUI FL | SUI X13 | FL SUI | DIR ST1 | N X14 | STREET2 ST1 | 'STREET2' | N DIR | N ST1 | N X15 | ST1 N |ST1 X16 | 'NUM'\n",
    "X16 -> DIR ST1\n",
    "X15 -> SS ST1\n",
    "X14 -> DIR ST1\n",
    "X13 -> FL ST1\n",
    "N -> 'NUM' \n",
    "CITY -> 'CITY'\n",
    "CT -> 'CITY' | CITY CITY\n",
    "STATE -> 'IL'\n",
    "Z -> 'ZIP'\n",
    "COUNTRY -> 'us' | 'US'\n",
    "DIR -> 'N.' | 'S.' | 'W.'|'E.'|'North'|'South'|'West'|'East'|'N'|'S'|'E'|'W'|'w.'|'s.'|'n.'|'e.'\n",
    "STREET1 -> 'STREET1'\n",
    "ST -> STREET1 ST | STREET1 N | STREET1 X10 | 'STREET1'\n",
    "X10 -> N ST\n",
    "AVE -> AVENUE AVE | 'AVENUE'\n",
    "AVENUE -> 'AVENUE'\n",
    "STREET2 ->\t'STREET2'\n",
    "ST1 -> STREET2 ST1 | 'STREET2'\n",
    "SUI -> SU N\n",
    "FL -> X11 F | N F | OTH F | F X11\n",
    "X11 -> N SS\n",
    "OTH -> 'Top' | 'Main'\n",
    "F -> 'FLOOR'\n",
    "SU -> 'SUITE'\n",
    "SS -> 'SUP'\n",
    "\"\"\")\n",
    "\n",
    "pattern = [(r'^(?!(?:^6[0-9]{4,4}$)$)\\d+','NUM'),(r'^(?!(?:^6[0-9]{4,4}$)|(\\(|\\)|IL|us|US|N\\.|W\\.|E\\.|S\\.|N|W|E|S|n\\.|w\\.|e\\.|s\\.|Ave|Ave\\.|ave|avenue|Avenue|AVENUE|ave\\.|West|North|East|,|South|Suite|suite|SUITE|Floor|Fl.|Fl|floor|nd|th)$).*','STREET1'),(r'(Suite|suite|SUITE)','SUITE'),(r'(nd|th)','SUP'),(r'(floor|Fl.|Fl|Floor)','FLOOR'),(r',','COM'),(r'\\(|\\)','BRAC'),(r'Ave|Ave.|ave|avenue|Avenue|AVENUE|ave.','AVENUE'),(r'^6[0-9]{4,4}$','ZIP')]\n",
    "tagger = nltk.RegexpTagger(pattern)\n",
    "    \n",
    "t = []\n",
    "f = 0\n",
    "p = 0\n",
    "start = 0\n",
    "end = 0\n",
    "for (y, x) in tagger.tag(nltk.word_tokenize(adr1)):\n",
    "    if x is not None and x != 'COM' and x != 'BRAC' and f == 0:\n",
    "        if x == 'STREET1':\n",
    "            x = 'NAME'\n",
    "        t.append(x)\n",
    "    elif x != None and x != 'COM' and x != 'BRAC' and f == 1:\n",
    "        t.append(x)\n",
    "    elif x != None and x != 'COM' and x != 'BRAC' and f == 2:\n",
    "        if x == 'STREET1':\n",
    "            x = 'STREET2'\n",
    "        t.append(x)\n",
    "    elif x != None and x != 'COM' and x != 'BRAC' and f == 3:\n",
    "        if x == 'STREET1':\n",
    "            x = 'CITY'\n",
    "        t.append(x)\n",
    "    elif x != None and x != 'COM' and x != 'BRAC' and f == 6:\n",
    "        t.append(x)\n",
    "    elif x == 'COM':\n",
    "        f += 1\n",
    "    elif x == None:\n",
    "        t.append(y)\n",
    "\n",
    "if 'AVENUE' in t:\n",
    "    p = 1\n",
    "\n",
    "if p == 1:\n",
    "    for (index, item) in enumerate(t):\n",
    "        if 'STREET1' in item:\n",
    "            start = index\n",
    "            break\n",
    "    for (index, item) in enumerate(t):\n",
    "        if 'AVENUE' in item:\n",
    "            end = index\n",
    "            break\n",
    "    for i in range(start, end):\n",
    "        t[i] = 'AVENUE'\n",
    "\n",
    "tokens = t\n",
    "grammar = grammar1\n",
    "    \n",
    "size = len(tokens)\n",
    "\n",
    "#creating table\n",
    "table = [ [[] for i in range(size)] for i in range(size) ]\n",
    "\n",
    "#creating production lookup dictionary\n",
    "lookup = {}\n",
    "for prod in grammar.productions():\n",
    "    if prod.rhs() in lookup:\n",
    "        lookup[prod.rhs()] += [prod.lhs()]\n",
    "    else:\n",
    "        lookup[prod.rhs()] = [prod.lhs()]\n",
    "    \n",
    "#filling diagonal\n",
    "for i in range(len(tokens)):\n",
    "    prods = grammar.productions(rhs=tokens[i])\n",
    "    table[i][i]= [x.lhs() for x in prods]\n",
    "\n",
    "#filling rest of table with cyk algorithm\n",
    "for i in range(2,size+1):\n",
    "    for j in range(size-i+1):\n",
    "        \n",
    "        for k in range(j,j+i-1):\n",
    "            \n",
    "            nt1, nt2 = table[j][k], table[k+1][j+i-1]\n",
    "            currentNts = []\n",
    "            \n",
    "            if nt1 and nt2:\n",
    "                for p1 in nt1:\n",
    "                    for p2 in nt2:\n",
    "                        \n",
    "                        if (p1,p2) in lookup:\n",
    "                            currentNts.extend(lookup[(p1,p2)])\n",
    "            table[j][j+i-1] += currentNts\n",
    "            \n",
    "IPython.display.display(HTML(\n",
    "    '<table><tr>{}</tr></table>'.format(\n",
    "        '</tr><tr>'.join(\n",
    "            '<td>{}</td>'.format('</td><td>'.join(str(_) for _ in row)) for row in table)\n",
    "        )\n",
    " ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbpresent": {
     "id": "ea92ac44-3103-4712-b35c-73314ce40e31"
    }
   },
   "source": [
    "<h3>3.3 Applying above CYK algorithm to parse address with PCFG (Probabilistic CFG):</h3>\n",
    "<pre>Where a normal CFG parser gives us two parse trees for the address \"<b>Harold Washington Library Center , 400 S. State Street , Cindy Pritzker Auditorium , Chicago , IL , us , 60605</b>\" , a PCFG parser can give us the most probable parse, based on multiplying the probabilities of the rules necessary for the derivation of each parse. This makes for a more accurate natural language understander.\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false,
    "nbpresent": {
     "id": "505a9aaf-1994-4d2d-87a7-dd3ffaad2890"
    },
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><td>['NM : 3.000e-01', 'X7 : 1.000e+00']</td><td>['NM : 1.200e-01']</td><td>['NM : 4.800e-02']</td><td>['NM : 1.920e-02']</td><td>['NM : 1.280e-02']</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['S : 8.361e-08']</td></tr><tr><td>[]</td><td>['NM : 3.000e-01', 'X7 : 1.000e+00']</td><td>['NM : 1.200e-01']</td><td>['NM : 4.800e-02']</td><td>['NM : 3.200e-02']</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['S : 2.090e-07']</td></tr><tr><td>[]</td><td>[]</td><td>['NM : 3.000e-01', 'X7 : 1.000e+00']</td><td>['NM : 1.200e-01']</td><td>['NM : 8.000e-02']</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['S : 5.225e-07']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>['NM : 3.000e-01', 'X7 : 1.000e+00']</td><td>['NM : 2.000e-01']</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['S : 1.306e-06']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['ADD2 : 5.000e-02', 'N : 1.000e+00']</td><td>['ADD1 : 1.000e-02', 'X9 : 1.000e-01', 'ADD2 : 4.000e-03']</td><td>['ADD1 : 9.000e-03']</td><td>['ADD1 : 2.700e-03']</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['X1 : 7.258e-06']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['DIR : 1.000e-01']</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['ADD1 : 1.000e-01', 'STREET1 : 1.000e+00', 'ST : 3.000e-01']</td><td>['ST : 9.000e-02', 'ADD1 : 7.500e-02']</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['X1 : 2.016e-04']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['ADD1 : 1.000e-01', 'STREET1 : 1.000e+00', 'ST : 3.000e-01']</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['X1 : 2.688e-04']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['ADD2 : 1.000e-02', 'STREET2 : 1.000e+00', 'ST1 : 4.000e-01']</td><td>['ADD2 : 1.600e-02', 'ST1 : 2.400e-01']</td><td>['ADD2 : 9.600e-03', 'ST1 : 1.440e-01']</td><td>[]</td><td>[]</td><td>[]</td><td>['X2 : 2.688e-03']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['ADD2 : 1.000e-02', 'STREET2 : 1.000e+00', 'ST1 : 4.000e-01']</td><td>['ADD2 : 1.600e-02', 'ST1 : 2.400e-01']</td><td>[]</td><td>[]</td><td>[]</td><td>['X2 : 4.480e-03']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['ADD2 : 1.000e-02', 'STREET2 : 1.000e+00', 'ST1 : 4.000e-01']</td><td>[]</td><td>[]</td><td>[]</td><td>['X2 : 2.800e-03']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['CITY : 1.000e+00', 'CT : 4.000e-01']</td><td>[]</td><td>[]</td><td>['X3 : 2.800e-01']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['STATE : 1.000e+00']</td><td>[]</td><td>['X4 : 7.000e-01']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['COUNTRY : 7.000e-01']</td><td>['X5 : 7.000e-01']</td></tr><tr><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>[]</td><td>['Z : 1.000e+00']</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import math\n",
    "#an example address string\n",
    "adr1 = \"Harold Washington Library Center , 400 S. State Street , Cindy Pritzker Auditorium , Chicago , IL , us , 60605\"\n",
    "\n",
    "#specify the grammer with each production with the probabilities\n",
    "grammar1 = \\\n",
    "    nltk.PCFG.fromstring(\"\"\"\n",
    "S -> NM X1 [0.6] | NM X6 [0.4]\n",
    "X6 -> ADD1 X3 [1.0]\n",
    "X1 -> ADD1 X2 [1.0]\n",
    "X2 -> ADD2 X3 [1.0]\n",
    "X3 -> CT X4 [1.0]\n",
    "X4 -> STATE X5 [1.0]\n",
    "X5 -> COUNTRY Z [1.0]\n",
    "NM -> X7 NM [0.4] | X7 X8 [0.1] | X7 N [0.2] | 'NAME' [0.3]\n",
    "X7 -> 'NAME' [1.0]\n",
    "X8 -> N NM [1.0]\n",
    "ADD1 -> X9 ST [0.3] | ST STREET1 [0.25] | 'STREET1' [0.1] | N DIR [0.1] | X9 AVE [0.05] | AVENUE AVE [0.1]| 'AVENUE' [0.06]| N ST [0.04]\n",
    "X9 -> N DIR [1.0]\n",
    "ADD2 -> FL ST1 [0.1]| X11 F [0.033]| N F [0.067]| OTH F [0.1]| F X11 [0.1]| SU N [0.1]| SUI FL [0.1]| SUI X13 [0.05]| FL SUI [0.05]| DIR ST1 [0.02]| N X14 [0.04]| STREET2 ST1 [0.04]| 'STREET2' [0.01]| N DIR [0.04]| N ST1 [0.05]| N X15 [0.01]| ST1 N [0.02]|ST1 X16 [0.02]| 'NUM' [0.05]\n",
    "X16 -> DIR ST1 [1.0]\n",
    "X15 -> SS ST1 [1.0]\n",
    "X14 -> DIR ST1 [1.0]\n",
    "X13 -> FL ST1 [1.0]\n",
    "N -> 'NUM' [1.0]\n",
    "CITY -> 'CITY' [1.0]\n",
    "CT -> 'CITY' [0.4] | CITY CITY [0.6]\n",
    "STATE -> 'IL' [1.0]\n",
    "Z -> 'ZIP' [1.0]\n",
    "COUNTRY -> 'us' [0.7] | 'US' [0.3]\n",
    "DIR -> 'N.' [0.1]| 'S.'[0.1] | 'W.' [0.1] |'E.' [0.1] |'North' [0.05] |'South' [0.05] |'West' [0.05]|'East' [0.05]|'N' [0.05] |'S' [0.05]|'E' [0.05] |'W' [0.05]|'w.' [0.05]|'s.' [0.05] |'n.' [0.05] |'e.' [0.05]\n",
    "STREET1 -> 'STREET1' [1.0]\n",
    "ST -> STREET1 ST [0.3] | STREET1 N [0.2]| STREET1 X10 [0.2]| 'STREET1' [0.3]\n",
    "X10 -> N ST [1.0]\n",
    "AVE -> AVENUE AVE [0.6] | 'AVENUE' [0.4]\n",
    "AVENUE -> 'AVENUE' [1.0]\n",
    "STREET2 ->\t'STREET2' [1.0]\n",
    "ST1 -> STREET2 ST1 [0.6] | 'STREET2' [0.4]\n",
    "SUI -> SU N [1.0]\n",
    "FL -> X11 F [0.3] | N F [0.2] | OTH F [0.2] | F X11 [0.3]\n",
    "X11 -> N SS [1.0]\n",
    "OTH -> 'Top' [0.5] | 'Main' [0.5]\n",
    "F -> 'FLOOR' [1.0]\n",
    "SU -> 'SUITE' [1.0]\n",
    "SS -> 'SUP' [1.0]\n",
    "\"\"\")\n",
    "\n",
    "pattern = [(r'^(?!(?:^6[0-9]{4,4}$)$)\\d+','NUM'),(r'^(?!(?:^6[0-9]{4,4}$)|(\\(|\\)|IL|us|US|N\\.|W\\.|E\\.|S\\.|N|W|E|S|n\\.|w\\.|e\\.|s\\.|Ave|Ave\\.|ave|avenue|Avenue|AVENUE|ave\\.|West|North|East|,|South|Suite|suite|SUITE|Floor|Fl.|Fl|floor|nd|th)$).*','STREET1'),(r'(Suite|suite|SUITE)','SUITE'),(r'(nd|th)','SUP'),(r'(floor|Fl.|Fl|Floor)','FLOOR'),(r',','COM'),(r'\\(|\\)','BRAC'),(r'Ave|Ave.|ave|avenue|Avenue|AVENUE|ave.','AVENUE'),(r'^6[0-9]{4,4}$','ZIP')]\n",
    "tagger = nltk.RegexpTagger(pattern)\n",
    "    \n",
    "t = []\n",
    "f = 0\n",
    "p = 0\n",
    "start = 0\n",
    "end = 0\n",
    "for (y, x) in tagger.tag(nltk.word_tokenize(adr1)):\n",
    "    if x is not None and x != 'COM' and x != 'BRAC' and f == 0:\n",
    "        if x == 'STREET1':\n",
    "            x = 'NAME'\n",
    "        t.append(x)\n",
    "    elif x != None and x != 'COM' and x != 'BRAC' and f == 1:\n",
    "        t.append(x)\n",
    "    elif x != None and x != 'COM' and x != 'BRAC' and f == 2:\n",
    "        if x == 'STREET1':\n",
    "            x = 'STREET2'\n",
    "        t.append(x)\n",
    "    elif x != None and x != 'COM' and x != 'BRAC' and f == 3:\n",
    "        if x == 'STREET1':\n",
    "            x = 'CITY'\n",
    "        t.append(x)\n",
    "    elif x != None and x != 'COM' and x != 'BRAC' and f == 6:\n",
    "        t.append(x)\n",
    "    elif x == 'COM':\n",
    "        f += 1\n",
    "    elif x == None:\n",
    "        t.append(y)\n",
    "\n",
    "\n",
    "if 'AVENUE' in t:\n",
    "    p = 1\n",
    "\n",
    "if p == 1:\n",
    "    for (index, item) in enumerate(t):\n",
    "        if 'STREET1' in item:\n",
    "            start = index\n",
    "            break\n",
    "    for (index, item) in enumerate(t):\n",
    "        if 'AVENUE' in item:\n",
    "            end = index\n",
    "            break\n",
    "    for i in range(start, end):\n",
    "        t[i] = 'AVENUE'\n",
    "            \n",
    "tokens = t\n",
    "grammar = grammar1\n",
    "    \n",
    "#creating table\n",
    "size = len(tokens)\n",
    "table = [ [[] for i in range(size)] for i in range(size) ]\n",
    "\n",
    "#creating production lookup dictionary\n",
    "lookup = {}\n",
    "for prod in grammar.productions():\n",
    "    if prod.rhs() in lookup:\n",
    "        lookup[prod.rhs()] += [(prod.lhs(),prod.prob())]\n",
    "    else:\n",
    "        lookup[prod.rhs()] = [(prod.lhs(),prod.prob())]\n",
    "\n",
    "#filling diagonal\n",
    "for i in range(len(tokens)):\n",
    "    prods = grammar.productions(rhs=tokens[i])\n",
    "    table[i][i]= [(x.lhs(),x.prob()) for x in prods]\n",
    "\n",
    "#filling rest of table with cyk algorithm\n",
    "for i in range(2,size+1):\n",
    "    for j in range(size-i+1):\n",
    "        \n",
    "        for k in range(j,j+i-1):\n",
    "            \n",
    "            nt1, nt2 = table[j][k], table[k+1][j+i-1]\n",
    "            currentNts = []\n",
    "            \n",
    "            if nt1 and nt2:\n",
    "                for p1 in nt1:\n",
    "                    for p2 in nt2:                  \n",
    "                        if (p1[0],p2[0]) in lookup:\n",
    "                            for o in lookup[(p1[0],p2[0])]:\n",
    "                                currentNts.append((o[0],p1[1]*p2[1]*o[1]))\n",
    "            table[j][j+i-1] += currentNts\n",
    "\n",
    "IPython.display.display(HTML(\n",
    "    '<table><tr>{}</tr></table>'.format(\n",
    "        '</tr><tr>'.join(\n",
    "            '<td>{}</td>'.format('</td><td>'.join(str( [str(x[0])+ ' : ' +\"{:.3e}\".format(x[1]) for x in _]) for _ in row)) for row in table)\n",
    "        )\n",
    " ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>References</h2>\n",
    "<pre>\n",
    "[1]NLTK : www.nltk.org\n",
    "[2]CKY implementation : http://www.cs.pomona.edu/classes/cs181NLP/lectures/Lec11/Lec11.pdf\n",
    "[3]Pawan Goyal, Lecture slides, Speech and natural language processing (CS60057), Autumn 2016, IIT Kharagpur.\n",
    "[4]NLTK Book : http://www.nltk.org/book/\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Developers</h2>\n",
    "<ul>\n",
    "<li>Richa Manral<a href=\"mailto:richa.manral22@gmail.com\">richa.manral22@gmail.com</a><br></li>\n",
    "<li>Fenil Fadadu <a href=\"mailto:fenilc017@gmail.com\">fenilc017@gmail.com</a><br></li>\n",
    "<li>Bhargavkumar Patel <a href=\"mailto:bhargav079@gmail.com\">bhargav079@gmail.com</a><br></li>\n",
    "<li>Minesh Gandhi <a href=\"mailto:mineshmini33@gmail.com\">mineshmini33@gmail.com</a><br></li>\n",
    "<li>Prachi Agarwal <a href=\"mailto:24prachiagarwal@gmail.com\">24prachiagarwal@gmail.com</a></li>\n",
    "</ul>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}