Optimal Dynamic Sequence Representations
Authors:
- Gonzalo NavarroGNGonzalo Navarro
- Yakov NekrichYNYakov Nekrich
- 1 January 2014
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 43 (5) , 1781-1806
Abstract
We describe a data structure that supports access, rank, and select queries, as well as symbol insertions and deletions, on a string S[1,n] over alphabet $[1..\sigma]$ in time $O(\log n/\log\log n)$, which is optimal even on binary sequences and in the amortized sense. Our time is worst case for the queries and amortized for the updates. This complexity is better than the best previous ones by a $\Theta(1+\log\sigma/\log\log n)$ factor. We also design a variant where times are worst case, yet rank and updates take $O(\log n)$ time. Our structure uses $nH_0(S)+o(n\log\sigma) + O(\sigma\log n)$ bits, where $H_0(S)$ is the zero-order entropy of $S$. Finally, we pursue various extensions and applications of the result.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Compact binary relation representations with rich functionalityInformation and Computation, 2013
- Efficient Fully-Compressed Sequence RepresentationsAlgorithmica, 2012
- Implicit indexing of natural language text by reorganizing bytecodesInformation Retrieval Journal, 2012
- Succinct indexes for strings, binary relations and multilabeled treesACM Transactions on Algorithms, 2011
- Compressing and indexing labeled trees, with applicationsJournal of the ACM, 2009
- Adaptive searching in succinctly encoded binary relations and tree-structured documentsTheoretical Computer Science, 2007
- Compressed representations of sequences and full-text indexesACM Transactions on Algorithms, 2007
- Compressed indexes for dynamic text collectionsACM Transactions on Algorithms, 2007
- Fractional cascading: II. ApplicationsAlgorithmica, 1986
- Fractional cascading: I. A data structuring techniqueAlgorithmica, 1986