HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Compressed Representations of Permutations, and Applications

Abstract : We explore various techniques to compress a permutation π over n integers, taking advantage of ordered subsequences in π, while supporting its application π(i) and the application of its inverse π^−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 π^k (i) of it, of integer functions, and of inverted lists and suffix arrays.
Document type :
Conference papers
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Monday, February 2, 2009 - 3:43:46 PM
Last modification on : Wednesday, May 6, 2020 - 8:18:02 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 9:50:11 PM


Files produced by the author(s)


  • HAL Id : inria-00358018, version 1
  • ARXIV : 0902.1038



Jérémy Barbay, Gonzalo Navarro. Compressed Representations of Permutations, and Applications. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.111-122. ⟨inria-00358018⟩



Record views


Files downloads