Openmoko keyboard mockup

[Carsten Haitzler (The Rasterman)]

On Tue, 6 Jan 2009 09:50:38 +0100 kimaidou <kimaidou at gmail.com> babbled:

> Hi all,
> 
> I am glad people (re-)start to talk about keyboards.
> 
> 2 points:
> 
> * Another great improvement compared to the iphone, illume, etc. ones, would
> be to have a transparent keyboard, using the whole screen, but allowing to
> see through it. Of course we need the transparency % to be changed by the
> user. What about the technical feasibility of that ? Would it be possible ?
> I thing for example about the Qwo keyboard (
> http://www.opkg.org/package_84.html ) which would be very finger friendly in
> full screen (like the other one)

not possible without compositing. not to mention the absolute HORROR of now
having to mix keyboard input with controlling the apps under it - which is it u
do? press the key or the "ok" button thats visible thru the key? compositing is
not a viable thing on the freerunner - u'll need a much lower res to make it
sane and even then it'll be really pushing it at qvga on the 2442.

> * I don't get how the dictionnary (illume and qtopia) actually helps to
> write some word. In mobile phones, on which you have only 9 numbers to type,
> so 3 letters by number, the "T9" dictionnary was really helpfull, because it
> showed a list of words possible with the combination of the letters entered.
> I could actually write sms faster with only 9 keys than now with a complete
> qwerty keyboard because the buttons were much bigger and I had only 9 button
> to search among. Here with the FR, the "eyes and brain" must locate the
> desired letter among much more and much smaller keys. And furthermore, I
> don't see the point with the dictionnary. The dictionnary only shows words
> with the same number of letters as the ones entered. So it does not provide
> a way to easily choose a word (for example, when I type "for" it must show
> "for", "forest", force", etc., but  with the illume keyboard it only shows
> "for" and other useless words like :"big", "fit", die", but", etc.--> not
> very related to "for" ) People using OpenOffice Writer with the
> autocompletion activated will understand what I am trying to explain with my
> limited english skills..

ok. let me draw u a keyboard (or part of it):

  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

i want to type "dog". for this example i will only use english as the example -
but it applies to all languages actually. now lets say i press "d" (i want to
type "dog"), then "o" then "g". but look at the keyboard - i may not EXACTLY
hit d, o and g. i probably hit them or something near them, so ad i try and hit
d i may hit e, and i may hit k and not o, and h instead of g, so i actually hit:
"ekh"

that's not "dog"! of course not. but it also is not any word in english (in the
dictionary) so obviously.. it must be wrong. i meant something else. now lets
stand back.

first key i press "e" is near d. it's also near r, s, w, and f. let's write the
"possible" keys i may have intended as a list per keystroke:
e, d, r, s, w, f
now for "k" (when i meant "o"):
k, i, u, j, m, l, o
and for "h" (when i meant "g"):
h, y, u, j, n, b, g

ok so now for every keystroke i have a list of possible keys near where i
pressed that i may have meant (again i have simplified this - in reality the
list of keys per press is more like 10-15 possible keys as it has a large
search area - this is the fuzz value in the .kbd file - it determines how far
the fuzzy matching should search in virtual keyboard units).

now what we do is start checking all combinations of all the letters per key
stroke, so we first try:

ekh -> wrong
eih -> wrong
euh -> wrong
ejh -> wrong
emh -> wrong
elh -> wrong
eoh -> wrong
eky -> wrong
eiy -> wrong
euy -> wrong
ejy -> wrong
emy -> wrong
ely -> wrong
eoy -> wrong
ekh -> wrong
eiu -> wrong
euu -> wrong
eju -> wrong
emu -> BINGO! a real word!
elu -> wrong
eou -> wrong
ekj -> wrong
eij -> wrong
etc.

in the end if you search permutations you'd get a list of words that "match"

emu, fig, dig, fly, sky, fog, rig, sob, dog, ... and so on.

now we have a list of words i possibly wanted that match. (its very much like
the 2 == avc, 3 == def, 4 == ghi, 5 == jkl etc. - but its not based on mapping
26 letters to just 8 numbers on a numberpad - because you have no actual
numberpad - its just a surface you tap on and you have a co-ordinate where you
press. so you dont NEED to map it that way - you can just present a qwerty
layout and just search for nearby keys u may have wanted to hit.

anyway - this is the simple version. now.. things get more complex. lets go
over the keys i possible wanted to hit again:

e, d, r, s, w, f
k, i, u, j, m, l, o
h, y, u, j, n, b, g

unlike the numberpas - the set of keys per press is entirely variable based on
what keys are near "within" the fuzz search radius. also unlike a keypad each
key will have a DISTANCE from the point i pressed so i know how far away it is
from the press point - thus the further away - the more unlikely it is i wanted
it. the closer it is, the more likely. so you can built a list of possible keys
i pressed PLUS a distance (0 == more likely, 9 == least likely) like this:

e0, d1, r2, s2, w3, f8
k1, i1, u4, j7, m8, l3, o1
h1, y2, u8, j9, n3, b6, g2 

how we have all the strokes and assigned a distance from the press point - for
here i just assigned a simple 0-9 value. now lets look at some of the possible
words above that match. each word can have a distance - if you add up the
distance of all the letters (based on the above), so we can give each word a
number rating (0 == more likely, bigger == less likely). let's do that:

emu 0 + 8 + 8 = 16
fig 8 + 1 + 2 = 11 
dig 1 + 1 + 2 = 4
fly 8 + 3 + 2 = 13
sky 2 + 1 + 2 = 5
fog 8 + 1 + 2 = 11
rig 2 + 1 + 2 = 5
sob 2 + 1 + 6 = 9
dog 1 + 1 + 2 = 4

now every word in out list (trust me normally this list is much longer) has a
number. so let's sort them from lowest to highest:

dig 4
dog 4
sky 5
rig 5
sob 9
fig 11
fog 11
emu 16

now we have a list of words you may have wanted to type from most to least
likely. but wait. we know more. languages have frequency corpuses. this means
some words are much more frequently used than others. dog is used much more
than emu for example (you are much more likely to want dog than emu when typing
something. now we have a dictionary that lists the frequency of use of a word.
lets look up the words in the above list in our dictionary:

dig 35
dog 130
sky 60
rig 13
sob 12
fig 82
fog 15
emu 5

now we have 2 bits of information. a number that tells us how likely it is you
wanted that word - and another - how common that word is in the given language.
even if it seems i more likely typed 1 word just from raw presses, i may have
meant another thats less likely, but much more common in the language. so we
need to adjust out closeness numbers. lets do this simply with this:

probability = distance * 100 / word_frequency

so:

dig 4 * 100 / 35  = 11
dog 4 * 100 / 130 = 3
sky 5 * 100 / 60  = 8 
rig 5 * 100 / 13  = 38
sob 9 * 100 / 12  = 75 
fig 11 * 100 / 82 = 13
fog 11 * 100 / 15 = 73
emu 16 * 100 / 5  = 320

now let's re-sort based on this new probability factor we calculated:

dog 3
sky 8
dig 11
dig 13
rig 38
fog 73
sob 75
emu 320

now we have a list of things i possibly wanted to type - ordered by what i most
likely wanted - dog at the top.

THIS is how dictionary correction works. using all the information available
(full co-ordinates of your finger press so it knows just how far the press is
from all keys, and frequency of use of a word in a language as well as a list
of valid words). this is a simplified explanation of how the dictionary
correction system works in the illume keyboard (of course its more complex in
that it has to do LOTS of lookups fast - or try - until some recent utf8
patches which i think actually still have bugs, it was acceptably fast, but
this need improving). it looks at combinations (no it doesn't brute-force try
every one - it knows that no words start with "hw" for example and so it stops
trying any more combinations of hw[something] as there is nothing left to try
that will work. and the simple probability division above has some weighting
factor of dict vs distance (not a simple multiply only). also it learns. as you
use a word more - it increases the frequency # for that word - so as you use
the system words YOU use a lot increase their frequency count and thus become
more likely to be chosen in a match list as the most likely - or at least be
near the top. this data is written to a nice simple text file in
~/.e/e/dicts-dynamic that is overlayed on the system dic files.

so the idea is - just type - dont worry if the words it displays AS you type
are not what you want - you haven't finished yet. it only matches words of the
length of chars you typed - because trying to complete all words that START
with the letters you typed would make the list of matches IMMENSELY long - so
it limits search space by you having to type a whole word in. then it has a
more limited set of possible matches. so just bash away and then click on the
word matched above (or if its not press the up-arrow on the top-left of the kbd
and select from the long list - if the word is NOT in the dictionary - EXACTLY
what you typed is at the top of the list there so its 2 clicks away instead of
1). as i said - it learns, so if the word is not in the dict, but you now
select it.. it gets added and starts accumulating frequency usage information.
after that it becomes part of the matching process.

there are other features too. the press+hold to get the zoom box to type
EXACTLY the letter you want when on the go. press and hold and the zoom box
comes up showing the area under your finger. as u drag it will pan showing the
letter selected. this lets you know just where the press point of your finger
is and to explicitly select a letter. if you select a letter this way - that
letter in the typing sequence will be "locked in place". illume's kbd wont
search for other possible letters you may have wanted to type. it assumes you
have been VERY explicit and want just that letter. you may just do this for 1
letter in a word or multiple - its up to you, but it lets you be VERY explicit.
this helps the matcher as it reduces the search range a lot. really though -
you only will want this for entering words you have never used before. so you
type a word - and its not in any dict. but you totally mistyped it. of course -
you are walking down the street. ok - so backspace it all (yes - i know
multiple strokes. this is an area things can improve to delete the whole word
in a single stroke). now re-type it slowly with press+hold, drag with zoom box,
release. per letter. now it will let you type it in - and it will be added to
your dict, never to need such manual treatment again as long as you keep your
private dict files.

THIS is how the keyboard works. it works surprisingly well - if you saw the
dogs breakfast of input data it gets from the touchscreen and just how totally
"out there" the keys you really pressed are - and how well it can hone in on
listing the word you probably wanted. if you just sit back and trust it for a
bit. just bash away and worry about it at the end of the word. it works pretty
well.

technically this would be possible for a shell too - if you had a dictionary
that held shell commands for example - and common cmd-line options. though the
problem here is you need a little more context.

anyway. i hope this helps people understand how it works. someone can throw
this onto the wiki if they like. this is the code i wrote for the illume kbd
(as well as all the ui bits, the theme bits, the actual generic kbd infra for
handling externally provided keyboard etc. etc.). it was entirely inspired by
qtopia's keyboard entry which had the core of these smarts done nicely - it
just was missing discoverability and easier usage. (where is return? how do i
backspace? where is ctrl/alt? how do i enter a space?). you basically need to
be taught these by someone who knows or find a manual and read it as there is
no obvious way to do many of these. layouts are fixed in code. it definitely
has the better dictionary code right now - that's something i need to improve.
i only have so many hours in a day though. and right now kbd is not on my
immediate todo list. the code is there for all to see - this is open source.
patches are of course welcome. i broke the code up into fairly well defined
layers. yes its not a walk in the park - doing the above take a bit of work but
anyone conversant with c and has good coding skills otherwise could handle it
no problems.

so... get tapping. :)

> My 2 cents :) , of course in a constructive way
> 
> Kimaidou
> 
> 2009/1/6 The Rasterman Carsten Haitzler <raster at rasterman.com>
> 
> > On Tue, 6 Jan 2009 11:08:41 +0530 "Shashank Bharadwaj" <
> > shanka.mns at gmail.com>
> > babbled:
> >
> > > On Tue, Jan 6, 2009 at 10:47 AM, The Rasterman Carsten Haitzler <
> > > raster at rasterman.com> wrote:
> > >
> > > > On Tue, 06 Jan 2009 02:46:15 +0000 Jan Henkins <jan at henkins.za.net>
> > > > babbled:
> > > >
> > > > > Hello there,
> > > > >
> > > > > Pascal d'Hermilly wrote:
> > > > > > With 2008.12 release, a well working finger-friendly keyboard is
> > the
> > > > > > most critical missing feature for me.
> > > > > > I've made a mockup of a keyboard that I think would make things a
> > lot
> > > > > > easier to type.
> > > > > > http://dhermilly.dk/pascal/openmoko/keyboard%20mockup.png
> > > >
> > >
> > > I think, the current Raster's Keyboard great for potrait mode. For
> > landscape
> > > mode(i.e holding neo sideways) however, the keyboard does not utilize the
> > > extra space. What we need is, imho, a keyboard that would increase in
> > size
> > > to take up the extra space in this landscape mode. That way we'll be able
> > to
> > > type even faster. If we could add that fuctionality to raster's keyboard,
> > > then it'd be just great.
> >
> > that's a matter of just fixing the code to handle resizing appropriately.
> >
> > --
> > ------------- Codito, ergo sum - "I code, therefore I am" --------------
> > The Rasterman (Carsten Haitzler)    raster at rasterman.com
> >
> >
> > _______________________________________________
> > Openmoko community mailing list
> > community at lists.openmoko.org
> > http://lists.openmoko.org/mailman/listinfo/community
> >
> 


-- 
------------- Codito, ergo sum - "I code, therefore I am" --------------
The Rasterman (Carsten Haitzler)    raster at rasterman.com