Sign in to follow this  
roby65

Implementing T9 with 1 MB RAM

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Quote:
Original post by roby65
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


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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Quote:
Original post by roby65
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?


Yep,only the needed words (5-6) using a binary search on file.

Share this post


Link to post
Share on other sites
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:

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
N


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"?

Share this post


Link to post
Share on other sites
If you have some cycles to waste, you can also make it more compact:

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this