The
assignment requires you to design and implement a program in C that can perform a predictive text function
similar to the T9 system employed in modern mobile phones.
There is a text file of words called words.txt that is available from the web site:
http://www.elec.york.ac.uk/intsys/users/jfm7/dsa.html
The file contains a list of 25,143 words. The predictive text system should operate in a similar way to that in
a mobile phone:
1 2 (abc) 3 (def)
4 (ghi) 5 (jkl) 6 (mno)
7 (pqrs) 8 (tuv) 9 (wxyz)
* 0 # (space)
For example to type the word hello, the following of keypresses are required: 4 3 5 5 6 #
Often certain lists of numeric keypresses can correspond to several words in the dictionary e.g. 6 3 offers
“me” and “of”, 8 4 6 3 offers the following possible words: “time”, “vine”. Your program must offer you
alternative matching words. It should provide matches as you type and allow you to accept one of the
possible matches via the “scrolling key” *. Acceptance of a suggested word should be via the # key.
A program is available from the URL above that has some useful functions that you may choose to use in
your program. There are some functions that will convert a word typed in from the keyboard into its
associated numeric key sequence (see table above).
You must choose a convenient data structure to place the words read in from the file words.txt (they must be
stored in memory). You will need to think about efficient ways of matching entered numeric sequences from
the keyboard to alternative matching words. Merely putting all the words in a single list and searching
through the entire list for words that have identical associated numeric sequences will be a very inefficient
solution. Programs that choose appropriate data structures and use algorithms that make the predictive text
system efficient will receive higher marks. You MUST work on the program on your own. Marks will be
deducted for work that is identified as being too similar to another student’s solution. You need to hand in to
the general office (with a cover sheet): a neat program listing, and a two page report discussing your choice
of data representation and algorithms. Discuss also the memory requirements and computational efficiency.
