Wednesday, November 23, 2011

One Handed Keyboards and Evolutionary Computing

If you’re reading this you likely have one advantage over me when it comes to typing. You can type the word QWERTY faster than I can.

These letters are found in order on the top row of the majority of the world’s keyboards and typewriters. The arrangement prevents keys jamming together, a design flaw inherent in 19th century typewriters that has long since been remedied. The arrangement was not intended for speed.

So, why am I so slow to type QWERTY? My keyboard is different. I’ve been using a Dvorak keyboard layout for just shy of a decade. Where you have QWERTY I have the letters ‘,.PYF. For your ASDF I have AOEU. The rest of the keyboard is similarly rearranged, the goal being to design an arrangement more conducive to efficient typing.

For every twelve miles your fingers travel typing English text on a QWERTY keyboard, you’ll travel one mile on a Dvorak. This makes typing a more comfortable experience and can reduce the risk of getting RSI.

Why did I make this change?

In 2002 I injured my right hand. Being a real man™ I didn’t seek medical attention and as a result was unable to type or perform other repetitive motions with my right hand for eighteen months. (This affected only my typing and a poorly judged attempt to learn guitar.)

It seems I was not the first person in recorded history to injure themselves and I read details of Colonel Robert Allen with interest. A writer, columnist, solider, KGB spy, high ranking US intelligence officer and former prisoner of war, he lived an interesting life. He lost his right arm in World War Two and rather than try to adapt to using a QWERTY keyboard with one hand he contacted Dvorak and asked if a keyboard’s keys could be better arranged for left hand only use.

Dvorak complied. Allen reached self-reported touch typing speeds of fifty words a minute. I averaged about thirty five, but as a coder I had to use all those awkward curly brackets at the edges of the keyboard. Besides, being able to touch type was more important to me than winning speed tests. Over the years I made a few tweaks, like swapping my spare Alt and Windows keys for shift and backspace respectively, and changing the F5 key for Enter – I can reach that with my middle finger quite easily.

Once my hand healed up I found myself unable to bear the inefficiency of a regular keyboard and learned to use Dvorak’s two handed keyboard.

So, why my renewed interest in keyboard layouts after a decade’s slumber? A friend and I were discussing Armistice Day. For those who don't know it commemorates the end of World War I with the wearing of poppies and a two minute silence. Money from the sale of poppies goes to, among other worthy endeavours, helping rehabilitate injured soldiers. Although it’s often viewed as a primarily British occasion I’m one of a growing number of Irish people who participate. My friend, naturally, was in favour of rehabilitating injured soldiers and taking time to remember those who have sacrificed, but felt that wearing a poppy might be absolving us of a responsibility to do more. As often happens in chats like these we both changed our positions a little and I resolved to see if I could do something practical.

No-one’s put serious research into designing one-handed keyboard layouts over the last sixty years and I’m arrogant enough to feel that I can fill that void.

Dvorak’s research and promotion was exhaustive. He studied the English language intensely, the physiology of the human hand, constructed meticulous timing experiments and invested a decade of his life in background investigations.

That seemed like hard work. I was eager to avoid it.

I started by coming up with a truly awful idea.

  1. Collect my blog posts to date
  2. Generate every possible keyboard layout
  3. Learn how to type on each layout
  4. Retype all my blogs using only one hand
  5. Time and score the results

While effective on paper it seemed time consuming. I’m restricted to evenings and weekends on this project and Mrs Geoff may be a mite peeved if I allocated my time in this manner. Luckily we can automate to a great extent. The length of time it takes to type a body of text is governed by how quickly you move between letters. Take the word ‘GAGA’ for example. That takes me about 318.75 milliseconds to type one-handed. I know this because to move between the keys G and A takes 159.38 milliseconds.  There’s no need to type the second GA, we can just multiply by two. With this in mind we can go through all my blog posts, count how many two letter combinations they have, and how often they occur. For an example, I've used the two letter combination ‘th’ 2,178 times in my blog (and in some other files I threw into the mix). It takes me 99.16 milliseconds to type ‘th’, so I’d need to spend a little under four minutes of my life typing ‘th’ to retype this blog with one hand. By crunching the numbers for all two letter combinations I find I’ve about 22 hours’ worth of typing were I to attempt it with five fingers.

But how did I calculate these timings? Rather than placing my trust in a stopwatch and my reaction times I wrote a small computer program to time my keystrokes. My last few articles have been typed left hand only; my computer calculated the average timings for each two letter combination as I typed.

That’s all well and good for my current layout, you may be tempted to say, but how can you use this data to measure other keyboard layouts? When we change keyboard layouts we rearrange what characters the buttons cause to appear on the screen. These timings don’t change when we swap the characters – it will take your fingers as long to travel from the top left to the bottom right of the keyboard regardless of what the buttons there do. By way of analogy, the time it takes you to walk between the first and last houses on your street will be unaffected if the current occupants move out and new neighbours move in. With that in mind I adapted my program so it could accurately judge the effect rearranging keys would have on my typing speed.

It’s interesting to note that I didn’t need any other data. There’s no internal representation of what a keyboard looks like in my program. As far as it is concerned the keys may well be all in one line, or piled on top of each other, or activated by singing specific frequencies. It has no idea how long my fingers are, how many fingers I have, or if I am in fact typing with my toes. The advantage of this approach is that it will generate a layout adapted to any injury and none for any keyboard, touch screen or other input device.

The finish line seemed in sight. I had good data on how quickly my fingers moved. I could quickly and easily test a layout to see how well it would work for me. All I had to do was adjust the program so it would evaluate every possible layout and I’d be finished. I'd have found the perfect keyboard layout.

Then I ran the numbers. At present I rearrange 49 keys on the keyboard. How many different, unique layouts do you think I could make by rearranging them? The answer is 49 factorial, often written as 49!. This means 49 multiplied by 48, multiplied by 47, multiplied by 46 and so on, all the way down to one. If you type 49! into Google and hit search it will do the multiplication for you. (Pen and paper would take some time, though you're welcome to try.) The result is 6.08281864 × 1062. Basically, it’s a rather large number. The universe is 13.7 billion years old. That’s 4.3 X 1017 seconds. If I started evaluating a million layouts a second at the dawn of the universe I still wouldn’t be anywhere near the halfway point by now. I’d also likely be incredibly bored with the endeavour.

I saw statistical analysis of English text in my future, and evenings spent studying the anatomy of the human hand, following in the noble steps of August Dvorak.

I resisted.

Imagine I made a thousand, random keyboard layouts. None would likely be particularly good. Many would have unusual setups like having the ~ key on the spacebar, or the letter E hidden in a corner, or a duplicated copy of the ` character. Still, some would be better than others. Through sheer force of numbers the program would accidentally produce some layouts with desirable traits.

But what is a desirable trait in this context?

When I type with one hand my fingers rest near the middle of the keyboard. (On a QWERTY keyboard this would be the letters FGHJ.) This central position is a good starting point when reaching for other keys. Now, the letters F, G and J aren't overly useful to me, even if two are required when spelling my name. If I strum my fingers on such a keyboard I'll find I've very quickly typed FGHJ, not a sequence that comes up frequently in English conversation.

Let's say one of my random layouts has the letters ZTHR instead. It's not immediately apparent but this has a slight advantage in that it lets me type the, that, those, theatre, thousands and so on that little bit faster. (It's important at this point to remember at this time that my program doesn't know where my fingers are - all it knows is how quickly I can move between keys.) Another layout may have randomly assigned the letters IN to a fortuitous location. It's like playing the lottery. It's very easy to pick the right lottery numbers if you buy a thousand quick pick tickets and don't worry about getting all the winning numbers on the same line.

So, let's go back to our thousand randomly arranged keyboard layouts. Roughly speaking, half will be above average and half below. Should we examine these better scoring layouts to see what makes them more effective, gather the useful adaptations and attempt to combine them?

This would involve hard work. We'd need to find a way to identify what precisely has made the layout better suited to the task at hand. Anatomy studies would seem likely. We'd need to find a way to balance competing needs: there is much competition for locations near the centre of the keyboard: is TH more useful than IN? Does moving IN from another area of the keyboard break a useful adaptation? Could something whacky, like putting a different key on the space bar, be a useful idea?

I tried for a simpler approach. I made space for another thousand layouts. I filled the first five hundred slots with the winning layouts from my first attempt. The remaining five hundred slots were filled by recombining existing layouts - 80% from the best scoring half, 20% from the other half.

How does this work? We take two layouts, let's call them X and Y. We take a random section (random length, starting at a random position) from layout Y and insert it in a random location in layout X. We then remove any duplicate keys. Do we seek out the best sections of each layout to be combined? No, that would be hard work. Instead we randomly breed layouts and see if the offspring show any improvement. As the process is entirely automated with no requirement for intelligent interaction we can get a computer to do this for us, over and over again, and see what our best result is at every turn. We can also compare our evolved layout's performance against whatever layout we normally use by examining the difference in score.

So, does it work? I started running this on my low-powered netbook about six hours ago. It's still changing, but here's the work in progress.

The underlined keys (V and T) represent the F and J keys on a QWERTY keyboard and are where my little and index fingers rest when typing with my left hand. The extreme left and right of the keyboard are the hardest keys for me to reach, you'll see they have infrequently used keys, and the more commonly used keys are clustered near the centre. (The letter 'I' may look odd but it's the easiest key to reach on the top row - it's right above my longest finger.)

As you can probably tell from the progress bar there's still some work to do. My regular keyboard has a duplicate '\' key, this one suggests a duplicate 'D'. I see this as an improvement, but could be better. You'll notice that the space bar is 'E'. As the most common letter this could be a good choice, but I'll be interested to see if it changes down the line.

So, what are the next steps? This is still a work in progress. I'd like to do longer runs with different population sizes and add more keys into the mix. I'm interested in hearing from others who'd like to get involved in the project. I'm especially interested in talking to any one-handed typists who'd be willing to have their typing timed, occupational therapists, or anyone who feels this might have practical applications in their lives.

Do let me know your thoughts.


Unknown said...

very nice post! I have been wondering whether the flat-style table-top layout is even "optimal". A ball or cube like object with keys dotted around strategically seems like it might allow lightening fast typing... like a mega ps3 controller!

Geoff said...

Interesting question! Not sure how I'd code for it though...