7_Dictionaries and Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python Dictionaries and Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook provides an opportunity practice using Python *dictionaries* - a useful data structure, that provides a convenient basis for storing and handling data in many different circumstances.\n",
    "\n",
    "### 1) Python Dictionaries\n",
    "\n",
    "We have seen several compound types: i.e.  lists and strings. These group together\n",
    "multiple elements and are all sequence types, i.e. they are inherently ordered. A Python dictionary is another compound type, however it is inherently not ordered but it is instead a mapping type. The essential purpose of a dictionary is very simple: to associate *keys* and *values*. Keys can be strings (e.g. **\"bill\"**), or numbers (e.g. **55**), or even tuples (e.g. the tuple **'(\"bill\",\"bryson\")')**, but **not** ordinary lists. The stored values may be any Python value; strings and numbers are common cases. A key can be paired with *at most one* value, i.e. if we assign a new value to a key, its previous value is lost. \n",
    "\n",
    "#### Getting started\n",
    "\n",
    "Start by trying out some simple operations with the Python interpreter. You can create an *empty* dictionary by assigning the value '{}'. This is illustrated in the example below, which also shows cases of assigning a value to a new key, and of assigning a new value to an existing key. Study the example thoroughly, and be sure you understand each step. When you've done so, try creating a dictionary of your own, to store phone numbers for a few people you know."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "salary = {}\n",
    "salary['al'] = 20000\n",
    "salary['bo'] = 50000\n",
    "print (salary, \"\\n\")\n",
    "\n",
    "print (salary['bo'], \"\\n\")\n",
    "\n",
    "salary['bo'] = 55000\n",
    "salary['al'] += 2000\n",
    "print (salary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Other operations possible on dictionaries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# To prepopulate the dictionary with some name:number pairs\n",
    "tel = { 'alf':111, 'bobby':222, 'calvin':333 }\n",
    "print (tel)\n",
    "\n",
    "# To look up / update values\n",
    "print (tel['bobby'])         # access a value\n",
    "tel['bobby'] = 555     # update a value\n",
    "print (tel)\n",
    "\n",
    "del tel['bobby']    # delete entry with given key\n",
    "print (tel)\n",
    "print (tel.keys())          # get keys\n",
    "print ('alf' in tel)        # also check keys exists\n",
    "print ('dave' in tel)      # again, check keys exist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **keys()** method returns all of the keys in a dictionary. We have to convert the returned object into a list, like we did with *range*. Same rule applies when calling the\n",
    "**values** method that returns the values present in the dictionary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "print (tel.keys())              # get keys\n",
    "print (list(tel.keys()))        # get list of keys\n",
    "print (tel.values())            # get values\n",
    "print (list(tel.values()))      # get list of values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we ask value for a key that is not there, we'll get an error. This is the main issue for correct use of dictionaries and it will crash your code!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# If you're not sure that a value is there, you need to check for it first\n",
    "\n",
    "k = 'eric'\n",
    "if k in tel:\n",
    "    print (k, ':', tel[k])\n",
    "else:\n",
    "    print (k, 'not found!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next explore what happens if we do a *simple iteration* over a dictionary, e.g. a loop of the form **\"for VAR in DICT:\"**. With each cycle, the loop variable is assigned the next key\n",
    "of dictionary, but there is no guarentee as to the order in which keys are returned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tel = {'alf': 111, 'bobby': 222, 'calvin': 333}\n",
    "for k in tel:\n",
    "    print (k, ':', tel[k])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try such a loop with your dictionary, and print the values assigned to **VAR** as the loop runs, so you can see what is assigned, i.e. does it print keys, values or key:value pairs? In the light of this, modify your loop to print the dictionary pairs as statements of the form **\"key = value\"**, e.g.:\n",
    "\n",
    "   <table border=\"1\" style=\"width:auto\">\n",
    "      <tr>\n",
    "        <td>al = 20000\n",
    "        <br>\n",
    "        bo = 50000\n",
    "        <br>\n",
    "        ced = 1500\n",
    "        </td>\n",
    "     </tr>\n",
    "   </table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Perform a simple iteration over the previously defined dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now try doing look-up for a key that is not in the dictionary. This gives an error, as shown in the notes. Avoiding such errors (which will crash your code) is a major issue in using dictionaries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Search for the salary of someone who's not in the dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can check if a key is present in a dictionary with a test of the form **\"KEY in DICT\"**, which returns **True** or **False**, as you will see below. Thus, we can avoid key look-up errors by couching the look-up step within a conditional that has such a test."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print('dave' in salary, \"\\n\")\n",
    "\n",
    "print('bo' in salary)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Sorting\n",
    "\n",
    "We often want to **sort** values into some order: e.g. numbers into *ascending / descending* order, or strings (such as words) into *alphabetic* order. Python provides for sorting of lists with:\n",
    "- **sorted** general function which *returns* a sorted copy of list\n",
    "- **.sort()** called from list which sorts the list \"*in place*\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = [7,11,3,9,2]       # \"sorted\" returns sorted variant of x\n",
    "sorted(x)              # but x itself unchanged\n",
    "print (x)\n",
    "x.sort()               # \".sort()\" modifies list `in-place'\n",
    "print (x)              # so x itself now different"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By default, sorting puts numbers into *ascending* order and strings into standard *alphabetic* order (upper before lower case). We can change default behaviour, using\n",
    "keyword arguments: for example, we can reverse standard sort order as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = [7,11,3,9,2]\n",
    "sorted(x)\n",
    "sorted(x,reverse=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Keyword **key** allows you to supply a *function*. The function computes some alternate value from item (of list being sorted). The items of the list are then sorted on the basis of these alternate values. For 'one-off' functions, we can use *lambda notation*.\n",
    "\n",
    "**Lambda notation**, from maths, is notation for writing functions. For example, what is\n",
    "$x^2 + 1$ - is it a single value, or a function? The expression $\\lambda x.x^2 + 1$ unambiguously denotes a function.\n",
    "\n",
    "In Python: for example\n",
    "\n",
    "    lambda x:(x * x) + 1\n",
    "\n",
    "means give me one input (x) and I'll give you back the result $x^2 + 1$\n",
    "\n",
    "    lambda s:s[1]\n",
    "\n",
    "given item s, computes/returns s[1]. This only makes sense if either:\n",
    "- s is a sequence, so s[1] is its 2nd element, or\n",
    "- s is a dictionary, so s[1] looks up value for key 1\n",
    "\n",
    "An example of using lambda for sorting list of pairs (tuples) by second value (the default sorts by first value)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# First value sort\n",
    "\n",
    "x = [('a', 3), ('c', 1), ('b', 5)]\n",
    "sorted(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To use the lambda expression, use *key* keyword arg, along with the lambda expression. The lambda function looks up second item of each pair and sorting is done based on these alternative values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "x = [('a', 3), ('c', 1), ('b', 5)]\n",
    "sorted(x, key=lambda s:s[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A further keyword arg **cmp** lets you supply a custom two argument function for comparing list items. It should return negative/0/positive value depending on whether the first argument is considered smaller than/same as/bigger than the second.\n",
    "\n",
    "Sometimes we want to address contents of a dictionary in sorted order. This is easy for sort based on order of keys. For example: printing a telephone directory in name order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "tel = {'alf': 111, 'bobby': 222, 'calvin': 333}\n",
    "\n",
    "for k in tel:\n",
    "    print (k, ':', tel[k])\n",
    "\n",
    "for k in sorted(tel):\n",
    "    print (k, ':', tel[k])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is more tricky for sort based on ordering of the values ...\n",
    "\n",
    "May use dictionaries to store numeric values associated with keys, e.g.\n",
    "- density of different metals\n",
    "- share price of companies\n",
    "- how often each possible outcome occurred in a series of experiments\n",
    "\n",
    "May want to handle dictionary in a manner ordered w.r.t. the values, e.g.\n",
    "- print metals in descending order of density\n",
    "- sort companies by share price, so can identify \"top ten\" companies\n",
    "\n",
    "Can use lambda function returning key's value in dictionary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "counts = {'a': 3, 'c': 1, 'b': 5}\n",
    "\n",
    "labels = counts.keys()\n",
    "print (list(labels))\n",
    "\n",
    "list_labels = list(labels)\n",
    "list_labels.sort(key=lambda v:counts[v])\n",
    "print (list_labels)   # puts labels into ascending order of count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another example prints metals in descending order of density"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "densities = {'iron':7.8, 'gold':19.3, 'zinc':7.13, 'lead':11.4}\n",
    "\n",
    "metals = densities.keys()\n",
    "print (list(metals))\n",
    "\n",
    "metals_list = sorted(metals,reverse=True,key=lambda m:densities[m])\n",
    "print (metals_list)\n",
    "\n",
    "for metal in metals_list:\n",
    "    print ('%8s = %5.1f' % (metal,densities[metal]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3) Exercises: lexical analysis\n",
    "\n",
    "To practice using dictionaries, we tackle a simple counting task, specifically, counting the words that appear in a text, as a simple case of lexical analysis. The file mobydick.txt, which contains the text of Melville's classic novel Moby Dick. To simplify later tasks, I have preprocessed the text, converting it to lowercase and removing punctuation. The other files are similarly preprocessed. All the necessary *.txt* files are in **Module 3 ** alongside the notebook.\n",
    "\n",
    "#### Counting words\n",
    "\n",
    "Our first task is to define a function **countWords** that will read through a file, and count the words within it into a dictionary. Your function definition should therefore proceed as follows:\n",
    "\n",
    "   <ol>\n",
    "        <li>create an empty dictionary</li>\n",
    "        <li>open the file for reading - *the name of the file should be an 'input parameter'*, i.e. specified in the function call, as in (e.g.): **countWords('mobydick.txt')**</li>\n",
    "        <li>use a **for**-loop to iterate over the file, reading in the lines of text, one at a time</li>\n",
    "        <li>count each word in the line into the dictionary - *we'll come back to this step in a moment*</li>\n",
    "        <li>when counting is complete, use a **return** statement, to *return* the dictionary of counts</li>\n",
    "   </ol>\n",
    "   \n",
    "To get the words from a line of text, we can use the **\".split()\"** method, which divides up a string at the places where *spaces* appear, returning the sub-strings as a list. Run the following cell to test this function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "s = 'this is a line'\n",
    "s.split()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In our function, as we read through the file, we can call the **.split()** method on each line, and use an embedded **for**-loop to iterate over the words returned, counting each into the dictionary. The dificulty in coding this task is *avoiding errors* from trying to look up keys (words) not already present in the dictionary. Hence, we must first check if a word is present (as shown earlier): if it is, we add one to its existing score, if it is not, we simply assign it a count of 1.\n",
    "\n",
    "Test your function definition by applying it to file **mobypara.txt** (containing a short extract from *Moby Dick*). Print out the dictionary of counts it returns, to check that the results look okay."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Insert your countWords function here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### II) Sorting and ranking\n",
    "\n",
    "Next, define a function **printTop20**, which is given a dictionary of counts, and prints out the 20 words with the highest frequencies, e.g. so a call **printTop20(counts)** would print out the 20 words with the highest counts, in descending order of frequency, each along with its count (e.g. in the form **\"word = count\"**, one word per line). Use file **mobypara.txt** for testing, and refer to the slides on \"Sorting Dictionaries by Value\" for help. When your definition works, apply it to the file **mobydick.txt** to determine the most common words in this large English text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Insert your printTop20 function in this cell and test it, first for mobypara.txt file and after for mobydickt.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### III) Stopwords\n",
    "\n",
    "If your code works, you'll find the most common terms to be *the*, *of*, *and*, *a*, *to*, *in*, etc., which are common in **all** English texts. Such words are of little use for discriminating between texts on different topics (e.g. sport vs. politics), a fact addressed in *language processing* applications (e.g. *information retrieval*: the technology behind *web browsers*) by putting them into a list of so-called *stopwords*, words that are *ignored* during the general counting of words in texts.\n",
    "\n",
    "The file **stopwords.txt**, provided with the other data files, contains a list of stopwords for English. Write a function **readStopWords** which reads in the words, and *returns* them as a list of strings. The function might be called (e.g.) as : **stops = readStopWords('stopwords.txt')** **Warning**: although the file has only one word per line, the lines of text that you read from it are *not* the correct strings for the words, because they include a final *linebreak* character that needs to be stripped off (e.g. using the **\".strip()\"** method, as in: **\"word = line.strip()\"**).\n",
    "\n",
    "Having defined the **readStopWords** function, modify your definition of **countWords** so that it takes a second parameter, a list of stopwords, and then only counts words from the text that are **not** stopwords. (You can check that an item **I** is not in a list **L** with the test **\"I not in L\"**.)\n",
    "\n",
    "Apply your modified definition of **countWords** to the full *Moby Dick* text, whilst supplying it with a list of stopwords, and print out the top-ranked words of the text by frequency again. Compare this to the set of words produced *without* of stopword list (which you should be able to reproduce now by supplying your new function definition with an *empty* stopword list). The two sets should look very different. Which do you think better captures the 'topic' of the text?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Insert your readStopWords function here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# After creating the previous function and making sure it works well, modify the countWords fuction from above and add it here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### IV) Extra Exercise: Similarity\n",
    "\n",
    "The data includes files **george01.txt . . . george04.txt**, which are news articles (that have again been *preprocessed*), which each mention a *George*: two concerning the death of the famous footballer *George Best*; the other two another George. A key question is whether we can detect that two fles share the same topic based on the words that they share.\n",
    "\n",
    "We can measure *similarity* by computing a simple metric of *lexical overlap* that ignores the counts of the words in the texts, and instead simply asks what *proportion* of the *distinct words* found in either file are *shared*. To count the number of words shared, we can simply iterate over one dictionary (i.e. using a **for**-loop), and for each word test its presence in the second dictionary (running a count of the words found in both). We can find out how many words there are in a single dictionary by using the **len** function (e.g. so \"len(d)\" returns the number of keys in dictionary **d**). If we simply add together the sizes of the two dictionaries, then we end up counting those words that appear in both dictionaries *twice*. However, we can correct for this by *subtracting* our count of the words in the overlap. Thus, if our dictionaries **d1** and **d2** share **N** words, then our similarity score would be **\"N / (len(d1) + len(d2) - N)\"** (taking care about integer division).\n",
    "\n",
    "Define a function **similarity**, which takes two dictionaries of word counts as arguments, and computes the above measure of similarity. Apply your function to compute similarity scores for each pair of texts from the *'George'* collection. Do the scores help identify the documents that share a topic? Are the scores better for this purpose when you do/do not use a list of stopwords?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Insert your definition for the similarity function in this cell"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}