Research Article
N-ary Huffman Encoding using High-Degree Trees - A Performance Comparison
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 183 - Issue 5 |
| Published: May 2021 |
| Authors: Ioannis S. Xezonakis, Svoronos Leivadaros |
10.5120/ijca2021921315
|
Ioannis S. Xezonakis, Svoronos Leivadaros . N-ary Huffman Encoding using High-Degree Trees - A Performance Comparison. International Journal of Computer Applications. 183, 5 (May 2021), 33-39. DOI=10.5120/ijca2021921315
@article{ 10.5120/ijca2021921315,
author = { Ioannis S. Xezonakis,Svoronos Leivadaros },
title = { N-ary Huffman Encoding using High-Degree Trees - A Performance Comparison },
journal = { International Journal of Computer Applications },
year = { 2021 },
volume = { 183 },
number = { 5 },
pages = { 33-39 },
doi = { 10.5120/ijca2021921315 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2021
%A Ioannis S. Xezonakis
%A Svoronos Leivadaros
%T N-ary Huffman Encoding using High-Degree Trees - A Performance Comparison%T
%J International Journal of Computer Applications
%V 183
%N 5
%P 33-39
%R 10.5120/ijca2021921315
%I Foundation of Computer Science (FCS), NY, 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
- Huffman, D. 1952. A Method for the Construction of Minimum-Redundancy Codes. In Proceedings of the I.R.E. 40 (9), 1098–1101.
- Suri, P. R., and Goel, M. 2008. Ternary Tree & a Coding Technique. International Journal of Computer Science and Network Security 8 (10), 102–107.
- 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.
- 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.
- Hashemian, R. 1995. Memory Efficient and High-Speed Search Huffman Coding. IEEE Trans. on Communications 43(10), 2576–2581.
- 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.
- 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.
- Alakuijala, J., and Vandevenne, L. 2013. Data Compression Using Zopfli. http://fh7922mg.bget.ru/ articles/compression/data-compression-using-zopfli.html.
- Baer, M. B. 2007. On Conditional Branches in Optimal Decision Trees. In Proc. IEEE International Symposium on Information Theory, 436–440.
- Moffat, A., and Turpin, A. 1997. On the Implementation of Minimum Redundancy Prefix Codes. IEEE Trans. on Communications 45 (10), 1200–1207.
- 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.
- Bibakis, V. Random Word Text Generator. http://randomtextgenerator.com/.
- Rodriguez-Clark, D. Frequency Analysis: Breaking the Code. http://crypto.interactive-maths.com/frequency-analysis- breaking-the-code.html.
- Mahoney, M. 2006. About the Test Data. https://cs.fit. edu/~mmahoney/compression/textdata.html.
- Arnold, R., and Bell, T, 1997. A Corpus for the Evaluation of Lossless Compression Algorithms. In Proc. IEEE Data Compression Conference, 201-210.
Index Terms
Keywords