You may partner for this assignment but only if you and your partner have worked together on 3 previous assignments or less this semester.
|
|
Can I read the synset or hypernym file twice? No, file i/o is very expensive so please read each file only once and store it in an appropriate data structure.
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.
What assumption can I make about the digraph G passed to the SAP constructor? It can be any digraph, not necessarily a DAG.
What data structure(s) should I use to store the synsets, synset ids, and hypernyms? This part of the assignment is up to you. You must carefully select data structures to achieve the specified performance requirements.
Do I need to store the glosses? No, you won't use them on this assignment.
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.
Should I re-implement breadth-first search in my SAP class? No, you should call the relevant method(s) in BreadthFirstDirectedPaths.java. You may modify BreadthFirstDirectedPaths.java to optimize your code, but if you do so, rename it, say to DeluxeBFS.java, and submit it.
I understand how to compute the length(int v, int w) method in time proportional to E + V but my length(Iterable<Integer> v, Iterable<Integer> w) method takes time proportional to a × b × (E + V), where a and b are the sizes of the two iterables. How can I improve it to be proportional to E + V? The key is using the constructor in BreadthFirstDirectedPaths that takes an iterable of sources instead of using a single source.
Is a vertex considered an ancestor of itself? Yes.
What is the root synset for the WordNet DAG?
40018,entity,that which is perceived or known or inferred to have its own distinct existence (living or nonliving)
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.
37558,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" 50265,news intelligence tidings word,new information about specific and timely events; "they awaited news of the outcome" 60428,parole word word_of_honor,a promise; "he gave his word" 60429,password watchword word parole countersign,a secret word or phrase known only to a restricted group; "he forgot the password" 80882,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" 80883,word,a brief statement; "he didn't say a word about it" 80884,word,a verbal command for action; "when I give the word charge!" 80885,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.
70,Aberdeen,a town in western Washington 71,Aberdeen,a town in northeastern South Dakota 72,Aberdeen,a town in northeastern Maryland 73,Aberdeen,a city in northeastern Scotland on the North Sea
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.
How can I make SAP immutable? You can (and should) save the associated digraph in an instance variable. However, because our Digraph data type is mutable, you must first make a defensive copy by calling the copy constructor.
|
|
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 being -> living_thing animate_thing -> object physical_object -> physical_entity person individual someone somebody mortal soul -> causal_agent cause 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
(distance = 23) white_marlin, mileage (distance = 32) Black_Plague, black_marlin (distance = 32) American_water_spaniel, histology (distance = 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,425, but do not hardwire this number into your program becaue your program must work for any valid input files.
Implement the remaining WordNet methods.
Implement Outcast.
|
|
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 this or any of your own invention without thoroughly testing your code. You can gain bonus points for correctly implementing some of these optimizations but you risk losing more points than you can gain if you introduce bugs that render your solution no longer correct.
|
|