File DirectAccessCodes.h

↰ Parent directory (ADS/compression)

The directly addressable codes of Brisaboa, Ladra and Navarro (DACs): a sequence :math:` x_0 , ldots , x_{n-1} ` of integers of variable length in little more than the bits of their binary codes, with access to any item in time proportional to its length rather than to its place, which the codes of the integers [see File IntegerCodes.h] read one after the other do not give.

Definition (ADS/compression/DirectAccessCodes.h)

Detailed Description

The bits of an integer are cut into chunks, the low :math:` b_0 ` bits, the next :math:` b_1 ` and so on; the level :math:` ell ` holds, for each integer that has bits beyond the first :math:` s_ell = b_0 + cdots + b_{ell - 1} , its chunk :math: ell ` in :math:` b_ell ` bits, in an array of fixed width, and a bit telling whether it continues past the level (none on the last level). The integer of place i at a level is at the place :math:` rank_1( i ) ` of the next one, among those that continue [see File RankSelect.h, with no select], so that :math:`[ x_i = sum_{ell} A_ell[ i_ell ] , 2^{s_ell} , quad

i_0 = i , quad i_{ell + 1} = rank_1( B_ell , i_ell ) , ` over the levels that it reaches: O( 1 + the levels of :math:` x_i ` ) time. With :math:` n_k ` the integers of more than k bits, the level of the chunk :math:` [ s , s + b ) ` costs :math:` n_s ( b + 1 ) ` bits (b + 0 on the last), plus 25% of the continuation bits for their ranks (one load and one sideways sum), and the widths :math:` b_0 , b_1 , ldots ` that minimize the sum are found by the dynamic program of the authors over the 64 places of a cut, \([ C( s ) = \min_{s < s' \le 64} \big( n_s ( s' - s ) + [ s' < w ] \, n_s ( 1 + 0.25 ) + C( s' ) \big) , \quad C( w ) = 0 , \` w the bits of the largest integer, in :math:\) O( w^2 ) ` steps on the counts :math:` n_s ; a fixed width b for every level trades bits for fewer levels, i.e., fewer ranks per access; a chunk of 8 or 16 bits is read as its byte or its pair of bytes, one load that stays in its line of the cache. The construction packs the chunks and the continuation bits of a level in order, a field of 64 bits at a time. The chunks of one width are a code with a fixed alphabet, the vbyte of the notes when every :math: b_ell = 7 `, the continuation bits moved to their own vector with rank.

The contracts [see File Contract.h]: the places asked for are in the sequence; the audit of the construction is that access() gives back each item. The functions are defined in DirectAccessCodes.tpp.

    1. Brisaboa, S. Ladra, G. Navarro, DACs: bringing direct access to variable-length codes, Information Processing and Management 49(1), 392-404, 2013, doi:10.1016/j.ipm.2012.08.003

  1. Navarro, Compact Data Structures, Cambridge University Press, 2016, section 3.4.2, doi:10.1017/CBO9781316588284

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes