AUTHORS: Yayuk Anggraini, Teddy Mantoro, Media A. Ayu
Download as PDF
ABSTRACT: Compression in Information Technology is the way to minimize the file size. Performance of compression algorithm is measured by the speed of process and the compression ratio. The compression time will effect on memory allocation and CPU performance, while the low compression ratio will weakens the ability of the algorithm to compress the data. Huffman and ShannonFano are two compression algorithms have same ways to work, but both produced a different performance. The test results concluded that the Shannon-Fano performance has a percentage of 1,56% lower than Huffman. This problem can be solved by adding a reversible transformation algorithm to the data source. Burrows-Wheeler Transform (BWT) produces output that is more easily to be processed at a later stage, and Move-to-front (MTF) is an algorithm to transform the data unifying and reduce redundancies. This study discusses a combination of BWT + MTF + Shannon-Fano algorithm and compare it with other algorithms (Shannon-Fano, Huffman and LZ77) which were applied on text files. The test results have shown that the combination of BWT + MTF + ShannonFano has the most efficient compression ratio, which is 60.89% higher at around 0.37% compared to LZ77. On compression time aspect, LZ77 is the slowest, approximately 39391,11 ms, while a combination of BWT + MTF + Shannon-Fano performs at approximately 1237,95 ms. This study concluded that the combination of BWT + MTF + Shannon-Fano algorithm performs as the most optimal algorithm in compression time (speed) and compression ratio (size).
KEYWORDS: BWT, MTF, Shannon-Fano, Huffman, LZ77, text files, compression algorithm optimization.
REFERENCES:
[1] D. Solomon, Data Compression, 4th ed. London: Spriger, 2007.
[2] P. Yellamma and N. Challa, “Performance Analysis Of Different Data Compression Techniques On Text File,” Int. J. Eng. Res. Technol., vol. 1, no. 8, (Oktober, pp. 1–6, 2012.
[3] B. Souley, P. Das, and S. Tanko, “A Comparative Analysis of Data Compression Techniques,” Int. J. Appl. Sci., vol. 2, no. 10, (April, pp. 63–82, 2014.
[4] J. M. Silaen, “Studi Perbandingan Algoritma Huffman dan Shannon- Fano dalam Pemampatan File Teks,” Pelita Inform. Budi Darma, vol. 7, no. 1, (Juli, pp. 60–66, 2014.
[5] K. Rastogi, K. Sengar, and M. T. Scholar, “Analysis and Performance Comparison of Lossless Compression Techniques for Text Data,” Int. J. Eng. Comput. Res., vol. 2, no. 1, pp. 16–19, 2014.
[6] P. Jeyanthi and V. Anuratha, “Analysis of Lossless Reversible Transformation Algorithms to Enhance Data Compression,” J. Glob. Res. Comput. Sci., vol. 3, no. 8, (Agustus, pp. 56–62, 2012.
[7] R. Bastys, “Fibonacci Coding Within the Burrows-Wheeler Compression Scheme,” Electron. Electr. Eng., vol. 1, pp. 28–32, 2010.
[8] M. Burrows and D. Wheeler, “A Block-Sorting Lossless Data Compression Algorithm,” Algorithm, Data Compression, no. 124, p. 18, 1994.
[9] A. S. E. Campos, “Move to Front,” 1999.
[Online]. Available: https://www.arturocampos.com/ac_mtf.html.
[Accessed: 15-Mar2017].
[10] M. Dipperstein, “Burrows-Wheeler Transform Discussion and Implementation,” 2010.
[Online]. Available: https://michael.dipperstein.com/bwt/.
[Accessed: 15-Mar-2017].
[11] R. R. Baruah, V. Deka, and M. P. Bhuyan, “Enhancing Dictionary Based Preprocessing For Better Text Compression,” Int. J. Comput. Technol., vol. 9, no. 1, (Maret, pp. 4–9, 2014.
[12] R. Râdescu, “Transform Methods Used in Lossless Compression of Text Files,” Rom. J. Inf. Sci. Technol., vol. 12, no. 1, (November, pp. 101–115, 2009.
[13] I. M. Pu, Fundamental Data Compression. London: ButterworthHeinemann, 2006.
[14] P. Widhiartha, “Pengantar Kompresi Data (Introduction to Data Compression)” 2008, Available: https://www.ilmukomputer.org/ wp-content/uploads/2008/10/ widhiartha_kompresidata.pdf.
[Accessed: 1-Nov-2017].
[15] C. P. Nugraha and R. G. Santosa, “Perbandingan Metode LZ77, Metode Huffman dan Metode Deflate Terhadap Kompresi Data Teks,” Informatika, vol. 10, no. 2, pp. 80–91, 2014.
[16] M. Dipperstein, “Huffman Code Discussion and Implementation,” 2010.
[Online]. Available: https://michael.dipperstein.com/Huffman/index.html.
[Accessed: 16-Apr-2017].
[17] H. Altarawneh and M. Altarawneh, “Data Compression Techniques on Text Files: A Comparison Study,” Int. J. Comput. Appl., vol. 26, no. 5, (Juli, pp. 42–54, 2011.
[18] S. Shanmugasundaram and R. Lourdusamy, “A Comparative Study Of Text Compression Algorithms,” Int. J. Wisdom Based Comput., vol. 1, no. 4, (December, pp. 68–76, 2011.
[19] S. Senthil, S. J. Rexiline, and L. Robert, “RIDBE: A Lossless, Reversible Text Transformation Scheme for Better Compression,” Int. J. Comput. Appl., vol. 51, no. 12, (Agustus, pp. 35–40, 2012.
[20] P. Jeyanthi and V. Anuratha, “Bwt Based Lossless Reversible Transformation Algorithms – An Analysis,” Int. J. Eng. Res. Appl., vol. 2, no. 5, (September-Oktober, pp. 807–814, 2012.
[21] E. C. Cankaya and O. Darwish, “Improving Compression Performance with a Star Encoding Front End : A Linguistic Comparison,” Proceedings of the International Conference on Foundations of Computer Science (FCS); Athens : 1-7 2013.