ANALISIS ALGORITMA MTF, MTF-1 DAN MTF-2 PADA BURROWS WHEELER COMPRESSION ALGORITHM
DOI:
https://doi.org/10.21460/jutei.2019.31.148Keywords:
Move-to-Front, Burrows Wheeler Compression, kompresi dataAbstract
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.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish articles in JUTEI agree on the following rules:
1. The author grants non exclusive royalty free rights, and is willing to publish articles online and complete (full access). With such rights JUTEI reserves the right to save, transfers, manages in various forms, maintains and publishes articles while keeping the author's name as the copyright owner.
2. Each author contained in the article has contributed fully to the substance and intellectual, and is accountable to the public. If in the future there is a copyright infringement notification then this will be responsibility of the author, not JUTEI.
