View publication
| Title | Compressed Representations of Permutations, and Applications |
| Authors | Jérémy Barbay, Gonzalo Navarro |
| Publication date | 2009 |
| 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. |
| Pages | 111-122 |
| Conference name | International Symposium on Theoretical Aspects of Computer Science |
| Publisher | IBFI Schloss Dagstuhl (Wadern, Germany) |
| Reference URL |
|