Compressed Representations of Permutations, and Applications
Jérémy Barbay and Gonzalo Navarro
We explore various techniques to compress a permutation p over
n integers, taking advantage of ordered subsequences in p,
while supporting its application p(i) and the application of its
inverse p^(-1)(i) in small time.
Our compression schemes yield several interesting byproducts, in many
cases matching, improving or extending the best existing results on
applications such as the encoding
of a permutation in order to support iterated applications p^k(i) of
it, of integer functions, and of inverted lists and suffix arrays.