Debian Codegraph @

README

raw
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