Beyond Dvorak via Genetic Algorithm

ColonelPanic writes: "I switched my computer keyboard to the Dvorak layout about a year ago. But now I've gone and done something really outlandish. I tried to discover the most efficient layout possible with a genetic algorithm. It's weird-looking, but I am typing with it now. I put the gory details up on the Web."

Comments

Other uses of genetic algorithms

[Anonymous Coward]

I used a genetic algorithm to figure out the best way for arranging my feet when I walk.

Results:

left

right

left

right...

choice of benchmark text

[Hollins]

I appreciate that he uses a lot of text for analysis. Ten years of email and C++ code are nice additions. However, the inclusion of the King James Bible and a few other works may have skewed the results somewhat, as shown by the presence of the word "thou" in the most-often used words list.

non qwerty-keyboards and unix

[jafuser]

The problem I've had with non-qwerty keyboards is that unix seems to be designed for qwerty, as you'll notice most of the common commands (ls, ps, pwd, cd) seem to be fairly "comfortable" to type, whereas when I was playing around with using dvorak once for a few weeks, it just felt much more awkward to type unix commands.

An improvement on the idea

[orangesquid]

You know what I really should do? There are certain words I *always* mistype with QWERTY, and I'm convinced it's partly the fault of the layout... I should use a genetic algorithm that evaluates based on speed *and* on letter arrangement, somehow. Not sure how to do this... but right now I'm running this command to see what words I mispell most often when using instant messenger:

nice cat ~/.gaim/logs/*.log|fgrep 'me:'|ispell -H -l|sort|uniq -c >~/badwords 2>/dev/null &

I love UNIX.

This genetic algorithm doesn't have sex

[XNormal]

According to the description in the article the algorithm has random seeding, mutations, a ranking function and survival of the fittest - but it doesn't have genetic exchange. New layouts are not chosen as combinations of two or more existing layouts.

Genetic exchange is very important for rapid evolution. The Earth was just a big bacterial soup for two billion years. Then sex was invented and then things started to get more interesting very quickly.

Re:This genetic algorithm doesn't have sex

[ajs]

I find it interesting and somewhat disappointing that the parent article was moderated funny just because it used the word sex. Exchange of "genetic" material is not always a part of genetic algorithms, but it's certainly an "interesting" topic in that context and it was fairly "insightful" of XNormal to bring it up.

Oh well.

True story from support desk hell

[mrneutron]

A friend does PC support (including telecommuter support) for a large retail company. A woman called in, to say that her home PC was acting stangely, and not typing the keys she pressed.

My friend went to her house with a new keyboard. When he looked at the old one, he saw that the keys were arranged alphabetically. with 'a' where the q is supposed to be, 'b' where the w is, etc.

She explained that she was having trouble finding the keys, so she rearranged them so she could find them easier.

Universal in a very limited universe

[Rui del-Negro]

All these layouts and evaluations are based on a) american keyboard layouts and b) the English language.

Even the regular QWERTY layout has some differences in other languages (ex, the 'Ç' in portuguese keyboards, the 'Ñ' in spanish keyboards, etc.), and the letter frequency is completely different. Most languages don't use the 'W' at all, and very rarely use the 'K'.

Most languages also have some specific 2-letter sequences that don't appear in other languages. In English you have 'th' and 'wh', for example. In Italian you have 'gl' and 'gn', in Spanish you have 'll', in Portuguese you have 'lh' and 'nh', etc.. These can make a big difference to the "perfect layout".

There are also some ridiculous mistakes such as the official french keyboard (which is AZERTY, and not QWERTY, BTW) not having the capital letter 'Ç', meaning you can't type 'Ça va?' (a very common sentence, meaning 'How are you doing?'). In the portuguese layout, the 'Ç' is a separate key, so you can use it to type 'ç' or 'Ç' (with shift). When I was working in Paris a couple of years ago I often wished I had my portuguese keyboard, not only because I'm used to QWERTY and kept making mistakes on their AZERTY keyboards, but also because it's actually easier to type in French with a portuguese keyboard.

Personally, I'm quite happy with the QWERTY layout; I would only change a couple of letters.

But I do wish people who write software would realise not everyone in the world uses the same keyboard layout they do, and that in other countries the same signs are often in different keys, making some key combinations impossible (ex., in the portuguese keyboard. the signs '[' and ']' are typed by pressing AltGr+8 and AltGr+9, or Ctrl+Alt+8 and Ctrl+Alt+9. So, when a program assigns some function to the combination Alt+[, it usually won't work on portuguese keyboards). Even worse are the programs (games, especially) that read they key's position instead of the character. So I press '' and get '=', I press '\' and get '~', I try to type 'ã' and get '\a', so on.

[sarcasm]

And of course, no keyboard is complete without the Windows "system keys"...

[/sarcasm]

RMN
~~~

C code?

[ForceOfWill]

I limited this experiment to the 30 keys under the four fingers of the two hands. They include the 26 letters of the English alphabet and four punctuation symbols (comma, period, quote, and semicolon). (A QWERTY layout typically has the slash in this region instead of quote.) Other punctuation was ignored. ... I also needed a corpus of sample text... I added... about 100,000 lines of C code.

Am I the only one who thinks optimizing for C code is silly when you ignore vital symbols like braces, brackets, and numbers even? At least he included the semicolon.

IBM's ATOMIK for PDA's

[Hollinger]

IBM did this in 2k1 for PalmOS PDA's, and called it ATOMIK (Alphabetically Tuned and Optimized Mobile Interface Keyboard). It's from our Alphaworks, and is designed so that it has:
1. Higher movement efficiency than any other existing touch keyboard.
2. Alphabetically-tuned layout: Generally, letters from A to Z run from the upper left corner to the lower right corner of the keyboard. This layout helps novice users find letters that are not yet memorized.
3. Letter connectivity of common words: Many common words or comment fragments of words, such as "the" and "ing" are totally connected.

You might want to take a look at http://www.almaden.ibm.com/u/zhai/topics/virtualke yboard.htm and scroll down for a list of very good research papers.

Before edition...

[Karpe]

...it was a Ask slashdot submission, and read: "I swtchrd my computre keybord to teh Dvorka layoot bout a yaer ago. But nbw I've gonn nad donn somethng raelly ouhlnadsh. I trid to discovr teh most efffcinet layoot posibel wth a getetic algorthm. It's wetird-lokng, but I m typnig wth ti noow. I ptu teh gorry detials up on the Web. Wht I sak is hw teh ehll do I chnage ti bak?!

Faulty assumptions used for the benchmark

[pslam]

Unfortunately this program uses the same faulty assumptions that Dvorak used to design his keyboard layout. Namely the following:

• Alternating between hands each key is fast
• Hands are not allowed to move left or right
• All four fingers on each hand must rest on the same row
• Moving up or down a row is slow, because of the above
• You don't use your thumbs except for space

Where did these assumptions come from? I've got about 15 years of piano playing under my belt, and I find the standard "touch typing" rules very strange choices indeed. I type in a pretty free-form style at about 150wpm, depending on coffee. So, I'll disprove these assumptions one by one:

• Alternating between hands each key is the absolute hardest action to do quickly. If you have a piano piece which has a segment like this (there's a few famous pieces like this) it'll either be relatively slow or you'll be practising it for months. Runs of keys in the same hand are far faster. I'd say about 5 times faster.
• Why are hands not allowed to move left or right? If you have 8 keys to press, all of which reside to the right of the 'D' key, I move my left hand right a few keys! What's the point in keeping it where it is and making your right hand do more work and even stretch to reach the central columns?
• Why must all 4 fingers rest on the same row? For a start, your fingers aren't even the same length! Place your hands naturally on a table, and compare to where the keys would be. You'll find that they would have been on "a,w,e,f" and "j,i,o,;". Somewhat luckily, qwerty keyboards have all of the vowels except "u" under these keys. There's no reason you can't have your fingers over arbitrary rows. With a bit of hand strength building, this is easy.
• Moving up and down rows is only slow if you "float" above the keyboard (not resting your wrist on the table/rest) and move your entire arms back and forward. This would be an awful technique to use and I'd suspect it would lead to strain problems very quickly. Stretching your fingers forward and backwards is fast. And with the previous point, this is mostly irrelevant anyway.
• So, why aren't we allowed to use thumbs for typing normal keys? It's perfect for hitting keys on the bottom row when all the others have been tied up. Just then, I typed "up." with right hand "2-4-1" (where 1 is thumb, 5 is little). Why? Because when fingers 2,4 have been tied up on the top row, the most convenient finger to use is my thumb. Try it.

Not to discourage trying to find new keyboard layouts too much, but it's best to start really from scratch and question the basis of all the original assumptions. The rules need to include:

• Model the positioning of the hands and fingers in detail. If you remove the restrictions that "touch-typing" enforce, then the key-to-finger mapping also depends on context.
• Encourage runs of keys in the same hand. About 3-4 keys in the same hand before switching is optimum.
• Discourage rapid switching between hands (every key, for example).

My theory about carpal tunnel and other typing related injuries is that "touch typing" is actually to blame. It encourages stiffening of the wrists and hands, discourages stretching, and generally leaves your hands as weak as they were before you started typing.

My advice to anyone that uses classical "touch typing" is to learn to the point of about 40wpm, and switch to improvisation. My advice to anyone wanting to switch to Dvorak for speed, or to reduce strain: it's ultimately limited by the speed of one-key-per-hand switching which is about 120wpm. From my experience with both, you're better off sticking with qwerty and going free-style.

Re:Faulty assumptions used for the benchmark

[The Pim]

I think you have a combination of unusual motor skills and incorrect reasoning.

Alternating between hands each key is the absolute hardest action to do quickly. If you have a piano piece which has a segment like this (there's a few famous pieces like this) it'll either be relatively slow or you'll be practising it for months. Runs of keys in the same hand are far faster. I'd say about 5 times faster.

Runs on the same hand are faster than alternation, sure. But alternation is much faster than arbitrary motions of one hand. Given the variety in English, optimizing for long runs will win on a very few words, and screw up the layout for everything else. I challenge you to refute this.

Dvorak does follow this principle for some short runs: th, sh, wh, rt, nd, and ng are all nice combinations that move in the pinky-to-index direction on one hand. But gymnastics with one hand will kill most typists, and alternation is about avoiding this.

Why are hands not allowed to move left or right? If you have 8 keys to press, all of which reside to the right of the 'D' key, I move my left hand right a few keys! What's the point in keeping it where it is and making your right hand do more work and even stretch to reach the central columns?

This requires incredible foresight and motor skills. For most people, the key to finding a key quickly is knowing its position relative to a fixed reference.

Why must all 4 fingers rest on the same row? For a start, your fingers aren't even the same length! Place your hands naturally on a table, and compare to where the keys would be. You'll find that they would have been on "a,w,e,f" and "j,i,o,;". Somewhat luckily, qwerty keyboards have all of the vowels except "u" under these keys. There's no reason you can't have your fingers over arbitrary rows. With a bit of hand strength building, this is easy.

I might agree about the natural position of the fingers (though I suspect the natural position is actually somewhere in-between asdf and awef). But the idea that each finger can be on its own row is just wrong for normal hands. Ask some normal people to try it, and they'll tell you.

Moving up and down rows is only slow if you "float" above the keyboard (not resting your wrist on the table/rest) and move your entire arms back and forward. This would be an awful technique to use and I'd suspect it would lead to strain problems very quickly. Stretching your fingers forward and backwards is fast. And with the previous point, this is mostly irrelevant anyway.

Resting wrists on the table, and stretching fingers without moving the hand, are both generally recognized as major contributors to CTS and other typing injuries. When I learned piano, I was definitely taught to keep my wrists up and move my hands with my fingers (eg, when reaching for a black key, the hand should advance).

So, why aren't we allowed to use thumbs for typing normal keys? It's perfect for hitting keys on the bottom row when all the others have been tied up. Just then, I typed "up." with right hand "2-4-1" (where 1 is thumb, 5 is little). Why? Because when fingers 2,4 have been tied up on the top row, the most convenient finger to use is my thumb. Try it.

I tried it. It's a disaster for me. Typing up with 2-4 is hard enough, requiring an awkward stretch of the ring finger. Getting to . with the thumb requires me to twist my whole arm in addition to contorting my hand, and hitting a target after such a long travel with such a fat digit is quite unreliable. Plus, this leaves my hand totally out of position for any subsequent typing.

I would think that given your claim that different fingers can easily go to different rows, you would prefer 2-5-4.

My theory about carpal tunnel and other typing related injuries is that "touch typing" is actually to blame. It encourages stiffening of the wrists and hands, discourages stretching, and generally leaves your hands as weak as they were before you started typing.

I'm not a doctor, but this flies in the face of all the medical advice I've read. What you call "stiffening" is what most people would call making gentle, comfortable motions. What you call "stretching" is what most people would call excessive and unnatural motion. What you call "leaving weak" is what most people would call avoiding strain. Maybe your hands can take it, but most people's can't.

Self-customized keyboards....

[RalphTWaP]

It sounds like the interesting possibility almost grasped here is the possibility of producing a self-customized layout on the fly.

hook the keyboard driver and tokenize input into words (corrections included where possible), feed through a spell-checker (to find what word was likely the target), and re-insert as input through the algorithm. Admittedly, this makes it more of a neural-net than a GA, but it is continuously evolving, and eventually, you should even out on the best keyboard layout for what you type on a daily basis

I expect my '_' key to end up somewhere on the home row in a couple of weeks (programming = bad typing habits)

Re:That's all fine and dandy...

[Decklarean]

Qwerty wasn't designed to slow people down... that's a myth.

Research on keyboard stuff found here:
http://web.mit.edu/jcb/www/Dvorak/