Optimizing 4-ary Huffman Trees and Normalizing Binary Code Structures to Minimize Redundancy and Level Reduction
DOI:
https://doi.org/10.21831/elinvo.v10i1.78722Keywords:
Lossless, Compression, Huffman, Binary, AudioAbstract
Since the present data expansion and increase are occurring at an increasingly rapid pace, the solution of adding storage space is not sustainable in the long run. The growing need for storage media can be addressed with lossless compression, which reduces stored data while allowing complete restoration. Huffman remains a potent method for data compression, functioning as a "back end" process and serving as the foundational algorithm in applications, among others, Monkey's PKZIP, WinZip, 7-Zip, and Monkey's Audio. Lossless compression of 16-bit audio requires binary structure adjustments to balance speed and optimal compression ratio. The use of a 4-ary Huffman tree (4-ary) branching procedure to generate binary code generation and to insert a maximum of 2 dummy data symbol variables that are given a binary value of 0 with the condition that if the number of MOD 3 data variables = remaining 2, then two dummy data are added, if the result is the remainder 0 = 1 dummy data, and if the remainder = 1 then it is not required. This process effectively maintains a high ratio level while speeding up the 4-ary Huffman code algorithm's performance in compression time. The results show that the efficiency reaches 95.94%, the ratio is 38%, and the comparison is 1/3 of the Level based on calculations, testing, and comparison with other generations of the Huffman code. The 4-ary algorithm significantly optimizes archived data storage, reducing redundancy to 0.124 and achieving an entropy value of 2.91 across various data types.
References
D. Groppi, A. Pfeifer, D. A. Garcia, G. KrajaÄić, and N. Duić, "A review on energy storage and demand side management solutions in smart energy islands," Renew. Sustain. Energy Rev., vol. 135, p. 110183, Jan. 2021.
F. Mentzer and M. Tschannen, "Learning better lossless compression using lossy compression," Proc. IEEE/CVF Conf. Comput. Vis. Pattern Recognit., pp. 6638--6647, 2020.
T. Hidayat, M. H. Zakaria, and A. N. C. Pee, "Survey of Performance Measurement Indicators for Lossless Compression Technique based on the Objectives," in 2020 3rd International Conference on Information and Communications Technology (ICOIACT), 2020, pp. 170–175.
T. Hidayat, M. H. Zakaria, and A. N. C. Pee, "Increasing the Huffman generation code algorithm to equalize compression ratio and time in lossless 16-bit data archiving," Multimed. Tools Appl., vol. 82, no. 16, pp. 24031–24068, Jul. 2023.
Z. Zhang et al., "From compressive sampling to compressive tasking: retrieving semantics in compressed domain with low bandwidth," PhotoniX, vol. 3, no. 1, p. 19, Sep. 2022.
J. Uthayakumar, T. Vengattaraman, and P. Dhavachelvan, "A survey on data compression techniques: From the perspective of data quality, coding schemes, data type and applications," J. King Saud Univ. - Comput. Inf. Sci., May 2018.
H. Li, X. Tuo, T. Shen, M. J. Henderson, J. Courtois, and M. Yan, "An improved lossless group compression algorithm for seismic data in SEG-Y and MiniSEED file formats," Comput. Geosci., vol. 100, no. December 2016, pp. 41–45, 2017.
T. Hidayat, M. H. Zakaria, and N. Che Pee, "Comparison of Lossless Compression Schemes for WAV Audio Data 16-Bit Between Huffman and Coding Arithmetic," Int. J. Simul. Syst. Sci. Technol., vol. 19, no. 6, pp. 36.1-36.7, Feb. 2019.
J. L. Bentley, D. D. Sleator, R. E. Tarjan, and V. K. Wei, "A locally adaptive data compression scheme," Commun. ACM, vol. 29, no. 4, pp. 320–330, Mar. 1986.
M. Sharma, "Compression Using Huffman Coding," IJCSNS Int. J. Comput. Sci. Netw. Secur., vol. 10, no. 5, p. 133, 2010.
S. R. Kodituwakku and U. S. Amarasinghe, "Comparison of Lossless Data Compression Algorithms For Text Data," Indian J. Comput. Sci. Eng., vol. 1, no. 4, pp. 416–425, 2010.
H. Al-Bahadili and S. M. Hussain, "A bit-level text compression scheme based on the ACW algorithm," Int. J. Autom. Comput., vol. 7, no. 1, pp. 123–131, 2010.
H. Hermassi, R. Rhouma, and S. Belghith, "Joint compression and encryption using chaotically mutated Huffman trees," Commun. Nonlinear Sci. Numer. Simul., vol. 15, no. 10, pp. 2987–2999, Oct. 2010.
R. A. Chowdhury, M. Kaykobad, and I. King, "An efficient decoding technique for Huffman codes," Inf. Process. Lett., vol. 81, no. 6, pp. 305–308, 2002.
P. R. Suri and M. Goel, "Ternary Tree and Memory-Efficient Huffman Decoding Algorithm," Int. J. Comput. Sci. Issues, vol. 8, no. 1, pp. 483–489, 2011.
D. Huffman, "A Method for the Construction of Minimum-Redundancy Codes," Proc. IRE, vol. 40, no. 9, pp. 1098–1101, Sep. 1952.
K. Chung, "Efficient Huffman decoding," Inf. Process. Lett., vol. 61, pp. 97–99, 1997.
R. Schack, "The length of a typical Huffman codeword," IEEE Trans. Inf. Theory, vol. 40, no. 4, pp. 1246–1247, Jul. 1994.
G. Katona and O. Nemetz, "Huffman codes and self-information," IEEE Trans. Inf. Theory, vol. 22, no. 3, pp. 337–340, May 1976.
R. Hashemian, "Memory efficient and high-speed search Huffman coding," IEEE Trans. Commun., vol. 43, no. 10, pp. 2576–2581, 1995.
P. M. Fenwick, "Huffman code efficiencies for extensions of sources," IEEE Trans. Commun., vol. 43, no. 2/3/4, pp. 163–165, Feb. 1995.
W. Szpankowski and S. Verdu, "Minimum Expected Length of Fixed-to-Variable Lossless Compression Without Prefix Constraints," IEEE Trans. Inf. Theory, vol. 57, no. 7, pp. 4017–4025, Jul. 2011.
M. B. Baer, "A general framework for codes involving redundancy minimization," IEEE Trans. Inf. Theory, vol. 52, no. 1, pp. 344–349, Jan. 2006.
X. Kavousianos, E. Kalligeros, and D. Nikolos, "Test Data Compression Based on Variable-to-Variable Huffman Encoding With Codeword Reusability," IEEE Trans. Comput. Des. Integr. Circuits Syst., vol. 27, no. 7, pp. 1333–1338, Jul. 2008.
J. S. Vitter, "Algorithm 673: Dynamic Huffman coding," ACM Trans. Math. Softw., vol. 15, no. 2, pp. 158–167, 1987.
A. Habib, A. S. M. L. Hoque, and M. R. Hussain, "H-HIBASE: Compression Enhancement of HIBASE Technique Using Huffman Coding," J. Comput., vol. 8, no. 5, pp. 1175–1183, May 2013.
R. Gallager, "Variations on a theme by Huffman," IEEE Trans. Inf. Theory, vol. 24, no. 6, pp. 668–674, Nov. 1978.
J. Ziv and A. Lempel, "A universal algorithm for sequential data compression," IEEE Trans. Inf. Theory, vol. 23, no. 3, pp. 337–343, May 1977.
Welch, "A Technique for High-Performance Data Compression," Computer (Long. Beach. Calif)., vol. 17, no. 6, pp. 8–19, Jun. 1984.
Y. K. Lin, S. C. Huang, and C. H. Yang, "A fast algorithm for Huffman decoding based on a recursion Huffman tree," J. Syst. Softw., vol. 85, no. 4, pp. 974–980, 2012.
J. Alakuijala et al., "Brotli," ACM Trans. Inf. Syst., vol. 37, no. 1, pp. 1–30, Jan. 2019.
K. Sayood, "Huffman Coding," Introd. to Data Compression, pp. 41–88, 2018.
H. Chen, W. Xie, A. Vedaldi, and A. Zisserman, "Vggsound: A Large-Scale Audio-Visual Dataset," in ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, pp. 721–725.
N. Griffioen, W. Sterkens, W. Dewulf, and J. Peeters, "Enhancing Battery Detection in X-Ray Imaging in WEEE with a 16 bit Deep Learning Pipeline," in 2024 Electronics Goes Green 2024+ (EGG), 2024, pp. 1–6.
D. Snyder, G. Chen, and D. Povey, "MUSAN: A Music, Speech, and Noise Corpus," no. October, Oct. 2015.
J. J. Bosch, R. Marxer, and E. Gómez, "Evaluation and combination of pitch estimation methods for melody extraction in symphonic classical music," J. New Music Res., vol. 45, no. 2, pp. 101–117, Apr. 2016.
J. J. Bosch, J. Janer, F. Fuhrmann, and P. Herrera, "A comparison of sound segregation techniques for predominant instrument recognition in musical audio signals," Proc. 13th Int. Soc. Music Inf. Retr. Conf. ISMIR 2012, no. Ismir, pp. 559–564, 2012.
E. Fonseca, M. Plakal, D. P. W. Ellis, F. Font, X. Favory, and X. Serra, "Learning Sound Event Classifiers from Web Audio with Noisy Labels," ICASSP, IEEE Int. Conf. Acoust. Speech Signal Process. - Proc., vol. 2019-May, no. 688382, pp. 21–25, 2019.
Published
How to Cite
Issue
Section
Citation Check
License
Copyright (c) 2025 Elinvo (Electronics, Informatics, and Vocational Education)
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The article published in ELINVO became ELINVO's right in publication.
This work by ELINVO is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
