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.

Re:choice of benchmark text

[Ubi_UK]

IN the same line of thinking:

-could, for instance, parsing the kernel through his routine create a 'kernel-hacking' keyboard?
i.e. specialist keyboards to do a specific job?

(and I would have CTRL-ALT-DEL right in the middle of my MS-Win-biased keyboard: now that would speed up things =)

Re:choice of benchmark text

[KILNA]

I had the same idea for a perl-optimized keyboard layout. But I don't know if having the home keys as punctuation would be well-received.

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.

Re:True story from support desk hell

[Hollins]

Actually, I think this is a good example of how product design should be driven by observing how people try to use things. A physically-remappable keyboard could be a good thing. I'd probably buy one.

My keyboard project (international dvorak layout)

[snowtigger]

Nice work.

I am working on a similar project: to create an international (european languages) dvorak-like layout for programmers or multi-lingual people.

In Europe, there is about one qwerty-type layout for each language or country. Most languages have some special characters (èàéüäö etc). If you want to use characters from another language, it may not be possible or require some special (difficult to remember and different for each layout) sequence.

What I am looking for is direct access to all special characters used by swedish, french, german, italian, spanish and programming languages (èàéäüö[]{}$# etc). Using dvorak as basic layout to build upon.

I will post more on this as soon as I have finished (after summer vacations)

Vindication...

[Junta]

His little test is a neat idea. The one potential cause for concenr I could see would be that he was influenced by literature praising dvorak in defining penalties for various tasks. I personally think the penalities are likely accurate, but to a QWERTY advocate, research that show dvorak is bette rby using dvorak based criteria would be begging the question...

That aside, I really agree that dvorak is a better keyboard layout, and his final layout's resemblance to dvorak testifies to the advantage of dvorak. I've never been able to type fast at al in QWERTY, and it always hurts quickly (unless I hunt and peck, which is my general method). With dvorak I can touch type comfortably for a long time, and much faster as well. While his final keyboard layout may be marginally better than dvorak, dvorak remains the better choice for much the same reason qwerty is used, you can set up a dvorak layout on almost any system and os, but with this funky layout, you need to be running X....

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.

Re:Faulty assumptions used for the benchmark

[Dixie_Flatline]

The big flaw in your argument is probably the one that you think is the best, namely that we should be encouraging runs of 3 to 4 letters on one hand.

Alas, the problem with this is that you're going to end up with a dominant hand. If you put 'the' in the middle of the right hand side of the keyboard, the right hand will be typing that a million times a day. Sure, it's faster, but it's not going to be ergonomically better.

Nobody that's typing for pure speed is going to use a normal keyboard. A chording keyboard will let you break 200wpm if you're good with it.

Besides, I'm not sure why you'd say that alternating keystrokes by hand is slower. It's clear to my that my left and right hands can type keys nigh simultaneously. It's just a matter of getting your hands to move quickly and precisely enough so that a keystroke from your right hand is instantaneously followed by a keystroke from your left hand. Having multiple keys close together so that they can be hit by the same hand merely makes it a little more convenient to coordinate.

And surely, as a piano player, you've heard the stories about players 'trilling' on two keys repeatedly, for years, and are now experiencing pains from it?

Lastly, I think that the best keys for the thumb are 'backspace', 'delete', 'space', and 'enter'. I use these keys far more than most letter keys every day. On average, I use the space key every 5 letters, and I probably use the backspace key once every 10. :)

Check out the kinesis ergonomic keyboards. If only they could have moved 'shift' so that I didn't have to use my pinky all the time.

why a genetic algorithm...

[danboo]

when there's a finite number of layouts? Yup, just 265,252,859,812,191,058,636,308,480,000,000 possibilities. I'm sure the guys at distributed.net would love to set up a project to figure this out.

- danboo

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

[bc3-au]

Actually re-learning to type with a better layout is quite quick.

I tried dvorak with the earlier versions of NT which allowed keyboard re-mapping and found myself bettering my typing speed, with less errors within 2 weeks.

Only problem then was the fact that stupid windows had keyboard layout set as a user preference, not a machine preference. It was *VERY* difficult remembering qwerty when trying to log in. (I'd rearranged my keys but login was done in default, not my personal mapping)

I should go out and buy a keyboard with a dvorak layout, but keyboards these days are so badly contstructed.

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/

Re:more qwerty myths...

[The Pim]

Everything you ever thought you know about the QWERTY layout was *wrong*.

http://www.independent.org/tii/news/liebowitz_econ omist.html

Liebowitz's article does not debunk anything. It merely gives evidence that some studies were flawed, puts forward its own flawed and ambiguous studies, and entirely ignores the compelling non-empirical arguments for Dvorak's superiority. (Do you not believe anything that has not been established by studies?) Let's not even mention the fact that Liebowitz has a strong prejudice about market efficiency to support (oops, mentioned it!).

Marcus Brooks has a longer rebuttal. I actually do not find it totally satisfactory either, but it should certainly make clear that Liebowitz has little credibility.

Another evolution condition..

[hyphz]

Hmm, interesting. I've been using Dvorak for a while now (and yes, I can still type fast on qwerty with the occasional pause). However, one thing I found about Dvorak was that spelling checkers become less useful on it - because of the closeness of common letters to each other, a Dvorak miskey tends to generate a correct spelling of the wrong word, rather than an incorrect spelling. This confounds automated spell checking. Has anyone tried to make a layout which minimises cases in which letters which can be substituted in words being next to each other is a Bad Thing?