| 1 |
========= |
| 2 |
Keymapper |
| 3 |
========= |
| 4 |
|
| 5 |
The Problem |
| 6 |
=========== |
| 7 |
|
| 8 |
Keyboard selection is a problem for many users since most ofthem have no |
| 9 |
idea which keyboard layout they have. |
| 10 |
|
| 11 |
This program uses a different approach. We simply ask the user to press |
| 12 |
a couple of keys and infer from their scan code which layout they belong |
| 13 |
to, thereby lowering the number of possibilities in a classic |
| 14 |
divide-and-conquer approach. |
| 15 |
|
| 16 |
Some difficulties show up. For instance, asking people to press a key |
| 17 |
they don't have is considered to be bad style. Todistinguish between |
| 18 |
German and Danish keyboards, we therefore have to offer multiple |
| 19 |
possible symbols. This should also be helpful with trying to distinguish |
| 20 |
between QWERTZ and AZERTY when the user has a cyrillic keyboard. :-) |
| 21 |
|
| 22 |
Inferring the decision tree from a large number of keyboard layouts is |
| 23 |
not efficient, thus the tree neds to be pre-calculated. |
| 24 |
|
| 25 |
There are two ways of selecting among possible layouts: |
| 26 |
|
| 27 |
* Ask the user to press a key with a particular symbol |
| 28 |
|
| 29 |
* Ask the user to choose the symbol which appears on a key, e.g. to the |
| 30 |
right of the tab key. |
| 31 |
|
| 32 |
This tool will only use the first approach. If it is not possible to |
| 33 |
distinguish between keyboard layouts that way, e.g. because their only |
| 34 |
difference is whether a particular key has an X or a Y symbol, a simple |
| 35 |
binary question ("Do you have an X key") may have to be asked. |
| 36 |
|
| 37 |
Basic selection algorithm |
| 38 |
========================= |
| 39 |
|
| 40 |
Initially, list all keyboards. Create a list of forbidden scan codes, |
| 41 |
which is initially empty. |
| 42 |
|
| 43 |
Select a symbol that appears on most keyboards, in as many places as |
| 44 |
possible, but not on any keys in the forbidden list. Remoce these |
| 45 |
keyboards from the keyboard list and add the scan codes of those |
| 46 |
keys to the forbidden list. |
| 47 |
|
| 48 |
Repeat until the list of keyboards is empty. |
| 49 |
|
| 50 |
Display the list of symbols to the user. Each scan code we get back is |
| 51 |
associated with at least one keyboard. Clear the list of scan codes and |
| 52 |
repeat this process if there is more than one. |
| 53 |
|
| 54 |
Heuristics |
| 55 |
---------- |
| 56 |
|
| 57 |
Unmodified, this method tends to pick 'obscure' keys like @, |
| 58 |
which tend to be in lots of different places historically. |
| 59 |
Unfortunately, the risk of this approach is that people will not find |
| 60 |
the key if it's not labelled as such on their keyboard. |
| 61 |
|
| 62 |
Some possible modifications are: |
| 63 |
|
| 64 |
* Initially, prefer ASCII letters and low-ASCII symbols. |
| 65 |
|
| 66 |
* Strongly prefer a symbol that's not selected with AltGr or, less |
| 67 |
strongly, Shift (unless the base key is a number). Especially in the |
| 68 |
former case, the symbol may not even appear on the keyboard. |
| 69 |
(DONE) (partly conflicts with the first part) |
| 70 |
|
| 71 |
* In order to avoid an "I can't find any of these keys" problem, it |
| 72 |
might be necessary to prepare two symbol lists in each step. The key |
| 73 |
codes should be distinct of course. |
| 74 |
(DONE) |
| 75 |
|
| 76 |
* Some key choices should be either avoided or combined. For instance, |
| 77 |
asking the user to press an A in order to find out whether the layout |
| 78 |
is French (qwerty vs. azerty) might be a bad idea if Cyrillic |
| 79 |
keyboards have not been either excluded (in a previous question) or |
| 80 |
included (by internally mapping а => a, ѡ => ω, etc., and accepting |
| 81 |
all ppossible answers). |
| 82 |
|
| 83 |
A list of Unicode glyph lookalikes should be findable on the Internet. |
| 84 |
In addition, it might make sense to always show capital letters. |
| 85 |
(TODO) |
| 86 |
|
| 87 |
* Do a global optimization to minimize tree depth. Currently, key |
| 88 |
selection locally favors deciding between many layouts with one |
| 89 |
symbol -- the problem is that the keys which end up selecting between |
| 90 |
the rest also select from a few of those already decided on by the |
| 91 |
first ones, thus they add more steps. A nicer strategy might be to |
| 92 |
find a group of symbols which collecively do the same thing, only |
| 93 |
better. |
| 94 |
|
| 95 |
Tests |
| 96 |
===== |
| 97 |
|
| 98 |
Testing this approach is the easiest part of the problem -- the |
| 99 |
FakeQuery class answers the questions depending on which keyboard map |
| 100 |
was passed to it. If multiple answers are possible, one is selected |
| 101 |
randomly. |
| 102 |
|
| 103 |
Redundancy |
| 104 |
---------- |
| 105 |
|
| 106 |
During twenty test runs with the nine initiall test keymaps, the system |
| 107 |
asked 27 questions on average, or three per keymap. Since 2^3 is 8, the |
| 108 |
generated decision tree is shorter than a binary tree, which suggests |
| 109 |
that generating two symbol lists in parallel doesn't result in asking |
| 110 |
additional questions. |
| 111 |
|
| 112 |
Graph output |
| 113 |
------------ |
| 114 |
|
| 115 |
Since the result is somewhat difficult to visualize, I added graphviz |
| 116 |
output. The result isn't pretty in any way (specifically, edge labels |
| 117 |
are not placed correctly) but it's a workable first step. |
| 118 |
|
| 119 |
File output |
| 120 |
----------- |
| 121 |
|
| 122 |
The data file produced by this tool consists of a number of lines: |
| 123 |
|
| 124 |
STEP ## |
| 125 |
+++++++ |
| 126 |
|
| 127 |
This line starts a new step. Steps are numbered; the first step is |
| 128 |
numbered zero. |
| 129 |
|
| 130 |
Steps are not necessarily numbered consecutively, but all references |
| 131 |
pint to steps which occur later in the file. Thus it is never necessary |
| 132 |
to keep the while file in memory. |
| 133 |
|
| 134 |
MAP name |
| 135 |
++++++++ |
| 136 |
|
| 137 |
This step uniquely identifies a keymap. |
| 138 |
|
| 139 |
The MAP command is the only command in is step. |
| 140 |
|
| 141 |
PRESS char |
| 142 |
++++++++++ |
| 143 |
|
| 144 |
Ask the user to press a character on the keyboard. Multiple PRESS |
| 145 |
commands may occur in a step; the characters (encoded in utf-8) |
| 146 |
need to be presented simultaneously ("Press one of these keys"). |
| 147 |
Auxiliary keys (shift, alt, ...) should be ignored. |
| 148 |
|
| 149 |
CODE code ## |
| 150 |
++++++++++++ |
| 151 |
|
| 152 |
Direct the evaluating code to process step ## next if the user has |
| 153 |
pressed a key which returned that keycode. |
| 154 |
|
| 155 |
Obviously, multiple CODE commands may occur in a step. |
| 156 |
|
| 157 |
FIND char |
| 158 |
+++++++++ |
| 159 |
|
| 160 |
Ask the user whether that character is present on their keyboard. |
| 161 |
|
| 162 |
This is a question of last resort; it's asked only if keymaps cannot be |
| 163 |
distinguished otherwise. |
| 164 |
|
| 165 |
This command will be accompanied by one YES and one NO command. |
| 166 |
|
| 167 |
FINDP char |
| 168 |
++++++++++ |
| 169 |
|
| 170 |
Equivalent to FIND, except that the user is asked to consider only the |
| 171 |
primary symbols (i.e. Plain and Shift). |
| 172 |
|
| 173 |
YES ## |
| 174 |
++++++ |
| 175 |
|
| 176 |
Direct the evaluating code to process step ## next if the user does have |
| 177 |
this key. |
| 178 |
|
| 179 |
NO ## |
| 180 |
+++++ |
| 181 |
|
| 182 |
Direct the evaluating code to process step ## next if the user does not |
| 183 |
have this key. |
| 184 |
|