Swadesh viewer for dictionary data.ipynb

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Swadesh viewer for dictionary data\n",
      "\n",
      "In this tutorial we will demonstrate how to extract entries that contain words from a [Swadesh list](http://en.wikipedia.org/wiki/Swadesh_list) from data in digitized dictionaries. The translation graph connects entries in dioctionaries, via annotation for \"heads\" and \"translations\" within the dictionary. We will demonstrate how to visualize this data with a plotting library and hwo to export parts of the graph to JSON for interactive visualizations in the web.\n",
      "\n",
      "You can download this tutorial as [IPython notebook](http://ipython.org/ipython-doc/dev/interactive/htmlnotebook.html) here:\n",
      "\n",
      "https://github.com/pbouda/notebooks/blob/master/Swadesh%20viewer%20for%20dictionary%20data.ipynb"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Data\n",
      "\n",
      "For this tutorial we will use data from the project \"[Quantitative Historical Linguistics](http://www.quanthistling.info/)\". The website of the project provides a ZIP package of GrAF/XML files for the printed sources that were digitized within the project:\n",
      "\n",
      "http://www.quanthistling.info/data/downloads/xml/data.zip\n",
      "\n",
      "The ZIP package contains several files encoded as described in the [ISO standard 24612](http://www.iso.org/iso/catalogue_detail.htm?csnumber=37326) \"Linguistic annotation framework (LAF)\". The QuantHistLing data contains dictionary and wordlist sources. Those were first tokenized into entries, for each entry you will find annotations for at least the head word(s) (\"head\" annotation) and translation(s) (\"translation\" annotation) in the case of dictionaries. We will only use the dictionaries of the \"Witotoan\" compoment in this tutorial. The ZIP package also contains a CSV file \"sources.csv\" with some information for each source, for example the languages as ISO codes, type of source, etc. Be aware that the ZIP package contains a filtered version of the sources: only entries that contain a Spanish word that is part of the Spanish swadesh list are included in the download package.\n",
      "\n",
      "For a simple example how to parse one of the source please see here:\n",
      "\n",
      "http://graf-python.readthedocs.org/en/latest/Querying%20GrAF%20graphs.html\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## What are translation graphs?\n",
      "\n",
      "In our case, translation graphs are graphs that connect all spanish translation with every head word that we find for each translation in our sources. The idea is that spanish is some kind of interlingua in our case: if a string of a spanish translation in one source matches a string in another source this will only be *one* node in our graph. For the head words, this is not the case: matching strings in head words in different source are different nodes in the graph. This holds even if the different sources describe the same language, as different sources will use different orthographies. \n",
      "\n",
      "To fullfil that need, head words are internally represented as a string with two parts: the head word and its source. Both parts are seperated by a pipe symbol \"|\". For example, in a [DOT file](http://en.wikipedia.org/wiki/DOT_language) such a node looks like this:\n",
      "\n",
      "> \"\u00f3c\u00e1ji|thiesen1998\" [lang=boa, source=thiesen1998_25_339];\n",
      "\n",
      "The square brackets contain additional attributes here. These attributes are not part of the node's name, they contain just additonal information that we store with the nodes.\n",
      "\n",
      "In comparison, a spanish translation looks like this:\n",
      "\n",
      "> \"vaca\" [lang=spa];\n",
      "\n",
      "There is no attribute \"source\" here, as this translation might occur in several sources. An edge connecting the two nodes looks like this:\n",
      "\n",
      "> \"vaca\" -- \"\u00f3c\u00e1ji|thiesen1998\";\n",
      "\n",
      "To handle such graphs our scripts use the [NetworkX Python library](http://networkx.lanl.gov/)."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Requirements\n",
      "\n",
      "The following Python libraries are required to process the GrAF/XML files and create the translation graphs:\n",
      "\n",
      "* NetworkX: http://networkx.lanl.gov/\n",
      "* graf-python: https://github.com/cidles/graf-python\n",
      "* requests: http://docs.python-requests.org/en/latest/ (only if you want automated download of the data)\n",
      "\n",
      "To visualize the graphs we use the [D3.js](http://d3js.org/) library, but we will load this on-the-fly when we start with the visualization."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import os\n",
      "import csv\n",
      "import codecs\n",
      "import re\n",
      "import glob\n",
      "\n",
      "import networkx\n",
      "import graf"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Get Witotoan sources\n",
      "\n",
      "In the first step we download and extract the data. You may change to a local \"tmp\" directory before the download or just download the data to the current working directory. For this you need to install the Python library `requests`. You may also download and extract the data manually, the data is only downloaded for you if the file `sources.csv` is not found."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "os.chdir(\"/Users/pbouda/Projects/git-github/notebooks/swadeshviewer\")\n",
      "if not os.path.exists(\"sources.csv\"):\n",
      "    import requests\n",
      "    import zipfile\n",
      "    r = requests.get(\n",
      "        \"http://www.quanthistling.info/data/downloads/xml/data.zip\")\n",
      "    with open(\"data.zip\", \"wb\") as f:\n",
      "        f.write(r.content)\n",
      "\n",
      "    z = zipfile.ZipFile(\"data.zip\")\n",
      "    z.extractall()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now we open the file \"sources.csv\" and read out all the sources that are part of the component \"Witotoan\" and that are dictionaries. We will store a list of those source in `witotoan_sources`:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sources = csv.reader(open(\"sources.csv\", \"rU\"), delimiter=\"\\t\")\n",
      "witotoan_sources = list()\n",
      "for source in sources:\n",
      "    if source[5] == \"Witotoan\" and source[1] == \"dictionary\":\n",
      "        witotoan_sources.append(source[0])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## GrAF to NetworkX\n",
      "\n",
      "Next we define a helper function that transform a GrAF graph into a networkx graph. For this we traverse the graph by querying for all entries. For each entry we look for connected nodes that have \"head\" or \"translation\" annotation. All of those nodes that are Spanish are stored in the list `spa`. All non-Spanish annotations are stored in `others`. In the end the collected annotation are added to the new networkx graph, and each spanish node is connected to all the other nodes for each entry:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def graf_to_networkx(graf, source = None):\n",
      "    g = networkx.Graph()\n",
      "    for (node_id, node) in graf.nodes.items():\n",
      "        spa = list()\n",
      "        others = dict()\n",
      "        if node_id.endswith(\"..entry\"):\n",
      "            _, page, pos_on_page, _ = node_id.split(\"..\")\n",
      "            for e in node.out_edges:\n",
      "                if e.annotations.get_first().label == \"head\" or e.annotations.get_first().label == \"translation\":\n",
      "                    # get lang\n",
      "                    for n in e.to_node.links[0][0].nodes:\n",
      "                        if n.annotations.get_first().label == \"iso-639-3\":\n",
      "                            if n.annotations.get_first().features.get_value(\"substring\") == \"spa\":\n",
      "                                spa.append(e.to_node.annotations.get_first().features.get_value(\"substring\"))\n",
      "                                break\n",
      "                            else:\n",
      "                                others[e.to_node.annotations.get_first().features.get_value(\"substring\")] = n.annotations.get_first().features.get_value(\"substring\")\n",
      "                                break\n",
      "            if len(spa) > 0:\n",
      "                for head in spa:\n",
      "                    g.add_node(head, attr_dict={ \"lang\": \"spa\" })\n",
      "                    for translation in others:\n",
      "                        g.add_node(u\"{0}|{1}\".format(translation, source), attr_dict={\n",
      "                            \"lang\": others[translation],\n",
      "                            \"source\": source,\n",
      "                            \"page\": page,\n",
      "                            \"pos_on_page\": pos_on_page\n",
      "                        })\n",
      "                        g.add_edge(head, u\"{0}|{1}\".format(translation, source))\n",
      "    return g"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Parse GrAF/XML files\n",
      "\n",
      "Now we parse all the XML files of the extracted ZIP package. For this we traverse through all the directories that have a name in `witotoan_sources'. The files we are looking for are the \"-dictinterpretation.xml\" files within each directory, as those contain the annotations for \"heads\" and \"translations\".\n",
      "\n",
      "First we create an empty list `graphs` that will later store all the networkx graphs:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "parser = graf.GraphParser()\n",
      "graphs = []"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Then we loop through all the Witotoan sources, parse the XML files and transform the graphs into networkx graph by calling the helper function that we defined above. We print a progress report within the loop, as parsing and transformation might take some time:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for d in witotoan_sources:\n",
      "    for f in glob.glob(os.path.join(d, \"dict-*-dictinterpretation.xml\")):\n",
      "        print(\"Parsing {0}...\".format(f))\n",
      "        graf_graph = parser.parse(f)\n",
      "        g = graf_to_networkx(graf_graph, d)\n",
      "        graphs.append(g)\n",
      "print(\"OK\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Parsing thiesen1998/dict-thiesen1998-25-339-dictinterpretation.xml...\n",
        "Parsing minor1987/dict-minor1987-1-126-dictinterpretation.xml..."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Parsing minor1971/dict-minor1971-3-74-dictinterpretation.xml..."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Parsing burtch1983/dict-burtch1983-19-262-dictinterpretation.xml..."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Parsing leach1969/dict-leach1969-67-161-dictinterpretation.xml..."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Parsing walton1997/dict-walton1997-9-120-dictinterpretation.xml..."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Parsing preuss1994/dict-preuss1994-797-912-dictinterpretation.xml..."
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "OK"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Merge all graphs\n",
      "\n",
      "Now we can merge all the individual graphs for each source into one big graph. This will collapse all Spanish nodes and so connect the nodes that have a common Spanish translation:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import copy\n",
      "combined_graph = copy.deepcopy(graphs[0])\n",
      "for gr in graphs[1:]:\n",
      "    for node in gr:\n",
      "        combined_graph.add_node(node, gr.node[node])\n",
      "    for n1, n2 in gr.edges_iter():\n",
      "        combined_graph.add_edge(n1, n2, gr.edge[n1][n2])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We count the nodes in the graph and the [number of connected components](http://networkx.lanl.gov/reference/generated/networkx.algorithms.components.connected.number_connected_components.html#networkx.algorithms.components.connected.number_connected_components) to get an impression how the graph \"looks\". The number of nodes is much higher then the number of connected components, so we already have a lot of the nodes connected in groups, either as a consequence from being part of one dictionary entry or through the merge we did via the Spanish node:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "len(combined_graph.nodes())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "23749"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "networkx.algorithms.components.number_connected_components(combined_graph)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "4614"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Extract a subgraph for all the words in the Spanish Swadesh list\n",
      "\n",
      "Next we will extract a subgraph from full graph. We will only search for nodes that have a Spanish word that is a part of the [Swadesh list](http://en.wikipedia.org/wiki/Swadesh_list). The [Natural Language Toolkit (NLTK)](http://www.nltk.org/) contains Swadesh lists for several languages and we will use NLTK's version of the Spanish list. You don't need to install the NLTK library (although I recommend learning about it!), as we will load the data directly from the NLTK github repository. Again, we use `requests` to download the data, but you may also download and extract the data manually.\n",
      "\n",
      "First we download and extract the Swadesh data:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "#os.chdir(\"c:/Users/Peter/Documents/Corpora/qlc\")\n",
      "if not os.path.exists(os.path.join(\"swadesh\", \"es\")):\n",
      "    import requests\n",
      "    import zipfile\n",
      "    r = requests.get(\n",
      "        \"https://github.com/nltk/nltk_data/blob/gh-pages/packages/corpora/swadesh.zip?raw=true\")\n",
      "    with open(\"swadesh.zip\", \"wb\") as f:\n",
      "        f.write(r.content)\n",
      "\n",
      "    z = zipfile.ZipFile(\"swadesh.zip\")\n",
      "    z.extractall()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Next, we get all the Spanish words from the Swadesh file:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "swadesh_words = list()\n",
      "with codecs.open(os.path.join(\"swadesh\", \"es\"), \"r\", \"utf-8\") as f:\n",
      "    for line in f:\n",
      "        swadesh_words.append(line.strip())"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now we are ready to loop through the graph and find all nodes are part of the Swadesh list. We will store all those nodes and their connections in seperate graphs, one graph for each Swadesh term. This allows us to use different word lists later, for example to extract semantic domains like *body parts*, *food*, etc."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "swadesh_graphs = list()\n",
      "for i, _ in enumerate(swadesh_words):\n",
      "    swadesh_graphs.append(networkx.Graph())\n",
      "    \n",
      "for node in combined_graph:\n",
      "    if \"lang\" in combined_graph.node[node] and \\\n",
      "            combined_graph.node[node][\"lang\"] == \"spa\":\n",
      "        # get the index of the word in the Swadesh list\n",
      "        swadesh_index = -1\n",
      "        for i, swadesh in enumerate(swadesh_words):\n",
      "            concepts = [x.strip() for x in swadesh.split(',')]\n",
      "            if node in concepts:\n",
      "                swadesh_index = i\n",
      "                break\n",
      "        if swadesh_index == -1:\n",
      "            continue\n",
      "        swadesh_graphs[swadesh_index].add_node(node)\n",
      "        \n",
      "        for n in combined_graph[node]:\n",
      "            if \"lang\" in combined_graph.node[n] and \\\n",
      "                    combined_graph.node[n][\"lang\"] != \"spa\":\n",
      "                word, source = n.split(\"|\")\n",
      "                lang = combined_graph.node[n][\"lang\"]\n",
      "                page = combined_graph.node[n][\"page\"]\n",
      "                pos_on_page = combined_graph.node[n][\"pos_on_page\"]\n",
      "                swadesh_graphs[swadesh_index].add_node(lang)\n",
      "                swadesh_graphs[swadesh_index].add_edge(node, lang)\n",
      "                swadesh_graphs[swadesh_index].add_node(word,\n",
      "                    attr_dict={ \"data_source\": source,\n",
      "                                \"page\": page,\n",
      "                                \"pos_on_page\": pos_on_page })\n",
      "                swadesh_graphs[swadesh_index].add_edge(lang, word)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 15
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Export the subgraph as JSON data\n",
      "\n",
      "Another method to visualize the graph is the [D3 Javascript library](http://d3js.org/). For this we need to export the graph as JSON data that will be loaded by a HTML document. The networkx contains a `networkx.readwrite.json_graph` module that allows us to easily transform the graph into a JSON document. The JSON data structure can then be writte to a file with the help of the Python `json` module:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from networkx.readwrite import json_graph\n",
      "import json\n",
      "\n",
      "for i, g in enumerate(swadesh_graphs):\n",
      "    json_data = json_graph.node_link_data(g)\n",
      "    json.dump(json_data, codecs.open(\"swadesh_data_{0}.json\".format(i), \"w\", \"utf-8\"))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "json.dump(swadesh_words, codecs.open(\"swadesh_list.json\", \"w\", \"utf-8\"))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 17
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Finally we need to create a HTML file to display the data. You can download an HTML file form here:\n",
      "\n",
      "https://github.com/pbouda/notebooks/blob/master/swadeshviewer/index.html\n",
      "\n",
      "Put the file `index.html` into the folder with the JSON files. Then open the file in any browser. You can view an online version here:\n",
      "\n",
      "http://www.peterbouda.eu/tutorials/swadeshviewer/index.html\n",
      "\n"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}