Data structure which is efficient to both store in memory and query
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.
Suppose that formula_1 is the information-theoretical optimal number of bits needed to store some data. A representation of this data is called:
For example, a data structure that uses formula_5 bits of storage is compact, formula_6 bits is succinct, formula_7 bits is also succinct, and formula_8 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, formula_9-ary trees and multisets, as well as suffix trees and arrays. The basic problem is to store a subset formula_10 of a universe formula_11, usually represented as a bit array formula_12 where formula_13 iff formula_14 An indexable dictionary supports the usual methods on dictionaries (queries, and insertions/deletions in the dynamic case) as well as the following operations:
for formula_17.
In other words, formula_18 returns the number of elements equal to formula_19 up to position formula_20 while formula_21 returns the position of the formula_22-th occurrence of formula_23.
There is a simple representation which uses formula_24 bits of storage space (the original bit array and an formula_25 auxiliary structure) and supports rank and select in constant time. It uses an idea similar to that for range-minimum queries; there are a constant number of recursions before stopping at a subproblem of a limited size. The bit array formula_26 is partitioned into "large blocks" of size formula_27 bits and "small blocks" of size formula_28 bits. For each large block, the rank of its first bit is stored in a separate table formula_29; each such entry takes formula_30 bits for a total of formula_31 bits of storage. Within a large block, another directory formula_32 stores the rank of each of the formula_33 small blocks it contains. The difference here is that it only needs formula_34 bits for each entry, since only the differences from the rank of the first bit in the containing large block need to be stored. Thus, this table takes a total of formula_35 bits. A lookup table formula_36 can then be used that stores the answer to every possible rank query on a bit string of length formula_37 for formula_38; this requires formula_39 bits of storage space. Thus, since each of these auxiliary tables take formula_25 space, this data structure supports rank queries in formula_41 time and formula_24 bits of space.
To answer a query for formula_43 in constant time, a constant time algorithm computes:
In practice, the lookup table formula_36 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; however, this takes formula_46 time in the worst case. A more complicated structure using formula_47 bits of additional storage can be used to support select in constant time. In practice, many of these solutions have hidden constants in the formula_48 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.
The formula_24 space approach can be improved by noting that there are formula_50 distinct formula_51-subsets of formula_52 (or binary strings of length formula_53 with exactly formula_51 1’s), and thus formula_55 is an information theoretic lower bound on the number of bits needed to store formula_26. There is a succinct (static) dictionary which attains this bound, namely using formula_57 space. This structure can be extended to support rank and select queries and takes formula_58 space. Correct rank queries in this structure are however limited to elements contained in the set, analogous to how minimal perfect hashing functions work. This bound can be reduced to a space/time tradeoff by reducing the storage space of the dictionary to formula_59 with queries taking formula_60 time.
It is also possible to construct a indexible dictionary supporting rank (but not select) that uses fewer than formula_61 bits. Such a dictionary is called a "monotone minimal perfect hash function", and can be implemented using as few as formula_62 bits.
Succinct hash tables.
A succinct hash table, also known as a "succinct unordered dictionary," is a data structure that stores formula_51 keys from a universe formula_64 using space formula_65 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. In the case where formula_66, their solution uses space formula_67 bits. Subsequently, it was shown that this space bound could be improved to formula_68 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. In the case where formula_66, their solution uses space formula_70 bits, and supports "worst-case" constant-time queries. This bound was subsequently improved to formula_71 bits, and then to formula_72 bits. Whereas the first two solutions support worst-case constant-time queries, the final one supports constant expected-time queries. The final solution also requires access to a lookup table of size formula_73, but this lookup table is independent of the set of elements being stored.
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 "k"th item. An alternative is to place the items in order with a delimiter (e.g., null-terminated string). This uses a delimiter instead of a length, and is substantially slower, since the entire sequence must be scanned for delimiters. Both of these are space-efficient. An alternative approach is out-of-band separation: the items can simply be placed one after another, with no delimiters. Item bounds can then be stored as a sequence of length, or better, offsets into this sequence. Alternatively, a separate binary string consisting of 1s in the positions where an item begins, and 0s everywhere else is encoded along with it. Given this string, the formula_74 function can quickly determine where each item begins, given its index. This is "compact" but not "succinct," as it takes 2"Z" space, which is O("Z").
Another example is the representation of a binary tree: an arbitrary binary tree on formula_53 nodes can be represented in formula_76 bits while supporting a variety of operations on any node, which includes finding its parent, its left and right child, and returning the size of its subtree, each in constant time. The number of different binary trees on formula_53 nodes is formula_78formula_79. For large formula_53, this is about formula_81; thus we need at least about formula_82 bits to encode it. A succinct binary tree therefore would occupy only formula_83 bits per node.