Entropy coding is a widely used technique for lossless data compression. The entropy coding schemes supporting the direct access capability on the encoded stream have been investigated in recent years. However, all prior schemes require auxiliary space to support the direct access ability. This paper proposes a rearranging method for prefix codes to support a certain level of direct access to the encoded stream without requiring additional data space. Then, an efficient decoding algorithm is proposed based on lookup tables. The simulation results show that when the encoded stream does not allow additional space, the number of bits per access read of the proposed method is above two orders of magnitude less than the conventional method. In contrast, the alternative solution consumes at least one more bit per symbol on average than the proposed method to support direct access. This indicates that the proposed scheme can achieve a good trade-off between space usage and access performance. In addition, if a small amount of additional storage space is allowed (it is approximately 0.057% in the simulation), the number of bits per access read in our proposal can be significantly reduced by 90%.

The codebook is important for canonical Huffman coding, which needs to contain the number of leaves in each layer of the canonical Huffman tree and the corresponding symbols. Specifically, as two conventional methods in [1], [2], only the number of leaves in each level of the canonical Huffman tree is needed to store. However, we provide a new method to store the number of internal nodes in each layer and compactly encode the string of numbers according to the specific property between the internal nodes.

In the conventional range asymmetric numeral systems (rANS), state$x$becomes larger after encoding a symbol$s$. In contrast, the proposed scheme directly outputs an$n$-bit digit$cdf_{s}+x\ (\text{mod}\ f_{s})$for symbol$s$, and decrease$x$via$x\leftarrow\lfloor x/f_{s}\rfloor$, where$2^{n}$denotes the denominator of the quantized frequency distribution,$f_{s}$and$cdf_{s}= \sum\nolimits_{i=0}^{s-1}f_{i}$represent the frequency of symbol$s$and the cumulative frequency counts, respectively. Therefore,$x$will become too small after encoding several symbols. To solve this issue, our proposal forces the state$x$always at a specific interval$I= [2^{T-vn}, 2^{T})$, and$I_{s}:=\left[f_{s}\times 2^{T-vn}, 2^{T}\right)$indicates the interval corresponding to symbol$s$, where$T, v\in \mathbb{N}$. The specific algorithm can be implemented based on the deque. Precisely, for a symbol$s$to be encoded, if the current$x$is within$I_{s}$, we encode it to an$n$-bit digit$cdf_{s}+x\ (\text{mod}\ f_{s})$and push the digit to deque. Otherwise, we first pop data from the deque to enlarge$x$before encoding. Finally, the remaining data in the deque is the desired encoded bit sequence.