Woua ! THAT is a complete explanation ! It shows well the complexity and power of the illume keyboard method. I apologize for not having well understand this before.<br>I will now definitely use the keyboard, and improve my dictionnary as I type.<br>
Thanks a lot for the complete explanation<br><br><br><br><div class="gmail_quote">2009/1/6 The Rasterman Carsten Haitzler <span dir="ltr"><<a href="mailto:raster@rasterman.com">raster@rasterman.com</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
On Tue, 6 Jan 2009 09:50:38 +0100 kimaidou <<a href="mailto:kimaidou@gmail.com">kimaidou@gmail.com</a>> babbled:<br>
<div class="Ih2E3d"><br>
> Hi all,<br>
><br>
> I am glad people (re-)start to talk about keyboards.<br>
><br>
> 2 points:<br>
><br>
> * Another great improvement compared to the iphone, illume, etc. ones, would<br>
> be to have a transparent keyboard, using the whole screen, but allowing to<br>
> see through it. Of course we need the transparency % to be changed by the<br>
> user. What about the technical feasibility of that ? Would it be possible ?<br>
> I thing for example about the Qwo keyboard (<br>
> <a href="http://www.opkg.org/package_84.html" target="_blank">http://www.opkg.org/package_84.html</a> ) which would be very finger friendly in<br>
> full screen (like the other one)<br>
<br>
</div>not possible without compositing. not to mention the absolute HORROR of now<br>
having to mix keyboard input with controlling the apps under it - which is it u<br>
do? press the key or the "ok" button thats visible thru the key? compositing is<br>
not a viable thing on the freerunner - u'll need a much lower res to make it<br>
sane and even then it'll be really pushing it at qvga on the 2442.<br>
<div class="Ih2E3d"><br>
> * I don't get how the dictionnary (illume and qtopia) actually helps to<br>
> write some word. In mobile phones, on which you have only 9 numbers to type,<br>
> so 3 letters by number, the "T9" dictionnary was really helpfull, because it<br>
> showed a list of words possible with the combination of the letters entered.<br>
> I could actually write sms faster with only 9 keys than now with a complete<br>
> qwerty keyboard because the buttons were much bigger and I had only 9 button<br>
> to search among. Here with the FR, the "eyes and brain" must locate the<br>
> desired letter among much more and much smaller keys. And furthermore, I<br>
> don't see the point with the dictionnary. The dictionnary only shows words<br>
> with the same number of letters as the ones entered. So it does not provide<br>
> a way to easily choose a word (for example, when I type "for" it must show<br>
> "for", "forest", force", etc., but with the illume keyboard it only shows<br>
> "for" and other useless words like :"big", "fit", die", but", etc.--> not<br>
> very related to "for" ) People using OpenOffice Writer with the<br>
> autocompletion activated will understand what I am trying to explain with my<br>
> limited english skills..<br>
<br>
</div>ok. let me draw u a keyboard (or part of it):<br>
<br>
q w e r t y u i o p<br>
a s d f g h j k l<br>
z x c v b n m<br>
<br>
i want to type "dog". for this example i will only use english as the example -<br>
but it applies to all languages actually. now lets say i press "d" (i want to<br>
type "dog"), then "o" then "g". but look at the keyboard - i may not EXACTLY<br>
hit d, o and g. i probably hit them or something near them, so ad i try and hit<br>
d i may hit e, and i may hit k and not o, and h instead of g, so i actually hit:<br>
"ekh"<br>
<br>
that's not "dog"! of course not. but it also is not any word in english (in the<br>
dictionary) so obviously.. it must be wrong. i meant something else. now lets<br>
stand back.<br>
<br>
first key i press "e" is near d. it's also near r, s, w, and f. let's write the<br>
"possible" keys i may have intended as a list per keystroke:<br>
e, d, r, s, w, f<br>
now for "k" (when i meant "o"):<br>
k, i, u, j, m, l, o<br>
and for "h" (when i meant "g"):<br>
h, y, u, j, n, b, g<br>
<br>
ok so now for every keystroke i have a list of possible keys near where i<br>
pressed that i may have meant (again i have simplified this - in reality the<br>
list of keys per press is more like 10-15 possible keys as it has a large<br>
search area - this is the fuzz value in the .kbd file - it determines how far<br>
the fuzzy matching should search in virtual keyboard units).<br>
<br>
now what we do is start checking all combinations of all the letters per key<br>
stroke, so we first try:<br>
<br>
ekh -> wrong<br>
eih -> wrong<br>
euh -> wrong<br>
ejh -> wrong<br>
emh -> wrong<br>
elh -> wrong<br>
eoh -> wrong<br>
eky -> wrong<br>
eiy -> wrong<br>
euy -> wrong<br>
ejy -> wrong<br>
emy -> wrong<br>
ely -> wrong<br>
eoy -> wrong<br>
ekh -> wrong<br>
eiu -> wrong<br>
euu -> wrong<br>
eju -> wrong<br>
emu -> BINGO! a real word!<br>
elu -> wrong<br>
eou -> wrong<br>
ekj -> wrong<br>
eij -> wrong<br>
etc.<br>
<br>
in the end if you search permutations you'd get a list of words that "match"<br>
<br>
emu, fig, dig, fly, sky, fog, rig, sob, dog, ... and so on.<br>
<br>
now we have a list of words i possibly wanted that match. (its very much like<br>
the 2 == avc, 3 == def, 4 == ghi, 5 == jkl etc. - but its not based on mapping<br>
26 letters to just 8 numbers on a numberpad - because you have no actual<br>
numberpad - its just a surface you tap on and you have a co-ordinate where you<br>
press. so you dont NEED to map it that way - you can just present a qwerty<br>
layout and just search for nearby keys u may have wanted to hit.<br>
<br>
anyway - this is the simple version. now.. things get more complex. lets go<br>
over the keys i possible wanted to hit again:<br>
<br>
e, d, r, s, w, f<br>
k, i, u, j, m, l, o<br>
h, y, u, j, n, b, g<br>
<br>
unlike the numberpas - the set of keys per press is entirely variable based on<br>
what keys are near "within" the fuzz search radius. also unlike a keypad each<br>
key will have a DISTANCE from the point i pressed so i know how far away it is<br>
from the press point - thus the further away - the more unlikely it is i wanted<br>
it. the closer it is, the more likely. so you can built a list of possible keys<br>
i pressed PLUS a distance (0 == more likely, 9 == least likely) like this:<br>
<br>
e0, d1, r2, s2, w3, f8<br>
k1, i1, u4, j7, m8, l3, o1<br>
h1, y2, u8, j9, n3, b6, g2<br>
<br>
how we have all the strokes and assigned a distance from the press point - for<br>
here i just assigned a simple 0-9 value. now lets look at some of the possible<br>
words above that match. each word can have a distance - if you add up the<br>
distance of all the letters (based on the above), so we can give each word a<br>
number rating (0 == more likely, bigger == less likely). let's do that:<br>
<br>
emu 0 + 8 + 8 = 16<br>
fig 8 + 1 + 2 = 11<br>
dig 1 + 1 + 2 = 4<br>
fly 8 + 3 + 2 = 13<br>
sky 2 + 1 + 2 = 5<br>
fog 8 + 1 + 2 = 11<br>
rig 2 + 1 + 2 = 5<br>
sob 2 + 1 + 6 = 9<br>
dog 1 + 1 + 2 = 4<br>
<br>
now every word in out list (trust me normally this list is much longer) has a<br>
number. so let's sort them from lowest to highest:<br>
<br>
dig 4<br>
dog 4<br>
sky 5<br>
rig 5<br>
sob 9<br>
fig 11<br>
fog 11<br>
emu 16<br>
<br>
now we have a list of words you may have wanted to type from most to least<br>
likely. but wait. we know more. languages have frequency corpuses. this means<br>
some words are much more frequently used than others. dog is used much more<br>
than emu for example (you are much more likely to want dog than emu when typing<br>
something. now we have a dictionary that lists the frequency of use of a word.<br>
lets look up the words in the above list in our dictionary:<br>
<br>
dig 35<br>
dog 130<br>
sky 60<br>
rig 13<br>
sob 12<br>
fig 82<br>
fog 15<br>
emu 5<br>
<br>
now we have 2 bits of information. a number that tells us how likely it is you<br>
wanted that word - and another - how common that word is in the given language.<br>
even if it seems i more likely typed 1 word just from raw presses, i may have<br>
meant another thats less likely, but much more common in the language. so we<br>
need to adjust out closeness numbers. lets do this simply with this:<br>
<br>
probability = distance * 100 / word_frequency<br>
<br>
so:<br>
<br>
dig 4 * 100 / 35 = 11<br>
dog 4 * 100 / 130 = 3<br>
sky 5 * 100 / 60 = 8<br>
rig 5 * 100 / 13 = 38<br>
sob 9 * 100 / 12 = 75<br>
fig 11 * 100 / 82 = 13<br>
fog 11 * 100 / 15 = 73<br>
emu 16 * 100 / 5 = 320<br>
<br>
now let's re-sort based on this new probability factor we calculated:<br>
<br>
dog 3<br>
sky 8<br>
dig 11<br>
dig 13<br>
rig 38<br>
fog 73<br>
sob 75<br>
emu 320<br>
<br>
now we have a list of things i possibly wanted to type - ordered by what i most<br>
likely wanted - dog at the top.<br>
<br>
THIS is how dictionary correction works. using all the information available<br>
(full co-ordinates of your finger press so it knows just how far the press is<br>
from all keys, and frequency of use of a word in a language as well as a list<br>
of valid words). this is a simplified explanation of how the dictionary<br>
correction system works in the illume keyboard (of course its more complex in<br>
that it has to do LOTS of lookups fast - or try - until some recent utf8<br>
patches which i think actually still have bugs, it was acceptably fast, but<br>
this need improving). it looks at combinations (no it doesn't brute-force try<br>
every one - it knows that no words start with "hw" for example and so it stops<br>
trying any more combinations of hw[something] as there is nothing left to try<br>
that will work. and the simple probability division above has some weighting<br>
factor of dict vs distance (not a simple multiply only). also it learns. as you<br>
use a word more - it increases the frequency # for that word - so as you use<br>
the system words YOU use a lot increase their frequency count and thus become<br>
more likely to be chosen in a match list as the most likely - or at least be<br>
near the top. this data is written to a nice simple text file in<br>
~/.e/e/dicts-dynamic that is overlayed on the system dic files.<br>
<br>
so the idea is - just type - dont worry if the words it displays AS you type<br>
are not what you want - you haven't finished yet. it only matches words of the<br>
length of chars you typed - because trying to complete all words that START<br>
with the letters you typed would make the list of matches IMMENSELY long - so<br>
it limits search space by you having to type a whole word in. then it has a<br>
more limited set of possible matches. so just bash away and then click on the<br>
word matched above (or if its not press the up-arrow on the top-left of the kbd<br>
and select from the long list - if the word is NOT in the dictionary - EXACTLY<br>
what you typed is at the top of the list there so its 2 clicks away instead of<br>
1). as i said - it learns, so if the word is not in the dict, but you now<br>
select it.. it gets added and starts accumulating frequency usage information.<br>
after that it becomes part of the matching process.<br>
<br>
there are other features too. the press+hold to get the zoom box to type<br>
EXACTLY the letter you want when on the go. press and hold and the zoom box<br>
comes up showing the area under your finger. as u drag it will pan showing the<br>
letter selected. this lets you know just where the press point of your finger<br>
is and to explicitly select a letter. if you select a letter this way - that<br>
letter in the typing sequence will be "locked in place". illume's kbd wont<br>
search for other possible letters you may have wanted to type. it assumes you<br>
have been VERY explicit and want just that letter. you may just do this for 1<br>
letter in a word or multiple - its up to you, but it lets you be VERY explicit.<br>
this helps the matcher as it reduces the search range a lot. really though -<br>
you only will want this for entering words you have never used before. so you<br>
type a word - and its not in any dict. but you totally mistyped it. of course -<br>
you are walking down the street. ok - so backspace it all (yes - i know<br>
multiple strokes. this is an area things can improve to delete the whole word<br>
in a single stroke). now re-type it slowly with press+hold, drag with zoom box,<br>
release. per letter. now it will let you type it in - and it will be added to<br>
your dict, never to need such manual treatment again as long as you keep your<br>
private dict files.<br>
<br>
THIS is how the keyboard works. it works surprisingly well - if you saw the<br>
dogs breakfast of input data it gets from the touchscreen and just how totally<br>
"out there" the keys you really pressed are - and how well it can hone in on<br>
listing the word you probably wanted. if you just sit back and trust it for a<br>
bit. just bash away and worry about it at the end of the word. it works pretty<br>
well.<br>
<br>
technically this would be possible for a shell too - if you had a dictionary<br>
that held shell commands for example - and common cmd-line options. though the<br>
problem here is you need a little more context.<br>
<br>
anyway. i hope this helps people understand how it works. someone can throw<br>
this onto the wiki if they like. this is the code i wrote for the illume kbd<br>
(as well as all the ui bits, the theme bits, the actual generic kbd infra for<br>
handling externally provided keyboard etc. etc.). it was entirely inspired by<br>
qtopia's keyboard entry which had the core of these smarts done nicely - it<br>
just was missing discoverability and easier usage. (where is return? how do i<br>
backspace? where is ctrl/alt? how do i enter a space?). you basically need to<br>
be taught these by someone who knows or find a manual and read it as there is<br>
no obvious way to do many of these. layouts are fixed in code. it definitely<br>
has the better dictionary code right now - that's something i need to improve.<br>
i only have so many hours in a day though. and right now kbd is not on my<br>
immediate todo list. the code is there for all to see - this is open source.<br>
patches are of course welcome. i broke the code up into fairly well defined<br>
layers. yes its not a walk in the park - doing the above take a bit of work but<br>
anyone conversant with c and has good coding skills otherwise could handle it<br>
no problems.<br>
<br>
so... get tapping. :)<br>
<div><div></div><div class="Wj3C7c"><br>
> My 2 cents :) , of course in a constructive way<br>
><br>
> Kimaidou<br>
><br>
> 2009/1/6 The Rasterman Carsten Haitzler <<a href="mailto:raster@rasterman.com">raster@rasterman.com</a>><br>
><br>
> > On Tue, 6 Jan 2009 11:08:41 +0530 "Shashank Bharadwaj" <<br>
> > <a href="mailto:shanka.mns@gmail.com">shanka.mns@gmail.com</a>><br>
> > babbled:<br>
> ><br>
> > > On Tue, Jan 6, 2009 at 10:47 AM, The Rasterman Carsten Haitzler <<br>
> > > <a href="mailto:raster@rasterman.com">raster@rasterman.com</a>> wrote:<br>
> > ><br>
> > > > On Tue, 06 Jan 2009 02:46:15 +0000 Jan Henkins <<a href="mailto:jan@henkins.za.net">jan@henkins.za.net</a>><br>
> > > > babbled:<br>
> > > ><br>
> > > > > Hello there,<br>
> > > > ><br>
> > > > > Pascal d'Hermilly wrote:<br>
> > > > > > With 2008.12 release, a well working finger-friendly keyboard is<br>
> > the<br>
> > > > > > most critical missing feature for me.<br>
> > > > > > I've made a mockup of a keyboard that I think would make things a<br>
> > lot<br>
> > > > > > easier to type.<br>
> > > > > > <a href="http://dhermilly.dk/pascal/openmoko/keyboard%20mockup.png" target="_blank">http://dhermilly.dk/pascal/openmoko/keyboard%20mockup.png</a><br>
> > > ><br>
> > ><br>
> > > I think, the current Raster's Keyboard great for potrait mode. For<br>
> > landscape<br>
> > > mode(i.e holding neo sideways) however, the keyboard does not utilize the<br>
> > > extra space. What we need is, imho, a keyboard that would increase in<br>
> > size<br>
> > > to take up the extra space in this landscape mode. That way we'll be able<br>
> > to<br>
> > > type even faster. If we could add that fuctionality to raster's keyboard,<br>
> > > then it'd be just great.<br>
> ><br>
> > that's a matter of just fixing the code to handle resizing appropriately.<br>
> ><br>
> > --<br>
> > ------------- Codito, ergo sum - "I code, therefore I am" --------------<br>
> > The Rasterman (Carsten Haitzler) <a href="mailto:raster@rasterman.com">raster@rasterman.com</a><br>
> ><br>
> ><br>
> > _______________________________________________<br>
> > Openmoko community mailing list<br>
> > <a href="mailto:community@lists.openmoko.org">community@lists.openmoko.org</a><br>
> > <a href="http://lists.openmoko.org/mailman/listinfo/community" target="_blank">http://lists.openmoko.org/mailman/listinfo/community</a><br>
> ><br>
><br>
<br>
<br>
</div></div>--<br>
<div><div></div><div class="Wj3C7c">------------- Codito, ergo sum - "I code, therefore I am" --------------<br>
The Rasterman (Carsten Haitzler) <a href="mailto:raster@rasterman.com">raster@rasterman.com</a><br>
<br>
</div></div></blockquote></div><br>