Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi
Yıl: 2023 Cilt: 38 Sayı: 2 Sayfa Aralığı: 771 - 780 Metin Dili: Türkçe DOI: 10.17341/gazimmfd.882745 İndeks Tarihi: 13-03-2023
Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi
Öz: 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.
Anahtar Kelime: Determination of canonical Huffman codeword lengths by evolution strategies
Öz: Huffman coding is widely used in data compression. Canonical Huffman coding is a subset of Huffman coding and has some advantages, such as shorter header and less memory usage. Therefore, studies on this coding have been continuing. The algorithm producing the lengths of Algebraic Canonical Huffman Codes (ACHC) is one of these studies and this algorithm obtains the code lengths nearest to optimum value. In this study, an algorithm obtaining the code lengths that are the basis for the production of canonical Huffman codes using Evolutionary Strategies (ESs) is proposed, and this algorithm means that the ACHC algorithm is optimized by the ESs method. ESs is an evolutionary algorithm that mostly uses the mutation. Replication creates many copies of a single ancestor. The copies are mutated to produce offspring. Among the offspring and the ancestor, the individual with the best fitness value is chosen as the ancestor of the next generation. This cycle continues until the stop criteria is met. In this study, the length array obtained by ACHC was used as the first ancestor. The optimum value was achieved as a result of the evolution of this ancestor by mutation. As a result of the tests, the required number of cycles to reach the optimum value was determined as a fixed number. In this case, the time complexity is O (n²), where n is the number of symbols used. The amount of memory used is O (n²) because of the usage of multiple individuals.
Anahtar Kelime: Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık
- Chen Y.G. Wan, Z. Xia ve M.S. Tong, A hardware Design Method for Canonical Huffman Code, 2017 Progress in Electromagnetics Research Symposium - Fall (PIERS - FALL), Singapore, 2017.
- Shao Z.e.A., A High Throughput VLSI Architecture Design of Canonical Huffman Encoder, IEEE Transactions on Circuits and Systems II : Express Briefs, 6 (1), 209-213, January 2022.
- Back T., Fogel D.B., Glossary, Evolutionary Computation 1: Basic Algorithms and Operations, Bristol and Philadelphia, Institute of Physics Publishing, XXV, 2000.
- Fogel D.B., 4: Principles of Evolutionary Process, Evolutionary Computation 1: Basic Algorithms and Operations, Bristol and Philadelphia, Institute of Physics Publishing, 23-26, 2000.
- Demir A.S., Mert M.B.G. A new selection strategy for multi objective genetic algorithm: MultiMoora Rank, Journal of the Faculty of Engineering and Architecture of Gazi University,37 (4), 2119-2131, 2022.
- Saraç T., Tutumlu B., A mix integer programming model and solution approach to determine the optimum, Journal of the Faculty of Engineering and Architecture of Gazi University, 37 (1), 329-345, 2022.
- Back T., 7: Introduction to Evolutionary Algorithms, Evolutionary Computation 1: Basic Algorithms and Operations, Bristol and Philadelphia, Institute of Physics Publishing, 59-62, 2000.
- C. Boisclair ve M. Wagner, Better Huffman Coding via Genetic Algorithm, The Proceedings of the 2008 International Conference on Genetic and Evolutionary Methods, GEM 2008, Las Vegas, 2008.
- 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, 34 (4), 9-20, 2019.
- G. Üçoluk ve H. Toroslu, Genetic algorithm approach for verification of the syllable based text compression technique, Computer Journal of Information Science, 23 (5), 365-372, 1997.
- F. Oroumchian, E. Darrudi, F. Taghiyareh ve N. Angoshtari, Experiments with persian text compression for web, Proceeding of the 13th international World Wide Web conference on alternate track papers & posters, WWW Alt. '04, 2004, New York, 2004.
- J. Lánský ve T. Kuthan, Genetic algorithms in syllable based text compression, içinde Proceedings of the Dateso 2007 Annual International Workshop on DAtabases, TExts, Specifications and Objects., Desna – Cerna ˇ Rıcka, 2007.
- A. Kattan ve R. Poli, Evolutionary lossless compression with GP-ZIP, 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computatioanal Intelligence, Hong Kong, 2008.
- A. Kattan ve R. poli, Evolutionary Lossless Compression with GP- ZIP*, In GECCO'08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation, 2008, Atlanta, 2008.
- A. Kattan ve R. Poli, Evolutionary synthesis of lossless compression algorithms with GP-zip2, Genetic Programming and Evolvable Machines, 12 (4), 335–364, 2011.
- A. Kattan ve R. Poli, Genetic-Programming Based Prediction of Data Compression Saving, 9th International Conference on Artificial Evolution (Evolution Artificielle), Strasbourg, France, 2009.
- A. Kattan ve R. Poli, Evolutionary Synthesis of Losless Compression Algorithms with GP-ZIP3, IEEE Congress on Evolutionary Computation, Barcelona, 2010.
- M. Zaki ve M. Sayed, The use of genetic programming for adaptive text compression, Int. J. Information and Coding Theory, 1 (1), 88–108, 2009.
- K. I. M. Abuzanouneh, Develop and Design Hybrid Genetic Algorithms with Multiple Objectives in Data Compression, IJCSNS International Journal of Computer Science and Network Security, 17 (10), Seoul, 2017.
- J. Platos ve P. Krömer, Evolving alphabet using genetic algorithms, Proceedings of the 2011 3rd World Congress on Nature and Biologically Inspired Computing, Salamanca, 2011.
- J. Platos ve P. Krömer, Optimizing alphabet using genetic algorithms, International Conference on Intelligent Systems Design and Applications, ISDA, Cordoba, 2011.
- J. Platos ve P. Krömer, Searching for Optimal Alphabet for Data, IEEE International Conference on Systems, Man, and Cybernetics, Seoul, Korea, 2012.
- Y. Wiseman, JPEG Quantization Tables for GPS Maps, Automatic Control and Computer Sciences, 55 (6), 568-576, 2021. 24. R. Ranjan, Canonical Huffman Coding Based Image Compression using Wavelet, Wireless Personel Communications,117 (3), 2193-2206, 2021.
- D. Huffman, A Method for the Construction of Minimum Redundancy Codes, Proceedings of the IRE, 40 (9), 1098-1101, 1952.
- A. Moffat ve A. Turpin, On the implementation of minimum redundancy prefix codes, IEEE Transactions on Communications, 45 (10), 1200-1207, 1997.
- A. Moffat, I. H. Witten ve T. C. Bell, Managing Gigabytes:Compressing and Indexing Documents and Images, Second Edition dü., E. Fox, Dü., San Francisco: Morgan Kauffmann Publishers, 1999.
- J. B. Connell, A Huffman-Shonnon-Fano Code, Proceedings of the IEEE, 61 (7), 1046-1047, July 1973.
- R. Günter, 9: Evolution Strategies, Evolutionary Computation 1: Basic Algorithms and Operations, Bristol, Institute of Physics Publishing, 2000, 81-88.
- A. Auger, Convergence results for the (1,λ)-SA-ES using the theory of φ-irreducible Markov chains, Theoretical Computer Science, 334, 35- 69, 2005.
- A. Auger ve A. N. Hansen, A Restart CMA Evolution Strategy with Increasing Population Size, IEEE Congress on Evolutionary Computation, Edinburgh, 2005.
- D. Solomon, Data Compression:The Complete Reference (4th ed.), Springer Publishing, 71, 2007.
| APA | Oral M, Aşşık M (2023). Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. , 771 - 780. 10.17341/gazimmfd.882745 |
| Chicago | Oral Mustafa,Aşşık M. Mustafa Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. (2023): 771 - 780. 10.17341/gazimmfd.882745 |
| MLA | Oral Mustafa,Aşşık M. Mustafa Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. , 2023, ss.771 - 780. 10.17341/gazimmfd.882745 |
| AMA | Oral M,Aşşık M Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. . 2023; 771 - 780. 10.17341/gazimmfd.882745 |
| Vancouver | Oral M,Aşşık M Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. . 2023; 771 - 780. 10.17341/gazimmfd.882745 |
| IEEE | Oral M,Aşşık M "Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi." , ss.771 - 780, 2023. 10.17341/gazimmfd.882745 |
| ISNAD | Oral, Mustafa - Aşşık, M. Mustafa. "Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi". (2023), 771-780. https://doi.org/10.17341/gazimmfd.882745 |
| APA | Oral M, Aşşık M (2023). Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 38(2), 771 - 780. 10.17341/gazimmfd.882745 |
| Chicago | Oral Mustafa,Aşşık M. Mustafa Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 38, no.2 (2023): 771 - 780. 10.17341/gazimmfd.882745 |
| MLA | Oral Mustafa,Aşşık M. Mustafa Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, vol.38, no.2, 2023, ss.771 - 780. 10.17341/gazimmfd.882745 |
| AMA | Oral M,Aşşık M Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2023; 38(2): 771 - 780. 10.17341/gazimmfd.882745 |
| Vancouver | Oral M,Aşşık M Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2023; 38(2): 771 - 780. 10.17341/gazimmfd.882745 |
| IEEE | Oral M,Aşşık M "Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi." Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 38, ss.771 - 780, 2023. 10.17341/gazimmfd.882745 |
| ISNAD | Oral, Mustafa - Aşşık, M. Mustafa. "Kanonik Huffman kod sözcükleri uzunluklarının evrim stratejileri algoritması ile belirlenmesi". Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 38/2 (2023), 771-780. https://doi.org/10.17341/gazimmfd.882745 |
