Compressed Data Structures for Dynamic Sequences

DOI10.1007/978-3-662-48350-3_74MaRDI QIDQ3452849zbMATH OpenOpenAlexFDO

Authors J. Ian Munro, Yakov Nekrich

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Abstract: We consider the problem of storing a dynamic string $S$ over an alphabet $Sigma=,1,ldots,sigma,$ in compressed form. Our representation supports insertions and deletions of symbols and answers three fundamental queries: $mathrmaccess(i,S)$ returns the $i$-th symbol in $S$, $mathrm{rank}_a(i,S)$ counts how many times a symbol $a$ occurs among the first $i$ positions in $S$, and $mathrm{select}_a(i,S)$ finds the position where a symbol $a$ occurs for the $i$-th time. We present the first fully-dynamic data structure for arbitrarily large alphabets that achieves optimal query times for all three operations and supports updates with worst-case time guarantees. Ours is also the first fully-dynamic data structure that needs only $n{H}_k+o(nlogsigma)$ bits, where $H_k$ is the $k$-th order entropy and $n$ is the string length. Moreover our representation supports extraction of a substring $S[i\mathrm{..}i+ell]$ in optimal $O(logn/loglogn+ell/lo{g}_{sigma}n)$ time.

Recommendations

• A general framework for dynamic succinct and compressed data structures
• scientific article; zbMATH DE number 2087558
• A universal algorithm for sequential data compression
• Compressed data structures for range searching
• Efficient fully-compressed sequence representations
• Compressed data structures: Dictionaries and data-aware measures
• Combinatorial compression algorithms for ordered record sequences
• On compressing and indexing repetitive sequences
• Dynamic Compressed Strings with Random Access

Cites work

• A Framework for Dynamizing Succinct Data Structures
• Algorithms and Computation
• Alphabet partitioning for compressed rank/select and applications
• An analysis of the Burrows-Wheeler transform
• Combinatorial Pattern Matching
• Compact representations of ordered sets
• Compressed indexes for dynamic text collections
• Compressed representations of sequences and full-text indexes
• CRAM: compressed random access memory
• Dynamic Compressed Strings with Random Access
• Dynamic Entropy-Compressed Sequences and Full-Text Indexes
• Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts
• Dynamic rank/select structures with applications to run-length encoded texts
• Fully functional static and dynamic succinct trees
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• New lower and upper bounds for representing sequences
• Optimal External Memory Interval Management
• Rank/select operations on large alphabets
• Succinct data structures for searchable partial sums with optimal worst-case performance
• Succinct indexes for strings, binary relations and multilabeled trees

Cited in

(29)

• Compressed depth sequences
• Finding modes with equality comparisons
• A faster implementation of online RLBWT and its application to LZ77 parsing
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Faster online computation of the succinct longest previous factor array
• Space-efficient B trees via load-balancing
• Compressed dynamic range majority and minority data structures
• Compressed data structures: Dictionaries and data-aware measures
• CRAM: compressed random access memory
• scientific article; zbMATH DE number 2185639 (Why is no real title available?)
• Alphabet partitioning for compressed rank/select and applications
• A universal algorithm for sequential data compression
• scientific article; zbMATH DE number 503181 (Why is no real title available?)
• A framework of dynamic data structures for string processing
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Efficient fully-compressed sequence representations
• Dynamic entropy-compressed sequences and full-text indexes
• Succinct dynamic one-dimensional point reporting
• Dynamic Entropy-Compressed Sequences and Full-Text Indexes
• Dynamic Compressed Strings with Random Access
• Automata, Languages and Programming
• Computing and Combinatorics
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• Random access in persistent strings and segment selection
• Breaking a barrier in constructing compact indexes for parameterized pattern matching
• Inverting parameterized Burrows-Wheeler transform
• Space-efficient B trees via load-balancing
• (Worst-case) optimal adaptive dynamic bitvectors
• Rank/select on dynamic compressed sequences and applications

This page was built for publication: Compressed Data Structures for Dynamic Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452849)