On compressing permutations and adaptive sorting
From MaRDI portal
Publication:391981
DOI10.1016/j.tcs.2013.10.019zbMath1358.68079arXiv1108.4408MaRDI QIDQ391981
Gonzalo Navarro, Jérémy Barbay
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.4408
68P10: Searching and sorting
05A05: Permutations, words, matrices
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68P05: Data structures
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Smooth Heaps and a Dual View of Self-Adjusting Data Structures, Efficient fully-compressed sequence representations, LRM-trees: compressed indices, adaptive sorting, and compressed permutations, Grammar compressed sequences with rank/select support, Wavelet trees for all, Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Succinct representations of permutations and functions
- Untangled monotonic chains and adaptive range search
- On computing the length of longest increasing subsequences
- An almost optimal algorithm for unbounded searching
- Sorting shuffled monotone sequences
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- Approximate string matching with compressed indexes
- LRM-trees: compressed indices, adaptive sorting, and compressed permutations
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Approximating minimum cocolorings.
- Partitioning permutations into increasing and decreasing subsequences
- Stronger Lempel-Ziv based compressed text indexing
- Rank and select revisited and extended
- Optimal lower bounds for rank and select indexes
- From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures
- Compressed representations of sequences and full-text indexes
- Alphabet Partitioning for Compressed Rank/Select and Applications
- Succinct indexes for strings, binary relations and multilabeled trees
- Measures of Presortedness and Optimal Sorting Algorithms
- On the Redundancy of Succinct Data Structures
- Optimal Succinctness for Range Minimum Queries
- Rank/select operations on large alphabets
- Self-adjusting binary search trees
- Sorting and Searching in Multisets
- New text indexing functionalities of the compressed suffix arrays
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
- COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- A Method for the Construction of Minimum-Redundancy Codes
- Bounding the inefficiency of length-restricted prefix codes
