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, insofar as the size of the stored or encoded data similarly depends upon the specific content of the data itself.

is the information-theoretical optimal number of bits needed to store some data. A representation of this data is called:

• implicit bits of space,

• succinct bits of space, and

• compact bits of space.

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.

Succinct indexable dictionaries

Succinct indexable dictionaries, also called rank/select dictionaries, form the basis of a number of succinct representation techniques, including binary trees-ary trees and multisets, as well as suffix trees and arrays. An indexable dictionary supports the usual methods on dictionaries (queries, and insertions/deletions in the dynamic case) as well as the following operations:

.

.

There is a simple representation auxiliary structure) and supports rank and select in constant time. It uses an idea similar to that for range-minimum queries is partitioned into large blocks bits and small blocks bits. A lookup table bits of space.

in constant time, a constant time algorithm computes:

can be replaced by bitwise operations and smaller tables that can be used to find the number of bits set in the small blocks. This is often beneficial, since succinct data structures find their uses in large data sets, in which case cache misses become much more frequent and the chances of the lookup table being evicted from closer CPU caches becomes higher. Select queries can be easily supported by doing a binary search on the same auxiliary structure used for rank bits of additional storage can be used to support select in constant time. notation which dominate before any asymptotic advantage becomes apparent; implementations using broadword operations and word-aligned blocks often perform better in practice.

Entropy-compressed solutions

space. This structure can be extended to support rank and select space. Correct rank time.

.

bits, so long as rank queries are limited to elements contained in the set. Such a dictionary is called a monotone minimal perfect hash function bits.

Succinct hash tables

A succinct hash table, also known as a succinct unordered dictionary, bits, and while supporting membership queries in constant expected time. If a succinct hash table also supports insertions and deletions in constant expected time, then it is referred to as dynamic, and otherwise it is referred to as static.

The first dynamic succinct hash table was due to Raman and Rao in 2003. bits for any constant number of logarithms and a little after that this bound was also optimal. The latter solution supports all operations in worst-case constant time with high probability.

The first static succinct hash table was due to Pagh in 1999. bits, and supports worst-case bits, bits. Whereas the first two solutions support worst-case constant-time queries, the final one supports constant expected-time queries., but this lookup table is independent of the set of elements being stored. More recently, Hu et al. while supporting worst-case constant-time queries.

Other examples

A string with an arbitrary length (Pascal string) takes Z + log(Z) space, and is thus succinct. If there is a maximum length – which is the case in practice, since 232 = 4 GiB of data is a very long string, and 264 = 16 EiB of data is larger than any string in practice – then a string with a length is also implicit, taking Z + k space, where k is the number of data to represent the maximum length (e.g., 64 bits).

When a sequence of variable-length items (such as strings) needs to be encoded, there are various possibilities. A direct approach is to store a length and an item in each record – these can then be placed one after another. This allows efficient next, but not finding the kth item. An alternative is to place the items in order with a delimiter (e.g., null-terminated string function can quickly determine where each item begins, given its index. This is compact but not succinct, as it takes 2Z space, which is O(Z).

Another example is the representation of a binary tree bits per node.

See also

• Minimal perfect hash function

• Succinct Non-Interactive Arguments of Knowledge

References