DACs: Bringing direct access to variable-length codes

作者:

Highlights:

摘要

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.

论文关键词:Variable length codes,Random access

论文评审过程:Received 20 January 2012, Revised 13 August 2012, Accepted 27 August 2012, Available online 8 October 2012.

论文官网地址:https://doi.org/10.1016/j.ipm.2012.08.003