Skip to content

Instantly share code, notes, and snippets.

@fabgoos

fabgoos/mrjob_inverted_index.ipynb

Created March 4, 2015 17:22
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save fabgoos/1abc0d2aad8d7215c75d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save fabgoos/1abc0d2aad8d7215c75d to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
mrjob_inverted_index.ipynb
{
"metadata": {
"name": "",
"signature": "sha256:fe53ee65cd50ca3911ccb1599ad48b058d34620c986ea437a0be5b1e94d4f435"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Inverted index calculation with mrjob\n",
"===\n",
"\n",
"This is a very simple and straighforward implementation of an inverted index calculation process using [mrjob](https://pythonhosted.org/mrjob). \n",
"\n",
"The following code is not run directly in the notebook, but instead it is saved to the current directory using the `%%writefile` command."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%writefile mr_wc.py\n",
"# this is the same example from the mrjob distribution. Just showing how to run it from inside a notebook\n",
"\n",
"from mrjob.job import MRJob\n",
"\n",
"class MRWordCountUtility(MRJob):\n",
"\n",
" def __init__(self, *args, **kwargs):\n",
" super(MRWordCountUtility, self).__init__(*args, **kwargs)\n",
" self.chars = 0\n",
" self.words = 0\n",
" self.lines = 0\n",
"\n",
" def mapper(self, _, line):\n",
" # Don't actually yield anything for each line. Instead, collect them\n",
" # and yield the sums when all lines have been processed. The results\n",
" # will be collected by the reducer.\n",
" self.chars += len(line) + 1 # +1 for newline\n",
" self.words += sum(1 for word in line.split() if word.strip())\n",
" self.lines += 1\n",
"\n",
" def mapper_final(self):\n",
" yield('chars', self.chars)\n",
" yield('words', self.words)\n",
" yield('lines', self.lines)\n",
"\n",
" def reducer(self, key, values):\n",
" yield(key, sum(values))\n",
"\n",
"if __name__ == '__main__':\n",
" MRWordCountUtility.run()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Overwriting mr_wc.py\n"
]
}
],
"prompt_number": 53
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The directory contains now the python source as well as other files.\n",
"\n",
"The following command lists the contents of the directory:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"!ls"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"14826.txt 14840.txt\r\n",
"14828.txt files.in\r\n",
"14829.txt google_ngram.ipynb\r\n",
"14832.txt mr_inverted_index.py\r\n",
"14833.txt mr_wc.py\r\n",
"14839.txt mrjob_inverted_index.ipynb\r\n"
]
}
],
"prompt_number": 71
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we run the program with an input text file. The actual output of the program is at the end, three lines starting with \"chars\", \"lines\" and \"words\". The other lines are informative messages from mrjob."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"!python mr_wc.py < 14826.txt"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"no configs found; falling back on auto-configuration\r\n",
"no configs found; falling back on auto-configuration\r\n",
"creating tmp directory /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_wc.fgonza.20150304.171640.111001\r\n",
"reading from STDIN\r\n",
"writing to /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_wc.fgonza.20150304.171640.111001/step-0-mapper_part-00000\r\n",
"Counters from step 1:\r\n",
" (no counters found)\r\n",
"writing to /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_wc.fgonza.20150304.171640.111001/step-0-mapper-sorted\r\n",
"> sort /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_wc.fgonza.20150304.171640.111001/step-0-mapper_part-00000\r\n",
"writing to /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_wc.fgonza.20150304.171640.111001/step-0-reducer_part-00000\r\n",
"Counters from step 1:\r\n",
" (no counters found)\r\n",
"Moving /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_wc.fgonza.20150304.171640.111001/step-0-reducer_part-00000 -> /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_wc.fgonza.20150304.171640.111001/output/part-00000\r\n",
"Streaming final output from /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_wc.fgonza.20150304.171640.111001/output\r\n",
"\"chars\"\t4691\r\n",
"\"lines\"\t86\r\n",
"\"words\"\t713\r\n",
"removing tmp directory /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_wc.fgonza.20150304.171640.111001\r\n"
]
}
],
"prompt_number": 93
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The following program implements an inverted indexing process using mrjob. "
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%writefile mr_inverted_index.py\n",
"from mrjob.job import MRJob\n",
"import os\n",
"import re\n",
"\n",
"WORD_RE = re.compile(r\"[\\w']+\")\n",
"\n",
"\n",
"class MRInvertedIndex(MRJob):\n",
"\n",
" def __init__(self, *args, **kwargs):\n",
" super(MRInvertedIndex, self).__init__(*args, **kwargs)\n",
"\n",
" def read_files(self, _, line):\n",
" filein = open(original_path + '/' + line)\n",
" for linein in filein:\n",
" yield(line, linein.strip())\n",
" \n",
" def find_words(self, filename, line):\n",
" for word in WORD_RE.findall(line):\n",
" word = word.lower()\n",
" yield (word, filename)\n",
" \n",
" def posting_lists(self, word, files):\n",
" yield (word, list(files))\n",
"\n",
" def steps(self):\n",
" # This function specifies the process pipeline. In this case we have a two-phases map-reduce process. \n",
" # The first phase process the input files and creates an entry per each file line. The second phase \n",
" # processes the lines and build the inverted index. The first process only has a mapper function,\n",
" # while the second one has both mapper and reducer.\n",
" return [self.mr(mapper=self.read_files),\n",
" self.mr(mapper=self.find_words,\n",
" reducer=self.posting_lists)]\n",
"\n",
"if __name__ == '__main__':\n",
" original_path = os.getcwd()\n",
" MRInvertedIndex.run()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Overwriting mr_inverted_index.py\n"
]
}
],
"prompt_number": 94
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"First we have to create a file with the list of files that we will process. In this case we list all the *.txt files in the current directory."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"!ls *.txt > files.in"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 95
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"!cat files.in"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"14826.txt\r\n",
"14828.txt\r\n",
"14829.txt\r\n",
"14832.txt\r\n",
"14833.txt\r\n",
"14839.txt\r\n",
"14840.txt\r\n"
]
}
],
"prompt_number": 96
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now we can run the program. The results are put in the file result.out."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"!python mr_inverted_index.py < files.in > result.out"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"no configs found; falling back on auto-configuration\r\n",
"no configs found; falling back on auto-configuration\r\n",
"creating tmp directory /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302\r\n",
"reading from STDIN\r\n",
"writing to /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302/step-0-mapper_part-00000\r\n",
"Counters from step 1:\r\n",
" (no counters found)\r\n",
"writing to /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302/step-1-mapper_part-00000\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Counters from step 2:\r\n",
" (no counters found)\r\n",
"writing to /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302/step-1-mapper-sorted\r\n",
"> sort /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302/step-1-mapper_part-00000\r\n",
"writing to /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302/step-1-reducer_part-00000\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Counters from step 2:\r\n",
" (no counters found)\r\n",
"Moving /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302/step-1-reducer_part-00000 -> /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302/output/part-00000\r\n",
"Streaming final output from /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302/output\r\n",
"removing tmp directory /var/folders/vz/rkqml9x917v4m1dfz713y0q00000gn/T/mr_inverted_index.fgonza.20150304.171715.767302\r\n"
]
}
],
"prompt_number": 97
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We show some results from the output file, which have 785 lines in total."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"!wc result.out\n",
"!head -100 result.out | tail -20\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
" 785 2738 33250 result.out\r\n"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\"april\"\t[\"14826.txt\", \"14840.txt\", \"14840.txt\"]\r\n",
"\"arbitration\"\t[\"14839.txt\"]\r\n",
"\"are\"\t[\"14826.txt\", \"14826.txt\", \"14826.txt\", \"14826.txt\", \"14826.txt\", \"14828.txt\", \"14833.txt\", \"14839.txt\", \"14840.txt\", \"14840.txt\", \"14840.txt\", \"14840.txt\"]\r\n",
"\"around\"\t[\"14833.txt\"]\r\n",
"\"as\"\t[\"14826.txt\", \"14826.txt\", \"14840.txt\"]\r\n",
"\"asia's\"\t[\"14826.txt\"]\r\n",
"\"asian\"\t[\"14826.txt\", \"14826.txt\"]\r\n",
"\"asked\"\t[\"14826.txt\"]\r\n",
"\"association\"\t[\"14826.txt\"]\r\n",
"\"at\"\t[\"14826.txt\", \"14826.txt\", \"14826.txt\", \"14839.txt\", \"14839.txt\", \"14840.txt\", \"14840.txt\"]\r\n",
"\"august\"\t[\"14829.txt\"]\r\n",
"\"australia\"\t[\"14839.txt\"]\r\n",
"\"australia's\"\t[\"14826.txt\", \"14826.txt\"]\r\n",
"\"australian\"\t[\"14826.txt\", \"14839.txt\"]\r\n",
"\"avowed\"\t[\"14826.txt\"]\r\n",
"\"awaiting\"\t[\"14826.txt\"]\r\n",
"\"aware\"\t[\"14826.txt\"]\r\n",
"\"bad\"\t[\"14828.txt\"]\r\n",
"\"baht\"\t[\"14832.txt\", \"14832.txt\", \"14832.txt\"]\r\n",
"\"ban\"\t[\"14839.txt\", \"14839.txt\", \"14839.txt\"]\r\n"
]
}
],
"prompt_number": 98
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment