Grouping objects

Aim

To understand how objects can be grouped together into collections

Glossary exercises

• a). Study the Lexicon class. This is a partial implementation of a class that supports the search for words. If a word is not in the lexicon, the complete implementation of this class should suggest a list of similar words. The central method to identify similar words is editDistance. Given two strings, this method computes their Levenshtein or edit distance. This method has already been implemented for you. The Levenshtein algorithm calculates the number of deviations between two words. For example, the edit distance between the words `exception' and `reception' is 2 because the difference between them is one letter transposition and one letter swap. Load the Lexicon class and call the editDistance method for different pairs of words. This method should return smaller numbers for similar words and larger numbers for less similar words
  • Download the starting program
• b). Implement the method wordExists within the Lexicon class. This method receives a string as parameter and returns a boolean value; true if the string exists in the wordsList ArrayList field of the Lexicon class and false otherwise. Hint: have a look at Section 4.8.2 The while loop of the textbook and specifically at the code of page 101 (94 in the third edition). That code is similar to the one you want to implement in this exercise. In both cases there has to be a loop that iterates over an ArrayList until either an element is found or we reach the end of the ArrayList. However the book exercise checks the parameter string is comprised within any of the elements of the ArrayList. In our case you want to check whether the parameter string is equal to any of the elements of the ArrayList. In order to make this comparison you would have to use the "equals" method of the String class. Have a look at that class and method in the Java API documentation.
  • Download the starting program
• c). The WordDistance class is a simple class which contains a word and its edit distance (to another word). This class is used to calculate the edit distance between a word and a set of words. Implement the method getEditDistance within the Lexicon class. This method receives two strings as parameters and returns an object of class WordDistance which contains the second string and its edit distance to the first string
  • Download the starting program
• d). Implement the method getEditDistances within the Lexicon class. This method receives a string as parameter and returns an ArrayList of WordDistance objects, one for each of the words in the WordsList field of the Lexicon class
  • Download the starting program
• e). Implement the method getMinDistance within the Lexicon class. This method receives an ArrayList of WordDistance objects as parameter and returns the WordDistance object with the minimum edit distance. If there are several matches, it returns the one with the lowest index.

  Note. This method might not seem easy to test as you have to provide an ArrayList as a parameter when you invoke it. In order to make the task easier you could use the ArrayList returned by the previous exercise. This is how you do this. First invoke the method in the previous exercise (getEditDistances) with a parameter of your choice. When the Method Result window reporting the returned ArrayList appears, click on the button labeled Get. What this means is that the returned value will be captured and will appear as one more object in the object's bench. A new pop up window will appear asking for the name of the instance, you could accept the suggested name (arrayLis1 or something like that). Now close the Method Result window. You will notice that a new object has indeed been added to the object's bench. This is the object you can use to test this exercise's method. In order to do this, when you invoke the getMinDistance method and the Method Call window appears, simply click on the ArrayList instance in the object's bench and the name of that object will appear as the parameter. Simply click Ok now and the method will be invoked with that object as parameter.

  • Download the starting program
• f). Implement the method getSimilarWords within the Lexicon class. This method can be used to retrieve a number of words similar to a specified word. It receives two parameters, a string containg the specified word and an integer indicating the number of similar words to be returned. It should return an ArrayList of Strings containing the similar words. The method should create an ArrayList of WordDistance objects, one for each of the words in the WordsList field of the Lexicon class (by invoking the getEditDistances method). In successive iterations, the most similar word should be identified, included in the ArrayList of Strings to be returned and removed from the ArrayList of WordDistance objects. This procedure ensures that the more similar words will be located at the beginning of the list of similar words and the less similar ones at the end of it. The most similar word can be identified by obtaining the WordDistance object with the minimum edit distance in the ArrayList of WordDistance objects (by invoking the getMinDistance method). This word can be included in the returned ArrayList by retrieving the string in the to field of the WordDistance object and adding it to the list of similar words to be returned. Finally the WordDistance object can be removed from the ArrayList of WordDistance objects by invoking the ArrayList method remove (look at the Java API for the ArrayList class). An additional requirement is that if the number of alternatives requested is greater than the actual number of words in the lexicon the returned ArrayList of strings should include all the words in the lexicon. Finally, given that the getEditDistance, getEditDistances, and getMinDistance methods will only be used for building the list of alternative words, they should be declared as private rather than public.
  • Download the starting program

---

Last updated at 8:58pm, Thursday September 22nd 2011 Dr Natalia Beloff (N.Beloff@sussex.ac.uk)