Design of Urdu Virtual Keyboard

Document Sample
Design of Urdu Virtual Keyboard Powered By Docstoc
					                         Proceedings of the Conference on Language & Technology 2009

                                 Design of Urdu Virtual Keyboard

                        M. Aamir Khan, M. Abid Khan and M. Naveed Ali
                 Department of Computer Science University of Peshawar, Pakistan

                     Abstract                                                          1         A   
                                                                              MT =         log 2  + 1
   This paper presents the first ever virtual keyboard
                                                                                      4 .9       W   
layout based on character frequency analysis of Urdu
                                                                    Here, W is the width of the key and A is the
Corpus. To optimize the keyboard layout Monte Carlo             distance to move to the target key K. Each mean time
Simulation with simulated annealing is used.                    was weighted by the digraph probability. The wpm
Furthermore, the proposed keyboard layout is                    (words per minute) was calculated by multiplying MT
augmented with word prediction list derived from                with the average number of characters per word. The
Urdu corpus to speed up text entry. Performance                 computed wpm is an “upper limit” on the text entry
analysis of keyboard layout is done for justification           speed. The “visual scan” time to find a key was
                                                                assumed to be zero. The keyboard layout can be done
                                                                manually [5] or using optimization techniques such as
                                                                Monte Carlo simulation [6].
1. Introduction
                                                                2. Urdu virtual keyboard design
    Virtual/soft keyboards allow users, to input text
using touch screen and stylus. For English language,                 Urdu has 37 base characters. The character set used
several virtual keyboard layouts have been proposed.            for designing the keyboard, proposed in this research
These include MacKenzie’s and Zhang’s OPTI layout,              paper, also contains Arabic characters. This facilitates
improved OPTI layout in a 5x6 layout (OPTI II) with             keypad to be used for entering Arabic text as well, but
38 wpm (words per minute), FITALY keyboard and                  it is not optimized for Arabic language. Table 1 shows
Chubon keyboards [6]. Evaluation of the performance             the set of Urdu alphabets.
of virtual keyboards involves the use of Fitts’ Law
[1][2]. Keyboard input speed is measured in wpm                         Table 1: Urdu language characters
(words per minute). Mean time (MT), to move to a key
on virtual keyboard, is computed in terms of moving                            ‫ت‬           ‫پ‬          ‫ب‬          ‫ا‬
to a target key K of width W lying at distance A from               ‫خ‬          ‫ح‬           ‫چ‬          ‫ج‬          ‫ث‬
the current position of pointing device [3]. The layout                        ‫ر‬           ‫ذ‬                     ‫د‬
of keys on virtual keyboard should be such that to                  ‫ص‬          ‫ش‬           ‫س‬          ‫ژ‬          ‫ز‬
minimize the mean time for all digraph movements.                   ‫غ‬          ‫ع‬           ‫ظ‬          ‫ط‬          ‫ض‬
The digraph frequencies are a natural feature of                    ‫ل‬          ‫گ‬                      ‫ق‬          ‫ف‬
languages. Mackenzie and Zhang evaluated the
                                                                    ‫ه‬                      ‫و‬          ‫ن‬          ‫م‬
performance of their virtual keyboard by computing
27x27 digraph frequencies from a corpus [5]. The
                                                                                ‫ة‬                     ‫ء‬           ‫ؤ‬
distances (amplitudes) for all the 27 x 27 digraph
movements in a given keyboard layout were
                                                                   The first step in designing a virtual keyboard is to
computed, and for each movement the Fitts’ Law was              determine the digraph frequencies. For Urdu language
used to compute the MT [5]. The following equation              computing, digraph frequencies require a corpus. A
was used to compute the MT [5].                                 raw corpus consisting of 16,638,852 words was
                                                                collected. It contained collections of newspaper

                        Proceedings of the Conference on Language & Technology 2009

articles, books and magazines. Table 2 shows the                 691                             143244             0.26029
character frequencies of individual Urdu alphabets in
                                                                 636              ‫ض‬              142813             0.25951
descending order.
                                                                 638               ‫ظ‬             104163             0.18928
     Table 2: Urdu character frequencies                         63a               ‫غ‬             100331             0.18231
                                                                 630               ‫ذ‬              79372             0.14423
Unicode      Alphabet     Frequency     Percentage
                                                                 62b              ‫ث‬               69641             0.12655
   627           ‫ا‬         6733610        12.23570
                                                                 624               ‫ؤ‬              32355             0.05879
   6cc                     5752357        10.45266
                                                                 621               ‫ء‬              24930             0.04530
   6a9                     3911143         7.10697
                                                                 6c2                              4390              0.00798
   631           ‫ر‬         3669392         6.66768
                                                                 698               ‫ژ‬              2522              0.00458
   648           ‫و‬         3327481         6.04639
                                                                 629               ‫ة‬              2275              0.00413
   6c1                     2994305         5.44098
                                                                 6d3                              1479              0.00269
   6d2                     2857846         5.19302
                                                                Total                           55032482          100.00000
   646           ‫ن‬         2773651         5.04003
   645           ‫م‬         2684946         4.87884
                                                                  The 46x46 digraph frequency table was computed
   62a          ‫ت‬          2117669         3.84803            from the corpus. The digraph is shown in the form of
   633          ‫س‬          1987451         3.61141            color chart in Figure 1. The dark shaded cells represent
                                                              higher frequency digraphs, whereas light shaded cells
   644           ‫ل‬         1915841         3.48129            represent lower frequency digraphs.
   628          ‫ب‬          1492997         2.71294                In Figure 1, the character on the Y axis shows the
  6ba                      1469466         2.67018
                                                              first character while the one on the X axis shows the
                                                              second character in a digraph. The order of characters
   62f           ‫د‬         1431230         2.60070            in columns and rows of digraph’s color chart is the
   67e          ‫پ‬           914273         1.66133            same as in table 1. The last column and the last row
   62c          ‫ج‬           844670         1.53486
                                                              represent the space character. The digraph frequency
                                                              table was used for computing the wpm performance of
  6be            ‫ه‬          800600         1.45478            the keyboard.
   626          ‫ئ‬           664594         1.20764
                                                                 To compute the performance of a given keyboard
   6af          ‫گ‬           643263         1.16888
                                                              layout, the following equation was used [5].
   639           ‫ع‬          636166         1.15598
   641                      546973         0.99391                          k     k
                                                                                         1         A         
   642          ‫ق‬           544460         0.98934                 MT = ∑∑                   log 2  i , j + 1 × d (i, j )
                                                                                                   W         
                                                                           i =0   j = 0 4 .9                 
   634          ‫ش‬           532262         0.96718
   62d          ‫ح‬           501602         0.91147                Here, Ai,j is the distance from key i to key j. The
   632           ‫ز‬          454158         0.82525            d(i,j) represents the digraph frequency of character i
   679                      420666         0.76440            followed by character j. The variable k is the number
   686          ‫چ‬           358159         0.65081
                                                              of characters in a given language. The diagonal entries
                                                              in digraph frequency table where i=j denote repeated
   62e          ‫خ‬           352729         0.64095
                                                              character where no movement of stylus is involved.
   635          ‫ص‬           327434         0.59498
                                                              For repeated characters, the repeat stylus tapping time
   622                      259879         0.47223            was set as 0.127 seconds as in Zhai [6].
   637          ‫ط‬           220613         0.40088
   688                      183081         0.33268

                         Proceedings of the Conference on Language & Technology 2009

                                     Figure 1: Urdu digraph color chart

    Designing a keyboard layout is a combinatorial            of keys is based on the work of Zhai et. al [6]. Figure
task and requires O(n!) searches [6]. The layout              2 shows the optimized layout of the Urdu keyboard.
should be arranged such that the MT is minimized.
For optimizing the keyboard layout, 700 runs of                   The speed of entering text, using the layout in
Monte-Carlo Simulation with simulated annealing               figure 2, was computed using the following equation
were executed. The best layout was found at 53rd              from Zhai [6].
simulation. In each run 100,000-200,000 random
movements were tried each on keyboard layout.                                 wpm = 60 / AWL× MT
Annealing schedule was adjusted by trial and error.
The width of each key was set at 50 pixels. The shape         where AWL is the average word length in a language.
                                                              MT is the mean time. In Urdu language, the average

                        Proceedings of the Conference on Language & Technology 2009

word size was found to be 7 characters. The constant         Figure 3: Improved Urdu virtual keyboard to
60 is the number of seconds in a minute. When a                 utilize the empty gaps between keys
space after each word is added it becomes 8
characters.                                                      A prototype version of keyboard was
                                                             implemented using Microsoft Visual C++ 6.0 for
                                                             Microsoft windows. The program helped the user by
                                                             highlighting the next probable keys and drawing
                                                             rings around the keys. The darker color showed the
                                                             higher probability of occurrence while the lighter
                                                             color showed lower probability of occurrence. The
                                                             most probable next character shows the ring in
                                                             blinking mode.

                                                                 Figure 4 shows the typing of the word          on
                                                             the keyboard. After the first three characters have
                                                             been entered, the next set of probable characters is
                                                             highlighted in different shades of red color. To
                                                             further improve the performance of user input speed,
                                                             a prediction list was added. Figure 5 shows the use of
                                                             prediction list.

   Figure 2: Corpus based optimized Urdu
virtual keyboard layout arranged in 7x7 cells

   For the optimized keyboard, MT was found to be

                 MT = 0.20609985

          wpm = (60/8×0.20609985) = 36.3901 wpm

    The predicted speed of the keyboard is thus
36.3901 words per minute. To utilize the space
between circular keys, the shape of keys was changed
to hexagonal. Figure 3 shows the improved design of
optimized layout.
                                                              Figure 4: Predictive input of the word ‫ر‬

                                  Proceedings of the Conference on Language & Technology 2009

Figure 5: Input with prediction list assistance                          ‫ا‬           ‫ا پ ن‬        41801         10
                                                                                 ‫ا‬                41399          5
   For analysis, the performance of the keyboard was
                                                                     ‫پ‬               ‫پ‬            40080          6
determined on various words. Table 3 shows the
                                                                                 ‫ا‬     ‫گ‬          39963          5
computed distances of typing 38 most frequently
occurring words [2] in the corpus along with a space                                 ‫ج س‬          38483          5
character after each word. The distances are                                          ‫ت ه‬         37790          6
computed in terms of keys to traverse a given                                          ‫ت‬          37160          4
particular word. The distance covered depends on the
position of keys and characters in a word.
                                                                   3. Evaluation
     Table 3: Distances for 38 frequent words
           along with a space character                               The proposed layout presented in Figure 2 was
                                                                   evaluated on 20 students of computer science
Word           Characters           Frequency   Distance           program. The average text entry speed was found to
                                     618958         3              be 13.47 wpm based on an initial two hour training
                              ‫م‬      510330         6              prior to the evaluation. The maximum speed achieved
                                     495344         3              was 22.5 wpm. When compared to virtual keyboards
                                                                   for English language, the text entry speed is
                                     417230         4
                                                                   comparable to OPTI and QWERTY layout [5]. The
    ‫اور‬              ‫ا و ر‬           352897         5
                                                                   predicted speed of OPTI layout is 58.2 words. Actual
                        ‫س‬            319683         4
                                                                   speed of OPTI has been found to be 44.3 wpm after
                      ‫ا‬              268072         4              20 sessions of text entry, each for 45 minutes [5].
                     ‫و‬               239480         4              With extended training of the user the text entry
    ‫اس‬                ‫ا س‬            221585         5              speed of Urdu virtual keyboard can be improved.
                        ‫ن‬            200405         4
                                     196799         6              4. Conclusion
                                     184643         3
                     ‫پ ر‬                                               The design of the virtual keyboard presented in
                                     173181         5
                                                                   this paper is based on character analysis of Urdu
                      ‫ب ه‬            127457         5
                                                                   corpus. The virtual keyboard is particularly useful for
                                     120063         2
                                                                   occasional users, who do not want or do not have
         ‫ا‬                    ‫ا‬      116695         4              time to learn the hardware based keyboard layout.
                     ‫ر‬               111749         5              Being the first virtual keyboard for Urdu language,
                              ‫ن‬      103967         7              comparative study of performance with other virtual
    ‫ان‬                ‫ا ن‬             97549         3              keyboards is not possible. The predicted speed of text
                      ‫و‬               90129         4              entry using this keyboard layout is 36.3901 wpm.
                 ‫ا‬                    89452         4              The keyboard is also usable for entering Arabic text,
                   ‫ت و‬                82484         3              but it is not optimized for Arabic.
     ‫و‬                ‫و‬               75497         3
                     ‫ل ئ‬              60458         8              5. References
                  ‫ت ه ا‬               55527         5              [1] P..M. Fitts, “The information capacity of the human
‫ن‬            ‫س ت ا ن‬     ‫پ ا‬          55404        15              motor system in controlling the amplitude of movement”,
                   ‫ر ن‬                52084         8              Journal of Experimental Psychology, 1954, pp. 381-391.
                   ‫ج و‬                51059         4              [2] M. Ijaz and S. Hussain. “Corpus Based Urdu Lexicon
                                      45321         2              Development”, in proc. the conference on Language &
                                                                   Technology (CLT07), Bara Gali Summer Campus,
    ‫و‬                    ‫و‬            43449         2              University of Peshawar, Agust 7-11, 2007, pp. 85-94.
                          ‫ن‬           42718         3

                            Proceedings of the Conference on Language & Technology 2009

[3] I. S. MacKenzie, A. Sellen and W. Buxton, “A
comparison of input devices in elemental pointing and
dragging tasks”, in proc. CHI, 1991.

[4] I. S. MacKenzie, “A note on the information theoretic
basis for Fitts’ law”, Journal of Motor Behavior, 1989, pp.

[5] I. S. MacKenzie and S. X. Zhang, “The Design and
evaluation of a High performance Soft Keyboard”, in proc.
CHI 91, 15-20 May 1999.

[6] S. Zhai, M. Hunter and B. A. Smith, “The Metropolis
Keyboard -- An Exploration of Quantitative Techniques for
Virtual Keyboard Design”, in proc. UIST'2000 - the 13th
Annual ACM Symposium on User Interface Software and
Technology, 2000.


Shared By: