|
Abstract |
We prove that, given a permutation pi over [1..n] formed of nRuns sorted blocks of sizes given by the vector R=(r_1,...,r_nRuns), there exists a compressed data structure encoding pi in n(1+H(R)) = n+sum_{i=1}^nRuns r_i log_2 (n/r_i) ≤ n(1+ log_2 nRuns) bits while supporting access to the values of pi() and pi^{-1}() in time O(log nRuns / log log n) in the worst case and O(H(R) / log log n) on average, when the argument is uniformly distributed over [1..n]. This data structure can be constructed in time O(n(1+H(R))), which yields an improved adaptive sorting algorithm. Similar results on compressed data structures for permutations and adaptive sorting algorithms are proved for other preorder measures of practical and theoretical interest. |
