Assignment 5
Due: 11:00 AM on Friday, October 21, 2011
Question #1
An n-gram, n greater than or equal to 2, is a sequence of n
non-whitespace characters. The n-gram frequency
matrix associated with a textfile is a matrix NM indexed by the n-grams
in the textfile such that the entry for n-gram x in this matrix is
the total number of occurrences of x in the textfile divided by
the total number of n-grams in the textfile.
Given two textfiles X and Y, let the similarity score between these
textfiles be defined as Sim(X, Y) = 1.0 - (Diff(X, Y)/2.0), where
Diff(X,Y) is the sum over all possible n-grams of the absolute values
of the differences in frequency of occurrence of each n-gram in textfiles
X and Y.
Write and document a Python script tcomp5.py which takes as
command-line arguments a master textfile, a value of n, and two or more comparison
textfiles and prints (1) the similarity of the master textfile and each comparison textfile
and (2) the name of the comparison file that is most similar to the
master textfile.
Your script must work on datafiles
nm1.dat,
nm2.dat,
nm3.dat,
nm4.dat, and
nm5.dat
to produce the output given in typescript-file
tcomp5.script.
Your code must implement the similarity computation using dictionaries to encode the
non-zero entries in n-gram frequency matrices.
You may assume that each given textfile has at least one word, i.e., no given
textfile is composed entirely of whitespace characters.
Question #2
Hints
You may find the answer scripts for Assignment #4 of use.
Submission
Please hand in printed copies of all of your Python script files.
You must also submit these files electronically using the
submit-assignment command.
Note that each script file must have the following comment
block at the top, where the X's are replaced with the appropriate
information, followed by a docstring briefly describing the program in that
script. For instance, my script for Question #1 of this assignment would
begin with the following comment block:
#########################################################
## CS 2500 (Fall 2011), Assignment #5, Question #1 ##
## Script File Name: tcomp5.py ##
## Student Name: Todd Wareham ##
## Login Name: harold ##
## MUN #: 8008765 ##
#########################################################
You do not have to develop your code on our CS departmental systems.
However, as your code will be compiled and tested on our CS departmental
systems as part of the assignment marking process,
you should ensure that your code compiles and runs correctly on at
least one of these systems.
- October 18, 2:05pm
Error in Question #1 of Assignment #5 (incorrect program results in script
file) fixed.
- August 15, 3:15pm
Assignment #5 posted.
Created: August 15, 2011
Last Modified: October 18, 2011