Implementing T9 with 1 MB RAM
Author
Hi guys,
i would like to talk about what i'm going to code, cause i need some suggestions :)
Embedded platform, RAM<1MB avaible, cpu < 100 Mhz.
I'm gonna write a T9 for that embedded system, but i'm sure i will encounter problems with the ram: i need to use as less RAM as i can, cause i need all the ram for the main program.
What i would do:
Load the dictionary into the RAM, then use some simple string comparing to find the nearest 4/5 words.
But this is a problem: the dictionary could be very big, using too much RAM.
Any ideas on another way to do this?
Author
Quote:Original post by feal87
db on file ordered.
binary search (on file) and load only needed data in real time.
I forgot to say that the "disk" is a memory stick, and access to it is damn slow
Quote:Original post by roby65Quote:Original post by feal87
db on file ordered.
binary search (on file) and load only needed data in real time.
I forgot to say that the "disk" is a memory stick, and access to it is damn slow
i've done a similiar app for an old (dr.dos only) PDT from symbol,and works fast. speed is not necessary, seeks times are. do a check
Author
Quote:Original post by feal87
i've done a similiar app for an old (dr.dos only) PDT from symbol,and works fast. speed is not necessary, seeks times are. do a check
So, should i load words from file everytime the user types anything?
Quote:Original post by roby65Quote:Original post by feal87
i've done a similiar app for an old (dr.dos only) PDT from symbol,and works fast. speed is not necessary, seeks times are. do a check
So, should i load words from file everytime the user types anything?
Yep,only the needed words (5-6) using a binary search on file.
Instead of a full blown dictionary (that is, if you really mean something like a c++-map, c#-dictionary, of similar associative arrays/containers), you could build something like this (pseudo-code), with keys only:
yielding a structure like
Unsupported letters would just be NULL, and if you are careful, lookup per Entry is O(const).
If even this key-only structure is too much, you could still cut it off at some level (i.e. for very long or uncommon words) and then load from disk.
Not trivial, but then you are not on a trivial system. Also don't forget that 1 MiB = 1024 KiB = 1048576 Byte, i.e., if you do it non-naive, then that's plenty of space.
sidenote: You are aware of that T9 is a patented "idea"?
const num_letters = ...;Entry { Entry *next[num_letters];};yielding a structure like
+-------A--------+ +---B---+ +---L---+ E N L P R O E H R R G A A M O T A R I L I O C NUnsupported letters would just be NULL, and if you are careful, lookup per Entry is O(const).
If even this key-only structure is too much, you could still cut it off at some level (i.e. for very long or uncommon words) and then load from disk.
Not trivial, but then you are not on a trivial system. Also don't forget that 1 MiB = 1024 KiB = 1048576 Byte, i.e., if you do it non-naive, then that's plenty of space.
sidenote: You are aware of that T9 is a patented "idea"?
If you have some cycles to waste, you can also make it more compact:
This would be 8 bytes per node on x86.
E.g., when you have a node with a, k, x set, then children[0] would be your a node, children[1] would be your k node, children[2] would be your x node.
Of course you should add some helper functions to that structure, like size(), char operator[](size_t), etc, otherwise your code gets scrambled ;)
Tbh, I didn't know that it has a name :D
struct Letters { bool a:1, b:1, c:1, d:1, e:1, f:1, g:1; bool h:1, i:1, j:1, k:1, l:1, m:1, n:1; bool o:1, p:1, q:1, r:1, s:1, t:1, u:1; bool v:1, w:1, x:1, y:1, z:1;};struct Node { Letters letters; Node *children;};This would be 8 bytes per node on x86.
E.g., when you have a node with a, k, x set, then children[0] would be your a node, children[1] would be your k node, children[2] would be your x node.
Of course you should add some helper functions to that structure, like size(), char operator[](size_t), etc, otherwise your code gets scrambled ;)
Quote:Original post by alvaro
What phresnel is talking about is called a trie.
Tbh, I didn't know that it has a name :D
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement