What you're describeing is called trie
. A compact radix tree is more compact.
Question
I'd like to store some data associated to words composed of simple ascii letters (a-Z) The goal is to retrieve very quickly the data associated to a word in a future parsing.
I though about the following structure:
struct Foo {
Foo *letter[26];
void *data;
};
Thus, it is possible to go down through the "letter tree" while parsing a word in a string and get the associated data.
"foo" => ['f' node] -> ['o' node] -> ['o' node]
The problem is the size of the entire tree if I got many words.
Is there a way to reduce the size of the tree without losing performances?
Solution
OTHER TIPS
Is there a reason you're using a tree instead of storing words in a hash table? These will tend to use a bit more memory, but will give you near constant time performance for table lookups.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow