Range coding is a type of entropy coding widely used in modern data compressors. However, its compression and decompression processes involve multiple range adjustments, and the bitstream can only be read sequentially during decoding, resulting in quite high latency. In addition, existing input-interleaved fast implementations demand additional computational and memory overhead for the post-compression byte-swizzling step, which leads to increased compression time. In this paper, we propose a parallel range coding method that employs multiple encoders and decoders without the need for the swizzling step. It is achieved by designing a sliding window mechanism to interleave the outputs of multiple encoders, so that the positions of each encoder's outputs in the bitstream follow a predictable and ordered pattern. This design reduces encoding latency and enables each decoder to pre-locate the data it needs to read during decoding, thereby improving both compression and decompression performance. The simulation results indicate that compared to the traditional range coding and existing multi-way input-interleaved implementations (which require a large amount of memory overhead during encoding), our proposal achieves an average throughput increase of 48.03%/81.08% and 74.01%/9.14% during encoding/decoding, respectively, with almost the same compression ratios.

Reversible data hiding (RDH) has been extensively studied in the field of multimedia security. Embedding capacity is an important metric for RDH performance evaluation. However, the embedding capacity of existing methods for independent and identically distributed (i.i.d.) gray-scale signals is still not good enough. In this paper, we propose a high-capacity RDH code construction method that employs asymmetric numeral systems (ANS) coding as the underlying coding framework. Based on the proposed framework, two RDH methods are presented. First, we propose a static RDH method that takes the constant host probability mass function (PMF) as input parameters and offers high embedding performance. Then, we give a dynamic RDH method that can eliminate the need for transmitting the host PMF in advance by designing a reversible dynamic probability calculator. The simulation results on discrete normally distributed signals demonstrate that the performance of the proposed static method is very close to the expected rate-distortion bound, and the proposed dynamic method can achieve satisfactory embedding capacity without prior knowledge of host PMF at the cost of slightly sacrificing steganographic data quality. Moreover, the experimental results on gray-scale images show that the proposed static method provides higher peak signal-to-noise ratio (PSNR) values and larger embedding capacities than some state-of-the-art methods, e.g., the embedding capacity of image Lena is as high as 3.571 bits per pixel.

Canonical binary AIFV coding [1] contains two trees T0and T1. We show the method to compress T0, and the method to compress T1is with a similar way. We provide a new method to store the number of leaves, master nodes and complete internal nodes in each layer and compactly encode the string of numbers according to the specific property between the nodes.

The Asymmetrical Numeral Systems (ANS) coding has received significant attention in well-integrated compression systems. One particularly insightful technique that has emerged is the interleaved ANS coder (IAC), which substantially enhances the throughput by using multiple encoders and decoders. However, IAC has a limitation that even a single bit error in the compressed bitstream may diffuse across multiple decoders, resulting in many symbols to be incorrectly decoded. In this paper, we propose a parallel method to mitigate the diffusion for a class of error patterns, by limiting the errors to affect only a single decoder. The simulation results show that compared with IAC, our proposal can reduce the average number of incorrectly decoded symbols by about 50% while maintaining comparable encoding and decoding throughput.

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%.

A universal scheme is proposed for the lossless compression of two-dimensional tables and matrices. Instead of standard row- or column-based compression, we propose to sort each column first and record both the sorted table and the corresponding permutation table of the sorting permutations. These two tables are then separately compressed. In this new scheme, both intra- and inter-column correlations can be efficiently captured, giving rise to improved compression ratio in particular when both column-wise and row-wise dependencies cooccur. This scheme reduces the problem of the compression of an arbitrary two-dimensional table to that of a ‘permutation table’ together with a ‘sorted table’, where the former is only dependent on the table dimension and the latter can be effectively compressed column-by-column using predictive methods. Based on this scheme, a new algorithm is proposed, SortComp (sort-and-compress). For correlated columns, we give an estimation of the asymptotic bit rate of the algorithm and compare it to column-oriented compression schemes. Numerical experiments on real-life csv datasets validate the advantages of SortComp compared to existing row- and column-oriented compression algorithms.

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.