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 on other sites
db on file ordered.
binary search (on file) and load only needed data in real time.

Share on other sites
Quote:
 Original post by feal87db 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 on other sites
Quote:
Original post by roby65
Quote:
 Original post by feal87db 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 on other sites
Quote:
 Original post by feal87i'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 on other sites
Quote:
Original post by roby65
Quote:
 Original post by feal87i'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 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 on other sites
What phresnel is talking about is called a trie.

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 alvaroWhat phresnel is talking about is called a trie.

Tbh, I didn't know that it has a name :D

Create an account

Register a new account

• Forum Statistics

• Total Topics
628367
• Total Posts
2982279

• 10
• 9
• 13
• 24
• 11