Dictionary algrarithms?
hi:
here is a design for a dictionary
Design
A dictionary is essentially a set of words. Dictionaries are used in various applications.
In a spell-checker, a dictionary is used simply to decide whether a given word is
correctly spelled. In information retrieval, however, the emphasis is on determining the
given word抯 stem. For example, the stem of 搈en?is 搈an? the stem of 揼oing?and
揼one?is 揼o? and the stem of 揼reen?is itself.
Note that, in a conventional printed dictionary, all the words with a common stem are
grouped together in a single entry.
Design an abstract data type, Dictionary, that captures the notion of a set of words
grouped in this way. Dictionary must be equipped with operations that enable an
application program to:
1. make the dictionary empty;
2. add a new word to the dictionary, indicating its stem if it is not itself a stem;
3. test whether the dictionary contains a given word;
4. determine the stem of a given word;
5. print the dictionary in alphabetical order, one line for each group of words
with a common stem (first the stem, then the other words in no particular
order).
Express your design in the form of a Java interface. Each operation must be
accompanied by a specification of its observable behaviour (as a comment).
You can assume that every group of words with a common stem is small.
implementation efficiency the operationthe operation that meets requirement 5
should be O(n), whilst the operations that meet requirements 2? should be faster than O(n).
I want to implement it like a hashtable, i set the word and the stem of it to be the key and value of the entry which is to be added into the buckets of hashtable.
but only using this data structure cannot achieve the efficiency in requirement 5;
so i used an array which hold the stems and corresponding words , the "stem" are added into the array in acsending order, and if the word to be added is not a stem, just add it into the end of the created linked list which the header is pointed at its "stem" in the array.
require 2 O(1) +O(logn) = O(logn) add both in array and hashtable
require 3 O(1)seach from hashtable
require 4 O(1)seach from hashtable according key get the value
require 5 O(n)print from array
I think my solution is not a prfect one.
what are you ideas and suggestion on this program?
