|
|
Should SAP work if the digraph is not a DAG? Yes, the definition still applies in the presence of directed cycles.
How efficiently should I implement the WordNet and SAP data type? For SAP, O(V+E) is acceptable. For WordNet, glosses() and isNoun() should take less than linear time.
How do I use In.java? Here is description of the API for In. And here is an example line of code:
In in = new In(args[0]);
What sort of data structure should I use to store the synsets? This part of the assignment is up to you. Many data types have been discussed in this class and you have to pick one that is going to be able to handle different sizes and efficiently access the data in the ways that the assignment describes.
Can I assume the hypernym digraph for WordNet is a DAG? Yes. However, your program should work on any input, not just the synset and hypernym files provided. You may assume that if there are V synsets, then the ids will be numbered 1 through V (sorry, not the usual 0 through V-1). However, there is no guarantee that the id numbers will appear consecutively in the synset file.
Should I re-implement breadth-first search in my SAP class? No, it is easier and better design to reuse BreadthFirstDirectedPaths.java. However, you may modify it (and expand the API) in order to optimize the computation. If so, be sure to submit your version, and perhaps rename it DeluxeBFS.java.
Can I use my own Digraph class? No, it must have the same API as our Digraph.java class; otherwise, you are changing the API to the SAP constructor (which takes a Digraph argument). Do not submit Digraph.java.
Is a vertex considered an ancestor of itself? Yes.
Can a noun appear in more than one synset? Absolutely. It will appear once for each meaning that the noun has. For example, here are all of the entries in synsets.txt that include the noun word.
37559,discussion give-and-take word,an exchange of views on some topic; "we had a good discussion"; "we had a word or two about it" 50266,news intelligence tidings word,new information about specific and timely events; "they awaited news of the outcome" 60429,parole word word_of_honor,a promise; "he gave his word" 60430,password watchword word parole countersign,a secret word or phrase known only to a restricted group; "he forgot the password" 80883,word,a unit of language that native speakers can identify; "words are the blocks from which sentences are made"; "he hardly said ten words all morning" 80884,word,a brief statement; "he didn't say a word about it" 80885,word,a verbal command for action; "when I give the word charge!" 80886,word,a word is a string of bits stored in computer memory; "large computers use words up to 64 bits long"
Can a synset consist of exactly one noun? Yes. Moreover, there can be several different synsets that consist of the same noun.
71,Aberdeen,a town in western Washington 72,Aberdeen,a town in northeastern South Dakota 73,Aberdeen,a town in northeastern Maryland 74,Aberdeen,a city in northeastern Scotland on the North Sea
Can two synsets have identical glosses? Yes.
24936,barley barleycorn,a grain of barley 24941,barleycorn,a grain of barley 64933,quadrant right_angle,a quarter of the circumference of a circle 64934,quadrant quarter-circle,a quarter of the circumference of a circle
Some of the glosses have example sentences at the end. What is this? The example sentence is considered to be part of the gloss. You shouldn't need to do anything special to handle it.
Any advice on how to read in and parse the synset and hypernym 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. You can find an example using split() in Domain.java. Use Integer.parseInt() to convert string id numbers into integers.
In WordNet, what should glosses() return if the noun is not in WordNet? Return an Iterable<String> that has zero elements.
How much memory should my WordNet program use on the wordnet data set? Provided you are not using excessive memory, e.g., quadratic proportional to the input size, and it makes your program faster or more readable, then it's ok to allocate more space than whatever java specifies on your computer. Note that it is also possible to implement WordNet without needing more memory.
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.
What should length() and ancestor() in SAP do if one of the input arguments is not an integer between 0 and G.V() - 1? Throwing an exception is probably the best approach. Returning -1 is also acceptable.
What should outcast() do if one of its arguments is not a noun in WordNet? We won't test such cases.
|
|
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.
Some examples. Here are some interesting examples that you can use in your code.
municipality -> administrative_district -> district -> region municipality -> populated_area-> geographic_area -> region
individual -> organism -> living_thing -> object
individual -> causal_agency -> physical_entity
edible_fruit -> garden_truck -> food -> solid -> matter -> physical_entity
edible_fruit->fruit->reproductive_structure -> plant_organ -> plant_part ->
natural_object -> unit -> object -> physical_entity
23 white_marlin, mileage 32 Black_Plague, black_marlin 32 American_water_spaniel, histology 32 Brown_Swiss, barrel_roll
Ambrose Saint_Ambrose St._Ambrose
|
|
If you read in synsets.txt first, you can identify the largest id before constructing the Digraph. Check that it is 81,426, but do not hardwire this number into your program.
Try some nouns that participate in many synsets, e.g., run, face and back.
|
|
There are a few things you can do to speed up a sequence of SAP computations on the same digraph. Do not attempt to do any of these unless you have thoroughly tested your code. Be sure that your solution is as modular as the code you change and works as well. In other words, test thoroughly.
// return length of shortest ancestral path between any vertex in v[] // and any vertex in w[]; -1 if no such path public int length(int[] v, int[] w) // return a common ancestor of some vertex in v[] and some vertex in w[] // that participates in a shortest ancestral path; -1 if no such path public int ancestor(int[] v, int[] w)
|
|