Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi

Year 2023, Volume: 38 Issue: 2, 771 - 780, 07.10.2022

M. Mustafa Aşşık , Mustafa Oral

https://doi.org/10.17341/gazimmfd.882745

Cited By: 2

Abstract

Huffman kodlama, veri sıkıştırma alanında yaygın bir şekilde kullanılmaktadır. Kanonik Huffman kodlama ise, Huffman kodlamanın bir alt kümesidir ve daha kısa başlık ve daha az hafıza yeri kullanılması gibi bazı avantajlara sahiptir. Bu nedenle bu kodlamayla ilgili geliştirme çalışmaları devam etmektedir. Cebirsel Kanonik Huffman Kodlama (CKHK) da bu çalışmalardan birisidir ve bu algoritma ile en iyi değere en yakın Huffman kod uzunlukları cebirsel yoldan elde edilmektedir. Bu çalışmada, kanonik Huffman kodlarının üretimine esas olan kod uzunluklarını Evrimsel Stratejiler (ESs) ile elde eden bir algoritma önerilmekte ve söz konusu algoritma aynı zamanda CKHK algoritmasının ESs yöntemi ile en iyileştirilmesi anlamına gelmektedir. ESs çoğunlukla mutasyonu kullanan bir evrimsel algoritmadır. Tek bir ata çoğalarak kendi kopyalarını oluşturur. Kopyalar mutasyona uğratılarak çocuklar elde edilir. Çocuklar ve atanın arasından en iyi uygunluk değerine sahip birey bir sonraki neslin atası seçilir. Durma şartı sağlanıncaya kadar bu döngü devam eder. Bu çalışmada ilk ata olarak CKHK ile edilen uzunluk dizisi kullanılmıştır. Bu atanın mutasyonla evrimleşmesi sonucunda en iyi değere ulaşılmıştır. Optimum değere ulaşmak için gerekli döngü sayısı testler sonucunda sabit bir sayı olarak belirlenmiş olup, bu durumda zaman karmaşıklığı, n alfabe sayısı olmak üzere O(n²) olarak tespit edilmiştir. Kullanılan hafıza miktarı ise çoklu bireyler nedeniyle O(n²) bayttır.

Keywords

• Veri sıkıştırma, • Kanonik Huffman kodlama, • Evrimsel algoritmalar, • Evrim stratejileri

References

• Chen Y., Wan G., Xia Z. ve Tong M. S., A hardware Design Method for Canonical Huffman Code, 2017 Progress in Electromagnetics Research Symposium - Fall (PIERS - FALL), Singapore, pp. 2212-2215, 2017.
• Back T., Fogel D. B., Glossary,Evolutionary Computation 1: Basic Algorithms and Operations, Bristol, Institute of Physics Publishing, p. XXV, 2000.
• Fogel D. B., 4: Principles of Evolutionary Process, Evolutionary Computation 1: Basic Algorithms and Operations, Bristol, Institute of Physics Publishing, pp. 23-26, 2000.
• Back T., 7: Introduction to Evolutionary Algorithms, Evolutionary Computation 1: Basic Algorithms and Operations, Bristol, Institute of Physics Publishing, pp. 59-62, 2000.
• Oral M., Aşşık M. M., An Algorithm that Calculates the Lengths of Codewords Algebraically for Canonical Huffman-like Encoding, Cukurova University Journal of The Faculty of Engineering and Architecture, vol. 34, no. 4, pp. 9-20, 2019.
• Üçoluk G., Toroslu H., Genetic algorithm approach for verification of the syllable based text compression technique, Computer Journal of Information Science, vol. 23, no. 5, pp. 365-372, 1997.
• Oroumchian F., Darrudi E., Taghiyareh F., Angoshtari N., Experiments with persian text compression for web,Proceeding of the 13th international World Wide Web conference on alternate track papers & posters WWW Alt. '04, New York, pp. 478-479, 2004.
• Lánský J., Kuthan T., Genetic algorithms in syllable based text compression,Proceedings of the Dateso 2007 Annual International Workshop on DAtabases, TExts, Specifications and Objects, Desna Ricka, pp.21-34, 2007
• Kattan A., Poli R., Evolutionary lossless compression with GP-ZIP,2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computatioanal Intelligence, Hong Kong, pp, 2468-2472, 2008.
• Kattan A.. Poli R., Evolutionary Lossless Compression with GP-ZIP*, In GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, Atlanta, pp-1211-1213, 2008.
• Kattan A., Poli R., Evolutionary synthesis of lossless compression algorithms with GP-zip2, Genetic Programming and Evolvable Machines, Vol. 12, no. 4, pp. 335–364, 2011.
• Kattan A., Poli R., Genetic-Programming Based Prediction of Data Compression Saving, 9th International Conference on Artificial Evolution (Evolution Artificielle), Strasbourg,pp. 182-193, 2009.
• Kattan A., Poli R., Evolutionary Synthesis of Losless Compression Algorithms with GP-ZIP3, IEEE Congress on Evolutionary Computation, Barcelona, pp. 1-8, 2010.
• Boisclair C., Wagner M., Better Huffman Coding via Genetic Algorithm, Proceedings of the 2008 International Conference on Genetic and Evolutionary Methods, GEM 2008, Las Vegas, pp. 30-34, 2008.
• Zaki M., Sayed M., The use of genetic programming for adaptive text compression, Int. J. Information and Coding Theory, Vol. 1, No. 1, pp.88–108, 2009.
• Abuzanouneh K. I. M., Develop and Design Hybrid Genetic Algorithms with Multiple Objectives in Data Compression, IJCSNS International Journal of Computer Science and Network Security, Seoul, Vol. 17 No. 10, pp. 32-39, 2017.
• Platos J., Krömer P., Evolving alphabet using genetic algorithms, Proceedings of the 2011 3rd World Congress on Nature and Biologically Inspired Computing, Salamanca, pp. 575-581, 2011.
• Platos J., Krömer P., Optimizing alphabet using genetic algorithms, International Conference on Intelligent Systems Design and Applications, ISDA, Cordaba, Vol. 189, pp. 498-503, 2011.
• Platos J., Krömer P., Searching for Optimal Alphabet for Data, IEEE International Conference on Systems, Man, and Cybernetics (SMC), Seoul,pp. 468-473, 2012.
• Huffman D., A Method for the Construction of Minimum Redundancy Codes, Proceedings of the IRE, Vol. 40, no. 9, pp. 1098-1101, 1952.
• Moffat A., Turpin A., On the implementation of minimum redundancy prefix codes, IEEE Transactions on Communications, Vol 45, no. 10, pp. 1200-1207, 1997.
• Moffat A., Witten I. H., Bell T. C., Managing Gigabytes:Compressing and Indexing Documents and Images, Second Edition, Morgan Kauffman Publishers, San Francisco, p. 39, 1999.
• Connell J. B., A Huffman-Shonnon-Fano Code, Proceedings of the IEEE, Vol. 61, no. 7, pp. 1046-1047, July 1973.
• Günter R., 9: Evolution Strategies, Evolutionary Computation 1: Basic Algorithms and Operations, Bristol, Institute of Physics Publishing, pp. 81-88, 2000.
• Auger A., Convergence results for the (1,λ)-SA-ES using the theory of φ-irreducible Markov chains, Theoretical Computer Science, vol.334, pp. 35-69, 2005.
• Auger A., Hansen A. N., A Restart CMA Evolution Strategy with Increasing Population Size, IEEE Congress on Evolutionary Computation, Edinburgh, pp. 1769-1776, 2005.
• Solomon D., Data Compression:The Complete Reference (4th ed.), Springer Publishing, p. 71, London, 2007.