DACs: Bringing direct access to variable-length codes |
| |
| Authors: | Nieves R Brisaboa Susana Ladra Gonzalo Navarro |
| |
| Institution: | 1. Database Laboratory, University of Coruña, Spain;2. Dept. of Computer Science, University of Chile, Chile |
| |
| Abstract: | 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. |
| |
| Keywords: | Variable length codes Random access |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
