Chapter 4.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import nltk\n",
    "import re\n",
    "from nltk.corpus import wordnet as wn\n",
    "from operator import itemgetter\n",
    "from timeit import Timer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**1. Find out more about sequence objects using Python's help facility. In the interpreter, type ** `help(str)`, `help(list)` **, and ** `help(tuple)` **. This will give you a full list of the functions supported by each type. Some functions have special names flanked with underscore; as the help documentation shows, each such function corresponds to something more familiar. For example ** `x.__getitem__(y)` ** is just a long-winded way of saying ** `x[y]` **.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on class tuple in module builtins:\n",
      "\n",
      "class tuple(object)\n",
      " |  tuple() -> empty tuple\n",
      " |  tuple(iterable) -> tuple initialized from iterable's items\n",
      " |  \n",
      " |  If the argument is a tuple, the return value is the same object.\n",
      " |  \n",
      " |  Methods defined here:\n",
      " |  \n",
      " |  __add__(self, value, /)\n",
      " |      Return self+value.\n",
      " |  \n",
      " |  __contains__(self, key, /)\n",
      " |      Return key in self.\n",
      " |  \n",
      " |  __eq__(self, value, /)\n",
      " |      Return self==value.\n",
      " |  \n",
      " |  __ge__(self, value, /)\n",
      " |      Return self>=value.\n",
      " |  \n",
      " |  __getattribute__(self, name, /)\n",
      " |      Return getattr(self, name).\n",
      " |  \n",
      " |  __getitem__(self, key, /)\n",
      " |      Return self[key].\n",
      " |  \n",
      " |  __getnewargs__(...)\n",
      " |  \n",
      " |  __gt__(self, value, /)\n",
      " |      Return self>value.\n",
      " |  \n",
      " |  __hash__(self, /)\n",
      " |      Return hash(self).\n",
      " |  \n",
      " |  __iter__(self, /)\n",
      " |      Implement iter(self).\n",
      " |  \n",
      " |  __le__(self, value, /)\n",
      " |      Return self<=value.\n",
      " |  \n",
      " |  __len__(self, /)\n",
      " |      Return len(self).\n",
      " |  \n",
      " |  __lt__(self, value, /)\n",
      " |      Return self<value.\n",
      " |  \n",
      " |  __mul__(self, value, /)\n",
      " |      Return self*value.n\n",
      " |  \n",
      " |  __ne__(self, value, /)\n",
      " |      Return self!=value.\n",
      " |  \n",
      " |  __new__(*args, **kwargs) from builtins.type\n",
      " |      Create and return a new object.  See help(type) for accurate signature.\n",
      " |  \n",
      " |  __repr__(self, /)\n",
      " |      Return repr(self).\n",
      " |  \n",
      " |  __rmul__(self, value, /)\n",
      " |      Return self*value.\n",
      " |  \n",
      " |  count(...)\n",
      " |      T.count(value) -> integer -- return number of occurrences of value\n",
      " |  \n",
      " |  index(...)\n",
      " |      T.index(value, [start, [stop]]) -> integer -- return first index of value.\n",
      " |      Raises ValueError if the value is not present.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# help(str)\n",
    "# help(list)\n",
    "help(tuple)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**2. Identify three operations that can be performed on both tuples and lists. Identify three list operations that cannot be performed on tuples. Name a context where using a list instead of a tuple generates a Python error.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# https://docs.python.org/3/library/stdtypes.html#typesseq\n",
    "\n",
    "exp_list = ['natural', 'language', 'processing']\n",
    "exp_tuple = 'natural', 'language', 'processing'\n",
    "\n",
    "# Common operations\n",
    "'language' in exp_list              # in\n",
    "'language' not in exp_tuple         # not in\n",
    "\n",
    "exp_list[0]                         # subsciption\n",
    "exp_tuple[1:]                       # slicing\n",
    "\n",
    "len(exp_list)                       # length\n",
    "len(exp_tuple)\n",
    "\n",
    "min(exp_list)                       # smallest item\n",
    "max(exp_tuple)                      # largest item\n",
    "\n",
    "exp_list.index('language')          # index of the first occurrence\n",
    "exp_tuple.index('processing', 1)    # index of the first occurrence (at or after index 1)\n",
    "\n",
    "# List operations(mutable) that cannot be performed on tuples\n",
    "exp_list[0] = 'Natural'\n",
    "del exp_list[1]\n",
    "exp_list.append('understanding')\n",
    "exp_list.insert(1, 'Language')\n",
    "exp_list.pop()\n",
    "exp_list.remove('Natural')\n",
    "exp_list.clear()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "tuple_only = 'natural', ['N', 'AE1', 'CH', 'ER0', 'AH0', 'L']\n",
    "# though it seems okay to create a list with ['natural', ['N', 'AE1', 'CH', 'ER0', 'AH0', 'L']]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**3.  Find out how to create a tuple consisting of a single item. There are at least two ways to do this.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'tuple'>\n",
      "<class 'tuple'>\n"
     ]
    }
   ],
   "source": [
    "tuple1 = 'single',\n",
    "tuple2 = tuple(['single'])\n",
    "print(type(tuple1))\n",
    "print(type(tuple2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**4.  Create a list ** `words = ['is', 'NLP', 'fun', '?']` **. Use a series of assignment statements (e.g. ** `words[1] = words[2]` **) and a temporary variable ** `tmp` ** to transform this list into the list ** `['NLP', 'is', 'fun', '!']` **. Now do the same transformation using tuple assignment.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['NLP', 'is', 'fun', '!']"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = ['is', 'NLP', 'fun', '?']\n",
    "words[0], words[1] = words[1], words[0]     # tmp is not necessary\n",
    "words[-1] = '!'\n",
    "words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['NLP', 'is', 'fun', '!']"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words_tuple = 'is', 'NLP', 'fun', '?'\n",
    "words_new = words_tuple[1], words_tuple[0], words_tuple[2], '!'\n",
    "list(words_new)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5. Read about the built-in comparison function ** `cmp` **, by typing ** `help(cmp)` **. How does it differ in behavior from the comparison operators?**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well, `cmp()` compare the two objects *x* and *y* and return an integer according to the outcome. The return value is negative if `x < y`, zero if `x == y` and strictly positive if `x > y`.  \n",
    "However, it was deprecated in Python3 and `cmp` is no longer a built-in comparison."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**6. Does the method for creating a sliding window of n-grams behave correctly for the two limiting cases: ** *n* = 1, **and ** *n* = `len(sent)` **?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['The', 'dog', 'gave', 'John', 'the', 'newspaper']]"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sent = ['The', 'dog', 'gave', 'John', 'the', 'newspaper']\n",
    "n = len(sent)     # n = 1\n",
    "[sent[i:i+n] for i in range(len(sent)-n+1)]\n",
    "# The two boundary cases both works."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**7. We pointed out that when empty strings and empty lists occur in the condition part of an ** `if` ** clause, they evaluate to ** `False` **. In this case, they are said to be occurring in a Boolean context. Experiment with different kind of non-Boolean expressions in Boolean contexts, and see whether they evaluate as ** `True` ** or ** `False` **.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "a = 1\n",
    "if a:\n",
    "    print('True')\n",
    "else:\n",
    "    print('False')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`False`, `None`, numeric zero of all types, and empty strings and containers (including strings, tuples, lists, dictionaries, sets and frozensets). All other values are interpreted as true."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**8. Use the inequality operators to compare strings, e.g. ** `'Monty' < 'Python'` **. What happens when you do ** `'Z' < 'a'` **? Try pairs of strings which have a common prefix, e.g. ** `'Monty' < 'Montague'` **. Read up on \"lexicographical sort\" in order to understand what is going on here. Try comparing structured objects, e.g. ** `('Monty', 1) < ('Monty', 2)` **. Does this behave as expected?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print('Monty' < 'Python')\n",
    "\n",
    "print('Z' < 'a')                  # 90('Z') and 97('a') in ASCII\n",
    "\n",
    "print('Monty' < 'Montague')\n",
    "# Lexicographical sort is introduced in Discrete Mathematics and Its Applications\n",
    "# https://en.wikipedia.org/wiki/Lexicographical_order\n",
    "\n",
    "print(('Monty', 1) < ('Monty', 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**9. Write code that removes whitespace at the beginning and end of a string, and normalizes whitespace between words to be a single space character.**  \n",
    "1. **do this task using ** `split()` ** and ** `join()`  \n",
    "2. **do this task using regular expression substitutions**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'this is a sample sentence.'"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = ' this is \\n a sample\\t sentence. '\n",
    "' '.join(s.split())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'this is a sample sentence.'"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import re\n",
    "s_ = re.sub(r'^\\s|\\s$', '', s)       # remove whitespace at the beginning and end of a string\n",
    "re.sub(r'\\s+', ' ', s_)              # normalize whitespace between words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**10. Write a program to sort words by length. Define a helper function ** `cmp_len` ** which uses the ** `cmp` ** comparison function on word lengths.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'to', 'by', 'sort', 'words', 'length', 'program']"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "word_list = 'a program to sort words by length'.split()\n",
    "sorted(word_list, key=len)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**11. Create a list of words and store it in a variable ** `sent1` **. Now assign ** `sent2 = sent1` **. Modify one of the items in ** `sent1` ** and verify that ** `sent2` ** has changed.**  \n",
    "a. **Now try the same exercise but instead assign ** `sent2 = sent1[:]` **. Modify ** `sent1` ** again and see what happens to ** `sent2` **. Explain.**  \n",
    "b. **Now define ** `text1` ** to be a list of lists of strings (e.g. to represent a text consisting of multiple sentences. Now assign ** `text2 = text1[:]` **, assign a new value to one of the words, e.g. ** `text1[1][1] = 'Monty'` **. Check what this did to ** `text2` **. Explain.**  \n",
    "c. **Load Python's ** `deepcopy()` ** function (i.e. ** `from copy import deepcopy` **), consult its documentation, and test that it makes a fresh copy of any object.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'list', 'of', 'words']"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sent1 = ['a', 'list', 'of', 'word']\n",
    "sent2 = sent1\n",
    "sent1[3] = 'words'\n",
    "sent2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 'list', 'of', 'Word']"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sent2 = sent1[:]\n",
    "sent1[3] = 'Word'\n",
    "sent2\n",
    "\n",
    "# sent2 = sent1[:] makes a copy of each element of sent1.\n",
    "# Since the elements are type of string,\n",
    "# the copy is just copy by value.\n",
    "# So the modification of sent1 doesn't affect sent2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Hush,', 'little', 'baby,', \"don't\", 'say', 'a', 'word,'],\n",
       " [\"Papa's\", 'Monty', 'to', 'buy', 'you', 'a', 'mockingbird.'],\n",
       " ['If', 'that', 'mockingbird', \"won't\", 'sing,'],\n",
       " [\"Papa's\", 'going', 'to', 'buy', 'you', 'a', 'diamond', 'ring.'],\n",
       " ['If', 'that', 'diamond', 'ring', 'turns', 'to', 'brass,'],\n",
       " [\"Papa's\", 'going', 'to', 'buy', 'you', 'a', 'looking-glass.'],\n",
       " ['If', 'that', 'looking-glass', 'gets', 'broke,'],\n",
       " [\"Papa's\", 'going', 'to', 'buy', 'you', 'a', 'billy-goat.'],\n",
       " ['If', 'that', 'billy-goat', 'runs', 'away,'],\n",
       " [\"Papa's\", 'going', 'to', 'buy', 'you', 'another', 'today.']]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text1 = [\"Hush, little baby, don't say a word,\".split(),\n",
    "         \"Papa's going to buy you a mockingbird.\".split(),\n",
    "         \"If that mockingbird won't sing,\".split(),\n",
    "         \"Papa's going to buy you a diamond ring.\".split(),\n",
    "         \"If that diamond ring turns to brass,\".split(),\n",
    "         \"Papa's going to buy you a looking-glass.\".split(),\n",
    "         \"If that looking-glass gets broke,\".split(),\n",
    "         \"Papa's going to buy you a billy-goat.\".split(),\n",
    "         \"If that billy-goat runs away,\".split(),\n",
    "         \"Papa's going to buy you another today.\".split()]\n",
    "text2 = text1[:]\n",
    "text1[1][1] = 'Monty'\n",
    "text2\n",
    "\n",
    "# text2 = text1[:] makes a copy of each element of sent1\n",
    "# The elements are lists and lists are objects.\n",
    "# Therefore, the copy is copy by reference.\n",
    "# The modification of text1 will affect text2 as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Hush,', 'little', 'baby,', \"don't\", 'say', 'a', 'word,'],\n",
       " [\"Papa's\", 'Monty', 'to', 'buy', 'you', 'a', 'mockingbird.'],\n",
       " ['If', 'that', 'mockingbird', \"won't\", 'sing,'],\n",
       " [\"Papa's\", 'going', 'to', 'buy', 'you', 'a', 'diamond', 'ring.'],\n",
       " ['If', 'that', 'diamond', 'ring', 'turns', 'to', 'brass,'],\n",
       " [\"Papa's\", 'going', 'to', 'buy', 'you', 'a', 'looking-glass.'],\n",
       " ['If', 'that', 'looking-glass', 'gets', 'broke,'],\n",
       " [\"Papa's\", 'going', 'to', 'buy', 'you', 'a', 'billy-goat.'],\n",
       " ['If', 'that', 'billy-goat', 'runs', 'away,'],\n",
       " [\"Papa's\", 'going', 'to', 'buy', 'you', 'another', 'today.']]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# https://docs.python.org/3/library/copy.html\n",
    "from copy import deepcopy\n",
    "text3 = deepcopy(text1)\n",
    "text1[1][1] = 'going'\n",
    "text3\n",
    "\n",
    "# the modification of original list won't affect the copy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**12. Initialize an n-by-m list of lists of empty strings using list multiplication, e.g. ** `word_table = [[''] * n] * m` **. What happens when you set one of its values, e.g. ** `word_table[1][2] = \"hello\"` **? Explain why this happens. Now write an expression using ** `range()` ** to construct a list of lists, and show that it does not have this problem.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['', '', 'hello'], ['', '', 'hello'], ['', '', 'hello'], ['', '', 'hello']]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = 4\n",
    "n = 3\n",
    "word_table = [[''] * n] * m\n",
    "word_table[1][2] = \"hello\"\n",
    "word_table\n",
    "\n",
    "# Phenomenon:\n",
    "# Each row's third column's value is changed to \"hello\".\n",
    "\n",
    "# Explanation\n",
    "# word_table is a list(M) with m elements of type list(N).\n",
    "# The multiplication(*m) just copy the reference of N.\n",
    "# The modification of N will affect other references as well.\n",
    "# Since N's element is type of string, the copy is value-copy,\n",
    "# so the first two element of N is not influenced."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['', '', ''], ['', '', 'hello'], ['', '', ''], ['', '', '']]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_table = [['' for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "new_table[1][2] = \"hello\"\n",
    "new_table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**13. Write code to initialize a two-dimensional array of sets called ** `word_vowels` ** and process a list of words, adding each word to ** `word_vowels[l][v]` ** where ** `l` ** is the length of the word and ** `v` ** is the number of vowels it contains.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 10\n",
    "word_vowels = [[set() for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "word_list = 'Write code to initialize an array and process a list of words'.split()\n",
    "for word in word_list:\n",
    "    l = len(word)\n",
    "    v = sum(1 for letter in word.lower() if letter in 'aeiou')\n",
    "    if l < n:                                # in case the length of word is larger than the array size n\n",
    "        word_vowels[l][v].add(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**14. Write a function ** `novel10(text)` ** that prints any word that appeared in the last 10% of a text that had not been encountered earlier.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def novel10(text):\n",
    "    novels = set()\n",
    "    text_list = text.split()\n",
    "    text_len = len(text_list)\n",
    "    for word in text_list[int(0.9 * text_len):]:\n",
    "        if word not in text_list[:int(0.9 * text_len)]:\n",
    "            novels.add(word)\n",
    "    for word in novels:\n",
    "        print(word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**15. Write a program that takes a sentence expressed as a single string, splits it and counts up the words. Get it to print out each word and the word's frequency, one per line, in alphabetical order.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Get: 1\n",
      "Write: 1\n",
      "a: 3\n",
      "alphabetical: 1\n",
      "and: 2\n",
      "as: 1\n",
      "counts: 1\n",
      "each: 1\n",
      "expressed: 1\n",
      "frequency: 1\n",
      "in: 1\n",
      "it: 2\n",
      "line: 1\n",
      "one: 1\n",
      "order: 1\n",
      "out: 1\n",
      "per: 1\n",
      "print: 1\n",
      "program: 1\n",
      "sentence: 1\n",
      "single: 1\n",
      "splits: 1\n",
      "string: 1\n",
      "takes: 1\n",
      "that: 1\n",
      "the: 2\n",
      "to: 1\n",
      "up: 1\n",
      "word: 1\n",
      "word's: 1\n",
      "words: 1\n"
     ]
    }
   ],
   "source": [
    "def split_and_word_freq(sent):\n",
    "    # splits = re.findall(r'\\w+', sent)\n",
    "    splits = re.findall(r\"\\w+(?:[-']\\w+)*\", sent)        # dealing with phrases like it's, warm-hearted\n",
    "\n",
    "    # create the word frequency using dictionary\n",
    "    word_freq = {}\n",
    "    for word in splits:\n",
    "        if word in word_freq:\n",
    "            word_freq[word] = word_freq[word] + 1\n",
    "        else:\n",
    "            word_freq[word] = 1\n",
    "    \n",
    "    # print word's frequency in alphabetical order\n",
    "    for key in sorted(word_freq.keys()):\n",
    "        print(key + ': ' + str(word_freq[key]))\n",
    "    \n",
    "sent = \"Write a program that takes a sentence expressed as a single string, splits it and counts up the words. Get it to print out each word and the word's frequency, one per line, in alphabetical order.\"\n",
    "split_and_word_freq(sent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**16. Read up on Gematria, a method for assigning numbers to words, and for mapping between words having the same number to discover the hidden meaning of texts (http://en.wikipedia.org/wiki/Gematria, http://essenes.net/gemcal.htm).**  \n",
    "a. **Write a function ** `gematria()` ** that sums the numerical values of the letters of a word, according to the letter values in ** `letter_vals` **:**\n",
    "```Python\n",
    ">>> letter_vals = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':80, 'g':3, 'h':8,\n",
    "... 'i':10, 'j':10, 'k':20, 'l':30, 'm':40, 'n':50, 'o':70, 'p':80, 'q':100,\n",
    "... 'r':200, 's':300, 't':400, 'u':6, 'v':6, 'w':800, 'x':60, 'y':10, 'z':7}\n",
    "```\n",
    "b. **Process a corpus (e.g. ** `nltk.corpus.state_union` **) and for each document, count how many of its words have the number 666.**  \n",
    "c. **Write a function ** `decode()` ** to process a text, randomly replacing words with their Gematria equivalents, in order to discover the \"hidden meaning\" of the text.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def gematria(word):\n",
    "    value = 0\n",
    "    letter_vals = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5, 'f':80, 'g':3, 'h':8,\n",
    "                  'i':10, 'j':10, 'k':20, 'l':30, 'm':40, 'n':50, 'o':70, 'p':80, 'q':100,\n",
    "                  'r':200, 's':300, 't':400, 'u':6, 'v':6, 'w':800, 'x':60, 'y':10, 'z':7}\n",
    "    for c in word:\n",
    "        if c in letter_vals:\n",
    "            value += letter_vals[c]\n",
    "    return value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1945-Truman.txt 2\n",
      "1946-Truman.txt 13\n",
      "1947-Truman.txt 0\n",
      "1948-Truman.txt 2\n",
      "1949-Truman.txt 2\n",
      "1950-Truman.txt 1\n",
      "1951-Truman.txt 0\n",
      "1953-Eisenhower.txt 1\n",
      "1954-Eisenhower.txt 6\n",
      "1955-Eisenhower.txt 3\n",
      "1956-Eisenhower.txt 1\n",
      "1957-Eisenhower.txt 2\n",
      "1958-Eisenhower.txt 5\n",
      "1959-Eisenhower.txt 1\n",
      "1960-Eisenhower.txt 5\n",
      "1961-Kennedy.txt 0\n",
      "1962-Kennedy.txt 11\n",
      "1963-Johnson.txt 0\n",
      "1963-Kennedy.txt 5\n",
      "1964-Johnson.txt 1\n",
      "1965-Johnson-1.txt 0\n",
      "1965-Johnson-2.txt 0\n",
      "1966-Johnson.txt 0\n",
      "1967-Johnson.txt 2\n",
      "1968-Johnson.txt 3\n",
      "1969-Johnson.txt 0\n",
      "1970-Nixon.txt 0\n",
      "1971-Nixon.txt 1\n",
      "1972-Nixon.txt 0\n",
      "1973-Nixon.txt 1\n",
      "1974-Nixon.txt 0\n",
      "1975-Ford.txt 0\n",
      "1976-Ford.txt 3\n",
      "1977-Ford.txt 0\n",
      "1978-Carter.txt 1\n",
      "1979-Carter.txt 2\n",
      "1980-Carter.txt 0\n",
      "1981-Reagan.txt 4\n",
      "1982-Reagan.txt 0\n",
      "1983-Reagan.txt 2\n",
      "1984-Reagan.txt 1\n",
      "1985-Reagan.txt 1\n",
      "1986-Reagan.txt 1\n",
      "1987-Reagan.txt 1\n",
      "1988-Reagan.txt 2\n",
      "1989-Bush.txt 1\n",
      "1990-Bush.txt 2\n",
      "1991-Bush-1.txt 0\n",
      "1991-Bush-2.txt 0\n",
      "1992-Bush.txt 3\n",
      "1993-Clinton.txt 1\n",
      "1994-Clinton.txt 2\n",
      "1995-Clinton.txt 1\n",
      "1996-Clinton.txt 2\n",
      "1997-Clinton.txt 1\n",
      "1998-Clinton.txt 4\n",
      "1999-Clinton.txt 1\n",
      "2000-Clinton.txt 3\n",
      "2001-GWBush-1.txt 1\n",
      "2001-GWBush-2.txt 0\n",
      "2002-GWBush.txt 0\n",
      "2003-GWBush.txt 3\n",
      "2004-GWBush.txt 2\n",
      "2005-GWBush.txt 2\n",
      "2006-GWBush.txt 0\n"
     ]
    }
   ],
   "source": [
    "for fileid in nltk.corpus.state_union.fileids():\n",
    "    cnt = 0\n",
    "    for word in nltk.corpus.state_union.words(fileid):\n",
    "        if word.isalpha() and gematria(word.lower()) == 666:\n",
    "            cnt += 1\n",
    "    print(fileid, cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# not tested\n",
    "def decode(text):\n",
    "    gematrias = {}\n",
    "    splits = text.split()\n",
    "\n",
    "    # create dictionary \n",
    "    # key: gematria value\n",
    "    # value: list of words with that gematria value\n",
    "    for word in splits:\n",
    "        if gematria(word) in gematrias:\n",
    "            gematrias[gematria(word)].add(word)\n",
    "        else:\n",
    "            gematrias[gematria(word)] = [word]\n",
    "            \n",
    "    for i in range(len(splits)):\n",
    "        splits[i] = random.choice(gematrias[gematria(word)])\n",
    "    \n",
    "    return ' '.join(splits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**17. Write a function ** `shorten(text, n)` ** to process a text, omitting the ** *n* ** most frequently occurring words of the text. How readable is it?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Write  function shorten   to process   omitting   most frequently occurring words of   How readable is it'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def shorten(text, n):\n",
    "    splits = re.findall(r\"\\w+(?:[-']\\w+)*\", text)\n",
    "    fdist = nltk.FreqDist(splits)\n",
    "    # most_freq = fdist.most_common(n)\n",
    "    # print(most_freq)\n",
    "    most_freq = []\n",
    "    for sample in fdist.most_common(n):\n",
    "        most_freq.append(sample[0])\n",
    "    for i in range(len(splits)):\n",
    "        if splits[i] in most_freq:\n",
    "            splits[i] = ''                     # in fact, the element should be deleted in the list\n",
    "    return ' '.join(splits)\n",
    "\n",
    "text = 'Write a function shorten(text, n) to process a text, omitting the n most frequently occurring words of the text. How readable is it?'\n",
    "shorten(text, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**18. Write code to print out an index for a lexicon, allowing someone to look up words according to their meanings (or pronunciations; whatever properties are contained in lexical entries).**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not understand yet... Just exchange the key and value in nldk.corpus.cmudict?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**19. Write a list comprehension that sorts a list of WordNet synsets for proximity to a given synset. For example, given the synsets ** `minke_whale.n.01, orca.n.01, novel.n.01` **, and ** `tortoise.n.01` **, sort them according to their ** `shortest_path_distance()` ** from ** `right_whale.n.01` **.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Synset('lesser_rorqual.n.01'),\n",
       " Synset('killer_whale.n.01'),\n",
       " Synset('tortoise.n.01'),\n",
       " Synset('novel.n.01')]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minke = wn.synset('minke_whale.n.01')\n",
    "orca = wn.synset('orca.n.01')\n",
    "novel = wn.synset('novel.n.01')\n",
    "tortoise = wn.synset('tortoise.n.01')\n",
    "right = wn.synset('right_whale.n.01')\n",
    "\n",
    "wn_list = [minke, orca, novel, tortoise]\n",
    "sorted(wn_list,\n",
    "       key=lambda x: right.shortest_path_distance(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**20. Write a function that takes a list of words (containing duplicates) and returns a list of words (with no duplicates) sorted by decreasing frequency. E.g. if the input list contained 10 instances of the word ** `table` ** and 9 instances of the word ** `chair` **, then ** `table` ** would appear before ** `chair` ** in the output list.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def decreasing_freq_with_no_duplicates(words):\n",
    "    wordset = set(words)\n",
    "    fdist = nltk.FreqDist(words)\n",
    "    return sorted(wordset,\n",
    "                 key=lambda x:fdist[x],\n",
    "                 reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['table', 'chair']"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = ['table'] * 10 + ['chair'] * 9\n",
    "decreasing_freq_with_no_duplicates(words)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**21. Write a function that takes a text and a vocabulary as its arguments and returns the set of words that appear in the text but not in the vocabulary. Both arguments can be represented as lists of strings. Can you do this in a single line, using ** `set.difference()` **?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def diff(text, vocab):\n",
    "    return set(text).difference(vocab)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'and', 'text'}"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text = 'a text and a vocabulary'.split()\n",
    "vocab = 'a vocabulary'.split()\n",
    "diff(text, vocab)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**22. Import the ** `itemgetter()` ** function from the operator module in Python's standard library (i.e. ** `from operator import itemgetter` **). Create a list words containing several words. Now try calling: ** `sorted(words, key=itemgetter(1))` **, and ** `sorted(words, key=itemgetter(-1))` **. Explain what ** `itemgetter()` ** is doing.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['wOrds', 'several', 'list', 'containing', 'words']"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "words = 'list wOrds containing several words'.split()\n",
    "sorted(words, key=itemgetter(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[operator.itemgetter()](https://docs.python.org/3/library/operator.html#operator.itemgetter)  \n",
    "`operator.itemgetter()` returns a callable object that fetches item from its operand using the operand’s `__getitem__()` method. If multiple items are specified, returns a tuple of lookup values. For example:\n",
    "\n",
    "After `f = itemgetter(2)`, the call `f(r)` returns `r[2]`.  \n",
    "After `g = itemgetter(2, 5, 3)`, the call `g(r)` returns `(r[2], r[5], r[3])`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**23. Write a recursive function ** `lookup(trie, key)` ** that looks up a key in a trie, and returns the value it finds. Extend the function to return a word when it is uniquely determined by its prefix (e.g. ** `vanguard` ** is the only word that starts with ** `vang-` **, so ** `lookup(trie, 'vang')` ** should return the same thing as ** `lookup(trie, 'vanguard'))` **.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def insert(trie, key, value):\n",
    "    if key:\n",
    "        first, rest = key[0], key[1:]\n",
    "        if first not in trie:\n",
    "            trie[first] = {}\n",
    "        insert(trie[first], rest, value)\n",
    "    else:\n",
    "        trie['value'] = value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'c': {'h': {'a': {'i': {'r': {'value': 'flesh'}},\n",
      "                   't': {'value': 'cat'}},\n",
      "             'i': {'c': {'value': 'stylish'},\n",
      "                   'e': {'n': {'value': 'dog'}}}}}}\n"
     ]
    }
   ],
   "source": [
    "trie = {}\n",
    "insert(trie, 'chat', 'cat')\n",
    "insert(trie, 'chien', 'dog')\n",
    "insert(trie, 'chair', 'flesh')\n",
    "insert(trie, 'chic', 'stylish')\n",
    "pprint.pprint(trie, width=40)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# original edition\n",
    "# must type the word completely\n",
    "def lookup(trie, key):\n",
    "    if key:\n",
    "        return lookup(trie[key[0]], key[1:])\n",
    "    else:\n",
    "        return trie['value']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'flesh'"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lookup(trie, 'chair')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# modification edition\n",
    "# can look up a word when it is uniquely determined by its prefix\n",
    "# (though the code is not elegant TAT\n",
    "def lookup1(trie, key):\n",
    "    if key:\n",
    "        return lookup1(trie[key[0]], key[1:])\n",
    "    else:\n",
    "        if 'value' in trie:\n",
    "            return trie['value']\n",
    "        if len(trie) == 1:\n",
    "            return lookup1(trie[list(trie)[0]], '')\n",
    "        else:\n",
    "            print('Invalid look up')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 127,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insert(trie, 'vanguard', 'pioneer')\n",
    "lookup1(trie, 'vang') == lookup1(trie, 'vanguard')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**24. Read up on \"keyword linkage\" (chapter 5 of (Scott & Tribble, 2006)). Extract keywords from NLTK's Shakespeare Corpus and using the NetworkX package, plot keyword linkage networks.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Scott & Tribble, 2006 is not available. And I haven't instaled NetworkX neither."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**25. Read about string edit distance and the Levenshtein Algorithm. Try the implementation provided in nltk.edit_distance(). In what way is this using dynamic programming? Does it use the bottom-up or top-down approach? [See also http://norvig.com/spell-correct.html]**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The blog is to be read."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**26. The Catalan numbers arise in many applications of combinatorial mathematics, including the counting of parse trees (6). The series can be defined as follows: ** $C_0=1$ **, and ** $C_{n+1}=\\sum_{0..n}(C_iC_{n-i})$.  \n",
    "a. **Write a recursive function to compute ** *n* **th Catalan number** $C_n$  \n",
    "b. **Now write another function that does this computation using dynamic programming.** \n",
    "c. **Use the ** `timeit` ** module to compare the performance of these functions as ** *n* ** increases.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def catalan_recursive(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            c += catalan_recursive(i) * catalan_recursive(n - i - 1)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 163,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "catalan_recursive(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def catalan_dp(n, lookup={0:1, 1:1}):\n",
    "    if n not in lookup:\n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            c += catalan_dp(i) * catalan_dp(n - i - 1)\n",
    "        lookup[n] = c\n",
    "    return lookup[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "42"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "catalan_dp(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i = 0\n",
      "Recursive: 0.002184530982049182\n",
      "Dynamic Programming 0.0023424150131177157\n",
      "i = 1\n",
      "Recursive: 0.0020310399995651096\n",
      "Dynamic Programming 0.002242524002213031\n",
      "i = 2\n",
      "Recursive: 0.01463045398122631\n",
      "Dynamic Programming 0.002049253002041951\n",
      "i = 3\n",
      "Recursive: 0.04760096099926159\n",
      "Dynamic Programming 0.0019739810086321086\n",
      "i = 4\n",
      "Recursive: 0.12554282997734845\n",
      "Dynamic Programming 0.001775078009814024\n",
      "i = 5\n",
      "Recursive: 0.4283594549924601\n",
      "Dynamic Programming 0.001807728986022994\n",
      "i = 6\n",
      "Recursive: 1.2319063549803104\n",
      "Dynamic Programming 0.0018030449864454567\n",
      "i = 7\n",
      "Recursive: 3.4462423990189563\n",
      "Dynamic Programming 0.001796147000277415\n",
      "i = 8\n",
      "Recursive: 10.815954695019173\n",
      "Dynamic Programming 0.001826263003749773\n",
      "i = 9\n",
      "Recursive: 30.390052033006214\n",
      "Dynamic Programming 0.0017969440086744726\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    print('i =', i)\n",
    "    print(\"Recursive:\", Timer('catalan_recursive(n)', 'n = i', globals=globals()).timeit(10000))\n",
    "    print(\"Dynamic Programming\", Timer('catalan_dp(n)', 'n = i', globals=globals()).timeit(10000))"
   ]
  },
  {
   "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}