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.