Introduction

Without predictive text, the user is required to press the appropriate key a number of times for a particular letter to be shown. For example, the letter 'u' is produced by pressing the '8' key twice. This makes entering text a slow and cumbersome process. The problem becomes even more apparent if we consider the word 'hello'. With this method, the user must press 4, 4, 3, 3, 5, 5, 5, then pause, then 5, 5, 5, 6, 6 and finally another 6.

Predictive Text (also known as T9) is a system that aims to reduce the number of key pressings necessary to enter text. It aims to allow the user to press each key only once. This allows the word 'hello' to be typed in 5 key presses instead of 12. It does this by restricting the available words to those in a dictionary.

Unfortunately, predictive text technology is not perfect. One problem concerns what should happen when a given key sequence could correspond to more than one word in the dictionary. For example, the sequence '228' could be interpreted as 'act', 'bat' or 'cat'. We call these words "predictive text clashes". Other clashes well-known to users of predictive text include "of" and "me"; "home", "gone" and "good", etc.

On Nokia phones, the * key is used to cycle between alternative words for the same numeric string. Thus, if entering "4663" produces "gone" when you meant "home", you press *. This moves on to the next word; if it's still not "home" you have to press * again. Normally, the words are arranged so that the more common words (like "home") will occur earlier in the list, and less common words (like "hoof") will occur later.

In these exercises, you are asked to develop a Java program for working with predictive text. For simplicity, we assume that the user does not need punctuation or numerals. Also, you need not attempt to order words by how common they are. You may also limit your solutions to using only lower-case letters.

1. Converting text to its numeric signature

java PredText university of birmingham

8648377489 63 2476464426

• You should have a method which takes a string argument, and returns the numeric key string result. Your method should not print its answer, but simply return it to the main method, which then prints it. This is so that you can use the method later in the exercise in circumstances when you don't want the answer printed.
• You will need a for-loop which iterates through the characters of the argument string. You will accumulate the result string character-by-character. You might like to use StringBuffer instead of String to avoid creating lots of strings which later get thrown away.

2. Converting a numeric string back to the original text

Predictive text solves this by restricting the available possibilities to the words occurring in a dictionary. This reduces the number of possibilities considerably. For example, for most dictionaries the numeric string '7733428' is reduced to only one possibility - it is the word 'predict'. Unix systems usually have a dictionary of words in /usr/dict/words or /usr/share/dict/words. If you're working on a non-unix system, you will need to download such a file from a unix system in order to do the remainder of these exercises.

Write a program which takes a numeric string argument, and prints out all the words in the dictionary that match it. For example,

java PredText 7733428

java PredText 4663

Notes

• You can extend the program you wrote for part 1, so that it answers both parts. In order to be able to answer both parts, it should check if the first character of the first argument is numeric: if it is, then your program is doing part 2, and if it is not, then your program is doing part 1.
• You can read in the dictionary line by line. Ignore lines which have non-alpha characters in them, and convert all uppercase to lowercase. For each word, use the method you wrote for part 1 to compute its numeric key string, and compare that with the program's argument. If they are the same, you have a match, so print out the word.
• If you prefer to answer part 3 first, then you can answer this part more efficiently.

3. Building a data structure

Modify your PredText program so it reads in the words and stores them in an appropriate data structure from Java's Collections Framework. (To use the classes in the Collections framework, you need to import java.util.*.)

From your data structure, compute the largest set of clashes. For example, if the set of 7 words

gone, good, goof, home, hone, hood, hoof

forms one of the largest sets of clashes, your program could print that set. (Probably you will find a set of clashes bigger than this one.)

Hints  

The following remarks allude to my solution, but you may well find a more elegant way of doing things. Feel free to diverge from my way of doing things.

• Create a simple class which pairs words and their numeric signatures, like this:

  class WordSig implements Comparable
  {
    String word;
    String sig;
  
    public WordSig (...) {...}
  
    public int compareTo(Object ws){ ... }
    public boolean equals(Object ws) { ... }
    ...
  }
  

  The idea is that you will store objects of this class, e.g. in an ArrayList. We will sort this list, in order of the numeric signatures. In order to sort an list, the objects stored in it must implement the Comparable interface. That means they must have a compareTo(Object) method which returns -1, 0 or 1 according to whether this object is less than, equal to, or greater than the argument object in the intended ordering.
• When you have created the list, you can sort it with the static method Collections.sort(). You can search the sorted list with Collections.binarySearch(). Find out more about Collections and the comparable interface in Horstmann/Cornell "Core Java".

4. Adding a Swing user interface

We encapsulate the original program in an object which we call the model. It contains accessor and mutator methods which act as an interface to the program. For every GUI component that can change the model, such as buttons or text entry fields, we create a control object. Control objects translate the user's actions into the model's mutator methods. Every GUI component that displays the object (such as status lights or text output fields) is represented by a view object. View objects observe the model, and change themselves when the model changes.

View classes typically extend GUI output classes, and implement Observer. The model class extends observable; thus, the view classes observe the model. The model is the only part of the GUI that interfaces with the underlying program.  Control classes extend GUI input classes. Some books say that the control classes should implement listeners; but I think it is more natural for the model to implement the listeners.  Thus, the flow of information is: the user drives the control classes. The model listens to them, and updates the underlying program. The views observe the model, and display appropriate information.

You should decide what your GUI will look like before you start writing it. An example layout is shown below:

• Design: the marker will look at your design, including your choice of classes, the relationships between them, information flow, coupling and cohesion.
  
• Coding: marks will be given for your choice of data structures, your use of the Java API, code indentation, choice of variable names, coding style.
  
• Testing: how have you established whether your code exhibits the desired behaviour? Pay attention to boundary and exceptional cases (e.g., null input; incorrect input) as well as the expected cases.