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

https://hal.inria.fr/inria-00358018
Contributor : Publications Loria <>
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

barbay_new.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

128

Files downloads

468