Using individual bits seems wasteful. Why not use HashMap-like sparse SmallArrays to increase the branching factor? The Prefix thing looks like it's on its way to being path compression, but it's a bit on the small side.
Why I'm thinking about any of this: I think it would be interesting to attempt path-compressed generalized tries. The process of addressing a key in a generalized trie is very serialization-like. Working in preorder, each step produces a statically known number of bits representing a constructor. The easy thing is to just stick a node there, but the path compression way would say to put together bits until there's a branch (or some limit is reached). If you have any thoughts on that, I'd be very interested in hearing them.
Using individual bits seems wasteful. Why not use
HashMap-like sparseSmallArrays to increase the branching factor? ThePrefixthing looks like it's on its way to being path compression, but it's a bit on the small side.Why I'm thinking about any of this: I think it would be interesting to attempt path-compressed generalized tries. The process of addressing a key in a generalized trie is very serialization-like. Working in preorder, each step produces a statically known number of bits representing a constructor. The easy thing is to just stick a node there, but the path compression way would say to put together bits until there's a branch (or some limit is reached). If you have any thoughts on that, I'd be very interested in hearing them.