THE UNIVERSITY OF BIRMINGHAM
School of Computer Science
Software Workshop Java
Predictive Text

Mark Ryan and Tim Cocks

Introduction

The introduction of short messaging services means many people now enter text into mobile phones. As these phones do not have a key for every letter in the alphabet, a compromise is being made to allow text to be entered, by putting more than one letter on a single key. A typical layout is shown below:

1 2 (abc) 3 (def)
4 (ghi) 5 (jkl) 6 (mno)
7 (pqrs) 8 (tuv) 9 (wxyz)
* space #

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

Write a program PredText to convert some strings to their corresponding numeric signature. The strings will be given on the command line. For example,
java PredText university of birmingham
will deliver the output
8648377489 63 2476464426
Notes

2. Converting a numeric string back to the original text

Because several letters become the same numeric digit, it is not possible to convert a numeric key string into a unique alpha string. For example, the numeric string '7733428' corresponds to 4*4*3*3*3*3*3 = 3,888 different alpha strings.

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
would probably just print the word "predict", while
java PredText 4663
would print out a large number of words including: gone, good, goof, home, hone, hood, hoof.

Notes

3. Building a data structure

Obviously, reading through the dictionary line by line each time is hugely inefficient. In order to make predictive text work fast, we need to read in the dictionary once and store it in an appropriate 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.

It might be better to use a forest of trees, instead of a list. The forest would consist of 26 trees, each one being "26-ary", i.e., each node has (up to!) 26 children. Words correspond to paths of the tree.

4. Adding a Swing user interface

Develop a Swing GUI for the application. It should not be necessary to modify PredText.java. To ensure your GUI is reliable and does not interfere with the existing code, you can use the Model View Controller (MVC) model of GUI development.  MVC is a good discipline for building GUIs, because it encourages separation of concerns. MVC also helps ensure that the user interface code is separate from the program code. This makes it easy to change the user interface without changing the underlying program, or change the program without changing the GUI.

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:



In this example, there are two controls: the buttons, and the text entry field underneath them. In my program, you can either press the buttons with the mouse, or you can type the digits into the textfield underneath using the numeric keypad of your keyboard. In both cases, the message appears in the text window above the keypad. In my program, you can even type alpha strings into the text field, but you might not get the characters you type. If you type an "a", it's equivalent to pressing a 2, so you will get one of "a", "b", or "c". To cycle through the words that match, you either press the button labelled *, or you type a * in the text entry field. On Nokia phones, the # key toggles upper and lower case and also toggles predictive text mode. I didn't implement the behaviour of the # key, and you don't have to either!

Mark scheme

Each exercise receives marks for

1. Converting text to its numeric signature

Design: ((no design needed for this very simple program.)) 0
Coding: Is there a self-contained method which does the conversion? The method should return the string rather than printing it directly.
Is the code nicely laid out and properly indented?
10
Testing: Has the student tried it on a variety of strings, including empty string and incorrect inputs?
Also try it on several expected strings, such as "meet me for a drink tonight"; in that case you should get 6338 63 367 2 37465 8664448.
10
Total 20

2. Converting a numeric string back to the original text

Design: ((no significant design needed for this very simple program.))
0
Coding: are there appropriate methods? Do they return their results instead of printing them?
Is the code nicely laid out and properly indented?
Are the variable names sensible? Variable and method names should begin with a lowercase letter, and class names should begin with an uppercase letter.
Does the same program work for part 1 and part 2, by detecting the kind of input?
10
Testing: Has the student tried it on a variety of strings, including empty string and incorrect inputs?
Try it on several numeric strings, such as 7733428 (probably gives only "predict") and 4663 (probably gives gone, good, goof, home, hone, hood, hoof).
10
Total 20

3. Building a data structure

Design: Has an appropriate set of classes been used, with meaningful relations between them?
6
Coding: Does the program build an appropriate data structure from the Collections framework?
Does the program follow the student's written design?
7
Testing:  Does the program print a large set of clashes? Check that the words printed are really clashes!
What happens if the dictionary is empty, or missing, or has no clashes?
7
Total 20

4. Adding a Swing user interface

Design: Is there an appropriate set of view and controller classes? Does the model properly encapsulate the underlying program? 10
Coding: Is the code reasonably commented and could it be maintained by a different programmer, if necessary? 10
Testing: Has the student devised an appropriate set of test cases, including multiple pressings of *, input which doesn't match any word, etc.
10
Functionality: Basic behaviour: is it possible to enter a numeric string and get a corresponding word to appear?
More complex behaviour: can the user press 0 for a space, and go on to enter a next word?
Can the user press * to cycle between clashes?
10
Total 40

Page written by Mark Ryan and Tim Cocks
Page maintained by Mark Ryan

Last modified: Tue Oct 12 18:03:46 BST 2004