SINHALA T9 TEXT ENTRY SYSTEM M.H. Dewapura This dissertation was submitted in requirements for the Master of Engineering degree Master of Science in computer science Department of Computer Science and Engineering University of Moratuwa Sri Lanka 2007 93366 Abstract T9 Text Input is an input technology used in mobile devices. It lets words be formed by a single key press for each letter, as opposed to the multiple key press approach used in the older generation of mobile phones. It works via active reference to a dictionary of commonly used words. T9 databases are currently available in 15 different character scripts in 62 languages including specialized language engines for Alphabetic, Chinese and Japanese languages. However it is not available for Sinhala. Development of T9 is more valuable for Sinhala than English as the number of letters assigned to a key in the Sinhala keypad is more than that of the English keypad. We developed a system for predictive keypad text entry in Sinhala. Predictive keypad text entry allows the user to type words efficiently just pressing a key one time for each letter. The major objectives achieved in this project are the building of a Sinhala word database, identification of common words and development of the algorithm for predictive keypad text entry and an application for the T9 PC simulator. We used the Sinhala keypad layout used in the Nokia mobile phones for our project. A large number of Sinhala words were collected, several tools to process the words were developed and a database, mapping key sequences to prioritized lists of Sinhala words, was built. A PC application to simulate keypad text entry, update the database with new words and to change word priorities was developed. Finally we compared the required number of key presses for Sinhala text input using T9 and using multi- tap text entry, and showed that our system enables users to enter Sinhala text easily, quickly and efficiently. D e c l a r a t i o n " I c e r t i t ) t h a t t h i s d i s s e r t a t i o n d o e s n o t i n c o r p o r a t e v , i t h o u t a c k n o w l e d g e m e n t a n : m a t e r i a l p r e v i o u s l y s u b m i t t e d f o r a d e g r e e o r d i p l o m a i n a n y u n i v e r s i t y : a n d t o t h e b e s t o f m y k n o w l e d g e a n d b e l i e f i t d o e s n o t c o n t a i n a n y m a t e r i a l p r e v i o u s l y p u b l i s h e d o r \ H i t t e n b y a n o t h e r p e r s o n e x c e p t w h e r e d u e r e f e r e n c e s m a d e i n t h e t e x t . " ( l y _ t e . v • ' - 1 i t c ' - ' (J_-~· ~ . . ? . ! : . / . L : . ' J . ' f . ? Y . , . ' ! M . I I . D e \ \ a p u r a . D a t e I e e r t i t ) t h a t t h e d e c l a r a t i o n a b o v e b y t h e c a n d i d a t e i s t r u e t o t h e b e s t o f m : k n o w l e d g e a n d t h a t t h i s r e p o r t i s a c c e p t a b l e f o r e v e l u a t i o n f o r t h e M S c i n C o m p u t e r S c i e n c e r e s e a r c h p r o j e c t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . P r o f . G i h a n Y . D i a s . P r o f e s s o r . D e p a r t m e n t o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g . U n i v e r s i t y o f M o r a t U \ \ a . I l l D a t e A c k n o w l e d g e m e n t s P r o j e c t s u p e r v i s o r , P r o f . G i h a n Y . D i a s h a s s h o w n l o t o f f l e x i b i l i t y i n c o n s u l t i n g h i m e i t h e r p e r s o n a l l y . t h r o u g h e m a i l s o r e v e n v i a p h o n e a s i t s a v e d l o t o f t i m e a n d e f f i - : J r t a n d l e d u s i n t h e c o r r e c t d i r e c t i o n . A l s o . w e r e f e r r e d r e s e a r c h p a p e r s p u b l i s h e d b y h i m . H i s i n t e r v e n t i o n h e l p e d t o f i n d r e s e a r c h m a t e r i a l s , c o l l e c t t h e S i n h a l a C o r p u s e t c . I w o u l d r e a l l y l i k e t o a p p r e c i a t e h i s s u p p o r t e x t e n d e d t o d a t e f r o m t h e d a y t h e p r o j e c t h a s i n i t i a t e d . M r . K a s u n K a r u n a r a t n a , w h o i s a M . S c . s t u d e n t i n t h e C o m p u t e r S c i e n c e a n d E n g i n e e r i n g d e p a r t m e n t o f t h e L 1 n i v e r s i t y o f M o r a t u w a , g a v e u s a t o o l t o c o n v e r t n o n - U n i c o d e t e x t i n t o U n i c o d e t e x t . I t w a s r e a l l y h e l p e d u s t o c o l l e c t w o r d s i n U n i c o d e f o r m a t . D r . R u w a n W e e r a s i n g h a , L a n g u a g e T e c h n o l o g y R e s e a r c h L a b o f t h e U n i v e r s i t y o f C o l o m b o w a s a b l e t o p r o v i d e u s t h e b e t a v e r s i o n o f t h e S i n h a l a C o r p u s a n d w i t h o u t i t . b u i l d i n g o f t h e S i n h a l a w o r d d a t a b a s e h a d n o t b e e n s u c c e s s f u l . A l s o , I w o u l d b e t h a n k f u l t o a l l t h e l e c t u r e s i n t h e D e p t . o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g , U n i v e r s i t y o f M o r a t u w a , w h o a t t e n d e d t o m y p r o g r e s s p r e s e n t a t i o n s . T h e i r f e e d b a c k l e d u s i n t h e c o r r e c t p a t h . S p e c i a l t h a n k i s d e s e r v e d b y D r . S a n a t h J a y a s e n a f o r h i s r e l e n t l e s s e f f o r t s o n s c h e d u l i n g p r o g r e s s m e e t i n g s a n d g u i d i n g u s o n a m e t h o d i c a l p r o j e c t p r o g r e s s . v T a b l e o f C o n t e n t s D e c l a r a t i o n . . . . . . . . . . . P a g e A b s t r a c t . . . . . . . . . . . . . . . . : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : . :~ A c k n o w l e d g e 1 n e n t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v L i s t o f F i g u r e s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v i i i L i s t o f T a b l e s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i x 1 . 0 C h a p t e r 1 - I n t r o d u c t i o n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 . 0 C h a p t e r 2 - L i t e r a t u r e R e v i e w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 . 1 T e x t E n t r y M e t h o d s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 . 1 . 1 K e y b o a r d s a n d a l l o c a t i o n s o f l e t t e r s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 . 1 . 2 C h o r d e d K e y b o a r d s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 . 1 . 3 V i r t u a l K e y b o a r d s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 . 1 . 4 T o u c h - s c r e e n s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 . 1 . 5 K e y p a d s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 . 2 U n i c o d e R e p r e s e n t a t i o n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 6 2 . 3 T 9 S o l u t i o n s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0 2 . 3 . 1 T 9 T e x t I n p u t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0 2 . 3 . 2 T 9 T e x t o u t p u t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 2 . 3 . 3 X T 9 M o b i l e I n t e r f a c e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 2 . 3 . 4 T 9 C o d i n g S y s t e m s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4 2 . 3 . 5 T 9 V s M u l t i - t a p t e x t e n t r y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 9 2 . 4 D i c t i o n a r y B u i l d i n g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 9 2 . 4 . 1 B u i l d i n g o f a C o r p u s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 0 2 . 4 . 2 C o r p u s A n n o t a t i o n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1 2 . 4 . 3 D o c u m e n t a t i o n o f t h e U C S C / L T R L S i n h a l a C o r p u s . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 3 . 0 C h a p t e r 3 - M e t h o d o l o g y o f D e s i g n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 3 . 1 M e t h o d o l o g y O v e r v i e w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 3 . 2 I m p l e m e n t a t i o n o f S i n h a l a T 9 t e x t e n t r y s y s t e m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 8 V I 3 . 2 . 1 B u i l d i n g o f a S i n h a l a D i c t i o n a r y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 8 3 . 2 . 2 D e v e l o p m e n t o f a n a l g o r i t h m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 3 . 2 . 3 D e v e l o p m e n t o f a n a p p l i c a t i o n f o r S i n h a l a T 9 t e x t e n t r y s y s t e m . . . . . . 4 6 4 . 0 C h a p t e r 4 - A n a l y s i s , c o n c l u s i o n a n d f u t u r e w o r k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1 4 . I T 9 S i n h a l a D i c t i o n a r y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1 4 . 2 T 9 - P C S i m u l a t o r . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1 4 . 3 A d d i t i o n a l F e a t u r e s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1 4 . 3 . 1 A b i l i t y t o a d d u s e r ' s o w n w o r d s . . . . : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1 4 . 3 . 2 A b i l i t y t o c o m p l e t i n g w o r d s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 4 . 3 . 3 A b i l i t y t o a d j u s t t h e o r d e r o f t h e w o r d s b a s e d o n u s e r p r e f e r e n c e . . . . . 5 2 4 . 4 F u t u r e w o r k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 4 . 4 . 1 A b i l i t y t o a d j u s t t h e o r d e r o f t h e w o r d s b a s e d o n u s e r p r i o r u s a g e . . . . 5 2 4 . 4 . 2 N e x t w o r d p r e d i c t i o n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 4 . 4 . 3 E n h a n c e d w o r d c o m p l e t i o n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 5 . 0 C h a p t e r 5 - S u m m a r y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 6 . 0 R e f e r e n c e s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4 V I I L i s t o f F i g u r e s P a g e F i g u r e I : A l l o c a t i o n o f l e t t e r s i n t h e U S E n g l i s h k e y b o a r d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 F i g u r e 2 : A l l o c a t i o n o f l e t t e r s i n t h e F r e n c h ( F r a n c e ) k e y b o a r d . . . . . . . . . . . . . . . . . . . . . . . 6 F i g u r e 3 : T h e D i v e h i P h o n e t i c k e y b o a r d l a y o u t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 F i g u r e 4 : W i j e s e k a r a K e y b o a r d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 F i g u r e 5 : S t a n d a r d S i n h a l a c o m p u t e r k e y b o a r d l a y o u t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 F i g u r e 6 : A n e r g o n o m i c c h o r d e d k e y b o a r d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 F i g u r e 7 : A s t a n d a r d m o b i l e p h o n e k e y p a d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I I F i g u r e 8 : T h r e e d i f f e r e n t E n g l i s h k e y p a d l a y o u t s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I 2 F i g u r e 9 : K e y p a d d e s i g n f o r T a m i l i n a l p h a b e t i c a l a r r a n g e m e n t . . . . . . . . . . . . . . . . . . . . . . 1 3 F i g u r e I 0 : T h e S i n h a l a k e y p a d l a y o u t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 5 F i g u r e I I : X T 9 M o b i l e I n t e r f a c e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 F i g u r e 1 2 : A l l o c a t i o n o f E n g l i s h l e t t e r t o k e y p a d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4 F i g u r e I 3 : C l a s s i f i c a t i o n o f t h e a r t i c l e s i n t h e c o r p u s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 F i g u r e 1 4 : F u n c t i o n a l i t y o f t h e T 9 T e x t e n t r y s y s t e m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 F i g u r e 1 5 : T 9 T e x t E n t r y S y s t e m F l o w c h a r t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 F i g u r e 1 6 : F i n d l i s t o f c o m p l e t e w o r d s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5 F i g u r e 1 7 : F i n d l i s t o f p a r t i a l w o r d s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 5 F i g u r e 1 8 : T y p i n g w o r d - @ c 2 5 ' l D J - a f t e r k e y p r e s s 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 7 F i g u r e 1 9 : T y p i n g w o r d - @ c 2 5 ' l D J - a f t e r k e y p r e s s 8 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 7 F i g u r e 2 0 : T y p i n g w o r d - @ c 2 5 ' l D J - a f t e r k e y p r e s s 8 9 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8 F i g u r e 2 1 : T y p i n g w o r d - @ c 2 5 ' l D J - a f t e r k e y p r e s s 8 9 7 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 8 F i g u r e 2 2 : T y p i n g w o r d - @ C 2 5 l D J - a f t e r k e y p r e s s 8 9 7 0 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 9 F i g u r e 2 3 : S a m p l e s e n t e n c e - ' ' ® ® e r r ; ® ; ; s l ' ® 2 5 ' l u < 3 ' C D c ; 6 6 2 5 ' l 8 J " . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 9 F i g u r e 2 4 : T 9 - 0 F F 1 n o d e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 0 V I I I L i s t o f T a b l e s P a g e T a b l e 1 : T h e b e s t e i g h t - k e y c o n s t r a i n e d a n d u n c o n s t r a i n e d k e y p a d d e s i g n s . . . . 1 2 T a b l e 2 : T h e a s s i g n m e n t o f S i n h a l a c h a r a c t e r s t o k e y p a d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 5 T a h l e .~ : T h e l . : n i c o d e c h a r a c t e r s a s s i g n e d t o S i n h a i a l e t t e r s a n d s i g n s . . . . . . . . . . . . i 8 T a b l e 4 : S a m p i e w o r d s f r o m t h e d a t a b a s e a n d t h e i r f r e q u e n c i e s . . . . . . . . . . . . . . . . . . . . . . . 4 1 T a b l e 5 : S a m p l e w o r d s a n d t h e i r k e y c o m b i n a t i o n s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 T a b l e 6 : O r d e r i n g w o r d s w i t h s a m e k e y .~equences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 0 I X