Subj : Serializing a trie (sorting problem)
To   : comp.programming
From : Peter Ammon
Date : Sat Jul 23 2005 04:39 pm

In short, how can I order the nodes of a tree or trie so that the 
distance between a parent and its children is as small as possible?

Some background:

I have a trie file representing a bunch of words, and it must hold as 
much data while being as compact as possible.  I have a 24 bit field in 
which to represent the character of the next node and its offset in the 
trie file; since there's 26 possible characters I can represent about 
645276 values for the location of a child (that is, ((1 << 24) - 25) / 26.

Currently, this value refers to the offset of the child from the start 
of the trie file.  By requiring two-byte alignment for nodes in the 
file, I can support any trie file size up to 1290552 bytes.

It occurs to me that I could order the trie such that children are 
closer to their parents.  If I can guarantee that no child is further 
away than 1290552 bytes, I could cram more data in even though the file 
size grows larger than my "pointer" size.

So how do I sort the nodes this way, that minimizes the largest distance 
between a node and its children?  To make it harder, some children are 
shared - a node can have multiple parents.

Thanks in advance!

-Peter

-- 
Pull out a splinter to reply.

.