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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.111-122, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00358018
Contributeur : Publications Loria <>
Soumis le : lundi 2 février 2009 - 15:43:46
Dernière modification le : mercredi 8 novembre 2017 - 09:18:07
Document(s) archivé(s) le : mardi 8 juin 2010 - 21:50:11

Fichiers

barbay_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Collections

Citation

Jérémy Barbay, Gonzalo Navarro. Compressed Representations of Permutations, and Applications. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.111-122, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00358018〉

Partager

Métriques

Consultations de la notice

104

Téléchargements de fichiers

208