A simplified variant of tabled asymmetric numeral systems with a smaller look-up table

• Published in: Distributed and parallel databases : an international journal 2021-09, Vol.39 (3), p.711-732
• Main Authors: Wang, Na, Wang, Chao, Lin, Sian-Jheng
• Format: Article
• Language: English
• Subjects: Algorithms; Asymmetry; Compression ratio; Computer Science; Data management; Data storage; Data Structures; Database Management; Decoding; Information Systems Applications (incl.Internet); Integers; Lookup tables; Memory Structures; Operating Systems; Special Issue on Spatio-Temporal Data Driven Urban Computing
• ISSN: 0926-8782; 1573-7578
• DOI: 10.1007/s10619-020-07316-9

Data storage is an indispensable part of data management system. Asymmetric numeral systems (ANS) is a widely used compression algorithm. A number of implementations, such as range asymmetric numeral systems (rANS) and tabled asymmetric numeral systems (tANS), were proposed. However, rANS requires some costly arithmetic operations (integer additions, multiplications and divisions), and tANS requires large space to store the entire behavior in a look-up table. When the integer addition is allowed, this paper proposes a variant of tANS, that requires much smaller look-up table than the conventional tANS. In addition, a decoding algorithm to decode multiple symbols at once is proposed. The simulation shows that with a slight loss of compression ratio (approximately 0.5 % lower), the proposed method has up to a 25 % ( 60 % ) better throughput than rANS in encoding (decoding).