On compressing permutations and adaptive sorting

DOI10.1016/J.TCS.2013.10.019zbMATH Open1358.68079arXiv1108.4408OpenAlexW2147996100MaRDI QIDQ391981FDOQ391981

Gonzalo Navarro, Jérémy Barbay

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Previous compact representations of permutations have focused on adding a small index on top of the plain data $<pi(1),pi(2),\mathrm{...}pi(n)>$, in order to efficiently support the application of the inverse or the iterated permutation. In this paper we initiate the study of techniques that exploit the compressibility of the data itself, while retaining efficient computation of $pi(i)$ and its inverse. In particular, we focus on exploiting {em runs}, which are subsets (contiguous or not) of the domain where the permutation is monotonic. Several variants of those types of runs arise in real applications such as inverted indexes and suffix arrays. Furthermore, our improved results on compressed data structures for permutations also yield better adaptive sorting algorithms.

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

zbMATH Keywords

permutationscompressionsuccinct data structuresadaptive sorting

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• Stronger Lempel-Ziv based compressed text indexing
• Compressed representations of sequences and full-text indexes
• Alphabet Partitioning for Compressed Rank/Select and Applications
• Optimal Succinctness for Range Minimum Queries
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Succinct indexes for strings, binary relations and multilabeled trees
• Self-adjusting binary search trees
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• A Method for the Construction of Minimum-Redundancy Codes
• On computing the length of longest increasing subsequences
• An almost optimal algorithm for unbounded searching
• Approximate string matching with compressed indexes
• Rank/select operations on large alphabets
• COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
• Rank and select revisited and extended
• Optimal lower bounds for rank and select indexes
• On the Redundancy of Succinct Data Structures
• Sorting shuffled monotone sequences
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• Approximating minimum cocolorings.
• Partitioning permutations into increasing and decreasing subsequences
• From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures
• Measures of Presortedness and Optimal Sorting Algorithms
• Sorting and Searching in Multisets
• Succinct representations of permutations and functions
• New text indexing functionalities of the compressed suffix arrays
• Untangled monotonic chains and adaptive range search
• Bounding the inefficiency of length-restricted prefix codes

Cited In (10)

• Grammar compressed sequences with rank/select support
• Efficient fully-compressed sequence representations
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems
• Fast Sorting and Pattern-Avoiding Permutations
• Wavelet trees for all
• Smooth Heaps and a Dual View of Self-Adjusting Data Structures
• Title not available (Why is that?)

This page was built for publication: On compressing permutations and adaptive sorting

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