|
|
|
|
A Simple Algorithm for Text Entry in
Mobile Communication
Devices
S. Rajeev1
, Somu Ghosh2 , G. Nirmal
Kumar3, S. N. Sivanandam4
1Research
Scholar, 2 & 3Graduate Students
Department of
Electronics & Communication Engineering
4Professor
& Head
Department of
Computer Science & Engineering,
PSG College of
Technology, Coimbatore, INDIA
email : rajeev@ieee.org
Abstract
: We introduce a simple and efficient algorithm
for single keystroke text input that can be used in various mobile communication
devices where a variety of techniques for fast text input on handheld machines
have been proposed. One approach is to make the speed of using a software
keyboard faster. “QWERTY” layout is often used for the software keyboard,
but to make things simple and easier, we submit an algorithm which works faster
and better than currently existing word based disambiguation systems.
Key Terms – Mobile computing, text entry, linguistic
optimization, input devices, disambiguation, prioritized word search.
1. Introduction
The telecommunication
industry has emerged to such an extent that the number of mobile phone users
have evolved from a couple of thousands in the last decade to almost 10 million
users in this decade. From voice the services extended to ASCII text messages
ranging to 250 characters as on today. The cell phone handset consists of
only 12 keys meant for the numeric keypad and other keys meant for direction,
menu and volume control along with other keys. This limits the number of keys
to a maximum of 15 [4], [5]. A central
reason to explore and examine the efficacy of the text entry algorithm is
the growth of Short Message Services (SMS) messages on mobile phones.
To accommodate
all the 26 characters along with the numeric and special characters is not
just difficult but rather impossible. So the designers of mobile-handsets
had come up with the plan of accommodating three or more characters per key
on the numeric keypad. Currently, the majority of SMS users use multi-press
as their method of text entry, although some cellular phones do feature word-based
disambiguation systems including T9® Text Input (“T9®”) [1] by Tegic Communications,
Inc., iTAP™ Intelligent Keypad Entry Systems by Morotola Inc., and EZiText™
by Zi Corporation. The user had to
type a maximum of three times per character, commonly referred to as MultiPress
mode. As a result of this user speed and efficiency decreased to a greater
extent when compared to the QWERTY users. Along with this the number of errors
also increased rapidly as an attempt to type fast. In the view of this difficulty
we present an algorithm based on [2] and [3] which will facilitate the user
for typing fast, at the same time reducing errors and number of key presses
also.
2. The Algorithm
The algorithm has three modules, Dictionary Module, Temporary
File Module, Window Module
Variables
DicCurLength
- Length of the presently selected word
DictionaryWordNo -
Position of the presently selected word in the dictionary
DicCurCode -
gives the combination of various keypad presses required to form a
particular word.
LengthWord -
Position of the word under consideration
StartWord -
Position of the current word
Functions
GetWord (KeyString,
WordNo)
i,j are integers,
TempString is a String
j = 0;
do until WordNo = 1
j
= j + 1;
if
Mid (KeyString, j, 1) = "," then
WordNo = WordNo – 1; end if; end
do;
for
each i = j + 1 not including Len (KeyString) do
TempString
= Mid (KeyString, i, 1)
if TempString = "," or TempString = "" then
exit; end if;
GetWord = GetWord & TempString; end for;
end;
2.1 Dictionary Module
IndexNumber, TempPosition are Integers
DicForward (KeyStroke) /*
KeyStroke is the combination of numbers entered by User*/
IndexNumber
= DictionaryPosition;
DicCurCode = (DicCurCode * 10) + KeyStroke;
DicCurLength = DicCurLength + 1;
do until Word >= Current Word
DictionaryPosition = DictionaryPosition
+ 100; end do;
if (DictionaryPosition
>= 100) then
DictionaryPosition = DictionaryPosition – 100;
do until Word >= Current Word
DictionaryPosition
= DictionaryPosition + 1; end do; end if;
if Word =
Current Word then DicForward = Current Word ;
else DicCurCode = DicCurCode / 10;
DictionaryPosition = IndexNumber;
DicCurLength = DicCurLength – 1; end
if;
end;
DicBackward (
)
DicCurCode = DicCurCode \ 10;
DicCurLength
= DicCurLength – 1;
do until
Word < Current Word
DictionaryPosition = DictionaryPosition – 100;
end do;
do until Word >= Current Word
DictionaryPosition = DictionaryPosition
+ 1; end do;
if Word = Current Word then
DicBackward = Current Word; end if;
end;
DicNextCycle (
)
DictionaryPosition = DictionaryPosition
+ 1;
if
Word <> Current Word then
DicBackward
( );
DicForward
( DicCurCode \ 10 ); end if;
DicNextCycle
= Current Word;
end;
2.2 Temporary File Module
TempAddData (WindowPosition,
DictNo= -1, DictLen= -1 are Integers)
if
DictNo = -1 then DictNo = DictionaryPosition; end if;
if
DictLen = -1 then
DictLen
= DicCurLength;
TempPosition
= WordNumber; end if;
if
Total Temp Size >= WordNumber + 1 then
Remove
(TempPosition); end if;
Write (WindowPosition,
DictNo, DictLen, TempPosition);
TemporaryFilePosition
= TempPosition;
end;
TempNextData (
)
TemporaryFilePosition
= TemporaryFilePosition + 1; end;
TempPrevData (
)
TemporaryFilePosition
= TemporaryFilePosition – 1; end;
2.3 Window Module
Tempvar, PreviousWord, RelativeWord, NextWord are Integers
CompleteWordEdit, SpaceMode, WordEnd are Boolean
KeyPress (PressedNumber)
select case PressedNumber
case 1 to 9
begin
TempString
= DicForward(PressedNumber)
if TempString <> "" then
if SpaceMode = True then
SpaceMode = False;
RelativeWord = 0;
LengthWord = 0;
WordNumber = WordNumber + 1; end if;
ReplaceText (TempString);
LengthWord = LengthWord + 1;
RelativeWord
= RelativeWord + 1;
DictionaryWordNo
= DictionaryPosition;
exit; end
if;
end;
case 0 /*Space*/
begin
if SpaceMode = False and LengthWord > 0 then
TempNextData;
TempAddData
(StartWord - PreviousWord);
PreviousWord = StartWord + LengthWord; end if;
StartWord = CurrentWord + 1;
RelativeWord = RelativeWord + 1;
SpaceMode = True;
end;
case N /*Moving
to next choice */
ReplaceText
DicNextCycle;
case
Z /*Moving left */
begin
if
CurrentWord <> 0 then
SpaceMode = False;
CurrentWord = CurrentWord – 1;
RelativeWord
= RelativeWord – 1;
if RelativeWord
= -1 then
TempAddData (GetWord (CurrentWord, 1),
DictionaryWordNo, LengthWord);
WordNumber = WordNumber – 1;
Tempvar = Val (GetWord (CurrentWord, 1));
TempPrevData
( );
LengthWord = Val (GetWord (CurrentWord, 3))
+
Tempvar-1;
RelativeWord
= LengthWord;
StartWord = CurrentWord – RelativeWord;
DictionaryWordNo = Val (GetWord (CurrentWord,
2)); end if;
if RelativeWord = LengthWord
then
WordEnd = True;
DictionaryPosition = Val (GetWord(CurrentWord, 2));
DicCurCode
= Val (Left (DictionaryPosition,
LengthWord));
DicCurLength = LengthWord;
else
WordEnd = False;
Reset Dictionary; end if; end if;
end;
case X /*Moving right
*/
begin
if
CurrentWord < Len (Current Word in Window) then
SpaceMode = False;
if Temporary
File Position <> Total Size - 1 then
NextWord = GetWord (Temporary File Position + 1, 1);
else NextWord = -1; end if;
CurrentWord = CurrentWord
+ 1;
RelativeWord = RelativeWord + 1;
if NextWord <> -1 and RelativeWord = NextWord +
LengthWord then
TempAddData (CurrentWord - StartWord –
LengthWord, DictionaryWordNo, LengthWord);
WordNumber
= WordNumber + 1;
Tempvar = Val
(GetWord (CurrentWord, 1));
TempNextData
( );
LengthWord =
Val (GetWord (CurrentWord, 3));
RelativeWord
= 0;
StartWord =
First Word in Window;
DictionaryWordNo
= Val (GetWord (CurrentWord, 2));
if RelativeWord =
LengthWord then
WordEnd = True;
DictionaryPosition = Val (GetWord (CurrentWord, 2));
DicCurCode =
Val (Current Word’s code));
DicCurLength
= LengthWord;
else
WordEnd = False;
Reset Dictionary;
end if; end if; end if;
end; end case;
end;
ReplaceText (NewString)
CurrentWord
= StartWord;
CurrentLength
= LengthWord;
CurrentText
= NewString;
end;
New Word additions
Whenever a new word is created it is added to end of list and
then finally reordered back into the list. To provide a link
begin
NewWord.link=CurrentWord.link;
CurrentWord.link=NewWord.add;
end;
Reordering of New Words
loop till
(CurNewWord.link=END)
N=LastAdd-
NextWord.Add;
loop
N-times
Shift words by a position from NextWord;
end loop;
CurNewWord=NextWord.Add
-1;
CurNewWord.Link=default;
CurNewWord.priority=1;
(CurNewWord.Add
- 1).Link=default;
end loop;
Prioritizing
The prioritizing function is used to manage the number of user
defined words. These words are prioritized according to the frequency of usage.
When not used frequently, the words can be deleted, thus maintaining the size
of the List. The permanent words have NULL priority.
begin
if Word.Priority!= (NULL or
10) then
CurWord.Priority+1; end if;
end;
begin /*To delete*/
if
Word.Priority=0 then
Delete (CurWord); end if;
end;
Word Editing
When an already typed word is modified, the dictionary pointer
location is moved to the most probable complete word present in the dictionary.
If it exists, the word is replaced by the modified extended word. If it does
not exist, the word is considered as a new word and then NewWord addition
procedure is followed
begin
if
(Wordloc is a substring of ModifiedWord) then
Wordloc=ModifiedWord;
else
NewWord (ModifiedWord) end if;
end;
When the word editing procedure is not opted by the user in
the creation of extended words, the algorithm provides the user with the choice
of adding words at the end of a word without modifying it in the dictionary.
In this case the added part of the word is considered as a new word and is
recognized by the relative positioning method by putting the value of separation
between the words as zero.
The given algorithm
is developed based on Sequential Index Search. The Sequential searching technique
searches through data in a sequential order. Thus it is has to pass through
n-1 data to reach to the nth datum. On a typical telephone keypad, groups
of letters in alphabetical order are associated with numeric keys. The user
sequentially presses the numeric keys which represent the letters in the numeric
keypad (a key press per letter), thus building the words sequentially.
The algorithm also searches sequentially moving from one possibility
to another in the added word list as and when the user presses the next numeric
to represent the succeeding letter in the word. Since the user cannot type
in more than three words a second, the program would appear to perform no
steps at all because of its effective search. Moreover the program exploits
human limitation of sequential text entry to perform a sequential search thereby
going in par and even better than human typing speed. This is comparatively
faster to the word guessing algorithm by which words are formed and cross
checked with the words present in the word list. The word guessing algorithm
also waits for the user to complete typing the entire word and then searches
for the most probable combination.
The graphs in Fig.1 gives the relation between the Skip Number
and Total Count. Skip Number denotes the number by which the pointer moves
in one attempt during the searching of the word in the dictionary. The Total
number of moves by the pointer in the process is given by Total Count. Based
on the graphs for a few sample words, the optimum Skip Number can be obtained.
The graph in
Fig.2 gives the number Graph showing number of movements of Dictionary Position before reaching the Word
|
|
|
|
|
|
|
|
Fig. 1(a...e). Skip Number Vs. Total Count
|
Fig.
2. Number of movements of
Dictionary Position before
reaching the Word
3. Comparison over existing Algorithm
There are several short comings in the presently used Word
Completing algorithms such as T9® by Tegic Communications[1].
·
The existing system stores word by means of having keystroke
position and word as an easy search parameter. The problem is that as the
amount of words increase the dictionary size increases proportionately and
so it cannot accommodate all the words the user would wish it to have. For
that we are using an improved storage mechanism by which words containing
part of existing words are replaced by the corresponding big words. Example
the word my and myself are stored as the same word thereby saving enough space
for another word.
·
The formation of compound words that the T9 dictionary used
in cell-phones is limited in scope to creation and not to editing. While editing
the compound word the dictionary fails to treat each word as a different word
and hence the user is not in a position to edit the word individuality.
·
The editing of the words which the current T9 supports is based
on the existence of the complete word in the dictionary and hence the user
is not able to insert a character in the middle of a word. Our algorithm has
overcome this drawback by allowing the user to navigate from character to
character thereby providing him with the option of complete editing of the
word and not pseudo-editing as done in conventional T9 system.
·
The algorithm also supports auto-save an option which is not
common in conventional T9 systems. The user can form a word by compounding
once. Later on the word becomes a valid word in the dictionary.
·
The special character set offered by the conventional T9 system
is very crude and supports only preliminary support for special character
like a dot and apostrophe. Our algorithm automatically prioritizes the format
for conventional special character utilization and gives the user faster access
to special characters without having to press the next option a dozen times
to get the corresponding character.
4. Time Complexity issues
Initializing
the file
When the user
starts using the program, the procedure initializes the routine to set file
pointers to various parts of the file. A suitable optimized number of file
pointers like n/10*a can be selected and thrown at the file. This takes a
small a relatively small time, but noticeable if the dictionary contains a
huge amount of words like the oxford dictionary.
KeyPress Events
·
When the user presses a key in the text entry mode the algorithm
automatically searches for the nearest and prioritized word by looking in
the downward direction, first going through all the main pointer array and
then going through one word at a time. Again this might be noticeable for
a dictionary containing a huge amount of words.
·
The algorithm optimizes this by using multiple key pointer
position and using single directional search which reduces the time taken
to search for a word
·
Since the user cannot type in more than three words a second,
the program would appear to perform no steps at all because of its effective
search. Moreover the program exploits human limitation of sequential text
entry to perform a sequential search thereby going in par and even better
than human typing speed.
Adding new words
This algorithm
keeps a provision for adding new words. If the user finds that the word he
wants to add is not in the dictionary then he can press a key designed for
adding new words. The new word is automatically entered in the dictionary
as well as in the text window.
The suggested
algorithm, by overcoming all the above short comings proves better with respect
to time, less-errors and is user friendly.
References
[1]
Tegic Communications, Inc. T9 text input. <http:// tegic.com>
[2]
S.
Rajeev, Somu Ghosh, G. Nirmal Kumar, S. N. Sivanandam, (2003) An Efficient
Algorithm for Single Key Stroke Text Entry for Mobile Communication Devices,
Proc. International Conference on Wireless Communication Networks (ICWCN-2003),
Chennai, India.
[3]
S. Rajeev, Somu Ghosh, G. Nirmal Kumar, (2003) New Scheme
for Single Key Stroke Word Typing System for Mobile Communication Devices,
National level Technical Symposia, Technologia 2003, National Institute
of Technology, Surathkal, India.
[4]
Danish, A., Danish, S., and Kimbrough, K. W. (1995) Entry
of alphabetical characters into a telephone system using a conventional telephone
keypad, U.S. patent 5,392,338, February 21, 1995.
[5]
MacKenzie,
I. S., Zhang, S. X. and Soukoreff, R. W.(1999) Text entry using soft keyboards,
Behaviour & Information Technology, 18 (4), 235-244.
[6]
Cormen,
T.H., Leiserson, C. E., Rivest, R. L.(1996) Introduction to Algorithms,
MIT Press.
AUTHORS
S. Rajeev, M.E.(CSE).,
Address
:
Lecturer & Research Scholar,
Department of Electronics and Communication
Engineering
PSG College of Technology
Peelamedu
Coimbatore – 641 004
Tamil Nadu
India.
Phone
: office : +91-422-2572177 –
436
residence
: +91-422-2643483
Email
: rajeev_cbe@yahoo.com, rajeev@ieee.org
Somu
Ghosh & G. Nirmal Kumar
Address
:
Undergraduate Students,
Department of Electronics and Communication
Engineering
PSG College of Technology
Peelamedu
Coimbatore – 641 004
Tamil Nadu
India.
S.
N. Sivanandam Ph. D
Address:
Professor and Head
Department of Computer Science &
Engineering
PSG College of Technology
Peelamedu
Coimbatore – 641 004
Tamil Nadu
India.
Phone : +91-422-2572177 – 478
Email : psgtech_it@mailcity.com