🔗 Succinct Data Structures

🔗 Computer science

In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations. The concept was originally introduced by Jacobson to encode bit vectors, (unlabeled) trees, and planar graphs. Unlike general lossless data compression algorithms, succinct data structures retain the ability to use them in-place, without decompressing them first. A related notion is that of a compressed data structure, in which the size of the data structure depends upon the particular data being represented.

Suppose that ${\displaystyle Z}$ is the information-theoretical optimal number of bits needed to store some data. A representation of this data is called:

• implicit if it takes ${\displaystyle Z+O(1)}$ bits of space,
• succinct if it takes ${\displaystyle Z+o(Z)}$ bits of space, and
• compact if it takes ${\displaystyle O(Z)}$ bits of space.

For example, a data structure that uses ${\displaystyle 2Z}$ bits of storage is compact, ${\displaystyle Z+{\sqrt {Z}}}$ bits is succinct, ${\displaystyle Z+\lg Z}$ bits is also succinct, and ${\displaystyle Z+3}$ bits is implicit.

Implicit structures are thus usually reduced to storing information using some permutation of the input data; the most well-known example of this is the heap.