File IntegerCodes.h

↰ Parent directory (ADS/compression)

The codes of the integers of chapter 11 of the notes: self-delimiting binary codewords for a sequence of positive integers, short for the small ones, written one after the other on a stream of bits [see File BitStream.h] or of bytes.

Definition (ADS/compression/IntegerCodes.h)

Detailed Description

Each code is optimal, by Shannon, for the distribution :math:` P[ x ] = 2^{-| c( x ) |} , and the choice among them is the choice of the distribution of the data (e.g., the d-gaps of the lists of an inverted index, dGaps()). With :math: B( x ) ` the binary code of x, of :math:` | B( x ) | = 1 + lfloor log_2 x rfloor ` bits:

  • the unary code :math:` U( x ) = 0^{x-1} 1 , x bits, optimal for :math: 2^{-x} ` (Fact 11.1);

  • Elias’ :math:` gamma( x ) = 0^{| B( x ) | - 1} B( x ) , :math: 2 lfloor log_2 x rfloor + 1 ` bits, optimal for :math:` 1 / ( 2 x^2 ) ` (Fact 11.3);

  • Elias’ :math:` delta( x ) = gamma( | B( x ) | ) B( x ) , :math: 1 + 2 lfloor log_2 | B( x ) | rfloor + | B( x ) | ` bits, :math:` 1 + o( 1 ) ` times the binary code (Fact 11.4); the notes keep the leading 1 of :math:` B( x ) `, which Elias drops since the length tells it, and so do these functions (one bit more than Elias’ code);

  • Rice’s :math:` R_k( x ) = U( q + 1 ) B_k( r ) , :math: q = lfloor ( x - 1 ) / 2^k rfloor ` and r the remainder in k bits, :math:` q + 1 + k ` bits (Fact 11.5), and Golomb’s code of modulus b, of which Rice’s is the case :math:` b = 2^k , whose remainder is in the truncated binary code ( :math: lfloor log_2 b rfloor ` or :math:` lceil log_2 b rceil ` bits): optimal for the geometric distribution :math:` ( 1 - p )^{x-1} p ` with :math:` b approx ln 2 / p ` (Gallager and van Voorhis);

  • PForDelta, a block of values coded in b bits each after subtracting a base, the values out of :math:` [ base , base + 2^b - 2 ] ` being exceptions marked by the escape :math:` 2^b - 1 ` and written apart in 64 bits (Fact 11.6), with b chosen so that 90% of the values fit; it is decoded with no branch per value, the design of Zukowski, Heman, Nes and Boncz, whose exceptions are linked in place of the escapes, and of the later OptPFD of Yan, Ding and Suel, which chooses b per block;

  • the variable-byte code, :math:` B( x ) ` in groups of 7 bits from the most significant, each in a byte whose high bit is 1 except in the last, :math:` 8 lceil | B( x ) | / 7 rceil ` bits (Fact 11.7), and the :math:` ( s , c ) -dense codes of Brisaboa, Farina, Navarro and Parama, which split the :math: s + c = 2^w ` values of a word of w bits into s stoppers and c continuers: :math:` s c^{k-1} ` integers take k words, and denseOptimalS() gives the s of the smallest output for given frequencies (the notes recall that the minimum is unique); the variable-byte code has :math:` s = c = 128 ` but wastes the codes of the leading groups of zeros, which the dense code with :math:` s = c = 128 ` does not;

  • the interpolative code of Moffat and Stuiver, for a strictly increasing sequence in :math:` [ low , hi ] : the middle item is written in :math: lceil log_2 ( hi - low - r + l + 1 ) rceil ` bits between the bounds left by the items around it, then the two halves recursively (Algorithm 11.1), no bit at all for a run of consecutive integers; it adapts to the clusters of the sequence and is not prefix-free, which is why it can beat Huffman’s code, optimal only among the static prefix-free codes, at the price of a slow, recursive decoding.

The Elias-Fano code of section 11.6, which can be searched in place, is in File EliasFano.h. signedToNatural() maps an integer of any sign to a natural number as the notes do (x to 2x, -x to 2x + 1), so that the codes of the positive integers apply to it.

Each code writes its bits with the most significant first, so that the stream equals the codeword on paper ( :math:` gamma( 9 ) = 0001001 , :math: R_4( 83 ) = 0000010010 ), and has a function of its length, the formula of the notes, which the encoder ensures. The decoders read a word at a time [see :ref:`file_ADS_succinct_BitStream.h]; the fast decoders of the literature (e.g., the tables of the unary parts, or the SIMD decoding of the variable-byte code by Lemire and Boytsov) are refinements of these.

The contracts [see File Contract.h]: the integers are positive where the code needs it (unary, gamma, delta, Rice, Golomb), the parameters are in range ( :math:` 0 le k < 64 , :math: b ge 1 , :math: s , c ge 1 ), the interpolative code gets a strictly increasing sequence in :math: [ low , hi ] `, and each encoder ensures that it wrote as many bits as its length function says; decode( encode( x ) ) == x is the audit of PForDelta. The functions are defined in IntegerCodes.tpp.

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

  1. Elias, Universal codeword sets and representations of the integers, IEEE Transactions on Information Theory 21(2), 194-203, 1975, doi:10.1109/TIT.1975.1055349

    1. Golomb, Run-length encodings, IEEE Transactions on Information Theory 12(3), 399-401, 1966, doi:10.1109/TIT.1966.1053907

    1. Gallager, D. C. van Voorhis, Optimal source codes for geometrically distributed integer alphabets, IEEE Transactions on Information Theory 21(2), 228-230, 1975, doi:10.1109/TIT.1975.1055357

    1. Rice, Some practical universal noiseless coding techniques, JPL Publication 79-22, Jet Propulsion Laboratory, 1979

  1. Zukowski, S. Heman, N. Nes, P. Boncz, Super-scalar RAM-CPU cache compression, Proc. 22nd ICDE, 59, 2006, doi:10.1109/ICDE.2006.150

  1. Yan, S. Ding, T. Suel, Inverted index compression and query processing with optimized document ordering, Proc. 18th WWW, 401-410, 2009, doi:10.1145/1526709.1526764

    1. Brisaboa, A. Farina, G. Navarro, J. R. Parama, Lightweight natural language text compression, Information Retrieval 10(1), 1-33, 2007, doi:10.1007/s10791-006-9001-9

  1. Moffat, L. Stuiver, Binary interpolative coding for effective index compression, Information Retrieval 3(1), 25-47, 2000, doi:10.1023/A:1013002601898

  1. Lemire, L. Boytsov, Decoding billions of integers per second through vectorization, Software: Practice and Experience 45(1), 1-29, 2015, doi:10.1002/spe.2203

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions