COS 226 Programming Assignment

WordNet

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 each synset can have several hypernyms.

We now describe the two data files that you will use to create the WordNet digraph.

• List of noun synsets. The file synsets.txt lists all the (noun) synsets in WordNet. Each line consists of three fields separated by ",". The first field is the synset id (an integer), the second field is the synset, and the third field is its dictionary definition (or gloss). For example, the following line

  45,AND_circuit AND_gate,a circuit in a computer that fires only when all of its inputs fire
  

  means that the synonym set whose elements are AND_circuit and AND_gate has an id number of 45, and it's gloss is a circuit in a computer that fires only when all of its inputs fire. Note that the elements of a synset are separated by spaces (and a synset element is not permitted to contain a space).

The individual nouns that comprise a synset are separated by spaces (and a synset element is not permitted to contain a space).

• Is-a relationships. The file hypernyms.txt contains the hypernym relationships in CSV format. The first field is a synset id; subsequent fields are the id numbers of the synset's hypernyms. For example, the following line

  171,22798,57458
  

  means that the the synset 171 ("Actifed") has 2 hypernyms: 22798 ("antihistamine") and 57458 ("nasal_decongestant"), representing that Actifed is both an antihistamine and a nasal decongestant. The synsets are obtained from the corresponding lines in the file synsets.txt.

  171,Actifed,trade name for a drug containing an antihistamine and a decongestant...
  22798,antihistamine,a medicine used to treat allergies...
  57458,nasal_decongestant,a decongestant that provides temporary relief of nasal...
  

Implement a 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)
public double distance(String nounA, String nounB)

// return the synset (second field of synsets.txt) that is the common
// ancestor of nounA and nounB in the shortest ancestral 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 a data type SAP with the following API.

// constructor
public SAP(Digraph G)

// return length of the shortest ancestral path of v and w
public int sap(int v, int w)

// return a common ancestor of v and w that participates in the shortest ancestral path
public int ancestor(int v, int w)

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:

• If either A or B is not a WordNet noun, the distance is infinity.

• Otherwise, the distance is the minimum length of any ancestral path between any synset v of A and any synset w of B.

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

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

(d_i)² = (dist(A_i, A₁))² + (dist(A_i, A₂))² + ... + (dist(A_i, A_n))²

Implement a data type Outcast with the following API

// constructor
public Outcast(WordNet wordnet)

// given an array of nouns, return the outcast
public String outcast(String[] nouns)

Deliverables. Submit WordNet.java, SAP.java, and Outcast.java that implement the APIs described above, along with a readme.txt file. Also submit any other supporting files (other than those in stdlib.jar and adt.jar).