Comparison of BWT and Sequitur Algorithms for Improving the Compression Ratio of Run-Length Encoding
Keywords:
text compression, Run-Length Encoding, Burrows-Wheeler Transform, Sequitur, compression ratioAbstract
Run-Length Encoding (RLE) is effective when identical symbols occur consecutively, a condition that is not consistently present in text. This study compares the Burrows-Wheeler Transform (BWT) and Sequitur as preprocessing mechanisms intended to improve the RLE compression ratio. Three processing paths were examined: direct RLE, BWT followed by RLE, and Sequitur followed by RLE. The evaluation focuses on symbol-length changes at the RLE stage and reports the output-to-input ratio and space saving. Direct RLE on “compression” retained 11 symbols. BWT rearranged the string to “nrsoocimpse”, but the RLE result also contained 11 symbols. Sequitur produced a grammar-based representation of “compression compass”; however, the visible sequence submitted to RLE remained unchanged after encoding. Accordingly, all tested RLE stages produced a 100% ratio and 0% space saving. The findings show that preprocessing benefits RLE only when it creates sufficiently long adjacent runs. The experiment is limited to short samples and does not include transform metadata or grammar-dictionary overhead.
References
Darnita, Y., Khairunnisyah, K., & Mubarak, H. (2019). Kompresi data teks dengan menggunakan algoritma Sequitur. Sistemasi, 8(1), 104. https://doi.org/10.32520/stmsi.v8i1.429
Saragih, S. R., & Utomo, D. P. (2020). Penarapan algoritma Prefix Code dalam kompresi data teks. KOMIK (Konferensi Nasional Teknologi Informasi dan Komputer), 4(1), 249–252. https://doi.org/10.30865/komik.v4i1.2691
Jalaludin, A., & Melita, Y. (2012). Implementasi metode Run Length Encoding untuk kompresi citra. Jurnal Teknik, 3(2), 249–254.
Mansyuri, U. (2021). Kompresi data teks dengan metode Run Length Encoding. Jurnal SIMASI, 1(2), 102–109.
Mahendra, A. D., Suryani, E., & Aziz, A. (2016). Analisis perbandingan kinerja kombinasi algoritma BWT-RLE-MTF-Huffman dan BWT-MTF-RLE-Huffman pada kompresi file. Jurnal Teknologi Informasi ITSmart, 1(2), 107. https://doi.org/10.20961/its.v1i2.606
Buulolo, E. (2017). Sequitur algorithm for particular character compression or words always returned. International Journal of Informatics and Computer Science (The IJICS), 1(1), 15–17.
Siahaan, S. (2019). Penerapan algoritma Sequitur pada kompresi record database pada database. JURIKOM (Jurnal Riset Komputer), 6(5), 511–516. https://www.ejurnal.stmik-budidarma.ac.id/index.php/jurikom/article/view/1644
Burrows, M., & Wheeler, D. J. (1994). A block-sorting lossless data compression algorithm (SRC Research Report 124). Digital Systems Research Center.
Nevill-Manning, C. G., & Witten, I. H. (1997). Identifying hierarchical structure in sequences: A linear-time algorithm. Journal of Artificial Intelligence Research, 7, 67–82. https://doi.org/10.1613/JAIR.374
Salomon, D. (2007). Data compression: The complete reference (4th ed.). Springer London. https://doi.org/10.1007/978-1-84628-603-2
