Compressed Representations of Permutations, and Applications

Details Compressed Representations of Permutations, and Applications Compressed Representations of Permutations, and Applications

2009-02-06

arxiv.org/abs/0902.1038v1

STACS 2009 (2009) 111-122

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Compressed Representations of Permutations, and Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compressed Representations of Permutations, and Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed Representations of Permutations, and Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-251529