Compressed Representations of Permutations, and Applications

Barbay, Jeremy; Navarro, Gonzalo

doi:10.4230/LIPIcs.STACS.2009.1814

Document

Compressed Representations of Permutations, and Applications

Authors Jeremy Barbay, Gonzalo Navarro

Part of: Volume: 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NoDerivs 3.0 Unported license
Publication Date: 2009-02-19

PDF

File

PDF

LIPIcs.STACS.2009.1814.pdf

Filesize: 190 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2009.1814
URN: urn:nbn:de:0030-drops-18148

Subject Classification

Keywords

Compression
Permutations
Succinct data structures
Adaptive sorting

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

We explore various techniques to compress a permutation $\pi$ over $n$ integers, taking advantage of ordered subsequences in $\pi$, while supporting its application $\pi(i)$ and the application of its inverse $\pi^{-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 $\pi^{k}(i)$ of it, of integer functions, and of inverted lists and suffix arrays.

Cite As Get BibTex

Jeremy Barbay and Gonzalo Navarro. Compressed Representations of Permutations, and Applications. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 111-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.STACS.2009.1814

Author Details

Jeremy Barbay

Gonzalo Navarro

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail