Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > Each node requires three pointers plus the character itself.

> Or, with enough work, you could get away with not using full-sized pointers, 
> perhaps. Indexes into arrays (with said arrays split into chunks if you have 
> trouble finding that much contiguous address space) might work too.

  I suppose that if you limit the size of the data container to 2^24 nodes,
you could use "pointers" of 3 bytes, which would be 9 bytes plus the
character. Alignment usually requires to round that up to 12 bytes. (The
extra space could be used for the end-of-string bit.)

  If you limited the number of nodes to 2^16 then you could use 8 bytes
per node. However, I'm not sure if such a limitation is very practical.

  Of course if you are willing to sacrifice some speed in order to squeeze
space, you could break the word/half-word boundaries, and compact eg. the
three 24-bit pointers and the 8-bit character into a 10-byte node in a
byte array. Or if you are not afraid of bit-fu, something more exotic like
21 bits for the "pointers" (giving a maximum of 2097152 nodes), 8 bits for
the characters and 1 bit for the end-of-string bit, which would result in
9 bytes per node.

-- 
                                                          - Warp

Post a reply to this message