ANALISIS ALGORITMA MTF, MTF-1 DAN MTF-2 PADA BURROWS WHEELER COMPRESSION ALGORITHM

  • Sagara Mahardika Sunaryo Prodi Informatika, UKDW
  • Lukas Chrisantyo Prodi Informatika, UKDW
  • Yuan Lukito Prodi Informatika, UKDW
Keywords: Move-to-Front, Burrows Wheeler Compression, kompresi data

Abstract

Kebutuhan kompresi data teks di era komputasi awan saat ini masih cukup tinggi. Data teks perlu dikompresi sekecil mungkin agar mudah dikirimkan. Burrows Wheeler Compression Algorithm (BWCA) adalah salah satu algoritma kompresi teks jenis block sorting yang bersifat non-proprietary dan cukup populer digunakan. Dalam prosesnya, BWCA menggunakan metode pemrosesan awal yang disebut Global Structure Transformation (GST) untuk menyusun karakter agar lebih baik hasil kompresinya. Penelitian ini membandingkan tiga metode pemrosesan awal Move-to-Front, yaitu MTF, MTF-1 dan MTF-2. Bahan uji kompresi berupa data Alkitab Bahasa Inggris, Indonesia dan Jawa, dan beberapa data yang berasal dari Calgary Corpus. Oleh karena kompresi teks adalah kompresi yang bersifat lossless dan reversibel, maka selain melakukan pengujian untuk pengompresian data, juga dilakukan pengujian untuk pendekompresian data dengan Inverse Burrows Wheeler Transform. Pengujian kompresi dan dekompresi pada data Alkitab maupun Calgary Corpus berhasil dilakukan dan menunjukkan MTF-1 mampu memberikan rasio kompresi yang lebih baik dikarenakan jumlah total tiap bit pada proses Huffman lebih sedikit dibandingkan dua metode lainnya.

References

K. Sayood. (2017). Introduction to Data Compression. San Fransisco: Elsevier.

R.R. Baruah & M.P. Bhuyan. (2014). Enhancing Dictionary Based Preprocessing for Better Text Compression. International Journal of Computer Trends and Technology. 9(1), hal. 4-9.

A. Andersson & S. Nilsson. (1994). A New Efficient Radix Sort. SFCS ’94 Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 714-721.

H. Itoh & H. Tanaka. (2003). An Efficient Method in Memory Construction of Suffix Arrays. SPIRE’99 Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, 81.

S.S. Nanda, K. Das, J. Padhi & S. Hota, “Advanced Move-to-Front for List Access Problem” dipresentasikan di International Conference on Circuit, Power and Computing Technologies (ICCPCT), India, 18-19 Maret 2016.

S. Deorowicz. (2003). Universal lossless data compression algorithms. Czech: Silesian University of Technology, Faculty of Automatic Control, Electronics and Computer Science, Institute of Computer Science.

D. Schiller. (2012). The Burrows-Wheeler Algorithm. Theoretical Computer Science Department, RWTH Aachen University, Germany. [Online]. Tersedia: htttp://tcs.rwth-aachen.de/lehre/Komprimierung/SS2012/ausarbeitungen/Burrows-Wheeler.pdf.

D. Solomon. (2010). Handbook of Data Compression. California: Springer.

C. McAnlis & A. Haecky. (2016). Understanding Compression: Data Compression for Modern Developers. California: O’Reilly Media.

H.A. Elsayed, “Burrows-Wheeler Transform and combination of Move-to-Front coding and Run Length Encoding for lossless audio coding” dipresentasikan di The 9th International Conference on Computer Engineering & Systems (ICCES), Mesir, 22-23 Desember 2014.

Published
2019-07-01
How to Cite
[1]
S. M. Sunaryo, L. Chrisantyo, and Y. Lukito, “ANALISIS ALGORITMA MTF, MTF-1 DAN MTF-2 PADA BURROWS WHEELER COMPRESSION ALGORITHM”, JUTEI, vol. 3, no. 1, pp. 21-30, Jul. 2019.