Asymmetric Encoding-Decoding Schemes for Lossless Data Compression PubID: pubid: 0000–0000 © 2023 IEEE
Hirosuke Yamamoto · 2026
Read Asymmetric Encoding-Decoding Schemes for Lossless Data Compression PubID: pubid: 0000–0000 © 2023 IEEE by Hirosuke Yamamoto (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-10991.txt.
Introduction
Sebastiano Grazzi, Sifan Liu, Gareth O. Roberts, and Jun Yang introduce a sampling algorithm based on Sub-Cauchy Projection. Markov chain Monte Carlo methods draw samples from complex probability distributions. Their method maps Euclidean space onto a spherical cap of a hypersphere. The cap is the complement of what they call, in homage to Pink Floyd, the dark side of the moon.
The projection generalizes stereographic projection, a classic map from sphere to plane. Mapping hard targets onto a bounded cap can tame heavy tails that slow samplers down. Their title promises an escape from that dark side: regions a chain rarely visits. The work serves statisticians whose posteriors stretch into awkward, heavy-tailed shapes.
Catalog record
| CREATOR | Hirosuke Yamamoto |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 88 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-10991
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymmetric Encoding-Decoding Schemes for Lossless Data Compression PubID: pubid: 0000–0000 © 2023 IEEE Hirosuke Yamamoto Abstract This paper proposes a new lossless data compression coding scheme named an asymmetric encoding-decoding scheme (AEDS), which can be considered as a generalization of tANS (tabled variant of asymmetric numeral systems). In the AEDS, a data sequence 𝒔 = s 1 s 2 ⋯ s n \bm{s}=s_{1}s_{2}\cdots s_{n} is encoded in backward order s t , t = n , ⋯ , 2 , 1 s_{t},t=n,\cdots,2,1 , while 𝒔 \bm{s} is decoded in forward order s t , t = 1 , 2 , ⋯ , n s_{t},t=1,2,\cdots,n in the same way as the tANS. But, the code class of the AEDS is much broader than that of the tANS. We show for i.i.d. sources that an AEDS with 2 states (resp. 5 states) can attain a shorter average code length than the Huffman code if a child of the root in the Huffman code tree has a probability weight larger than 0.61803 (resp. 0.56984). Furthermore, we derive several upper bounds on the average code length of the AEDS, which also hold for the tANS, and we show that the average code length of the optimal AEDS and tANS with N N states converges to the source entropy with speed O ( 1 / N ) O(1/N) as N N increases. I Introduction The most well-known and commonly used noiseless data compression codes are the Huffman code [ 3 ] and the arithmetic code [ 4 , 5 , 6 ] . However, new codes that are superior to these codes have been proposed recently. The AIFV (almost instantaneous fixed-to-variable length) code [ 7 , 8 , 9 , 10 ] can attain a better compression rate than the Huffman code by using multiple coding trees and allowing a little decoding delay. Furthermore, the arithmetic code can be replaced with the ANS (asymmetric numeral systems) proposed by Duda [ 11 , 12 , 13 , 14 , 15 , 16 ] . In conventional data compression coding such as Huffman coding and arithmetic coding, a data sequence \bm{s}=s_{1}s_{2}\cdots s_{n} is encoded and decoded in the same order in the way of s_{t},t=1,2,\cdots,n . On the other hand, in the ANS, \bm{s} is encoded in backward order s_{t},t=n,\cdots,2,1 , while \bm{s} is decoded in forward order s_{t},t=1,2,\cdots,n . This backward-order encoding allows the ANS to encode and decode data sequences using a single integer variable although an interval of [0,1) (or integers) and its division are used in the encoding and decoding of the arithmetic code. Because of this feature, the ANS can achieve almost the same compression rate as the arithmetic code with less arithmetic operations than the arithmetic code, and the ANS is used in many practical systems [ 16 ] . Especially, the tANS (tabled variant of ANS) [ 11 , 12 , 13 , 14 , 15 , 16 ] has the advantage of being able to encode and decode data sequences at high speed by using a lookup table instead of arithmetic operations. Although there have been little detailed information-theoretical analyses on the ANS, the coding rate has been evaluated information-theoretically for each variant of the ANS in [ 20 ] recently. In this paper, we propose an asymmetric encoding-decoding scheme (AEDS) that uses backward-order encoding and forward-order decoding, as in the ANS, but does not use arithmetic operations such as Huffman coding. The AEDS can be considered as a generalization of the tANS, but the code class of the AEDS is much broader than that of the tANS. In Section II, we introduce the AEDS as a generalization of the tANS. In Section III, we demonstrate that an AEDS can be easily constructed using an arbitrary code tree, and an AEDS with 2 states (resp. 5 states) based on the Huffman code tree can attain a shorter average code length than the Huffman code if a child of the root in the Huffman code tree has a probability weight larger than 0.61803 (resp. 0.56984). We also show that when the AEDS is applied to sources with uniform distributions, an AEDS based on a non-Huffman code tree can attain a shorter average code length than the AEDS based on the Huffman code tree. In Section IV, we consider a restricted AEDS called a state-divided AEDS (sAEDS), and we derive several upper bounds of the average code length, which also hold for the tANS in addition to the sAEDS. Finally in Section V, we treat the case such that the number N of states used in sAEDS is large, and we show that the average code length of the optimal AEDS and tANS converges to the source entropy with speed O(1/N) as N increases. All theorems and lemmas shown in Sections III–V are proved in Appendixes -B – -I . In order to construct an AEDS, the phased-in code 1 1 1 The phased-in code is the Huffman code for a uniformly distributed source over a finite alphabet. But, the phased-in code is also used for sources with non-uniform or unknown probability distributions. Refer [ 22 ] [ 23 ] . The phased-in code is also called the CBT (complete binary tree) code. is often used in this paper. Hence, the average code length of the phased-in code is evaluated in Appendix -A . In this paper, \lg a means \log_{2}a , \lfloor a\rfloor (resp. \lceil a\rceil ) is the greatest integer less than (resp. the least integer larger than) or equal to a , and |\mathcal{A}| represents the cardinality of a discrete set \mathcal{A} . II AEDS generalized from tANS II-A tANS We first introduce tANS (tabled variant of ANS) [ 15 , 16 ] . Let \mathcal{S} be a finite discrete alphabet and p=\{p(s)\,|\,s\in\mathcal{S}\} be a memoryless source probability distribution. In the encoding and decoding of the tANS, the following sets are used. • \mathcal{X}=\{N,N+1,\cdots,2N-1\} , where N is a positive integer, is the set of internal states with |\mathcal{X}|=N . • \mathcal{X}_{s} is a subset of \mathcal{X} corresponding to s\in\mathcal{S} such that \mathcal{X}_{s}\cap\mathcal{X}_{s^{\prime}}=\emptyset if s\neq s^{\prime} and \mathcal{X}=\bigcup_{s\in\mathcal{S}}\mathcal{X}_{s} . Letting N_{s}=|\mathcal{X}_{s}| , we have N=\sum_{s\in\mathcal{S}}N_{s} . • \mathcal{Y}_{s}=\{N_{s},N_{s}+1,\cdots,2N_{s}-1\} is another set corresponding to s\in\mathcal{S} with N_{s}=|\mathcal{Y}_{s}| . Usually, N and N_{s} are selected so that p(s)\approx N_{s}/N for each s\in\mathcal{S} . Since \mathcal{X}_{s} and \mathcal{Y}_{s} have the same size N_{s} , we can have one-to-one correspondence between \mathcal{X}_{s} and \mathcal{Y}_{s} , and hence, between (s,y)\in\mathcal{S}\times\mathcal{Y}_{s} and x\in\mathcal{X}_{s}\subset\mathcal{X} . We represent this correspondence by two functions x=C[s,y] and (s,y)=D[x] , and we assume that these functions C and D are given 2 2 2 How to construct \mathcal{X}_{s},s\in\mathcal{S} and functions C and D are given in e.g., [ 15 , 16 , 17 , 18 , 19 ] . . In the tANS, an i.i.d. data sequence \bm{s}=s_{1}s_{2}\cdots s_{n} , s_{t}\in\mathcal{S} is encoded in backward order of s_{t} , t=n,n-1,\cdots,2,1 and is decoded in forward order of s_{t} , t=1,2,\cdots,n in the following way when N=2^{k} for an integer k . Encoding procedure of tANS 1. Set a data sequence \bm{s}=s_{1}s_{2}\cdots s_{n} , and select x_{n}\in\mathcal{X} arbitrarily. 2. Repeat ( 1 )–( 4 ) in backward order, starting