Optimal Dynamic Sequence Representations

DOI10.1137/130908245zbMath1320.68060arXiv1206.6982OpenAlexW2568539266MaRDI QIDQ5173255

Yakov Nekrich, Gonzalo Navarro

Publication date: 9 February 2015

Published in: SIAM Journal on Computing, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1206.6982

zbMATH Keywords

stringssuccinct data structuresrank and select

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Dynamic range majority data structures, Compressed Data Structures for Dynamic Sequences, Unnamed Item, Space-efficient B trees via load-balancing, Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree, Compact binary relation representations with rich functionality, Suffix array and Lyndon factorization of a text, Computing the parameterized Burrows-Wheeler transform online, A faster implementation of online RLBWT and its application to LZ77 parsing, Wavelet trees for all, Space-efficient construction of compressed suffix trees, Efficient fully-compressed sequence representations, A framework for succinct labeled ordinal trees over large alphabets, Efficient dynamic range minimum query, Burrows-Wheeler transform and LCP array construction in constant space, Dynamic relative compression, dynamic partial sums, and substring concatenation, LZ77 computation based on the run-length encoded BWT, Lempel-Ziv factorization powered by space efficient suffix trees, Fully Functional Static and Dynamic Succinct Trees, Dynamic path queries in linear space, Parallel computation of the Burrows Wheeler transform in compact space, Indexing the bijective BWT, Computing the Burrows-Wheeler transform in place and in small space, Succinct dynamic cardinal trees