Comparison of Knuth Morris Pratt and Boyer Moore algorithms for a web-based dictionary of computer terms

Ali Khumaidi, Yusuf Aras Ronisah, Harjono Padmono Putro

Abstract


Computer students need a dictionary of computer terms to deepen lectures. In developing dictionary applications, the term computer will choose the fastest and most efficient memory algorithm. The comparison algorithm is Knuth Morris Pratt (KMP) and Boyer Moore (BM) algorithm. Based on previous research, the KMP algorithm has a better performance compared to other string matching algorithms. However, other studies have concluded that the BM algorithm has better performance. Besides, the Zhu-Takaoka algorithm is more efficient than the KMP algorithm in dictionary development. The BM algorithm has the same search concept as the Zhu-Takaoka algorithm. The determination of the fastest and most efficient algorithm in this study uses the Exponential Comparison Method (ECM). ECM sets criteria for when searching and using the memory in the search process. The results of the comparison of the KMP and BM algorithm are the search time for the BM algorithm is 37.9%, and the KMP algorithm is 62.1%. The results of the use of search memory for the KMP algorithm are 50.6%, and the BM algorithm is 49.4%. The total ECM score shows that the BM algorithm is 0.55% better than the KMP algorithm.

Keywords


String Maching; Knuth-Morris-Pratt; Boyer Moore; Exponential Comparison Method; Dictionary of Computer Terms

Full Text:

PDF

References


R. Janani and S. Vijayarani, “An Efficient Text Pattern Matching Algorithm for Retrieving Information from Desktop,†Indian J. Sci. Technol., vol. 9, no. 43, Nov. 2016, doi: 10.17485/ijst/2016/v9i43/95454.

M. B. Sri, R. Bhavsar, and P. Narooka, “String Matching Algorithms,†Int. J. Eng. Comput. Sci., vol. 7, no. 3, 2018.

Diptarama, R. Yoshinaka, and A. Shinohara, “Fast Full Permuted Pattern Matching Algorithms on Multi-track Strings,†in Proceedings of the Prague Stringology Conference 2016, 2016, pp. 7–21.

P. Chettri and C. Kar, “Comparative Study between Various Pattern Matching Algorithms,†in International Conference on Computing & Communication, 2016.

H. Handrizal, A. Budiman, and D. R. Ardani, “Implementation and Analysis Zhu-Takaoka Algorithm and Knuth-Morris-Pratt Algorithm for Dictionary of Computer Application Based on Android,†IJISTECH (International J. Inf. Syst. Technol., vol. 1, no. 1, p. 8, Nov. 2017, doi: 10.30645/ijistech.v1i1.2.

R. Muntazari, A. Arini, and H. B. Suseno, “Application Of The Boyer Moore Method In The Application Dictionary Of Web-Based Information Technology Terms (Case Study: Pt. Erefka Tiga Pilar Utama),†Integr. (Journal Inf. Technol. Vocat. Educ., vol. 1, no. 2, 2019.

S. Maryana, E. Kurnia, and A. Ruyani, “Web-based application on employee performance assessment using exponential comparison method,†in IOP Conference Series: Materials Science and Engineering, 2019.

Kholil, D. Prinajati, and N. A. Annisari, “Flood Management Model in Digital Era, Using SAST (Strtategic Assumption Surfacing and Testing) and the Exponential Comparison Method (ECM): A Case Study in Jakarta,†J. Sci. Res. Reports, pp. 1–9, Aug. 2019, doi: 10.9734/jsrr/2019/v24i330156.

C. S. Rao and S. V. Raju, “A Novel Multi Pattern String Matching Algorithm with While Shift,†in Proceedings of the Second International Conference on Information and Communication Technology for Competitive Strategies - ICTCS ’16, 2016, pp. 1–5, doi: 10.1145/2905055.2905108.

M. R. Apriyadi, E. Ermatita, R. F. Malik, and D. P. Rini, “Knuth Morris Pratt - Boyer Moore Hybrid Algorithm for Knowledge Management System Model on Competence Employee in Petrochemical Company,†in 2019 International Conference on Informatics, Multimedia, Cyber and Information System (ICIMCIS), 2019, pp. 201–206, doi: 10.1109/ICIMCIS48181.2019.8985201.

N. Kumari, “Online Assessment Of Similarity Between Sentences In Question Analogue Systems,†University Phagwara, Punjab (India), 2016.

R. Rahim, I. Zulkarnain, and H. Jaya, “A review: search visualization with Knuth Morris Pratt algorithm,†in IOP Conference Series: Materials Science and Engineering, 2017.

R. Rahim, A. S. Ahmar, A. P. Ardyanti, and D. Nofriansyah, “Visual Approach of Searching Process using Boyer-Moore Algorithm,†in Journal of Physics: Conference Series, 2017.

F. A. S. Cipriano, “Collaboration Application For Research Education Article Ranking, Using Social Tagging And Boyermoore Horspool String Pattern Algorithm,†University of San Carlos Cebu City, Philippines, 2015.




DOI: http://dx.doi.org/10.26555/jifo.v14i1.a17038

Refbacks

  • There are currently no refbacks.


Copyright (c) 2020 Ali Khumaidi, Yusuf Aras Ronisah, Harjono Padmono Putro

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

____________________________________
JURNAL INFORMATIKA
ISSN : 1978-0524 (print) | 2528-6374 (online)

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View JIFO stats