Directly Addressable Codes (DACs)

Directly Addressable Codes (DACs) consist in a variable-length encoding scheme for integers that enables direct access to any element of the encoded sequence and obtains compact spaces.

The original idea was published in SPIRE'09. More details can be found in Susana Ladra's PhD thesis. There is also a journal article, published in IPM, which contains all the results from the thesis.

In this page we provide two versions of the source code for DACs. They are implemented in C. Both of them create the representation for a sequence of integers and support fast direct access to any element. One of them obtains the most compact space we can reach, while the other limits the number of levels to a maximum number given by the user (this may use more space and be faster).

  • DACs, optimization with no further restrictions: source code.
  • DACs, optimization limiting the number of levels to use: source code.

The folder src contains the source code for DACs. We also include a testing program to show how to use them.

Acknowledgements

If you use this source code, please quote the journal article as follows:

@ARTICLE{BLNipm13,
    TITLE = "{DACs}: Bringing Direct Access to Variable-Length Codes",
    AUTHOR = "N. Brisaboa and S. Ladra and G. Navarro",
    JOURNAL = "Information Processing and Management (IPM)",
    VOLUME = 49,
    NUMBER = 1,
    PAGES = "392--404",
    YEAR = 2013
}

About us

We are two researchers from the University of A Coruña (Spain) and one from the University of Chile (Chile).

This work was supported in part by Ministerio de Educación y Ciencia [TIN2006-15071-C03-03], Ministerio de Ciencia e Innovación (PGE and FEDER) [TIN2009-14560-C03-02 and CDTI CEN-20091048], Xunta de Galicia (Feder) [2010/17], and Fondecyt [1-080019,1-110066].