A simplified variant of tabled asymmetric numeral systems with a smaller look-up table | Distributed and Parallel Databases Skip to main content
Springer Nature Link
Log in

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

  • Published:
Distributed and Parallel Databases Aims and scope Submit manuscript

Abstract

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

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Notes

  1. http://www.data-compression.info/Corpora/CalgaryCorpus/.

References

  1. Bokka, V., Nakano, K.: Optimal algorithms for the multiple query problem on reconfigurable meshes, with applications. IEEE Trans. Parallel Distrib. Syst. 12(9), 875–887 (2001)

    Article  Google Scholar 

  2. Brunelle, N., Robins, G.: Compression-aware algorithms for massive datasets. In: Proceedings of the 2015 Data Compression Conference, pp. 441–441 (2015)

  3. Chandra, A., Chakrabarty, K.: System-on-a-chip test-data compression and decompression architectures based on golomb codes. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 20(3), 355–368 (2001)

    Article  Google Scholar 

  4. Chen, D., Chiang, Y.: Alphabet partitioning techniques for semiadaptive huffman coding of large alphabets. IEEE Trans. Commun. 55(3), 436–443 (2007)

    Article  Google Scholar 

  5. Cho, Y., Pearlman, W.A.: Hierarchical dynamic range coding of wavelet subbands for fast and efficient image decompression. IEEE Trans. Image Process. 16(8), 2005–2015 (2007)

    Article  MathSciNet  Google Scholar 

  6. Conrad, K.J., Wilson, P.R.: Grammatical ziv-lempel compression: achieving ppm-class text compression ratios with lz-class decompression speed. In: Proceedings of the 2016 Data Compression Conference (DCC), pp. 586–586 (2016)

  7. Ding, J., Chen, H.: Adaptive golomb code for joint geometrically distributed data and its application in image coding. IEEE Trans. Circuits Syst. Video Technol. 23(4), 661–670 (2013)

    Article  Google Scholar 

  8. Dong, L., Lu, D.: Parallel algorithm of visualization of reservoir numerical simulation based on pebi grids. In: Proceedings of the 2011 Fourth International Symposium on Parallel Architectures, Algorithms and Programming, pp. 302–305 (2011)

  9. Dubé, D., Yokoo, H.: Fast construction of almost optimal symbol distributions for asymmetric numeral systems. In: Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), pp. 1682–1686 (2019)

  10. Duda, J.: Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv:1311.2540 (2013)

  11. Duda, J., Tahboub, K.: The use of asymmetric numeral systems as an accurate replacement for huffman coding. In: Proceedings of the 2015 Picture Coding Symposium (PCS), pp. 65–69 (2015)

  12. Duda, J., Niemiec, M.: Lightweight compression with encryption based on asymmetric numeral systems (2016). arXiv:1612.04662

  13. Giesen, F.: Interleaved entropy coders. arXiv preprint arXiv:1402.3392 (2014)

  14. Goyal, M., Tatwawadi, K.: Deepzip: Lossless data compression using recurrent neural networks. In: Proceedings of the 2019 Data Compression Conference (DCC), pp. 575–575 (2019)

  15. Hashemian, R.: Memory efficient and high-speed search Huffman coding. IEEE Trans. Commun. 43(10), 2576–2581 (1995). https://doi.org/10.1109/26.469442

    Article  MATH  Google Scholar 

  16. Hashempour, H., Lombardi, F.: Application of arithmetic coding to compression of vlsi test data. IEEE Trans. Comput. 54(9), 1166–1177 (2005)

    Article  Google Scholar 

  17. Hayashi, T., Nakano, K.: Optimal parallel algorithms for finding proximate points, with applications. IEEE Trans. Parallel Distrib. Syst. 9(12), 1153–1166 (1998)

    Article  Google Scholar 

  18. Hertz, D., Azenkot, Y.: Memory/speed tradeoffs for look-up table decoding of systematic linear block codes. IEEE Trans. Commun. 38(1), 109–111 (1990)

    Article  MathSciNet  Google Scholar 

  19. Huang, B., Sriraja, Y.: Improvement of burst error correction using a look-up table with low density parity check coding for compressed ultraspectral sounder data. In: Proceedings of the 2006 8th International Conference Advanced Communication Technology, vol. 2, pp. 1172–1176 (2006)

  20. Jas, A., Ghosh-Dastidar, J.: An efficient test vector compression scheme using selective huffman coding. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 22(6), 797–806 (2003). https://doi.org/10.1109/TCAD.2003.811452

    Article  Google Scholar 

  21. Konstantinov, F., Gryzov, G.: The use of asymmetric numeral systems entropy encoding in video compression. In: Proceedings of the International Conference on Distributed Computer and Communication Networks, pp. 125–139. Springer (2019)

  22. Ma, C., Liu, D.: Convolutional neural network-based arithmetic coding for hevc intra-predicted residues. IEEE Trans. Circuits Syst. Video Technol. 30(7), 1901–1916 (2020)

    Google Scholar 

  23. Muscedere, R., Dimitrov, V.: Efficient techniques for binary-to-multidigit multidimensional logarithmic number system conversion using range-addressable look-up tables. IEEE Trans. Comput. 54(3), 257–271 (2005)

    Article  Google Scholar 

  24. Najmabadi, S.M., Wang, Z.: High throughput hardware architectures for asymmetric numeral systems entropy coding. In: Proceedings of the 2015 9th international symposium on image and signal processing and analysis (ISPA), pp. 256–259. IEEE (2015)

  25. Najmabadi, S.M., Tungal, H.S.: Hardware-based architecture for asymmetric numeral systems entropy decoder. In: Proceedings of the 2017 Conference on Design and Architectures for Signal and Image Processing (DASIP), pp. 1–6. IEEE (2017)

  26. Najmabadi, S.M., Tran, T.H.: An architecture for asymmetric numeral systems entropy decoder—a comparison with a canonical huffman decoder. J. Signal Process. Syst. 91(7), 805–817 (2019)

    Article  Google Scholar 

  27. Nakagawa, M., Man, D.: A simple parallel convex hulls algorithm for sorted points and the performance evaluation on the multicore processors. In: Proceedings of the 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, pp. 506–511 (2009)

  28. Ruan, X., Katti, R.: Using improved shannon-fano-elias codes for data encryption. In: Proceedings of the 2006 IEEE International Symposium on Information Theory, pp. 1249–1252 (2006)

  29. Sun, X., Zhang, W.: A parallel two-level hybrid method for tridiagonal systems and its application to fast poisson solvers. IEEE Trans. Parallel Distrib. Syst. 15(2), 97–106 (2004)

    Article  Google Scholar 

  30. Teng, C.Y.: Compression of smil documents. In: Proceedings of the DCC 2000. Data Compression Conference, p. 572 (2000)

  31. Wei, R.: Differential encoding by a look-up table for quadrature-amplitude modulation. IEEE Trans. Commun. 59(1), 84–94 (2011)

    Article  Google Scholar 

  32. Weißenberger, A., Schmidt, B.: Massively parallel ans decoding on gpus. In: Proceedings of the 48th International Conference on Parallel Processing, pp. 1–10 (2019)

  33. Witten, I.H., Bell, T.C.: The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression. IEEE Trans. Inf. Theory 37(4), 1085–1094 (1991)

    Article  Google Scholar 

  34. Yokoo, H.: On the stationary distribution of asymmetric numeral systems. In: Proceedings of the 2016 International Symposium on Information Theory and Its Applications (ISITA), pp. 631–635. IEEE (2016)

Download references

Funding

Funding was provided by the Natural Science Foundation of Anhui Province (Grant No. BJ2100330001).

Author information

Authors and Affiliations

  1. University of Science and Technology of China, Hefei, China

    Na Wang, Chao Wang & Sian-Jheng Lin

Authors
  1. Na Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chao Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sian-Jheng Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Na Wang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wang, N., Wang, C. & Lin, SJ. A simplified variant of tabled asymmetric numeral systems with a smaller look-up table. Distrib Parallel Databases 39, 711–732 (2021). https://doi.org/10.1007/s10619-020-07316-9

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10619-020-07316-9

Keywords

Search

Navigation