File PackedBits.h

↰ Parent directory (ADS/compression)

The bits of the compressors of this folder, packed in bytes, since their input and their output are streams of bytes: a PackedBitWriter appends bits, the first one in the most significant bit of the first byte, and a PackedBitReader reads them back in the same order.

Definition (ADS/compression/PackedBits.h)

Detailed Description

A code of k bits goes in with one call, the most significant bit first, so that the value of the bits read so far is the integer whose binary digits they are; this is the order in which the canonical code of Huffman [see File CanonicalHuffman.h] and the arithmetic coder [see File ArithmeticCoding.h] read their input, one bit at a time, and in which a dyadic fraction :math:` v / 2^k ` is written as :math:` 0.b_1 b_2 ldots b_k . The last byte is padded with zeros, and a PackedBitReader gives zeros past the end of its bytes, which is what the decoder of the arithmetic code expects; the decoders that must not read past the end check it with position(). The streams of bits on words of 64 bits, with the fields read a word at a time, are those of the integer codes [see :ref:`file_ADS_succinct_BitStream.h].

The contracts [see File Contract.h]: a code has at most 64 bits. The operations are defined in PackedBits.tpp.

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

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes