Pascal: Journal of Computer Science and Informatics
Vol. 1 No. 01 (2023): Pascal: Journal of Computer Science and Informatics

Comparison of BWT and Sequitur Algorithms for Improving the Compression Ratio of Run-Length Encoding

Rian Syahputra (Universitas Budi Darma)



Article Info

Publish Date
18 Dec 2023

Abstract

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.

Copyrights © 2023






Journal Info

Abbrev

komputer

Publisher

Subject

Decision Sciences, Operations Research & Management Education Electrical & Electronics Engineering Library & Information Science Social Sciences

Description

Pascal: Journal of Computer Science and Informatics is a national scientific journal that publishes research articles in the field of Computer Science and Informatics which include: Computer Engineering, Information Engineering, Computer Science, Information Systems, Information Technology, Software ...