Package it.unimi.dsi.sux4j.util
Succinct data structures for collections.
This package provides implementations of some succinct techniques for the storage of static
lists. The main ingredient is the Elias–Fano representation of monotone sequences. For
monotone sequences, such as file pointers, an
EliasFanoMonotoneLongBigList
is the obvious choice. For general
sequences, you can either use an EliasFanoPrefixSumLongBigList
,
which stores the sequence using its prefix sums, or an
EliasFanoLongBigList
. The former is faster and provides also
prefix sums, but the latter provides a better compression ratio if the values stored are skewed
towards small values. EliasFanoIndexedMonotoneLongBigList
provides contentbased addressing methods.

Class Summary Class Description EliasFanoIndexedMonotoneLongBigList An extension ofEliasFanoMonotoneLongBigList
providing indexing (i.e., contentbased addressing).EliasFanoLongBigList A compressed big list of longs; each element occupies a number of bits bounded by one plus its bit length plus the logarithm of the average bit length of an element.EliasFanoMonotoneLongBigList An implementation of Elias–Fano's representation of monotone sequences; an element occupies a number of bits bounded by two plus the logarithm of the average gap.EliasFanoMonotoneLongBigList16 An implementation of Elias–Fano's representation of monotone sequences with number of lower bits set fixed to 16.EliasFanoPrefixSumLongBigList A compressed big list of longs providing prefix sums; an element occupies a number of bits bounded by two plus the logarithm of the average value.SignedFunctionStringMap A string map based on a signed function.TwoSizesLongBigList A compressed big list of longs; small elements and large elements are stored separately, using two different, optimally chosen bit sizes.ZFastTrie<T> A zfast trie, that is, a predecessor/successor data structure using low linear (in the number of keys) additional space and answering to the query string x in time x/w + log(max{x, x^{}, x^{+}}) with high probability, where w is the machine word size, and x^{}/x^{+} are the predecessor/successor of x in the currently stored set, respectively.ZFastTrie.ExitData<U> ZFastTrie.Handle2NodeMap<U> A linearprobing hash map that compares keys using signatures as a first try.ZFastTrie.InternalNode<U> A internal node.ZFastTrie.Leaf<U> An external node, a.k.a. leaf.ZFastTrie.Node<U> A node of the trie.ZFastTrie.ParexData<U>