Efficient fully-compressed sequence representations

DOI10.1007/s00453-012-9726-3zbMath1307.68029OpenAlexW1973228454MaRDI QIDQ472482

Jérémy Barbay, Yakov Nekrich, Gonzalo Navarro, Travis Gagie, Francisco Claude

Publication date: 19 November 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10533/128161

zbMATH Keywords

compact data structurescompressed sequence representationscompressed text indexingentropy-bounded structuresrank and select on sequences

Mathematics Subject Classification ID

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

Related Items

Compressed string dictionary search with edit distance one, Compressed spaced suffix arrays, Lyndon array construction during Burrows-Wheeler inversion, Grammar compressed sequences with rank/select support, Random access in persistent strings and segment selection, Unnamed Item, High-order entropy compressed bit vectors with rank/select, Fast compressed self-indexes with deterministic linear-time construction, Spaces, Trees, and Colors, Range majorities and minorities in arrays, Succinct navigational oracles for families of intersection graphs on a circle, From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures, Fast Compressed Self-Indexes with Deterministic Linear-Time Construction

Uses Software

• WebGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On compressing permutations and adaptive sorting
• Succinct representations of permutations and functions
• A simple storage scheme for strings achieving entropy bounds
• Sorting shuffled monotone sequences
• Approximate string matching with compressed indexes
• Adaptive searching in succinctly encoded binary relations and tree-structured documents
• Rank and select revisited and extended
• Optimal lower bounds for rank and select indexes
• New Lower and Upper Bounds for Representing Sequences
• Compressed representations of sequences and full-text indexes
• Alphabet-Independent Compressed Text Indexing
• Worst-Case Optimal Adaptive Prefix Coding
• Succinct indexes for strings, binary relations and multilabeled trees
• An analysis of the Burrows—Wheeler transform
• Compressing and indexing labeled trees, with applications
• On the Redundancy of Succinct Data Structures
• On the Size of Succinct Indices
• Indexing compressed text
• Compact Rich-Functional Binary Relation Representations
• Extended Compact Web Graph Representations
• Rank/select operations on large alphabets
• Squeezing succinct data structures into entropy bounds
• Optimal Trade-Offs for Succinct String Indexes
• Storing a Compressed Function with Constant Time Access
• Worst-case Analysis of Set Union Algorithms
• New text indexing functionalities of the compressed suffix arrays
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Dynamic entropy-compressed sequences and full-text indexes
• Optimal Dynamic Sequence Representations
• Practical Entropy-Compressed Rank/Select Dictionary
• Statistical Encoding of Succinct Data Structures
• COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
• More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
• An experimental investigation of set intersection algorithms for text searching
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• A Method for the Construction of Minimum-Redundancy Codes