Fundamentals of Algorithms Pr

Fundamentals of Algorithms
Problem Definition

The rapid growth of Short Message Service (SMS) text messaging is generating substantial commercial and research interest in fast and efficient text input methods for mobile devices. This paper presents an empirical study that compares two mobile phone text input techniques. The methods are ‘multi-press input with timeout’, T9 method. The study shows that there is a significant speed difference between the two text input methods.

World-wide growth of SMS use.
In this research paper, we address the different ways of inputting text into mobile phones and the entry speed. Inputting text can be done in several ways, these include, Multi Press Input Method, and the T9 input method. To implement the above features we’ll be only using the numeric pad of a normal QWERTY keyboard, which will act similar to the keypad of any normal mobile phone. Keys for alphabets, digits, some special characters will be provided. Also, the Next, Clear, Previous options will be provided. In some cases time between different inputs will also be taken into consideration.

A dictionary will also be made to implement the T9 Input Method.
We could have implemented the T9 method using various data structures . Some of them were “trie” data structure or by using a doubly linked list.
These algorithms, usually better algorithms but which do the same thing are being used effectively worldwide in mobile and cellular phones for text entries. SMS, inputting names, any other textual data in such gadgets is being entered these days using these methods only. But we have implemented T9 through the use of 2-d arrays and certain manipulations.

Literature Survey

This paper describes the T9 Text Input@ product (T9), which can be used by small device designers to meet the text-entry needs of diverse populations of users.

We have studied various research papers regarding this text prediction method and have tried to implement it on our own by using 2- d Arrays and applying certain manipulations to them for finding the result.

We have studied the following research papers for our project that are registered with ACM

1.Predicting Text Entry Speed on Mobile Phones- Miika Silfverberg, I. Scott MacKenzie, Panu Korhonen

2. An Evaluation of Mobile Phone Text Input Methods- Lee Butts and Andy Crockburn

3. Bringing Text Input beyond the Desktop- Christina James and Michael Longe

4. Mobile Phone Text Entry -Lee Butts Dr. Andy Cockburn
Literature analysis
Text entry on contemporary mobile phones is mainly based on the 12-key keypad (Figure 1).
Figure1:12-key pad

This paper describes a method for predicting potential expert user text entry speedfor input methods that utilize the 12-key keypad.
Tegic Communications (“Tegic”) developed a technique called “T9” for text input to enable efficient generation of any desired text using a keyboard with only a small number of keys.
Multiple letters are assigned to each key, so that the specific letter intended by a single keystroke is ambiguous. The system is based on a process known as “word level disambiguation”, where the system compares a sequence of ambiguous keystrokes to words in a large database to determine the intended word.

The two text entry methods discussed in this project are-
Multi Press Input Method
This approach brings out the problem of segmentation. When a character is placed in the same key as the previously entered character (e.g., the word on), the system must determine whether the new key pressed still “belongs to” the previous character or represents a new character.
Therefore, a mechanism is required to specify the start of a new character.

T9 Input Method
To overcome the problem of ambiguity is to add linguistic knowledge to the system. The T9 input method, uses a dictionary as the basis for disambiguation. In this method each key is pressed only once. For example, to enter “the”, the user enters the key sequence 8-4-3-0. The 0-key, for SPACE, delimits words and terminates disambiguation of the preceding keys. T9 compares the word possibilities to its linguistic database to “guess” the intended word.

Multi way key Input:
1. If the user want to type “going”.
Sol: 4,666,444,66,4
2. If the user want to type “where”.
Sol: 9,44,33,777,33
T9 Input:
1. If the user want to type “going”.
Sol: 4,6,4,6,4
2. If the user want to type “where”.
Sol: 9,4,3,7,3

Movement Model (Flits’ Law)
The core of this paper is the application of Fitts’ law to the mobile phone keypad. Fitts’ law is a quantitative model for rapid, aimed movements. It can be used to calculate the potential text entry speed of an expert user, assuming that the text entry performance of an expert is highly over learned, and thus is limited only by motor performance.

Fitts’ law is expressed as
MT = a + b log2(A/W + 1)

where A is the length (amplitude) of a movement, and W is
target size (width),

Various studies have been carried out over the years, comparing the two methods over speed and accuracy. The results are as follows—

Method Index Finger Thumb

Multi-press
– wait for timeout 22.5 20.8
– Timeout kill 27.2 24.5
T9 45.7 40.6
Figure 6. Results of model predictions (wpm)
Flow Chart

Interface Design:
Main Menu

1. Multi-Press Input Method

2. T9 Input Method

3 Exit

User Interface
Data structure used.

We observed that the most time consuming process in text prediction was of searching for words in the dictionary, and adding new words to the buffer.
We have designed a 2-d array and stored the words in them after reading them from an input file.
Complexity analysis
After running our code we found that the time complexity comes out to be O(n).
On the other hand, the space complexity for bounded space is O(nlogn)
Where n=no of words
Algorithms proposed
For T9 Input Method

1. fp= fopen(‘linguistic database’,’r’).
2. while(!=eof(fp))
a[i][j]->valueof each character
3. for h=0->19
{
TempArray[h]->null
}
4. For p=0->p<w.end.length-1
if(w.end[p][0].compareTo(show)==0)
{
TempArray[u]->w.end[p][1]
display(TempArray[u]+u)
u=u+1
}
5. If TempArray[0]!=null
Result->TempArray[0]
else
result->show
else

if(chars==”*”)

Display TempArray[q]
z->true;
while(z==true)

q->q+1
if(TempArray[q]==null)
q->0
result=TempArray[q]
display TempArray[q]
z=false

else

if(chars==”#”)
last=””
result=””
str=new StringBuffer()
last+=result
result=””
z=false
String TempArray[]=null
6. display last
7. display result

For Multipress
1. if (chars!=”*”&& chars!=”#”)
{
a=chars
2. read from file

3. for j=0->a
inline=infile.readLine()
u=inline.length()
if(result.length()==0)
{
result=” ”
}
4. Display result.charAt(result.length()-1)+” ” +inline.charAt(0+p)
5. Display p
6. if(result.charAt(result.length()-1)==inline.charAt(0+p))
{
p=p+1
if(p==u-1)
p=0
tt=inline.substring(p, p+1);
if (result.length()>0) result=result.substring(0,result.length()-1);

7. result+=tt
8. display p
}
9. else
{
p=0
tt=inline.substring(0, 1)
result+=tt
}

}
else
{

10. if(chars.equals(“#”))
{
if (result.length()>0)
{
11. result=result.substring(0,result.length()-1)
p=0
}
}
12. if(chars.equals(“*”))
p=0

Screen shots

Shortcomings
Every good thing has some drawbacks so does our project. The problem is that if the word doesn’t exist in the dictionary then it shows the code entered by the user in spite of adding the word to the dictionary.
Future scope and improvements-
There is a lot of scope for further development. We can design certain T9 games such as scramble, wordcross etc. we can design T9 navigation system where we can find the things located in our mobile by entering only the initials.eg.
745(SIL) = Silence ringer, 336(DEN) = Dentist appointment / calendar, 322(FAC) = Facebook / Internet , 269(AMY) = Winehouse / music download

Conclusion

This project of ours is a humble effort to implement the T9 method using various data structures, and although various other better text prediction methods exist ,but the understanding of the basic text prediction method will give us an insight usually better algorithms but which do the same thing are being used effectively worldwide in mobile and cellular phones for text entries. SMS, inputting names, any other textual data in such gadgets will really help us to learn more about text mobility, and also in text input methods for the physically impaired .
References:-
1. Dunlop, M. D. & Crossan, A. (2000), ‘Predictive text entry methods for mobile phones’, Personal Technologies pp. 134-143.
GSM Association (2000),

2. Miika Silfverberg, I. Scott MacKenzie, Panu Korhonen, Predicting Text Entry Speed on Mobile Phones-April 2000

3. James, C. L. & Reischel, K. M. (2001), Text input formobile devices:
comparing model prediction to actual performance, in ‘Proc of CHI2001’, ACM,New York, pp. 365-371.

4. – Lee Butts and Andy Crockburn, An Evaluation of Mobile Phone Text Input Methods-

5. Bringing Text Input beyond the Desktop- Christina James and Michael Longe

6.Mobile Phone Text Entry -Lee Butts Dr. Andy Cockburn..November 2001