COS 226 Programming Assignment Checklist: WordNet

Frequently Asked Questions

Is a vertex considered an ancestor of itself? Yes, this is the typical convention.

Can I assume the id numbers will be integers in a small range? Yes, if there are V synsets, the ids will be numbered 1 through V (sorry, not the usual 0 through V-1).

Should my program work on datasets other than WordNet? Absolutely. It should work on any datasets in the appropriate format.

Should SAP work if the digraph is not a DAG? Yes, the definition still applies in the presence of cycles.

Some of the glosses have example sentences at the end. What is this? That's just part of the gloss.

Any advice on how to read in and parse the data files? Use the readLine() method in our In library to read in the data, one line at a time. Use the split() method in Java's String library to divide a line into fields. Use Integer.parseInt() to convert string id numbers into integers.

I'm an ontologist and I noticed that your hypernyms.txt file contains both is-a and is-instance-of relationships. Yes, you caught us. This ensures that every noun (except entity) has a hypernym. Here is an article on the subtle distinction.

Input, Output, and Testing

Input and output. We encourage you to create your own (possibly pathological) inputs to help test your program. If your datasets create problems for other programs (or ours!), we'll award extra credit. The input should be very small, and it should expose a potential flaw that other programs are likely to face. In your readme.txt, you should describe what the input is testing.

Extra credit. Submit either an interesting example (or corner case) that you used to test your code, preferably a case that arises in the WordNet digraph (and one that uses everyday words). But you can also make up your own small synsets.txt and hypernyms.txt files.

• Find a synset with several paths to the same ancestor (preferably consisting of everyday entities).
• Find two synsets with different paths to common ancestors.
• Find two synsets that have no common ancestors.
• Find two nouns that have the largest (finite) distance between them.
• Find the noun with the most ancestors.
• Find some interesting outcast input files.

Submission and readme

Here is a template readme.txt file. It should contain the following information:

Possible progress steps

• Download the directory wordnet. It contains the WordNet data files synsets.txt and hypernyms.txt described in the assignment.

• Read in and parse the files synsets.txt and hypernyms.txt. Don't worry about storing the data in any data structures yet. Test that you are parsing the input correctly before proceeding.

• Create a data type WordNet. Divide the constructor into two subtasks.

  • Read in the synsets.txt file and build appropriate data structures.

  • Read in the hypernyms.txt file and build a Digraph.

  If you read in synsets.txt first, you can identify largest id before constructing the Digraph. Check that it is 81,426, but do not hardwire this number into your program.

• Add the method isNoun() and glosses(). If you chose appropriate data structures when parsing synsets.txt, this step will be relatively easy.

  Try some nouns that participate in many synsets, e.g., run, face and back.

• Create the data type SAP. This step can and should be done without using WordNet. First, think carefully about designing a correct and efficient algorithm for computing the shortest ancestral path. Consult a staff member if you're unsure. Design small DAGs to test and debug your code.

Optional Optimizations

There are a few things you can do to speed up a sequence of SAP computations on the same digraph.

• The bottleneck operations is re-initializing arrays of length V to perform the computation. This should be done once for the first SAP computation, but for subsequent ones, you can remember which array entries changed in the previous computation, and only re-initialize those entries. Since only a small number of entries will change, this can lead to dramatic savings.

• To compute the distance between two nouns A and B, you compute the SAP between all pairs of synsets of A and synsets of B, and return the shortest such one. Naively, this involves a * b SAP calculations if A is involved in a synsets and B is involved in b synsets. However, it's possible to compute the overall shortest SAP with one or two graph searches (as opposed to a*b).