Gesture Typing¶

Typing quickly and accurately on a smartphone screen is hard! One invention to make it easier is gesture typing, in which your finger can trace a path consisting of letter-to-letter segments. When you lift your finger the path (and the word) is complete. Below we see the path for the word "hello." Note that the path is imprecise; it didn't quite hit the "L", but the word was recognized anyways, because "Hello" is a known word, whereas "Hekko", "Hwerklo", etc., are not.

Questions About Gesture Typing¶

My colleague Nicolas Schank examined (and answered) the question of what word has the longest path length. I mentioned this to Shumin Zhai, the pioneer of gesture typing, and between the three of us we expanded the list of questions:

1. What words have the longest path length?
2. What words have the highest ratio of path length to word length?
3. What is the average segment length, over a typical typing work load?
4. Is there a better keyboard layout to minimize the average segment length over a work load?
5. How often are two words confused because they have similar paths?
6. Is there a better keyboard layout to minimize confusion?
7. Is there a better keyboard layout to maximize overall user satisfaction?

Let's look at each of these questions, but first, let's get a rough idea for of the concepts we will need to model.

Vocabulary¶

We will need to talk about the following concepts:

• Keyboard: We'll need to know the location of each letter on the keyboard (we consider only letters, not the other symbols).
• Location: A location is a point in two-dimensional space (we assume keyboards are flat).
• Path: A path connects the letters in a word. In the picture above the path is curved, but a shortest path is formed by connecting straight line segments, so maybe we need only deal with straight lines.
• Segment: A line segment is a straight line between two points.
• Length: Paths and Segments have lengths; the distance traveled along them.
• Words: We will need a list of allowable words (in order to find the one with the longest path).
• Work Load: If we want to find the average path length over a typical work load, we'll have to represent a work load: not

just a list of words, but a measure of how frequent each word (or each segment) is.

• Confusion: We need some measure of whether (or perhaps to what degree) the paths for two words can be confused with each other.
• Satisfaction: This is a very difficult concept to define. A user will be more satisfied with a keyboard if it allows for fast, accurate typing, and if it gives the user a feeling of mastery, not frustration.

Note: Before we get started writing any real code, I've taken all the imports I will need throughout this notebook and gathered them together here:

Representing Keyboards and Points¶

The representation for a keyboard needs to describe the location of each of the letters. Using the principle of "Do the simplest thing that could possibly work," I represent a keyboard as a dict of {letter: point} pairs, where there will be 26 letters, A-Z, and each point will mark the x-y coordinates of the center of the corresponding key. In a standard keyboard the letters are not all on a strict rectangular grid; the A key is half way between the Q and W in the horizontal direction. I would like to have a programmer-friendly way of defining keyboard layouts. For example, a programmer should be able to write:

Keyboard(('Q W E R T Y U I O P',
          ' A S D F G H J K L ',
          '   Z X C V B N M   '))

and this would be equivalent to the dict:

{'Q': Point(0, 0),   'W': Point(1, 0), ...
 'A': Point(0.5, 1), 'S': Point(1.5, 1), ...
 'Z': Point(1.5, 2), 'X': Point(2.5, 2), ...}

Note that one key width is two characters in the input to Keyboard. Here is the implementation:

What about Point? At first glance, Python does not appear to have a two-dimensional point as a builtin data type, but on second thought, it does: complex. A complex number is a point in the two-dimensional complex plane; we can use that to model the two-dimensional (x, y) plane. Because complex numbers are built in, manipulating them will be efficient. A bonus is that the distance between points A and B is simply abs(A-B); easier than the usual formula involving squares and a square root. Thus, the simplest possible thing I could do to represent points is

Point = complex

That would work fine. However, I would like to refer to the x coordinate of point p as p.x rather than p.real, and I would like points to display nicely, so I will do the second-simplest thing: make Point be a subclass of complex with x and y properties and a __repr__ method:

Alternative representations for points include an (x, y) tuple or namedtuple, or a NumPy two-element array, or a class.

Alternatives for Keyboard include a subclass of dict, or a class that contains a dict.

Now we can check that Keyboard works:

Computing Path Length¶

Now let's figure out the path length for a word: the sum of the lengths of segments between letters. So the path length for 'WORD' would be the sum of the segment lengths for 'WO' plus 'OR' plus 'RD':

Let's make a function to compute this:

Let's check with a simpler example that we know the answer to:

That makes it clearer—the O is four keys to the right of the T, on the same row, so the distance between them is 4.

Here's another one that you can verify on your own:

Question 1: Longest Path Length?¶

To know what the longest word is, we'll have to know what the allowable words are. The so-called TWL06 word list gives all the words that are legal in the game of Scrabble; that seems like a reasonable list (although it omits proper nouns). Here's how to load a copy:

That's a lot of words; which one has the longest path?

And the ten longest paths? Including the lengths? We'll use a helper function, print_top, which prints the top n items in a seqence according to some key function:

Question 2: Highest Path Length to Word Length Ratio?¶

Very long words tend to have long path lengths. But what words have the highest ratio of path length to word length? (I decided to measure word length by number of letters; an alternative is number of segments.)

Question 3: Average Segment Length on Work Load?¶

What is the average segment length for a typical typing work load? To answer that, we need to know what a typical work load is. We will read a file of "typical" text, and count how many times each segment is used. A Workload is a dict of the form {segment: proportion, ...}, e.g. {'AB': 0.02}, where each key is a two-letter string (or bigram) representing a segment, and each value is the proportion of time that segment appears in the workload. Since the distance from A to B on a keyboard is the same as the distance from B to A, we can combine them together into one count; I'll arbitrarily choose count them both under the alphabetically first one. I make a Counter of all two-letter segments, and normalize it so that the counts sum to 1 (and are thus probabilities).

Note: Some re trickiness here: ([A-Z][A-Z]) means a group of two consecutive letters. But if I only looked for that, then in the text 'FOUR' I would find ['FO', 'UR']. So I use the ?= operator, which says to check for a match, but don't consume the matched characters. So I can find ['FO', 'OU', 'UR'], which is what I want.

Let's see what a workload looks like for a tiny text:

I happened to have a file of about a megabyte of random text, smaller.txt; that should work fine as a typical work load:

Let's peek at the most common segments:

The most popular segments, at about 4% each are HT/TH and ER/RE. Now we can compute the workload average:

So, on average, your finger has to travel a little over 3 keys from one letter to the next over a typical workload.

Aside: Visualizing a Keyboard¶

We'll need a way of visualizing what a keyboard looks like. I could just print letters, but I think it is more compelling to use IPython's matplotlib module. In the function show_kbd we'll draw a square around the center point of each key, and annotate the square with the key letter.

Question 4: Keyboard with Minimal Workload Average?¶

Now for a much harder question: can we find a different keyboard layout that has a smaller average segment length over the workload? First, let's note that there are two ways to modify a keyboard:

• Keep the keys in the same locations but swap letters. (This is an operation you can do on a physical keyboard just by prying off the key caps and swapping them.)
• Change the locations of keys. (On a physical keyboard you'd need a saw and glue to do this, but it is easier on a virtual keyboard.)

Let's start by limiting ourselves to just swapping letters.

This is an optimization problem. There are many permutations of letters; too many to try them all. To be precise, there are 26! (26 factorial) permutations, which is about 10²⁶ (fun fact: 25 and 26 are the only integers for which n! ≈ 10ⁿ). If we can't try them all, we need some way to sample the configurations, trying to make progress towards a better one. Again, we'll try the simplest thing that could possibly work:

1. Pick two keys at random.
2. Swap them.
3. If that gives a better (lower) workload total, keep them that way.
4. If not, swap back.
5. Repeat this for a given number of times, say 1000.

Note 1: This strategy is called hillclimbing, drawing on the metaphor of getting to a high peak by trying to take a step, and continuing if the step is uphill, and returning if it is not. This technique often finds a local maximum—a solution that is better than all its neighbors, but not as good as another solution that is many steps away.

Note 2: I make scorer be a parameter, in case we later decide we want to minimize something else other than workload_average.

Let's see how well we can do:

That's a pretty good improvement! We decreased the workload average by about a third. (If you are reading this in an active IPython notebook, you can re-run the cell above and see a different result each time.)

Visualizing improved¶

Let's get a better feeling for what improved does. We will keep track of the workload average after each swap, and plot that as a curve. We will repeat that 10 times (because each run has random variation).

I'll add another parameter, scores, to improved, If it is not None, then it should be a list into which we can accumulate all the scores (after each time step). Then I'll add a new function, plot_improvements, that plots the scores that improved accumulates.

This plot is interesting. I note the following:

• Each curve follows a slightly different path (because the swaps are random).
• The curves are grouped very tightly together; the variance is small. Almost everywhere, the difference between the best and the worst is about 0.2 or less. By the end, almost all the curves are between 1.9 and 2.0.
• We make rapid progress, decreasing from 3.2 to around 2.2 in about 200 swaps, and to around 2.0 in about 500 swaps.
• After 1000 swaps, progress is slow, and after 2000, even slower.

I can't say we've found the best possible keyboard, but it looks like progress will be slow in improving over about 1.9.

Keys in Different Physical Locations¶

Now let's allow keys to be in different physical locations. Rather than allowing complete freedom of movement, we'll start from a few different fixed key layouts and swap keys from there. I'll define three layouts and gather them into a dict:

Here is a function to report on a collection of keyboards such as this (after improving them):

(Note: The plots of different-shaped keyboards have different-sized squares around the keys. Some of the plots have a lot of whitespace around them. If anyone knows an easy way to tell plot to display them better, let me know.)

So the more compact keyboards with a smaller diameter (4-by-7 and 5-by-6) seem to perform slightly better than qwerty.

Question 5: How often are two words confused because of similar paths?¶

When can one word be confused with another? When their paths are similar (which means that their corresponding letters are in similar locations). For example, on a Qwerty keyboard, the paths for "HELLO" and "JELLO" are similar, because H and J are adjacent, and the other letters are the same.

We'd like to know, for a given keyboard, how confusing is it? How many words have paths on the keyboard that can be confused for other words? We have our work cut out for us:

1. Determine what letters could be confused for each other.
2. Determine what words/paths can be confused.
3. Invent some metric for the overall confusingness of a keyboard.
4. Try to find less-confusing keyboards.

Letter Confusions¶

So, as a first step, we will make a mapping from each key to the keys that it can be confused with. I'll say that any key within a distance of 1.5 units on the keyboard is a neighboring key, and thus a potential confusion:

We see, for example, that Q, off in the corner, has only A, W, and itself as neighbors, while G, in the middle of the keyboard, has 8 neighbors.

Word Confusions¶

Consider each of the letters in the word "HELLO," and all the possible choices for neighbors of each letter:

These are five columns of letters, and if we pick one letter from each column, we get a path that is formed by letters that are each confusions of letters in the original word, and so the whole path is a confusion for the original word. So "JELLO" is a confusion for "HELLO", as would be "BDKKI" and "YWPPP", except those are not words.

It turns out that there is a library function, itertools.product, that will take alternative choices, and generate all possible ways of assembling a sequence consisting of one selection (letter) from each alternative choice.

How many paths are there?

Let's look at a few of them:

And let's see all the paths that are also words:

Only 4 out of 5000; That's pretty good, but it means "HELLO" is still a confusing word. We can package this as the function confusions:

So far, so good. But I'm worried about the efficiency of confusions.

My first concern is that WORDS has 178,691 words, including many unusual words, so there might be too many confusions. I will read in a smaller word set, with only common words:

More Efficient confusions¶

Another issue is that confusions is really slow:

It took (on my computer) 3 seconds to compute this. Why so long? Let's count:

There are 7 × 5 × 5 × 5 × 5 × 8 × 5 × 6 × 8 = 8,400,000 paths for confusions to consider. 'PALEOMAGNETISMS' would have about 10,000 times more paths. Looking at every path is slow, but for most paths, we're wasting our time. For example, one choice for the first two neighboring letters of 'SO' is 'XP', but 'XP' does not start any word in the dictionary. Nevertheless, itertools.product will generate 240,000 combinations that start with 'XP', and will then rule them out one at a time. It would be better to stop as soon as we see 'XP', and never consider continuations of this path.

So that gives us the key idea for a more efficient version of confusions: only follow paths that form a prefix of some word. I'll make a set of all the prefixes of the COMMON words:

We can describe the more efficient version of the confusions algorithm:

1. Maintain a queue of partial paths, where a partial path is a string representing choices for neighboring letters for a prefix of the word. For example, 'HE' and 'JE' are both partial paths for the word 'HELLO'. Initialize the queue to have just one partial path, the empty string.
2. Remove a partial path from the queue. Find all possible ways to extend the path by adding a neighboring letter, but only if doing so creates a path that is a prefix of some word in the dictionary. For example, given the word 'HELLO', and the partial path 'JE', consider all the neighbors of 'L' (namely, 'K', 'M', 'L', 'O', or 'P'), but only 'JEM', 'JEL', and 'JEO' are prefixes of words, so add just those to the queue.
3. When a partial path reaches the same length as the word ('HELLO' in this example), then don't extend it any farther; instead check to see if the path is a word. If it is, yield it as a result.

A word is confusable if it has a confusion word (other than itself).

Let's check the speed (remember the old version took over 3 seconds):

We went from about 3 seconds to about 100 microseconds: that's 30,000 times faster! We can look at some more confusions:

Visualizing Paths on a Keyboard¶

It would be nice to see potentially confusable word paths on a keyboard. I'll add a call to plot_paths in show_kbd:

Let's see how it works on three similar paths:

OK, we're on the right track, but I see three problems, which I think I can solve:

• The letters are obscured by the circles. Solution: offset paths away from the center.
• When the paths are the same, they overwrite each other. Solution: offset each path towards a different corner.
• There is no indication what direction the path is going in. Solution: put a black square on the start position.

That looks busier, but it is easier to follow the paths. Another example:

Average Confusions of a Keyboard¶

The question is: how confusing is a keyboard? One metric for confusingness is the percentage of words that are confused with other words:

About half the common words are confusable, with a little bit of variation between keyboards.

Question 6: Is there a Keyboard that Minimizes Confusion?¶

Consider this:

Computing confusingness takes about 500 times longer than computing workload_average, so if we want to use confusingness as a scoring function, we will have to settle for fewer swaps:

This did indeed reduce confusingness (which was 54%); not bad for only 100 swaps.

Question 7: Is there a Keyboard that Maximizes User Satisfaction?¶

What is user satisfaction? I don't know, but for now I'll approximate satisfaction (or rather, dissatisfaction, since lower scores are better) with a combined score that is the product of workload average and confusingness. Then I (rather arbitrarily) scale the result by 5, just because I think a number like "2.1" looks better than "0.42".

First we'll define the combined scorer function and incorporate it into title:

Now let's try to minimize confusion. This should take around 2 minutes:

Success! We were in fact able to make progress on the combined metric. If we could run 50,000 swaps instead of just 500, we could probably do even better. To do so would require either (1) more computers, (2) more patience, or (3) more efficient algorithms. I'll leave it up to you to make more progress.

Note: Each time this notebook is run, different random results can occur. I'll record a keyboard found by one of the good runs (only 11% confusingness) here, just in case another run is not as good:

Bonus Question: What about the Keybee Keyboard?¶

In December 2017 the Keybee keyboard was announced, claiming to cut the path length in half. The keyboard uses hexagonal keys:

Let's see if we can replicate it. I'll give keyboard optional arguments to scale the (x, y) positions to get the proper hex grid layout (even though I will still draw each key with a square around it rather than a hexagon; I'll leave it to you to fix that if you want):

That's not pretty, but the keys are in the right places. The path length of 1.9 is better than the 3.2 for the QWERTY layout, but not twice as good, and not as good as some of the layouts we were able to achieve with square keys, and the advantage may be due to the fact that the keys overlap by 13%, not because the layout is especially clever. Can we improve the layout?

This does indeed cut the path length to half of QWERTY, so maybe there is something to be said for hex grids. Note: the space key was moved to the edge, because it doesn't contribute to the workload. The Keybee FAQ says "the space key is the most important key on a keyboard," so clearly they are aiming at two-thumb typing, not gesture typing; perhaps that's why it was so easy to improve their layout for our purposes.

Here is Keybee with some word paths:

Summary¶

So where are we? Let's revisit our initial questions and see what answers we have:

1. What words have the longest path length?
   Answered: "PALEOMAGNETISMS" etc.
2. What words have the highest ratio of path length to word length?
   Answered: "PALAPA" etc.
3. What is the average segment length, over a typical typing work load?
   Answered: 3.23 keys, for Qwerty keyboard, on our sample workload.
4. Is there a better keyboard layout to minimize the average segment length over a work load?
   Answered: Yes, many layouts at around 1.9 on Qwerty; or 1.7 or 1.8 on more square keyboards.
5. How often are two words confused because they have similar paths?
   Answered: On Qwerty, 26% of the words in a small dictionary, and 55% of the words in running text have at least one possible confusion. Other layouts are worse.
6. Is there a better keyboard layout to minimize confusion?
   Partially Answered: We found a keyboard with less confusingness than Qwerty. The computation of confusingness takes too long to do very much hillclimbing search.
7. Is there a better keyboard layout to maximize overall user satisfaction?
   Partially Answered: We defined a combined metric, and found

a keyboard with a better score. There are no doubt better metrics, and better keyboards to be found.

Going Beyond¶

Now it is your turn to answer the open questions, or make up some questions of your own. Good luck! Here are a few ideas to get you started:

• Hillclimbing just keeps the one best keyboard it has found so far. Other optimization techniques such as

beam search or genetic algorithms or ant colony optimization maintain several candidates at a time. Is that a good idea?

• The code in this notebook emphasizes clarity, not efficiency. Can you modify the code (or perhaps port it to another language) and make it twice as efficient? 10 times? 100 times?

• What other factors do you think are important to user satisfaction with a keyboard. Can you measure them?

• Consider the 5 paths below. They all start at 'P', move in a straight line to 'T', and then go to 'S', but they all make different stops along the top row. In other words, the 5 paths all trace exacty the same lines, so they are very confusing, but our definition of confusions makes most of them different. Can you think

of a better way to handle confusions for paths like this?