|
|||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |
See:
Description
Class Summary | |
---|---|
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. |
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. |
ShiftAddXorSignedStringMap | Deprecated. Moved to the DSI utilities. |
TwoSizesLongBigList | A compressed big list of longs; small elements and large elements are stored separately, using two different, optimally chosen bit sizes. |
Succinct data structures for collections.
This package provides implementations of some succinct techniques for the storage of static lists. The main ingrediant is the
Elias–Fano representation of monotone sequences. For monotone sequences, such as file pointers,
an EliasFanoMonotoneLongBigList
is the obvious choise. 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.
|
|||||||||
PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES |