document: permutations of the integers @xmath5 = \{1,\ldots , n\}$ ] are a basic building block for the succinct encoding of integer functions  @xcite , strings  @xcite , and binary relations  @xcite , among others . 
   a permutation @xmath0 is trivially representable in @xmath6 bits , which is within @xmath7 bits of the information theory lower bound of @xmath8 bits . and @xmath9=\{1,\ldots , x\}$ ] . ] in many interesting applications , efficient computation of both the permutation @xmath2 and its inverse @xmath3 
   is required . 
   the lower bound of @xmath8 bits yields a lower bound of @xmath10 comparisons to sort such a permutation in the comparison model . yet , a large body of research has been dedicated to finding better sorting algorithms which can take advantage of specificities of each permutation to sort . 
   trivial examples are permutations sorted such as the identity , or containing sorted blocks  @xcite ( e.g. @xmath11 or @xmath12 ) , or containing sorted subsequences  @xcite ( e.g. @xmath13 ) : algorithms performing only @xmath7 comparisons on such permutations , yet still @xmath14 comparisons in the worst case , are achievable and obviously preferable . 
   less trivial examples are classes of permutations whose structure makes them interesting for applications : see mannila s seminal paper  @xcite and estivil - castro and wood s review  @xcite for more details . 
   each sorting algorithm in the comparison model yields an encoding scheme for permutations : it suffices to note the result of each comparison performed to uniquely identify the permutation sorted , and hence to encode it . since an adaptive sorting algorithm performs @xmath15 comparisons on many classes of permutations , each adaptive algorithm yields a _ compression scheme _ for permutations , at the cost of losing a constant factor on some other `` bad '' classes of permutations . 
   we show in section  [ sec : applications ] some examples of applications where only `` easy '' permutations arise . yet 
   such compression schemes do not necessarily support in reasonable time the inverse of the permutation , or even the simple application of the permutation : this is the topic of our study . 
   we describe several encodings of permutations so that on interesting classes of instances the encoding uses @xmath15 bits while supporting the operations @xmath2 and @xmath3 in time @xmath16 . 
   later , we apply our compression schemes to various scenarios , such as the encoding of integer functions , text indexes , and others , yielding original compression schemes for these abstract data types . 
   the _ entropy _ of a sequence of positive integers @xmath17 adding up to @xmath1 is @xmath18 . by convexity of the logarithm , @xmath19 . 
   [ def : entrop ]    [ [ sec : sequences ] ] * succinct encodings of sequences * + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +    let @xmath20 $ ] be a sequence over an alphabet @xmath21 $ ] . 
   this includes bitmaps when @xmath22 ( where , for convenience , the alphabet will be @xmath23 ) . 
   we will make use of succinct representations of @xmath24 that support operations @xmath25 and @xmath26 : @xmath27 gives the number of occurrences of @xmath28 in @xmath29 $ ] and @xmath30 gives the position in @xmath24 of the @xmath31th occurrence of @xmath28 .    for the case 
   @xmath22 , @xmath24 requires @xmath1 bits of space and @xmath25 and @xmath26 can be supported in constant time using @xmath32 bits on top of @xmath24 @xcite . 
   the extra space is more precisely @xmath33 for some parameter @xmath34 , which is chosen to be , say , @xmath35 to achieve the given bounds . in this paper 
   , we will sometimes apply the technique over sequences of length @xmath36 ( @xmath1 will be the length of the permutations ) . 
   still , we will maintain the value of @xmath34 as a function of @xmath1 , not @xmath37 , which ensures that the extra space will be of the form @xmath38 , i.e. , it will tend to zero when divided by @xmath37 as @xmath1 grows , even if @xmath37 stays constant . 
   all of our @xmath39 terms involving several variables in this paper can be interpreted in this strong sense : asymptotic in @xmath1 . 
   thus we will write the above space simply as @xmath40 . 
   raman _ et al . _ 
   @xcite devised a bitmap representation that takes @xmath41 bits , while maintaining the constant time for the operations . here 
   @xmath42 , where @xmath43 is the number of occurrences of symbol @xmath28 in @xmath24 , is the so - called _ zero - order entropy _ of @xmath24 . for the binary case this simplifies to @xmath44 , where @xmath45 is the number of bits set in @xmath24 . 
   grossi _ et al . _ 
   @xcite extended the result to larger alphabets using the so - called _ wavelet tree _ , which decomposes a sequence into several bitmaps . by representing those bitmaps in plain form , 
   one can represent @xmath24 using @xmath46 bits of space , and answer @xmath47 $ ] , as well as @xmath25 and @xmath26 queries on @xmath24 , in time @xmath48 . 
   by , instead , using raman _ 
   s representation for the bitmaps , one achieves @xmath49 bits of space , and the same times . 
   et al . _ 
   @xcite used multiary wavelet trees to maintain the same compressed space , while improving the times for all the operations to @xmath50 . 
   [ [ sec : meas - disord - perm ] ] * measures of disorder in permutations * + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +    various previous studies on the presortedness in sorting considered in particular the following measures of order on an input array to be sorted . among others , 
   mehlhorn  @xcite and guibas  _ et al . _ 
   @xcite considered the number of pairs in the wrong order , knuth  @xcite considered the number of ascending substrings ( runs ) , cook and kim  @xcite , and later mannila  @xcite considered the number of elements which have to be removed to leave a sorted list , mannila  @xcite considered the smallest number of exchanges of arbitrary elements needed to bring the input into ascending order , skiena  @xcite considered the number of encroaching sequences , obtained by distributing the input elements into sorted sequences built by additions to both ends , and levcopoulos and petersson  @xcite considered shuffled upsequences and shuffled monotone sequences . 
   estivil - castro and wood  @xcite list them all and some others . 
   we first introduce a compression method that takes advantage of ( ascending ) runs in the permutation . then we consider a stricter variant of the runs , which allows for further compression in applications when those runs arise , and in particular allows the representation size to be sublinear in @xmath1 . 
   next , we consider a more general type of runs , which need not be contiguous . 
   one of the best known sorting algorithm is merge sort , based on a simple linear procedure to merge two already sorted arrays , resulting in a worst case complexity of @xmath14 . yet , checking in linear time for _ down - step _ positions in the array , where an element is followed by a smaller one , partitions the original arrays into ascending runs which are already sorted . 
   this can speed up the algorithm when the array is partially sorted  @xcite . 
   we use this same observation to encode permutations . 
   a _ down step _ of a permutation @xmath0 over @xmath5 $ ] is a position @xmath51 such that @xmath52 . 
   a _ run _ in a permutation @xmath0 is a maximal range of consecutive positions @xmath53 which does not contain any down step . let @xmath54 be the list of consecutive down steps in @xmath0 . 
   then the number of runs of @xmath0 is noted @xmath55 , and the sequence of the lengths of the runs is noted @xmath56 . 
   for example , permutation @xmath11 contains @xmath57 runs , of lengths @xmath58 . whereas previous analyses  @xcite of adaptive sorting algorithms considered only the number @xmath59 of runs , we refine them to consider the distribution @xmath60 of the sizes of the runs . 
   there is an encoding scheme using at most @xmath61 bits to encode a permutation @xmath0 over @xmath5 $ ] covered by @xmath59 runs of lengths @xmath60 . 
   it supports @xmath2 and @xmath3 in time @xmath62 for any value of @xmath63 $ ] . 
   if @xmath51 is chosen uniformly at random in @xmath5 $ ] then the average time is @xmath64 . 
   [ thm : main ]    the hu - tucker algorithm @xcite ( see also knuth @xcite ) produces in @xmath65 time a prefix - free code from a sequence of frequencies @xmath66 adding up to @xmath1 , so that ( 1 ) the @xmath51-th lexicographically smallest code is that for frequency @xmath67 , and ( 2 ) 
   if @xmath68 is the bit length of the code assigned to the @xmath51-th sequence element , then @xmath69 is minimal and moreover @xmath70 ( * ? ? ? 
   * , eq .  ( 27 ) ) . 
   we first determine @xmath60 in @xmath7 time , and then apply the hu - tucker algorithm to @xmath60 . 
   we arrange the set of codes produced in a binary trie ( equivalent to a huffman tree @xcite ) , where each leaf corresponds to a run and points to its two endpoints in @xmath0 . because of property ( 1 ) , reading the leaves left - to - right yields the runs also in left - to - right order . 
   now we convert this trie into a wavelet - tree - like structure @xcite without altering its shape , as follows . starting from the root , first process 
   recursively each child . for the leaves 
   do nothing . 
   once both children of an internal node have been processed , the invariant is that they point to the contiguous area in @xmath0 covering all their leaves , and that this area of @xmath0 has already been sorted . 
   now we merge the areas of the two children in time proportional to the new area created ( which , again , is contiguous in @xmath0 because of property ( 1 ) ) . as we do the merging , each time we take an element from the left child we append a 0 bit to a bitmap we create for the node , and a 1 bit when we take an element from the right list . 
   when we finish , we have the following facts : ( 1 ) @xmath0 has been sorted , ( 2 ) the time for sorting has been @xmath71 plus the total number of bits appended to all bitmaps , ( 3 ) each of the @xmath67 elements of leaf @xmath51 ( at depth @xmath68 ) has been merged @xmath68 times , contributing @xmath68 bits to the bitmaps of its ancestors , and thus the total number of bits is @xmath72 . 
   therefore , the total number of bits in the hu - tucker - shaped wavelet tree is at most @xmath73 . to this 
   we must add the @xmath74 bits of the tree pointers . 
   we preprocess all the bitmaps for @xmath25 and @xmath26 queries so as to spend @xmath75 extra bits (  [ sec : sequences ] ) .    to compute @xmath3 we start at offset @xmath51 at the root bitmap @xmath76 , with position @xmath77 , and bitmap size @xmath78 . 
   if @xmath79 = 0 $ ] we go down to the left child with @xmath80 and @xmath81 . 
   otherwise we go down to the right child with @xmath82 , @xmath83 , and @xmath84 . when we reach a leaf , the answer is @xmath85 .    to compute @xmath2 
   we do the reverse process , but we must first determine the leaf @xmath86 and offset @xmath31 within @xmath86 corresponding to position @xmath51 : we start at the root bitmap @xmath76 , with bitmap size @xmath78 and position @xmath87 . if @xmath88 we go down to the left child with @xmath89 . 
   otherwise we go down to the right child with @xmath90 and @xmath91 . 
   we eventually reach leaf @xmath86 , and the offset within @xmath86 is @xmath31 . 
   we now start an upward traversal using the nodes that are already in the recursion stack ( those will be limited to @xmath92 soon ) . 
   if @xmath86 is a left child of its parent @xmath93 , then we set @xmath94 , else we set @xmath95 , where @xmath76 is the bitmap of @xmath93 
   . then we set @xmath96 until reaching the root , where @xmath97 .    in both cases 
   the time is @xmath98 , where @xmath37 is the depth of the leaf arrived at . 
   if @xmath51 is chosen uniformly at random in @xmath5 $ ] , then the average cost is @xmath99 . 
   however , the worst case can be @xmath100 in a fully skewed tree . 
   we can ensure @xmath101 in the worst case while maintaining the average case by slightly rebalancing the hu - tucker tree : if there exist nodes at depth @xmath102 , we rebalance their subtrees , so as to guarantee maximum depth @xmath103 . 
   this affects only marginally the size of the structure . 
   a node at depth @xmath37 can not add up to a frequency higher than @xmath104 ( see next paragraph ) . 
   added over all the possible @xmath59 nodes we have a total frequency of @xmath105 . 
   therefore , by rebalancing those subtrees we add at most @xmath106 bits . 
   this is @xmath107 if @xmath108 , and otherwise the cost was @xmath109 anyway . for the same reasons the average time stays @xmath64 as it increases at most by @xmath110 . 
   the bound on the frequency at depth @xmath37 is proved as follows . 
   consider the node @xmath86 at depth @xmath37 , and its grandparent @xmath93 . 
   then the uncle of @xmath86 can not have smaller frequency than @xmath86 . 
   otherwise we could improve the already optimal hu - tucker tree by executing either a single ( if @xmath86 is left - left or right - right grandchild of @xmath93 ) or double ( if @xmath86 is left - right or right - left grandchild of @xmath93 ) avl - like rotation that decreases the depth of @xmath86 by 1 and increases that of the uncle of @xmath86 by 1 . 
   thus the overall frequency at least doubles whenever we go up two nodes from @xmath86 , and this holds recursively . 
   thus the weight of @xmath86 is at most @xmath111 . 
   the general result of the theorem can be simplified when the distribution @xmath60 is not particularly favorable . 
   there is an encoding scheme using at most @xmath112 bits to encode a permutation @xmath0 over @xmath5 $ ] with a set of @xmath59 runs . 
   it supports @xmath2 and @xmath3 in time @xmath62 for any value of @xmath63 $ ] . 
   [ cor : mainbal ]    as a corollary , we obtain a new proof of a well - known result on adaptive algorithms telling that one can sort in time @xmath113 
   @xcite , now refined to consider the entropy of the partition and not only its size . 
   we can sort an array of length @xmath1 covered by @xmath59 runs of lengths @xmath60 in time @xmath114 , which is worst - case optimal in the comparison model among all permutations with @xmath59 runs of lengths @xmath60 so that @xmath115 . [ cor : mainsort ] 
   some classes of permutations can be covered by a small number of runs of a stricter type . 
   we present an encoding scheme which uses @xmath107 bits for encoding the permutations from those classes , and still @xmath116 bits for all others . 
   a _ strict run _ in a permutation @xmath0 is a maximal range of positions satisfying @xmath117 . 
   the _ head _ of such run is its first position . 
   the number of strict runs of @xmath0 is noted @xmath118 , and the sequence of the lengths of the strict runs is noted @xmath119 . 
   we will call @xmath120 the sequence of run lengths of the sequence formed by the strict run heads of @xmath0 .    for example 
   , permutation @xmath12 contains @xmath121 strict runs , of lengths @xmath122 . 
   the run heads are @xmath123 , and contain 2 runs , of lengths @xmath124 . 
   instead , @xmath11 contains @xmath125 strict runs , all of length 1 . 
   there is an encoding scheme using at most @xmath126 bits to encode a permutation @xmath0 over @xmath5 $ ] covered by @xmath118 strict runs and by @xmath127 runs , and with @xmath120 being the @xmath59 run lengths in the permutation of strict run heads . 
   it supports @xmath2 and @xmath3 in time @xmath62 for any value of @xmath63 $ ] . 
   if @xmath51 is chosen uniformly at random in @xmath5 $ ] then the average time is @xmath128 . 
   [ thm : strict ]    we first set up a bitmap @xmath129 marking with a 1 bit the beginning of the strict runs . 
   set up a second bitmap @xmath130 such that @xmath131 = r[\pi^{-1}(i)]$ ] . 
   now we create a new permutation @xmath132 of @xmath133 $ ] which collapses the strict runs of @xmath0 , @xmath134 . 
   all this takes @xmath7 time and the bitmaps take @xmath135 bits using raman _ 
   s technique , where @xmath25 and @xmath26 are solved in constant time (  [ sec : sequences ] ) . 
   now build the structure of thm . 
   [ thm : main ] for @xmath132 
   . the number of down steps in @xmath0 is the same as for the sequence of strict run heads in @xmath0 , and in turn the same as the down steps in @xmath132 . 
   so the number of runs in @xmath132 is also @xmath59 and their lengths are @xmath120 . 
   thus we get at most @xmath136 bits to encode @xmath132 , and can compute @xmath132 and its inverse in @xmath137 worst case and @xmath128 average time .    to compute @xmath2 , we find @xmath138 and then compute @xmath139 . 
   the final answer is @xmath140 . to compute @xmath3 
   , we find @xmath141 and then compute @xmath142 . 
   the final answer is @xmath143 . 
   this adds only constant time on top of that to compute @xmath132 and its inverse . 
   once again , we might simplify the results when the distribution @xmath120 is not particularly favorable , and we also obtain interesting algorithmic results on sorting . 
   there is an encoding scheme using at most @xmath144 bits to encode a permutation @xmath0 over @xmath5 $ ] covered by @xmath118 strict runs and by @xmath127 runs . 
   it supports @xmath2 and @xmath3 in time @xmath62 for any value of @xmath63 $ ] . 
   [ cor : strictbal ]    we can sort a permutation of @xmath5 $ ] , covered by @xmath118 strict runs and by @xmath59 runs , and @xmath120 being the run lengths of the strict run heads , in time @xmath145 , which is worst - case optimal , in the comparison model , among all permutations sharing these @xmath59 , @xmath118 , and @xmath120 values , such that @xmath146 . 
   [ cor : strictsort ]      levcopoulos and petersson  @xcite introduced the more sophisticated concept of partitions formed by interleaved runs , such as _ shuffled upsequences _ 
   we discuss here the advantage of considering permutations formed by shuffling a small number of runs . 
   a decomposition of a permutation @xmath0 over @xmath5 $ ] into _ shuffled upsequences _ is a set of , not necessarily consecutive , subsequences of increasing numbers that have to be removed from @xmath0 in order to reduce it to the empty sequence . 
   the minimum number of shuffled upsequences in such a decomposition of @xmath0 is noted @xmath147 , and the sequence of the lengths of the involved shuffled upsequences , in arbitrary order , is noted @xmath148 . 
   for example , permutation @xmath13 contains @xmath149 shuffled upsequences of lengths @xmath150 , but @xmath151 runs , all of length 2 . 
   whereas the decomposition of a permutation into runs or strict runs can be computed in linear time , the decomposition into shuffled upsequences requires a bit more time . 
   fredman  @xcite gave an algorithm to compute the size of an optimal partition , claiming a worst case complexity of @xmath14 . 
   in fact his algorithm is adaptive and takes @xmath152 time . 
   we give here a variant of his algorithm which computes the partition itself within the same complexity , and we achieve even better time on favorable sequences @xmath148 . 
   [ lem : partitioninsus ] given a permutation @xmath0 over @xmath5 $ ] covered by @xmath147 shuffled upsequences of lengths @xmath148 , there is an algorithm finding such a partition in time @xmath153 . 
   initialize a sequence @xmath154 , and a splay tree @xmath155 @xcite with the node @xmath156 , ordered by the rightmost value of the sequence contained by each node . for each further element @xmath2 , 
   search for the sequence with the maximum ending point smaller than @xmath2 . if any , add @xmath2 to this sequence , otherwise create a new sequence and add it to @xmath155 . 
   fredman  @xcite already proved that this algorithm computes an optimal partition . 
   the adaptive complexity results from the mere observation that the splay tree ( a simple sorted array in fredman s proof ) contains at most @xmath147 elements , and that the node corresponding to a subsequence is accessed once per element in it . 
   hence the total access time is @xmath153 ( * ? ? ? 
   * thm .  2 ) . 
   the complete description of the permutation requires to encode the computation of both the partitioning algorithm and the sorting one , and this time the encoding cost of partitioning is as important as that of merging .    [ 
   thm : sus ] there is an encoding scheme using at most @xmath157 bits to encode a permutation @xmath0 over @xmath5 $ ] covered by @xmath147 shuffled upsequences of lengths @xmath148 . 
   it supports the operations @xmath2 and @xmath3 in time @xmath158 for any value of @xmath63 $ ] . 
   if @xmath51 is chosen uniformly at random in @xmath5 $ ] the average time is @xmath159 . 
   partition the permutation @xmath0 into @xmath147 shuffled upsequences using lemma  [ lem : partitioninsus ] , resulting in a string @xmath24 of length @xmath1 over alphabet @xmath160 $ ] which indicates for each element of the permutation @xmath0 the label of the upsequence it belongs to . encode @xmath24 with a wavelet tree using raman  _ et al . 
   _ s compression for the bitmaps , so as to achieve @xmath161 bits of space and support retrieval of any @xmath47 $ ] , as well as symbol @xmath25 and @xmath26 on @xmath24 , in time @xmath158 (  [ sec : sequences ] ) . store also an array @xmath162 $ ] so that @xmath163 $ ] is the accumulated length of all the upsequences with label less than @xmath37 . 
   array @xmath164 requires @xmath165 bits . 
   finally , consider the permutation @xmath132 formed by the upsequences taken in label order : @xmath132 has at most @xmath147 runs and hence can be encoded using @xmath166 bits using thm . 
   [ thm : main ] , as @xmath148 in @xmath0 corresponds to @xmath60 in @xmath132 . 
   this supports @xmath167 and @xmath168 in time @xmath158 . 
   now @xmath169+rank_{s[i]}(s , i))$ ] can be computed in time @xmath158 . 
   similarly , @xmath170)$ ] , where @xmath37 is such that @xmath163 < ( \pi')^{-1}(i ) \le a[\ell+1]$ ] , can also be computed in @xmath158 time . 
   thus the whole structure uses @xmath171 bits and supports @xmath2 and @xmath3 in time @xmath158 . 
   the obstacles to achieve the claimed average time are the operations on the wavelet tree of @xmath24 , and the binary search in @xmath164 . 
   the former can be reduced to @xmath172 by using the improved wavelet tree representation by ferragina _ 
   et al . _ 
   (  [ sec : sequences ] ) . 
   the latter is reduced to constant time by representing @xmath164 with a bitmap @xmath173 $ ] with the bits set at the values @xmath163 + 1 $ ] , so that @xmath163 = select_1(a',\ell)-1 $ ] , and the binary search is replaced by @xmath174 . with raman _ 
   _ s structure (  [ sec : sequences ] ) , @xmath175 needs @xmath176 bits and operates in constant time . 
   again , we might prefer a simplified result when @xmath148 has no interesting distribution , and we also achieve an improved result on sorting , better than the known @xmath152 .    [ cor : susbal ] 
   there is an encoding scheme using at most @xmath177 bits to encode a permutation @xmath0 over @xmath5 $ ] covered by @xmath147 shuffled upsequences . 
   it supports the operations @xmath2 and @xmath3 in time @xmath158 for any value of @xmath63 $ ] . 
   [ cor : sortsus ] we can sort an array of length @xmath1 , covered by @xmath147 shuffled upsequences of lenghts @xmath148 , in time @xmath153 , which is worst - case optimal , in the comparison model , among all permutations decomposable into @xmath147 shuffled upsequences of lenghts @xmath148 such that @xmath178 . 
   consider a full - text inverted index which gives the word positions of any word in a text . 
   this is a popular data structure for natural language text retrieval @xcite , as it permits for example solving phrase queries without accessing the text . for each different text word , 
   an increasing list of its text positions is stored . 
   let @xmath1 be the total number of words in a text collection @xmath179 $ ] and @xmath59 the vocabulary size ( i.e. , number of different words ) . 
   an uncompressed inverted index requires @xmath180 bits . 
   it has been shown @xcite that , by @xmath181-encoding the differences between consecutive entries in the inverted lists , the total space reduces to @xmath182 , where @xmath183 is the zero - order entropy of the text if seen as a sequence of words (  [ sec : sequences ] ) . 
   we note that the empirical law by heaps @xcite , well accepted in information retrieval , establishes that @xmath59 is small : @xmath184 for some constant @xmath185 depending on the text type .    several successful methods to compress natural language text 
   take words as symbols and use zero - order encoding , and thus the size they can achieve is lower bounded by @xmath186 @xcite . 
   if we add the differentially encoded inverted index in order to be able of searching the compressed text , the total space is at least @xmath187 . 
   now , the concatenation of the @xmath59 inverted lists can be seen as a permutation of @xmath5 $ ] with @xmath59 runs , and therefore thm . 
   [ thm : main ] lets us encode it in @xmath188 bits . within the same space we can add @xmath59 numbers telling where the runs begin , in an array 
   @xmath189 $ ] . 
   now , in order to retrieve the list of the @xmath51-th word , we simply obtain @xmath190 ) , \pi(v[i]+1 ) , \ldots , \pi(v[i+1]-1)$ ] , each in @xmath62 time . 
   moreover we can extract any random position from a list , which enables binary - search - based strategies for list intersection @xcite . 
   in addition , we can also obtain a text passage from the ( inverse ) permutation : to find out @xmath191 $ ] , @xmath192 gives its position in the inverted lists , and a binary search on @xmath193 finds the interval @xmath194 
   \le \pi^{-1}(j ) < v[i+1]$ ] , to output that @xmath191 = i$]th word , in @xmath137 time . 
   this result is very interesting , as it constitutes a true word - based _ self - index _ 
   @xcite ( i.e. , a compressed text index that contains the text ) . 
   similar results have been recently obtained with rather different methods @xcite . 
   the cleanest one is to build a wavelet tree over @xmath155 with compression @xcite , which achieves @xmath195 bits of space , and permits obtaining @xmath196 $ ] , as well as extracting the @xmath31th element of the inverted list of the @xmath51th word with @xmath197 , all in time @xmath198 .    yet 
   , one advantage of our approach is that the extraction of @xmath37 consecutive entries @xmath199)$ ] takes @xmath200 time if we do the process for all the entries as a block : start at range @xmath201 $ ] at the root bitmap @xmath76 , with position @xmath77 , and bitmap size @xmath78 . 
   go down to both left and right children : to the left with @xmath201 \leftarrow [ rank_0(b , i),rank_0(b , i')]$ ] , same @xmath202 , and @xmath89 ; to the right with @xmath201 \leftarrow [ rank_1(b , i),rank_1(b , i')]$ ] , @xmath83 , and @xmath91 . 
   stop when the range @xmath201 $ ] becomes empty or when we reach a leaf , in which case report all answers @xmath203 , @xmath204 . by representing the inverted list as @xmath205 
   , we can extract long inverted lists faster than the existing methods . 
   [ cor : invfile ] there exists a representation for a text @xmath179 $ ] of integers in @xmath206 $ ] ( regarded as word identifiers ) , with zero - order entropy @xmath207 , that takes @xmath208 bits of space , and can retrieve the text position of the @xmath31th occurrence of the @xmath51th text word , as well as the value @xmath191 $ ] , in @xmath137 time . 
   it can also retrieve any range of @xmath37 successive occurrences of the @xmath51th text word in time @xmath209 . 
   we could , instead , represent the inverted list as @xmath0 , so as to extract long text passages efficiently , but the wavelet tree representation can achieve the same result . another interesting functionality that both representations share , and which is useful for other list intersection algorithms @xcite , 
   is that to obtain the first entry of a list which is larger than @xmath210 . 
   this is done with @xmath25 and @xmath26 on the wavelet tree representation . in our permutation representation , we can also achieve it in @xmath62 time by finding out the position of a number @xmath210 within a given run . 
   the algorithm is similar to those in thm . 
   [ thm : main ] that descend to a leaf while maintaining the offset within the node , except that the decision on whether to descend left or right depends on the leaf we want to arrive at and not on the bitmap content ( this is actually the algorithm to compute @xmath25 on binary wavelet trees @xcite ) .    finally , we note that our inverted index data structure supports in small time all the operations required to solve conjunctive queries on binary relations . 
   suffix arrays are used to index texts that can not be handled with inverted lists . given a text @xmath179 $ ] of @xmath1 symbols over an alphabet of size @xmath59 , the _ suffix _ array @xmath211 
   $ ] is a permutation of @xmath5 $ ] so that @xmath212,n]$ ] is lexicographically smaller than @xmath213,n]$ ] . as suffix arrays 
   take much space , several compressed data structures have been developed for them @xcite . 
   one of interest for us is the _ compressed suffix array ( csa ) _ of sadakane @xcite . 
   it builds over a permutation @xmath214 of @xmath5 $ ] , which satisfies @xmath215 = ( a[i]~\textrm{mod}~n ) + 1 $ ] ( and thus lets us move virtually one position forward in the text ) @xcite . 
   it turns out that , using just @xmath214 and @xmath74 extra bits , one can @xmath216 _ count _ the number of times a pattern @xmath217 $ ] occurs in @xmath155 using @xmath218 applications of @xmath214 ; @xmath219 _ locate _ any such occurrence using @xmath220 applications of @xmath214 , by spending @xmath221 extra bits of space ; and @xmath222 _ extract _ a text substring @xmath223 $ ] using at most @xmath224 applications of @xmath214 . hence this is another self - index , and its main burden of space is that to represent permutation @xmath214 . 
   sadakane shows that @xmath214 has at most @xmath59 runs , and gives a representation that accesses @xmath225 $ ] in constant time by using @xmath226 bits of space . 
   it was shown later @xcite that the space is actually @xmath227 bits , for any @xmath228 and constant @xmath229 . here 
   @xmath230 is the @xmath231th order empirical entropy of @xmath155 @xcite .    with thm . 
   [ thm : main ] we can encode @xmath214 using @xmath232 bits of space , whose extra terms aside from entropy are better than sadakane s 
   . those extra terms can be very significant in practice . 
   the price is that the time to access @xmath214 is @xmath137 instead of constant . on the other hand , 
   an interesting extra functionality is that to compute @xmath233 , which lets us move ( virtually ) one position backward in @xmath155 . 
   this allows , for example , displaying the text context around an occurrence without having to spend any extra space . 
   still , although interesting , the result is not competitive with recent developments @xcite . 
   an interesting point is that @xmath214 contains @xmath234 strict runs , for any @xmath231 @xcite . 
   therefore , cor . 
   [ cor : strictbal ] lets us represent it using @xmath235 bits of space . for @xmath231 limited as above , 
   this is at most @xmath236 bits , which is similar to the space achieved by another self - index @xcite , yet again it is slightly superseded by its time performance . 
   munro  _ et al . _ 
   @xcite described how to represent a permutation @xmath0 as the concatenation of its cycles , completed by a bitvector of @xmath1 bits coding the lengths of the cycles . 
   as the cycle representation is itself a permutation of @xmath5 $ ] , we can use any of the permutation encodings described in  [ sec : compr - techn ] to encode it , adding the binary vector encoding the lengths of the cycles . 
   it is important to note that , for a specific permutation @xmath0 , the difficulty to compress its cycle encoding @xmath132 is not the same as the difficulty to encode the original permutation @xmath0 .    given a permutation @xmath0 with @xmath28 cycles of lengths @xmath237 , there are several ways to encode it as a permutation @xmath132 , depending on the starting point of each cycle ( @xmath238 } n_i$ ] choices ) and the order of the cycles in the encoding ( @xmath239 choices ) . as a consequence , each permutation @xmath0 with @xmath28 cycles of lengths @xmath237 
   can be encoded by any of the @xmath238 } i\times n_i$ ] corresponding permutations . 
   any of the encodings from theorems  [ thm : main ] , [ thm : strict ] and  [ thm : sus ] can be combined with an additional cost of at most @xmath240 bits to encode a permutation @xmath0 over @xmath5 $ ] composed of @xmath28 cycles of lengths @xmath237 to support the operation @xmath4 for any value of @xmath241 , in time and space function of the order in the permutation encoding of the cycles of @xmath0 . 
   the space `` wasted '' by such a permutation representation of the cycles of @xmath0 is @xmath242 bits . to recover some of this space , 
   one can define a canonical cycle encoding by starting the encoding of each cycle with its smallest value , and by ordering the cycles in order of their starting point . 
   this canonical encoding always starts with a @xmath243 and creates at least one shuffled upsequence of length @xmath28 : it can be compressed as a permutation over @xmath244 $ ] with at least one shuffled upsequence of length @xmath245 through thm  [ thm : sus ] . 
   munro and rao  @xcite extended the results on permutations to arbitrary functions from @xmath5 $ ] to @xmath5 $ ] , and to their iterated application @xmath246 , the function iterated @xmath231 times starting at @xmath51 . 
   their encoding is based on the decomposition of the function into a bijective part , represented as a permutation , and an injective part , represented as a forest of trees whose roots are elements of the permutation : the summary of the concept is that an integer function is just a `` hairy permutation '' . combining the representation of permutations from @xcite with any representation of trees supporting the level - ancestor operator and an iterator of the descendants at a given level yields a representation of an integer function @xmath247 using @xmath248 bits to support @xmath246 in @xmath249 time , for any fixed @xmath250 , integer @xmath241 and @xmath63 $ ] . 
   janssen  _ et al . _ 
   @xcite defined the _ degree entropy _ of an ordered tree @xmath155 with @xmath1 nodes , having @xmath67 nodes with @xmath51 children , as @xmath251 , and proposed a succinct data structure for @xmath155 using @xmath252 bits to encode the tree and support , among others , the level - ancestor operator . 
   obviously , the definition and encoding can be generalized to a forest of @xmath231 trees by simply adding one node whose @xmath231 children are the roots of the @xmath231 trees .    encoding the injective parts of the function using janssen  _ et al . _ 
   @xcite succinct encoding , and the bijective parts of the function using one of our permutation encodings , yields a compressed representation of any integer function which supports its application and the application of its iterated variants in small time . 
   [ cor : fun ] there is a representation of a function @xmath253\rightarrow[n]$ ] that uses @xmath254 bits to support @xmath246 in @xmath255 time , for any integer @xmath231 and for any @xmath63 $ ] , where @xmath155 is the forest representing the injective part of the function , and @xmath59 is the number of runs in the bijective part of the function . 
   bentley and yao  @xcite , when introducing a family of search algorithms adaptive to the position of the element searched ( aka the `` unbounded search '' problem ) , did so through the definition of a family of adaptive codes for unbounded integers , hence proving that the link between algorithms and encodings was not limited to the complexity lower bounds suggested by information theory .    in this paper 
   , we have considered the relation between the difficulty measures of adaptive sorting algorithms and some measures of `` entropy '' for compression techniques on permutations . in particular , we have shown that some concepts originally defined for adaptive sorting algorithms , such as runs and shuffled upsequences , are useful in terms of the compression of permutations ; and conversely , that concepts originally defined for data compression , such as the entropy of the sets of sizes of runs , are a useful addition to the set of difficulty measures that one can consider in the study of adaptive algorithms . 
   it is easy to generalize our results on runs and strict runs to take advantage of permutations which are a mix of up and down runs or strict runs ( e.g. @xmath256 , with only a linear extra computational and/or space cost . 
   the generalization of our results on shuffled upsequences to sms  @xcite , permutations containing mixes of subsequences sorted in increasing and decreasing orders ( e.g. @xmath257 ) is sligthly more problematic , because it is np hard to optimally decompose a permutation into such subsequences  @xcite , but any approximation scheme  @xcite would yield a good encoding . 
   j.  barbay and g.  navarro . 
   compressed representations of permutations , and applications . 
   technical report tr / dcc-2008 - 18 , department of computer science ( dcc ) , university of chile , december 2008 .
summary: we explore various techniques to compress a permutation @xmath0 over @xmath1 integers , taking advantage of ordered subsequences in @xmath0 , while supporting its application @xmath2 and the application of its inverse @xmath3 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 @xmath4 of it , of integer functions , and of inverted lists and suffix arrays . 
   jrmy barbay    gonzalo navarro