Time Complexity of Knuth Morris Algorithm and Rejang Algorithm in Rejang-Indonesian Translator

Sastya Hendri Wibowo; Rozali Toyib; Yulia Darnita; Satria Abadi

doi:10.30595/juita.v12i2.23954

Authors

Sastya Hendri Wibowo Muhammadiyah University of Bengkulu
Rozali Toyib Muhammadiyah University of Bengkulu
Yulia Darnita Muhammadiyah University of Bengkulu
Satria Abadi Muhammadiyah University of Bengkulu

DOI:

https://doi.org/10.30595/juita.v12i2.23954

Keywords:

Knuth Morris algorithm, Rejang algorithm, time complexity

Abstract

Among the pattern-matching algorithms is the Knuth-Morris algorithm. In order to minimize the number of comparisons required and, in the worst scenario, achieve an ideal O(n+m) running time, the Knuth-Morris search algorithm skips unneeded comparisons. Every character in the text and every character in the pattern must be checked at least once by the pattern-matching algorithm. The Knuth-Morris algorithm's primary goal is to preprocess the pattern string P in order to determine the failure function f, which displays P's precise shift, so that earlier comparisons can be reused. In order to extract the fundamental word of the attached sentence, words containing affixes are separated using the Rejang stemming method. The purpose of this research is to determine the time complexity of the Rejang method and the Knuth-Morris algorithm based on affix groups. The Rapid Application Development (RAD) approach, which entails planning, designing, building, and implementing, is used during the research stages. The research results have produced efficient and effective Knuth Morris algorithm and Rejang algorithm, where efficiency is indicated by the algorithm time complexity of O (log n), and effectiveness is indicated by the accuracy results of 99% against testing 6000 affixed words.

Author Biographies

Sastya Hendri Wibowo, Muhammadiyah University of Bengkulu

Informatics Engineering Study Program

Rozali Toyib, Muhammadiyah University of Bengkulu

Informatics Engineering Study Program

Yulia Darnita, Muhammadiyah University of Bengkulu

Informatics Engineering Study Program

Satria Abadi, Muhammadiyah University of Bengkulu

Informatics Engineering Study Program

References

[1] S. Wibowo, B. Soerowirdjo, Ernastuti, and A. Tarigan, “Development of stemming algorithm for Rejang Speech stemmer based on rejang Speech structure,” J. Adv. Res. Dyn. Control Syst., vol. 11, no. 5 Special Issue, pp. 1858–1870, 2019.

[2] S. H. Wibowo, B. Soerowirdjo, Ernastuti, and A. Tarigan, “Spelling checker of words in Rejang Speech using the n-gram and Euclidean distance methods,” J. Comput. Theor. Nanosci., vol. 16, no. 12, pp. 5384–5395, 2019, doi: 10.1166/jctn.2019.8607.

[3] S. H. Wibowo, “Sistem Informasi Bahasa Rejang Berbasis Natural Speech Processing ( NLP ) Untuk Pelestarian Budaya Lokal,” vol. 5, no. 2, pp. 426–433, 2024, doi: 10.47065/josh.v5i2.4270.

[4] S. H. Wibowo, R. Toyib, M. Muntahanah, and Y. Darnita, “Time complexity in Rejang Speech stemming,” J. Infotel, vol. 14, no. 3, pp. 174–179, 2022, doi: 10.20895/infotel.v14i3.764.

[5] R. Sovia, S. Defit, Yuhandri, and Sulastri, “Development of natural Speech processing on structure-based Minangkabau Speech stemming algorithm,” Indones. J. Electr. Eng. Comput. Sci., vol. 31, no. 1, pp. 542–552, 2023, doi: 10.11591/ijeecs.v31.i1.pp542-552.

[6] A. Sinaga, Adiwijaya, and H. Nugroho, “Development of word-based text compression algorithm for Indonesian Speech document,” 2015 3rd Int. Conf. Inf. Commun. Technol. ICoICT 2015, pp. 450–454, 2015, doi: 10.1109/ICoICT.2015.7231466.

[7] P. Beynon-Davies, C. Came, H. Mackay, and D. Tudhope, “Rapid application development (Rad): An empirical review,” Eur. J. Inf. Syst., vol. 8, no. 3, pp. 211–232, 1999, doi: 10.1057/palgrave.ejis.3000325.

[8] V. Kralev and R. Kraleva, “Methods and tools for rapid application development,” Proc. III Int. Sci. Pract. Conf. "Methodology Mod. Res. (March 29, 2017, Dubai, UAE), vol. 1, no. 4 (20), pp. 21–24, 2017.

[9] N. M. N. Daud, N. A. A. A. Bakar, and H. M. Rusli, “Implementing Rapid Application Development (RAD) methodology in developing practical training application system,” Proc. 2010 Int. Symp. Inf. Technol. - Syst. Dev. Appl. Knowl. Soc. ITSim’10, vol. 3, pp. 1664–1667, 2010, doi: 10.1109/ITSIM.2010.5561634.

[10] D. Tudhope, P. Beynon-Davies, H. Mackay, and R. Slack, “Time and representational devices in rapid application development,” Interact. Comput., vol. 13, no. 4, pp. 447–466, 2001, doi: 10.1016/S0953-5438(00)00050-3.

[11] R. Setiawan, A. Kurniawan, W. Budiharto, I. H. Kartowisastro, and H. Prabowo, “Flexible affix classification for stemming Indonesian Speech,” 2016 13th Int. Conf. Electr. Eng. Comput. Telecommun. Inf. Technol. ECTI-CON 2016, 2016, doi: 10.1109/ECTICon.2016.7561257.

[12] W. B. Demilie, “Implemented Stemming Algorithms for Information Retrieval Applications,” J. Inf. Eng. Appl., vol. 10, no. 3, pp. 1–6, 2020, doi: 10.7176/jiea/10-3-01.

[13] R. D. Djati Pramono and S. Lorena, “Implementasi algoritma knuth-morris-pratt dalam aplikasi untuk penerjemahan idiom bahasa inggris 1),2),” pp. 1–6, 2015.

[14] O. Saputra, “Penerapan Algoritma Knuth Morris Pratt dalam Aplikasi Penerjemah Teks,” no. 13510072, 2013.

[15] B. L. Pramudita, “Implementasi Algoritma Knuth Morris Pratt pada Alat Penerjemah Suara,” no. 13511042.