On Sun 01 Feb 2009 00:31:09 Carsten Haitzler wrote: > On Fri, 30 Jan 2009 21:16:57 +0100 Olof Sjobergh <[email protected]> said: > > On Fri, Jan 30, 2009 at 8:12 PM, The Rasterman Carsten Haitzler > > > > <[email protected]> wrote: > > > On Fri, 30 Jan 2009 08:31:43 +0100 Olof Sjobergh <[email protected]> said: > > >> But I think a dictionary format in plain utf8 that includes the > > >> normalised words as well as any candidates to display would be the > > >> best way. Then the dictionary itself could choose which characters to > > >> normalise and which to leave as is. So for Swedish, you can leave å, ä > > >> and ö as they are but normalise é, à etc. Searching would be as simple > > >> as in your original implementation (no need to convert from multibyte > > >> format). > > > > > > the problem is - the dict in utf8 means searching is slow as you do it > > > in utf8 space. the dict is mmaped() to save ram - if it wasnt it'd need > > > to be allocated in non-swappable ram (its a phone - it has no swap) and > > > thus a few mb of your ram goes into the kbd dict at all times. by using > > > mmap you leave it to the kernels paging system to figure it out. > > > > > > so as such a dict change will mean a non-ascii format in future for > > > this reason. but there will then need to be a tool to generate such a > > > file. > > > > Searching in utf8 doesn't mean it has to be slow. Simple strcmp works > > fine on multibyte utf8 strings as well, and should be as fast as the > > dictionary was before adding multibyte to widechars conversions. But > > if you have some other idea in mind, please don't let me disturb. =) > > the problem is - it INSt a simple key>value lookup. it's a possible-match > tree build on-the-fly. that means you jump about examining 1 character at a > time. the problem here is that 1 char may or may not be 1 byte or more and > that makes it really nasty. if it were a simple key lookup for a given > simple string - life would be easy. this is possible - but then u'd have to > generate ALL permutations first then look ALL of them up. if you weed out > permutations AS you look them up you can weed out something like 90% of the > permutations as you KNOw there are no words starting with qz... so as you > go through qa... qs.... qx... qz... you can easily stop all the > combinations with qs, qz ans qx as no words begin with that (if you have an > 8 letter word with 8 possible letters per character in the word thats 8^6 > lookups you avoided (in the case above - ie all permutations of the other 6 > letters). thats 262144 lookups avoided... just there. for... 1 of the above > impossible permutation trees. now add it up over all of them.
Do you consider this paper relevant? http://citeseer.ist.psu.edu/schulz02fast.html "Fast String Correction with Levenshtein-Automata", (2002), Klaus Schulz, Stoyan Mihov It actually uses tries to avoid generating and comparing exhaustively all permutations of the input word (typed keys), but instead traverses *only* know words and accumulates permutations unless a max-errors limit gets exceeded, in which case this path dies. It describes a mathematical model for correcting typos, but since i have already implemented it (in java) i know think it can be retrofitted to perform what you describe in: http://wiki.openmoko.org/wiki/Illume_keyboard Keep up the good work. Kostis _______________________________________________ Openmoko community mailing list [email protected] http://lists.openmoko.org/mailman/listinfo/community
