文章基本信息

标题：Compressed Representations of Permutations, and Applications
本地全文：下载
作者：Jeremy Barbay ; Gonzalo Navarro
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2009
卷号：3
页码：111-122
DOI：10.4230/LIPIcs.STACS.2009.1814
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Compression; Permutations; Succinct data structures; Adaptive sorting