Differences

This shows you the differences between two versions of the page.

research:articles:progress_20110228 [2011/12/18 20:24]
chiragmehta [Background]
research:articles:progress_20110228 [2019/11/07 19:40] (current)
Line 4: Line 4:
  
   This is the final solution for my experiment to find the most optimal keyboard layout for use by one-finger or cursor+click movement:   This is the final solution for my experiment to find the most optimal keyboard layout for use by one-finger or cursor+click movement:
-  +
     V D R N G F Q     V D R N G F Q
     _ A E I O U _     _ A E I O U _
     K H T S L B J     K H T S L B J
     X C W M Y P Z     X C W M Y P Z
-     + 
-  The vowels in the second row would be enlarged to cover the width of the entire row.  +  The vowels in the second row would be enlarged to cover the width of the entire row.
  
 ==== Background ==== ==== Background ====
  
-The primary goal of the [[:home|KType]] project is to improve communication for people with [[research:disabilities|disabilities]]. I am developing an [[http://ktype.net|iPad app]] that presents the users with an on-screen keyboard with large keys that can be re-arranged easily for comfort and efficiency. The application makes communication easier by predicting what the user will type next. I [[research:articles:progress_20110209|analyzed how people talk]] on Twitter to create KType's prediction engine. Improving prediction is just one way to reduce the effort needed to communicate. Another way is to minimize the amount of movement required to type.+The primary goal of the [[:home|KType]] project is to improve communication for people with [[research:disabilities|disabilities]]. I am developing an [[https://ktype.net|iPad app]] that presents the users with an on-screen keyboard with large keys that can be re-arranged easily for comfort and efficiency. The application makes communication easier by predicting what the user will type next. I [[research:articles:progress_20110209|analyzed how people talk]] on Twitter to create KType's prediction engine. Improving prediction is just one way to reduce the effort needed to communicate. Another way is to minimize the amount of movement required to type.
 ==== Motivation ==== ==== Motivation ====
  
-The computer keyboard layout we are all familiar with is called QWERTY based on the first six letters in the top row. It was [[http://home.earthlink.net/~dcrehr/whyqwert.html|designed by C. L. Sholes]] in 1878 for using a typewriter with two hands and the letters were arranged in a special, non-alphabetical order to improve the speed of typing by minimizing jamming of the typewriter. Since computer keyboards don't jam, many people have tried to re-arrange the keyboard layout to improve typing efficiency; a layout popular among computer programmers is called [[http://en.wikipedia.org/wiki/Dvorak_Simplified_Keyboard|Dvorak]]. But all of these layouts are optimized for users with two hands, ten fingers.+The computer keyboard layout we are all familiar with is called QWERTY based on the first six letters in the top row. It was [[https://home.earthlink.net/~dcrehr/whyqwert.html|designed by C. L. Sholes]] in 1878 for using a typewriter with two hands and the letters were arranged in a special, non-alphabetical order to improve the speed of typing by minimizing jamming of the typewriter. Since computer keyboards don't jam, many people have tried to re-arrange the keyboard layout to improve typing efficiency; a layout popular among computer programmers is called [[https://en.wikipedia.org/wiki/Dvorak_Simplified_Keyboard|Dvorak]]. But all of these layouts are optimized for users with two hands, ten fingers.
  
 Potential users of KType might use head-tracking and blink-action to type. Existing keyboard layouts are inefficient for typing with a single finger or cursor+click movement. KType users could certainly benefit from a keyboard layout that requires the least amount of movement when typing with just one finger. With that goal in mind, I sought to design such a layout - the Optimus Keyboard Layout. Potential users of KType might use head-tracking and blink-action to type. Existing keyboard layouts are inefficient for typing with a single finger or cursor+click movement. KType users could certainly benefit from a keyboard layout that requires the least amount of movement when typing with just one finger. With that goal in mind, I sought to design such a layout - the Optimus Keyboard Layout.
Line 36: Line 36:
  
   Imagine just three keys 'A', 'C', and 'T' arranged next to each other like [A][C][T]:   Imagine just three keys 'A', 'C', and 'T' arranged next to each other like [A][C][T]:
-  +
   Distance between A and C                            1   Distance between A and C                            1
   Frequency of typing 'AC' or 'CA'               x  200  =  200 (for A, C)   Frequency of typing 'AC' or 'CA'               x  200  =  200 (for A, C)
Line 51: Line 51:
  
   Re-arrange the three keys 'A', 'C', and 'T' to [C][A][T]:   Re-arrange the three keys 'A', 'C', and 'T' to [C][A][T]:
-  +
   Distance between A and C                            1   Distance between A and C                            1
   Frequency of typing 'AC' or 'CA'               x  200  =  200 (for A, C)   Frequency of typing 'AC' or 'CA'               x  200  =  200 (for A, C)
Line 74: Line 74:
  
 These restrictions mean that I could be ignoring a more efficient keyboard layout (possibly circular) but given the fact that almost every keyboard in existence is close to a grid (3 rows of 10 keys) and the iPad has a rectangular screen, a grid-like layout will work for my users. The closer the grid is to a square, the lower the score is. I prefer 7x4 (28 key slots) grid because it is closer to square than 9x3 (27 key slots) and only has two blanks as compared to 6x5 (30 key slots) grid with 4 blanks. Additionally, the KType interface is suited quite well for [[progress_20110204#keyboard_in_use|4 rows of letters]]. These restrictions mean that I could be ignoring a more efficient keyboard layout (possibly circular) but given the fact that almost every keyboard in existence is close to a grid (3 rows of 10 keys) and the iPad has a rectangular screen, a grid-like layout will work for my users. The closer the grid is to a square, the lower the score is. I prefer 7x4 (28 key slots) grid because it is closer to square than 9x3 (27 key slots) and only has two blanks as compared to 6x5 (30 key slots) grid with 4 blanks. Additionally, the KType interface is suited quite well for [[progress_20110204#keyboard_in_use|4 rows of letters]].
-  + 
-The 26 alphabets could be arranged into a grid of 7x4 in over 10^29 ways, into a grid of 6x5 in over 10^32 ways. Planet Earth has only [[http://www.wolframalpha.com/input/?i=number+of+atoms+on+earth|10^50 atoms]] so given the current state of technology and my dwindling savings account, it is impossible to simulate every possible keyboard layout and calculate its score to find Optimus. In computer science terms, this is problem is in [[http://en.wikipedia.org/wiki/NP_(complexity)|NP]].+The 26 alphabets could be arranged into a grid of 7x4 in over 10^29 ways, into a grid of 6x5 in over 10^32 ways. Planet Earth has only [[https://www.wolframalpha.com/input/?i=number+of+atoms+on+earth|10^50 atoms]] so given the current state of technology and my dwindling savings account, it is impossible to simulate every possible keyboard layout and calculate its score to find Optimus. In computer science terms, this is problem is in [[https://en.wikipedia.org/wiki/NP_(complexity)|NP]].
  
 ==== Reddit & Computer Science to the rescue ==== ==== Reddit & Computer Science to the rescue ====
  
-After realizing that I was trying to find a perfect solution to an uncomputable problem, I decided to put my four years of college to use. I dug into [[http://en.wikipedia.org/wiki/Computational_complexity_theory|complexity theory]] articles and papers to see if someone has solved this exact problem but that effort was fruitless. I turned to [[http://www.reddit.com/r/compsci/comments/fo96y/ask_cs_what_npproblem_am_i_trying_to_solve_here/|reddit/r/compsci]] subreddit and rephrased my problem into more understandable terms: How would you seat 26 people in a big room of cubicles such that people who like each other a lot end up sitting close to each other? While I did not get an exact answer (and neither did I expect one), I got a lot of leads: genetic optimization, dynamic programming, distance preserving embedding graphs, facilities problem, k-means clustering, and simulated annealing.+After realizing that I was trying to find a perfect solution to an uncomputable problem, I decided to put my four years of college to use. I dug into [[https://en.wikipedia.org/wiki/Computational_complexity_theory|complexity theory]] articles and papers to see if someone has solved this exact problem but that effort was fruitless. I turned to [[https://www.reddit.com/r/compsci/comments/fo96y/ask_cs_what_npproblem_am_i_trying_to_solve_here/|reddit/r/compsci]] subreddit and rephrased my problem into more understandable terms: How would you seat 26 people in a big room of cubicles such that people who like each other a lot end up sitting close to each other? While I did not get an exact answer (and neither did I expect one), I got a lot of leads: genetic optimization, dynamic programming, distance preserving embedding graphs, facilities problem, k-means clustering, and simulated annealing.
  
-I was very interested in using genetic algorithms to evolve a better keyboard from two or more good keyboards but found it impossible to combine two keyboard layouts into a new one. How would one combine the QWERTY and DVORAK layouts to create a new generation in one-pass anyway? I had similar issues in applying k-means clustering, graph layouts etc. to my problem. I don't mean it is impossible to use these methods, I just couldn't find a logical, simple way to apply these solutions to my problem. After fiddling with tons of algorithms, I found that [[http://en.wikipedia.org/wiki/Simulated_annealing|simulated annealing]] works pretty nicely for this particular problem.+I was very interested in using genetic algorithms to evolve a better keyboard from two or more good keyboards but found it impossible to combine two keyboard layouts into a new one. How would one combine the QWERTY and DVORAK layouts to create a new generation in one-pass anyway? I had similar issues in applying k-means clustering, graph layouts etc. to my problem. I don't mean it is impossible to use these methods, I just couldn't find a logical, simple way to apply these solutions to my problem. After fiddling with tons of algorithms, I found that [[https://en.wikipedia.org/wiki/Simulated_annealing|simulated annealing]] works pretty nicely for this particular problem.
  
-Update 2011-02-28, 1:25pm: Redditor [[http://www.reddit.com/r/compsci/comments/fu8p1/thanks_for_helping_me_rcompsci_i_used_your/c1iozyc|deong]] mentioned that this problem is called [[http://en.wikipedia.org/wiki/Quadratic_assignment_problem|Quadratic assignment problem]], which is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.+Update 2011-02-28, 1:25pm: Redditor [[https://www.reddit.com/r/compsci/comments/fu8p1/thanks_for_helping_me_rcompsci_i_used_your/c1iozyc|deong]] mentioned that this problem is called [[https://en.wikipedia.org/wiki/Quadratic_assignment_problem|Quadratic assignment problem]], which is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.
 ==== Algorithms behind Optimus ==== ==== Algorithms behind Optimus ====
  
Line 100: Line 100:
  
   Rank #1, Score: 130575410797   Rank #1, Score: 130575410797
-  +
     _ J Y M L D Z     _ J Y M L D Z
     Q B U O A N G     Q B U O A N G
Line 106: Line 106:
     _ V F S H W K     _ V F S H W K
  
-  +
   Rank #2, Score: 130676148330   Rank #2, Score: 130676148330
-  +
     _ K W H S F V     _ K W H S F V
     X C I T E R P     X C I T E R P
Line 116: Line 116:
  
   Rank #3, Score: 130683308691   Rank #3, Score: 130683308691
-  +
     V F S H W K _     V F S H W K _
     P R E T I C Z     P R E T I C Z
Line 152: Line 152:
  
   Rank #1, Score: 135242359724   Rank #1, Score: 135242359724
-  +
     V D R N G F Q     V D R N G F Q
     _ A E I O U _     _ A E I O U _
Line 207: Line 207:
  
   Score: 234828339277 - QWERTY   Score: 234828339277 - QWERTY
-  +
     Q W E R T Y U I O P     Q W E R T Y U I O P
     A S D F G H J K L _     A S D F G H J K L _
Line 214: Line 214:
  
   Score: 285170559534 - DVORAK   Score: 285170559534 - DVORAK
-  +
     _ _ P Y F G C R L _     _ _ P Y F G C R L _
     A O E U I D H T N S     A O E U I D H T N S
Line 221: Line 221:
  
   Score: 228186373801 - ABCDEF   Score: 228186373801 - ABCDEF
-  +
     A B C D E F G H I _     A B C D E F G H I _
     J K L M N O P Q R _     J K L M N O P Q R _
Line 228: Line 228:
  
   Score: 142812598543 - Random Grid 10x3   Score: 142812598543 - Random Grid 10x3
-  +
     X V W H E R M B J _     X V W H E R M B J _
     Z C D A T O U Y P _     Z C D A T O U Y P _
Line 235: Line 235:
  
   Score: 130575410797 - Random Grid 7x4   Score: 130575410797 - Random Grid 7x4
-  +
     _ J Y M L D Z     _ J Y M L D Z
     Q B U O A N G     Q B U O A N G
Line 243: Line 243:
  
   Score: 135242359724 - Fixed Vowel Row - Optimus   Score: 135242359724 - Fixed Vowel Row - Optimus
-    +
     V D R N G F Q     V D R N G F Q
     _ A E I O U _     _ A E I O U _
Line 251: Line 251:
 The Random Grid 10x3 layout is 40% better than QWERTY and 50% better than DVORAK. Surprisingly, the simple ABCDEF is better than both QWERTY and DVORAK when it comes to typing regular English words with one-finger but it is still no match for Random Grid 10x3. The absolute best layout is indeed Random Grid 7x4 but it is only marginally better than the best Fixed Vowel Row layout - Optimus. The Random Grid 10x3 layout is 40% better than QWERTY and 50% better than DVORAK. Surprisingly, the simple ABCDEF is better than both QWERTY and DVORAK when it comes to typing regular English words with one-finger but it is still no match for Random Grid 10x3. The absolute best layout is indeed Random Grid 7x4 but it is only marginally better than the best Fixed Vowel Row layout - Optimus.
  
-I will be using this Optimus layout in the KType iPad application. The Optimus Keyboard Layout and all the other layouts I designed as part of KType are released under [[http://creativecommons.org/licenses/by/3.0/|Creative Commons Attribution 3.0 Unported]] license. You are free to use these layouts in your products and projects freely. Feel free to [[people:Chirag Mehta|contact me]] if you wish to discuss customizing these layouts to better suit your application.+I will be using this Optimus layout in the KType iPad application. The Optimus Keyboard Layout and all the other layouts I designed as part of KType are released under [[https://creativecommons.org/licenses/by/3.0/|Creative Commons Attribution 3.0 Unported]] license. You are free to use these layouts in your products and projects freely. Feel free to [[people:Chirag Mehta|contact me]] if you wish to discuss customizing these layouts to better suit your application.
  
 ==== Download Source Code ==== ==== Download Source Code ====
  
-Download: [[http://ktype.net/share/ktype-design-optimus.zip|ktype-design-optimus.zip]] (480 kb).+Download: [[https://ktype.net/share/ktype-design-optimus.zip|ktype-design-optimus.zip]] (480 kb).
  
 The file contains the following letter-pair frequency table, Python source code to generate the keyboard layouts using various algorithms, resulting keyboard layouts, and analysis of simulated annealing effects. The file contains the following letter-pair frequency table, Python source code to generate the keyboard layouts using various algorithms, resulting keyboard layouts, and analysis of simulated annealing effects.
Line 585: Line 585:
 |J|Z|5151| |J|Z|5151|
 |Q|Z|3030| |Q|Z|3030|
 +
 
research/articles/progress_20110228.1324268653.txt.gz · Last modified: 2011/12/18 20:24 by chiragmehta
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki