Efficacy of Degenerate Keyboard Maps

Some devices with limited size, such as smart phones, implement a reduced keyboard, with each key mapping to several letters. The effectiveness of the keyboard rests upon how well keystrokes distinguish between words of equal length. Keyboards with fewer than 26 keys map one key to a subset of letters. Then typing out a word often specifies a list of possibilities from which the intended word must be chosen.
The graphs here illustrate the balance between degeneracy and the number of keys for different mappings. For coarser mappings there are larger groups of words that share the same keystrokes. Each point represents the number of words with a certain degeneracy. The first point, for the group with degeneracy of one, on the left side, is for words that are totally differentiated by a particular keyboard map. The next point, degeneracy of two, is for words that have one other candidate word from the same keystrokes, and so on.


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


The dropdown menu contains common mappings shown as lists of groups of keys. One example is the telephone, with three to four letters per key over eight keys. The other control chooses the number of words to calculate on, chosen from a list of the most used words. The graph then shows the number of lists of words that cannot be distinguished by the keystrokes for each keyboard. For a full 26-letter keyboard all words are distinguishable, but for other keyboard there are groups of two or more words that are indistinguishable. On most devices these short lists are disambiguated by a further selection.
The efficacy of reduced keyboards can be seen as the clusters of degenerate words remain small. For instance, for the telephone mapping the top 50 words are all distinguished and the next 50 have only two pair of words that must be selected from later.
Other mappings seen in smart phones include using whole rows or half-rows of the keyboard, so that keys have two letters each. In all cases, even with crude keyboards that have only six or even three buttons, disambiguation seems a palatable task. That is, typing in the smart phone keyboard can produce a handful of candidate words that can be chosen from on the display. Furthermore, as most software lists the candidate words in order of common usage, these keyboards are practical to use. Only the very crudest, a three-key keyboard (with ten letters on one key) creates rather long lists of specified words.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.