Call for Paper - November 2023 Edition
IJCA solicits original research papers for the November 2023 Edition. Last date of manuscript submission is October 20, 2023. Read More

N-ary Huffman Encoding using High-Degree Trees - A Performance Comparison

Print
PDF
 
Download Full Text
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 183 - Number 5
Year of Publication: 2021
Authors:
Ioannis S. Xezonakis, Svoronos Leivadaros
10.5120/ijca2021921315

Ioannis S Xezonakis and Svoronos Leivadaros. N-ary Huffman Encoding using High-Degree Trees - A Performance Comparison. International Journal of Computer Applications 183(5):33-39, May 2021. BibTeX

@article{10.5120/ijca2021921315,
	author = {Ioannis S. Xezonakis and Svoronos Leivadaros},
	title = {N-ary Huffman Encoding using High-Degree Trees - A Performance Comparison},
	journal = {International Journal of Computer Applications},
	issue_date = {May 2021},
	volume = {183},
	number = {5},
	month = {May},
	year = {2021},
	issn = {0975-8887},
	pages = {33-39},
	numpages = {7},
	url = {http://www.ijcaonline.org/archives/volume183/number5/31925-2021921315},
	doi = {10.5120/ijca2021921315},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

In this paper an n-ary Huffman Encoding and Decoding application is implemented, using different degrees of tree structures. The goal is to compare the performance of the algorithm in terms of compression ratio, decompression speed and weighted path length when using higher degree trees, compared to the 2-ary Huffman Code. The Huffman tree degrees compared are 2-ary, 3-ary, 4-ary, 5-ary, 6-ary, 7-ary, 8-ary and 16-mal. The impact that branch prediction has on the performance of the n-ary Huffman Decoding is also presented.

References

  1. Huffman, D. 1952. A Method for the Construction of Minimum-Redundancy Codes. In Proceedings of the I.R.E. 40 (9), 1098–1101.
  2. Suri, P. R., and Goel, M. 2008. Ternary Tree & a Coding Technique. International Journal of Computer Science and Network Security 8 (10), 102–107.
  3. Suri, P. R., and Goel, M., Ternary Tree and Memory - Efficient Huffman Decoding Algorithm. 2011. International Journal of Computer Science Issues 8 (1), 483–489.
  4. Suri, P. R., and Goel, M. 2009. Ternary Tree & FGK Huffman Coding Technique. International Journal of Computer Science and Network Security 9 (1), 316–324.
  5. Hashemian, R. 1995. Memory Efficient and High-Speed Search Huffman Coding. IEEE Trans. on Communications 43(10), 2576–2581.
  6. Habib, A., and Rahman, M. S. 2017. Balancing Decoding Speed and Memory Usage for Huffman Codes Using Quaternary Tree. Applied Informatics 4 (1), 1–15.
  7. Habib, Α., Islam, M. J., and Rahman, M. S. 2018. Huffman Based Code Generation Algorithms: Data Compression Perspectives. Journal of Computer Science 14 (12), 1599–1610.
  8. Alakuijala, J., and Vandevenne, L. 2013. Data Compression Using Zopfli. http://fh7922mg.bget.ru/ articles/compression/data-compression-using-zopfli.html.
  9. Baer, M. B. 2007. On Conditional Branches in Optimal Decision Trees. In Proc. IEEE International Symposium on Information Theory, 436–440.
  10. Moffat, A., and Turpin, A. 1997. On the Implementation of Minimum Redundancy Prefix Codes. IEEE Trans. on Communications 45 (10), 1200–1207.
  11. Jeong, C., Hang, S., and Burgstaller, B. 2014. Improved Branch Prediction for Just-in-Time Decompression of Canonical Huffman Bytecode Streams. Frontier and Innovation in Future Computing and Communications. Springer, 719–729.
  12. Bibakis, V. Random Word Text Generator. http://randomtextgenerator.com/.
  13. Rodriguez-Clark, D. Frequency Analysis: Breaking the Code. http://crypto.interactive-maths.com/frequency-analysis- breaking-the-code.html.
  14. Mahoney, M. 2006. About the Test Data. https://cs.fit. edu/~mmahoney/compression/textdata.html.
  15. Arnold, R., and Bell, T, 1997. A Corpus for the Evaluation of Lossless Compression Algorithms. In Proc. IEEE Data Compression Conference, 201-210.

Keywords

Huffman Encoding, Decoding Speed, Compression Ratio, Octernary Huffman, Hexadecimal Huffman, Branch Prediction Rate