Efficient Fully-Compressed Sequence Representations
Preprint
Abstract
We present a data structure that stores a sequence $s[1..n]$ over alphabet $[1..\sigma]$ in $n\Ho(s) + o(n)(\Ho(s){+}1)$ bits, where $\Ho(s)$ is the zero-order entropy of $s$. This structure supports the queries \access, \rank\ and \select, which are fundamental building blocks for many other compressed data structures, in worst-case time $\Oh{\lg\lg\sigma}$ and average time $\Oh{\lg \Ho(s)}$. The worst-case complexity matches the best previous results, yet these had been achieved with data structures using $n\Ho(s)+o(n\lg\sigma)$ bits. On highly compressible sequences the $o(n\lg\sigma)$ bits of the redundancy may be significant compared to the the $n\Ho(s)$ bits that encode the data. Our representation, instead, compresses the redundancy as well. Moreover, our average-case complexity is unprecedented. Our technique is based on partitioning the alphabet into characters of similar frequency. The subsequence corresponding to each group can then be encoded using fast uncompressed representations without harming the overall compression ratios, even in the redundancy. The result also improves upon the best current compressed representations of several other data structures. For example, we achieve $(i)$ compressed redundancy, retaining the best time complexities, for the smallest existing full-text self-indexes; $(ii)$ compressed permutations $\pi$ with times for $\pi()$ and $\pii()$ improved to loglogarithmic; and $(iii)$ the first compressed representation of dynamic collections of disjoint sets. We also point out various applications to inverted indexes, suffix arrays, binary relations, and data compressors. ...
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Optimal lower bounds for rank and select indexesTheoretical Computer Science, 2007
- Rank and select revisited and extendedTheoretical Computer Science, 2007
- A simple storage scheme for strings achieving entropy boundsTheoretical Computer Science, 2007
- Efficient, Low-Complexity Image Coding With a Set-Partitioning Embedded Block CoderIEEE Transactions on Circuits and Systems for Video Technology, 2004
- New text indexing functionalities of the compressed suffix arraysJournal of Algorithms, 2003
- Digital Video: An Introduction to MPEG-2Journal of Electronic Imaging, 1998
- On the implementation of minimum redundancy prefix codesIEEE Transactions on Communications, 1997
- Managing Gigabytes: Compressing and Indexing Documents and ImagesIEEE Transactions on Information Theory, 1995
- Sorting Shuffled Monotone SequencesInformation and Computation, 1994
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952