DACs: Bringing direct access to variable-length codes

We present a new variable-length encoding scheme for sequences of integers, Directly Addressable Codes (DACs), which enables direct access to any element of the encoded sequence without the need of any sampling method. Our proposal is a kind of implicit data structure that introduces synchronism in the encoded sequence without using asymptotically any extra space. We show some experiments demonstrating that the technique is not only simple, but also competitive in time and space with existing solutions in several applications, such as the representation of LCP arrays or high-order entropy-compressed sequences.

► We present Directly Addressable Codes (DACs). ► DACs are a new variable-length encoding scheme for sequences of integers. ► DACs enable fast direct access to any element of the encoded sequence. ► DACs are always faster, and almost always smaller, than alternative encodings.