Compressed Representations of Permutations, and ApplicationsReportar como inadecuado

Compressed Representations of Permutations, and Applications - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 DCC - Department Of Computer Science

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 π^−1i 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.

Mots-clés : Compression Permutations Succinct Data Structures Adaptive Sorting

Autor: Jérémy Barbay - Gonzalo Navarro -



Documentos relacionados