Hacker News new | comments | show | ask | jobs | submit login
Compressing Radix Trees Without Too Many Tears (2017) (medium.com)
58 points by noch 9 months ago | hide | past | web | favorite | 7 comments

See also djb’s crit-bit trees, which are a tighter and simpler version of PATRICIA trees - https://cr.yp.to/critbit.html - and agl‘s nice literate code explanation of how they work - https://github.com/agl/critbit/

And my qp tries, which are smaller and faster than crit-bit trees https://dotat.at/prog/qp/

Both critbit and qp tries are wonderful.

I have pure-functional implementations of the central critbit algorithms in OCaml (https://github.com/tonyg/ml-critbit/blob/master/critbit.ml) and Typed Racket (https://github.com/tonyg/racket-critbit/blob/master/critbit....). I was surprised to find the OCaml implementation is competitive speedwise with the built-in Set implementation over strings.

Oh hey, I've used qp-tries in an interpreter for a Forth-like language. They're really elegant IMO. Thanks for publicizing and implementing your discovery!

Always a pleasure to hear about people making good use of them!

Radix trees are often used in routing tables. On Linux, for IPv4, there is an additional level of compression to avoid the cost of many intermediate nodes. I've described the algorithm used on Linux here: https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-lin...

An obvious way to save space that is not mentioned is of course not to have alphabet sized pointer arrays in each node and if the alphabet is big, for example Unicode characters, it is not really an option to begin with. In that case you would use some kind of dictionary to store the pointers to child nodes. You can also dynamically switch between different node implementations depending on the number of child nodes.

Compressing tree data is not trivial. E.g. using per-node heap allocation could take many times the space of the actual data (memory used by the allocator, metainformation, alignment padding, etc.). Using a custom allocator can reduce the memory usage dramatically.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact