Succinct data structures

Martijn Faassen:

To introduce succinct data structures it’s useful to compare them to compression. You use compression to shrink the size required to represent this data. Compression can be useful to save disk space, or transmit less data over the network, or to save memory. But to do anything useful with compressed data, such as access it or query it, you first need to uncompress it again. Then afterwards if you want to save space, you need to compress it again.

Succinct data structures are different: they store their content in a compact fashion like compression, but the compact form of the data has useful properties. You can still use it!

This is a field that seems to have emerged in computer science relatively recently; many of the important data structures were invented in the last 25 years.


e = get, head

Dive into said