File BitStream.h

↰ Parent directory (ADS/succinct)

The streams of bits on which the integer codes are written and read [see File IntegerCodes.h]: BitWriter appends bits to a BitVector [see File BitVector.h] and BitReader reads them back from a place that moves forward, both in O( 1 ) time per field of up to 64 bits.

Definition (ADS/succinct/BitStream.h)

Detailed Description

  • write( v , len ) and read( len ) move a field with its least significant bit first, the order of the words, with two shifts;

  • writeBinary( v , len ) and readBinary( len ) move it with its most significant bit first, the order in which the codes are written on paper ( :math:` gamma( 9 ) = 0001001 ), so that the bits of the stream read from the first one are the codewords of the notes; the field is turned around by reverseBits() [see :ref:`file_ADS_combinatorial_Bitwise.h], 5 rounds of masks;

  • writeUnary( q ) writes q zeros and a 1, the unary code :math:` U( q + 1 ) ` of the notes, and readUnary() counts the zeros up to the 1 a word at a time, by the trailing zeros of the word, ruler() [see File Bitwise.h], rather than a bit at a time, in :math:` O( 1 + q / 64 ) ` time.

Writing the codes into words of 64 bits, rather than bytes, is what the fast decoders of the literature do (e.g., the bit streams of the WebGraph framework of Boldi and Vigna and of the succinct libraries): a codeword of up to 64 bits spans at most two words, and the unary part is decoded with one instruction per word.

The contracts [see File Contract.h]: a field has at most 64 bits and its value fits in them, and a reader never reads past the end of its bits. The functions are defined in BitStream.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 11

  1. Boldi, S. Vigna, The WebGraph framework I: compression techniques, Proc. 13th WWW, 595-602, 2004, doi:10.1145/988672.988752

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes