A Comparison of Text Compression Performance of Statistical Coding Methods in Turkish and English

Yıl 2023, Cilt: 15 Sayı: 3, 16 - 27, 31.12.2023

Ibrahim Ozturk Hakan Celil Kaya

https://doi.org/10.29137/umagd.1294273

Öz

Data compression is the set of operations performed to enable digital data to occupy less space than it does in memory. These operations are carried out by utilizing more or less repeated data chunks depending on the file type. In this way, compression operations allow for a more efficient use of the memory and data communication bus. Compression techniques are divided into two groups: lossless and lossy compression. Lossless compression includes dictionary-based coding and statistical coding methods. Statistical coding represents the most frequently occurring characters in the data with shorter codewords, while less common characters are represented by longer codewords. Although the frequency of character use is at the heart of statistical coding methods, the processing steps differ depending on the method used. In this study, the performances of the Huffman, Shannon-Fano, and Arithmetic coding methods, which use statistical coding for compression, were compared on English and Turkish texts. Text-based files within the Calgary corpus for English and compilations of newspaper columns for Turkish are used in the study. The comparisons are made based on savings rate, compression-decompression times, Bit per character (BPC), and entropy metrics. The results show performance differences in savings rate, BPC, and entropy metrics between statistical coding methods for English and Turkish texts.

Anahtar Kelimeler

Data Compression, Statistical Coding, Huffman Coding, Shannon-Fano Coding, Arithmetic Coding

İstatiksel Kodlama Yöntemlerinin Türkçe ve İngilizce Metinlerde Sıkıştırma Başarımı Karşılaştırma Örneği

Öz

Veri sıkıştırma, dijital ortamda bulunan verilerin hafızada olduğundan daha az yer kaplayabilmesi için yapılan işlem adımları bütünüdür. Bu işlemler dosya türlerine göre değişen az ya da çok tekrar eden veri öbeklerinden yararlanarak gerçekleştirilir. Böylece sıkıştırma işlemleri hafızanın ve veri iletişim hattının taşıma kapasitesini daha verimli kullanımına olanak sağlamaktadır. Sıkıştırma teknikleri kayıplı ve kayıpsız olarak iki gruba ayrılmaktadırlar. Kayıpsız sıkıştırma, sözlük tabanlı kodlama ve istatistiksel kodlama yöntemlerini içermektedir. İstatiksel kodlama, veri içindeki sık görülen karakterleri daha kısa kod kelimesiyle temsil ederken, daha az görülen karakterleri daha uzun kod kelimesiyle temsil edilmesi mantığına dayanmaktadır. İstatiksel kodlama yöntemlerinin temelinde karakter kullanım sıklıkları yer alsa da işlem basamakları yöntemlere bağlı olarak farklılık göstermektedir. Bu çalışmada sıkıştırma için istatiksel kodlamayı kullanan Huffman, Shannon-Fano ve Aritmetik kodlama yöntemlerinin İngilizce ve Türkçe metinler üzerindeki başarımları karşılaştırılmıştır. Çalışmada kullanılmak üzere İngilizce için Calgary külliyatı içerisinde bulunan metin tabanlı dosyalar, Türkçe için gazetelerde yayımlanmış köşe yazılarından derlemeler yapılmıştır. Karşılaştırmalar tasarruf oranı, sıkıştırma-açma süreleri, BPC (Bit per character) ve entropi metrikleri üzerinden sağlanmıştır. Sonuçlar istatiksel kodlama yöntemlerinin İngilizce ve Türkçe metinler arasında tasarruf oranı, BPC ve entropi ölçütlerinde başarım farklılıkları olduğunu ortaya koymaktadır.

Anahtar Kelimeler

Veri Sıkıştırma, İstatiksel Kodlama, Huffman Kodlama, Shannon-Fano Kodlama, Aritmetik Kodlama

Kaynakça

• Abramson, N. (1963). Information theory and coding.
• Aktaner, A. (1995). Entropi Kodlama ile EKG Veri Sıkıştırma İstanbul Teknik Üniversitesi]. Fen Bilimleri Enstitüsü.
• Bell, T., Witten, I. H., & Cleary, J. G. (1989). Modeling for text compression. ACM Comput. Surv., 21(4), 557–591. https://doi.org/10.1145/76894.76896
• Bulut, F. (2016). Huffman Algoritmasıyla Kayıpsız Hızlı Metin Sıkıştırma. El-Cezerî Fen ve Mühendislik Dergisi, 3(2), 0-0. https://doi.org/10.31202/ecjse.264192
• Bulut, F. (2017). Bilgi Kuramındaki Entropi Kavramıyla İlgili Farklı Matematiksel Modeller. Bilge International Journal of Science and Technology Research, 1(2), 167-174.
• Çelikel Çankaya, E., Palaniappan, V., & Latifi, S. (2010). Fazlalıktan Yararlanarak Kayıplı Metin Sıkıştırma Gerçekleştirimi. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 16(3), 235 - 245.
• Çölkesen, T. F. (2021). Veri Yapıları ve Algoritmalar. Papatya Yayınları.
• Diri, B. (1999). Türkçe'nin biçimbilim yapısına dayalı bir metin sıkıştırma sistemi Yıldız Teknik Üniversitesi]. Fen Bilimleri Enstitüsü
• Gilbert, H., & Handschuh, H. (2004). Security Analysis of SHA-256 and Sisters. In M. Matsui & R. J. Zuccherato, Selected Areas in Cryptography Berlin, Heidelberg.
• Github. (2023). https://github.com/hckaya/stcc
• Güneş, F., & Işık, A. D. (2018). Türkçede Sık Kullanılan Harfler ve Öğretilmesi. Sınırsız Eğitim ve Araştırma Dergisi, 3(1), 1-26.
• Güzeldereli, E. A. (2012). Veri Gizlemede Sıkıştırma Algoritması Kullanımı ve Uygulaması Sakarya Üniversitesi]. Fen Bilimleri Enstitüsü.
• Huffman, D. A. (1952). A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE, 40(9), 1098-1101. https://doi.org/10.1109/JRPROC.1952.273898
• Ince, I. F., Bulut, F., Kilic, I., Yildirim, M. E., & Ince, O. F. (2022). Low dynamic range discrete cosine transform (LDR-DCT) for high-performance JPEG image compression. The Visual Computer, 38(5), 1845-1870. https://doi.org/10.1007/s00371-022-02418-0
• Koşan, M. A., Coşkun, A., & Karacan, H. (2019). Yapay Zekâ Yöntemlerinde Entropi Journal of Information Systems and Management Research, 1(1), 15-22.
• Mantoro, T., Ayu, M. A., & Anggraini, Y. (2017, 23-25 Nov. 2017). The performance of text file compression using Shannon-Fano and Huffman on small mobile devices. 2017 International Conference on Computing, Engineering, and Design (ICCED),
• Mesut, A. (2006). Veri Sıkıştrmada Yeni Yöntemler Trakya Üniversitesi ]. Fen Bilimleri Enstitüsü.
• Oral, M., & Aşşık, M. M. (2019). Kanonik Huffman Benzeri Kodlama için Kod Sözcüklerinin Uzunluklarını Cebirsel Olarak Hesaplayan Bir Algoritma. Çukurova Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 34(4), 9-20. https://doi.org/10.21605/cukurova mmfd.702021
• Öztürk, E., & Mesut, A. (2021). Kısa Metinlerin Sıkıştırılması için BERT Tabanlı bir Yöntem. Avrupa Bilim ve Teknoloji Dergisi(32), 177-182. https://doi.org/10.31590/ejosat.1039450
• Rahman, M. A., & Hamada, M. (2019). Lossless Image Compression Techniques: A State-of-the-Art Survey. Symmetry, 11(10), 1274. https://www.mdpi.com/2073-8994/11/10/1274
• Sayood, K. (2006). Introduction to Data Compression. Elsevier Science. https://books.google.com.tr/books?id=044wLaqZ8twC
• Shanmugasundaram, S., & Lourdusamy, R. (2011). A Comparative Study Of Text Compression Algorithms. International Journal of Wisdom Based Computing, 2(4), 68-76. https://doi.org/10.21917/ijct.2011.0062
• Shannon, C. E. (1948). A mathematical theory of communication. The Bell System Technical Journal, 27(3), 379-423. https://doi.org/10.1002/j.1538-7305.1948.tb01338.x
• Stecuła, B., Stecuła, K., & Kapczyński, A. (2022). Compression of Text in Selected Languages-Efficiency, Volume, and Time Comparison. Sensors, 22(17), 6393. https://www.mdpi.com/1424-8220/22/17/6393
• Storer, J. A., & Szymanski, T. G. (1982). Data compression via textual substitution. J. ACM, 29(4), 928–951. https://doi.org/10.1145/322344.322346
• Welch, T. A. (1984). A Technique for High-Performance Data Compression. Computer, 17(6), 8-19. https://doi.org/10.1109/MC.1984.1659158
• Witten, I. H., Neal, R. M., & Cleary, J. G. (1987). Arithmetic coding for data compression. Commun. ACM, 30(6), 520–540. https://doi.org/10.1145/214762.214771
• Ziv, J., & Lempel, A. (1977). A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3), 337-343. https://doi.org/10.1109/TIT.1977.1055714
• Ziv, J., & Lempel, A. (1978). Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5), 530-536. https://doi.org/10.1109/TIT.1978.1055934