COS 226 Programming Assignment


WordNet is a semantic lexicon for the English language that is used extensively by computational linguists and cognitive scientists. WordNet groups words into sets of synonyms called synsets and describes semantic relationships between them. One such relationship is the is-a relationship, which connects a hyponym (more specific synset) to a hypernym (more general synset). For example, a plant organ is a hypernym to plant root and plant root is a hypernym to carrot.

The WordNet DAG. Your first task is to build the WordNet graph: each vertex v is an integer that represents a synset, and each directed edge v→w represents that w is a hypernym of v. The graph is directed and acyclic (a DAG), though not necessarily a tree since a synset can have several hypernyms. A small subgraph of the WordNet graph is illustrated below.

We now describe the two data files that you will use to create the WordNet digraph. The files are in CSV format: each line contains a sequence of fields, separated by commas.

Efficiently implement an immutable data type WordNet with the following API:

// constructor takes the name of the two input files
public WordNet(String synsets, String hypernyms)

// return all of the glosses associated with a given noun's synsets
public Iterable<String> glosses(String noun)

// is the word a WordNet noun?
public boolean isNoun(String word)

// return the distance between nounA and nounB (defined below); -1 if infinite
public int distance(String nounA, String nounB)

// return the synset (second field of synsets.txt) that is the common ancestor
// of nounA and nounB in a shortest ancestral path; null if no such path (defined below)
public String sap(String nounA, String nounB)

Shortest ancestral path. An ancestral path between two vertices v and w in a digraph is a directed path from v to a common ancestor x, together with a directed path from w to the same ancestor x. A shortest ancestral path is an ancestral path of minimum total length. For example, in the digraph at left, the shortest ancestral path between 3 and 11 has length 4 (with common ancestor 1). In the digraph at right, one ancestral path between 1 and 5 has length 4 (with common ancestor 5), but the shortest ancestral path has length 2 (with common ancestor 0).

Implement an immutable data type SAP with the following API:

// constructor
public SAP(Digraph G)

// return length of shortest ancestral path of v and w; -1 if no such path
public int length(int v, int w)

// return a common ancestor of v and w that participates in a shortest ancestral path; -1 if no such path
public int ancestor(int v, int w)
Also, include a main() that takes the name of a digraph input file (standard format used by Digraph) as a command-line argument, constructs the digraph, reads in vertex pairs from standard input (for illustration purposes, the text that you type is shown in bold), and prints out the length of the shortest ancestral path between the two vertices and a common ancestor that participates in that path.
% more digraph1.txt             % java SAP digraph1.txt
13                               3 11
11                               sap = 4, ancestor = 1
 7  3                            
 8  3                            9 12
 3  1                            sap = 3, ancestor = 5
 4  1
 5  1                            7 2
 9  5                            sap = 4, ancestor = 0
10  5
11 10                            1 6
12 10                            sap = -1, ancestor = -1
 1  0
 2  0

Measuring the semantic relatedness of two nouns. Semantic relatedness refers to the degree to which two concepts are related. Measuring semantic relatedness is a challenging problem. For example, most of us agree that George Bush and John Kennedy (two US presidents) are more related than are George Bush and chimpanzee (two primates). However, not most of us agree that George Bush and Eric Arthur Blair are related concepts. But if one is aware that George Bush and Eric Arthur Blair (aka George Orwell) are both communicators, then it becomes clear that the two concepts might be related.

We estimate the semantic relatedness of two nouns distance(A, B) as follows:

Using this notion of distance, add the methods distance() and sap() to the WordNet data type.

Outcast detection. Given a list of nouns A1, A2, ..., An, which noun is the least related to the others? To identify an outcast, compute the sum of the squares of the distance between each noun and every other one:

(di)2 = (dist(Ai, A1))2 + (dist(Ai, A2))2 + ... + (dist(Ai, An))2
and return a noun At for which dt is maximum.

Implement an immutable data type Outcast with the following API:

// constructor
public Outcast(WordNet wordnet)

// given an array of nouns, return an outcast
public String outcast(String[] nouns)
Also include a main() that takes the name of a synset file, the name of a hypernym file, followed by the names of outcast files, and prints out an outcast in each file.
% more outcast1.txt
horse zebra cat bear table

% more outcast2.txt
apple pear peach banana lime lemon blueberry strawberry mango watermelon potato

% more outcast3.txt
water soda bed orange_juice milk apple_juice tea coffee

% java Outcast synsets.txt hypernyms.txt outcast1.txt outcast2.txt outcast3.txt
outcast1.txt: table
outcast2.txt: potato
outcast3.txt: bed

Watson. Another application of WordNet is a Watson client. So for example, the Watson client could be given a Jeopardy clue such as: This is a mammal that lives in Asia and eats bamboo. And Watson would look up mammal and check which definitions in the subtree of the mammal node of the graph have both Asia and bamboo and then produce: What is a giant_panda?

In the readme.txt, produce your own example of a Watson question and answer that could be solved with the current WordNet data. Note that your example can solve the answer using a different connection between nodes instead of the subtree.

Deliverables. Submit,, and that implement the APIs described above, along with a a readme.txt file. Also submit any other supporting files (excluding those in stdlib.jar and algs4.jar).

This assignment was created by Alina Ene and Kevin Wayne.
Copyright © 2006