Levente Uzonyi wrote:
> ...
> I tried with our trie and got pretty bad results, though it has no path
> compression yet. It had 27942 selectors and 238065 internal nodes. So 
> even if it were optimized for space, it'd still take 5498440 bytes to 
> store it. Path compression could decrease the number of internal nodes 
> anywhere between 3-10x, but it'd introduce new objects 
> (strings/arrays) which are not present currently, so I doubt it would 
> be possible to create a trie which takes less than 2MB for this 27942 
> selectors.

In my Cuis image, I have 10725 selectors and about 102900 nodes. The 
first implementations I did took between 1.5 and 2.6 Mb for this. Today 
I did path compression, and I managed to do it without creating new 
strings or arrays. This uses 640kb, with about 1/7 node count: 14289 
nodes. Next optimization will be to avoid leave nodes when simple 
(holding just one key/value pair). This will get it down to 469kb. 
Making the node class a compact class, it will use 411kb. I guess it 
could use about 1Mb for your 27942 symbols. I already know how to go 
down to 385 kb, but at the expense of more complicated code, needing to 
migrate between two kinds of nodes, so I think I'll stop at 411 kb.

Cheers,
Juan Vuletich