

-------------------------------------------------------------------------------
G. Rama Krishna						rk_gaddipati@yahoo.com
MMS, BITS Pilani,
Rajasthan, INDIA.
333 031.

Dt: 22-04-2002.
-------------------------------------------------------------------------------


Hi every one.....

T9 (T9 is a registered name of Tegic Systems (now with AOL), usage of this name 
any where else in the document or attached files is not violate the copyrights 
or any other rights the owners possess) - do you know about it?  Hope you all 
by now have T9-enabled cell phones..!  
Now my program is just a simulation of that! For those who don't know about T9, 
let me explain!

T9 Text Input  Algorithm
------------------------
You know that a normal cell phone (I am talking about the second generation 
phones, which hardly have 15 keys) don't have 26 keys to uniqely represent a 
character in the English alphabets..  So each key is normally mapped to 3 or 4 
English alphabets. This makes the things difficult... I magine typing a 50 
character SMS message on sucha key board.  You will end-up pressing the keys 
for a minimum of100 times to formulate all 'meaningful' words.

What T9 aims at is one key press per any character!!  It uses its dictionary 
and the usage priorities of each word to predict the words possible with key 
combinations you have used and then gives you 'best' possible word.

Why don't you please have a look at http://www.t9.com/ for more details on that.


Key Layouts:
-----------

Though normally all the cell phones use a similar sort of key layouts { I don't 
know wether the keyboard layout is standardised}, I currently assume the 
following layout for my program

1[.-+]  2[ABC]  3[DEF]
4[GHI]  5[JKL]  6[MNO]
7[PQRS] 8[TUV]  9[WXYZ]
*       0       #

where the characters in the square brackets are associated with the number to 
the left side of them.

As I am not sure of the standardization of layout, and for sure I know that 
SONY J6 has this layout (as I have one cell phone of SONY J6 model), I named 
one of my header files as sonyj6.h which has the key layouts.  You can change 
this appropriately, if you want it for a different layout!


Dictionary:
----------

My program takes the dictionay file (or a file with a list of words) as a 
command line argument and uses this as the dictionary for the words you type.  
For a considerable size of list, you can use the word list distributed with 
linux, which is usually located at:
    /usr/share/dict/words

Make:
-----

Use the makefile  in the directory to build the program.  Just run the command 
make and it will do the rest for you.

Usage:
------

run the program with the file containing the list of words as the first arguemnt

	% t9 /usr/share/dict/words

Press the appropriate keys to type your message. The program gives the possible 
combinations of words from your dictionary, in the order of the priorites 
calculated!  The pririties for the words formed are indicated in the brackets.  
0 (Zero) stands for an infinite priority and for all other numbers, the larger 
the value of the number, the higher is the priority associated with that word.


Implementation Details:
-----------------------

I should say you, it is a simple assignment for a student doing Data 
Structures.  The program program esentially implements a Trie and thats it!  
The priority of the substrings are the no. of words following it (no. of words 
having this as substring) and a substring which can by itself be a word, will 
have infinite priority (ie., zero)!  And thats all, you have the entire problem 
solved.


NOTE:
-----

The entire algorithm and implementation was developed by me after seeing how my 
cell phone with T9 works.  Especially the priority rule I used is a brain child 
of mine, where as the T9 claims that it calculates on the basis of how widely 
that word is used (I don't know how it gets that value!).  

This is just an attempt to give one of the wonderful uses of trie-s and to 
demonstrate the T9 algorithm.

I don't want to violate any copyrights or patent rules. All the trademarks 
belong to their respective owners.


-------------------------------------------------------------------------------
with best wishes for all your assignments....

ramu (Gaddipati Rama Krishna)
-------------------------------------------------------------------------------
