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

Authors

  • Ali Khumaidi Universitas Krisnadwipayana
  • Yusuf Aras Ronisah Universitas Krisnadwipayana
  • Harjono Padmono Putro

Keywords:

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

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.

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.

Downloads

Published

2020-01-01

Issue

Vol. 14 No. 1 (2020): January 2020

Section

Articles

License

Authors who publish with Jurnal Informatika (JIFO) agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.

 

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