EMPIRICAL PERFORMANCE EVALUATION OF KNUTH MORRIS PRATT AND BOYER MOORE STRING MATCHING ALGORITHMS

  • SARHAN S. DAWOOD Dept.of Computer Science, College of Science, University of Duhok.Kurdistan Region-Iraq
  • SAMAN A. BARAKAT Dept.of Computer Science, College of Science, University of Duhok.Kurdistan Region-Iraq
Keywords: Boyer Moore, Knuth Morris Pratt, String Matching, Performance Evaluation

Abstract

Many algorithms have been proposed for string matching in order to find a specific pattern in a given text. These algorithms have been used in many applications such as software editors, genetics, Internet search engines, natural language processing, etc. The aim of this paper is to evaluate the performance of two popular algorithms: Boyer Moore (BM) and Knuth Morris Pratt (KMP) in terms of execution time. The algorithms have been programmed using Java and Java Microbenchmark Harness to evaluate their execution time using a number of experimental test scenarios. Results show that the BM algorithm outperformed the KMP algorithm in all test scenarios.

Downloads

Download data is not yet available.

References

 AbdulRazzaq, A. A., Rashid, N. A. A., Hasan, A. A., & Abu-Hashem, M. A. (2013). The exact string matching algorithms efficiency review. Global Journal on Technology, 4(2), 576–589.

 Boyer, R. S., & Moore, J. S. (1977). A fast string searching algorithm. Communications of the ACM, 20(10), 762–772. https://doi.org/10.1145/359842.359859

 Catania, L. (2018). A fast string matching algorithm with moderately long patterns and small alphabets. https://doi.org/10.13140/RG.2.2.13345.51040

 Chandraseta, R. (2017). Optimization of Boyer-Moore-Horspool-Sunday Algorithm. Retrieved from https://www.semanticscholar.org/paper/Optimization-of-Boyer-Moore-Horspool-Sunday-Chandraseta/d740cce2b915860a3ac6b237ea818655f9f2a5fd

 Charras, C., & Lecroq, T. (2004). Handbook of Exact String Matching Algorithms.

 Choudhary, R., Rasool, A., & Khare, N. (2012). Variation of Boyer-Moore String Matching Algorithm: A Comparative Analysis. International Journal of Computer Science and Information Security, 10(2), 95–101.

 De V. Smit, G. (1982). A comparison of three string matching algorithms. Software: Practice and Experience, 12(1), 57–66. https://doi.org/10.1002/spe.4380120106

 Ersin, A. K., Carus, A., & Mesut, A. (2007). The Efficiency Of String Matching Algorithms On Natural Languages.

 Gurung, D., Chakraborty, U. K., & Sharma, P. (2016). Intelligent Predictive String Search Algorithm. Procedia Computer Science, 79, 161–169. https://doi.org/10.1016/j.procs.2016.03.116

 Knuth, D. E., Morris, Jr., J. H., & Pratt, V. R. (1977). Fast Pattern Matching in Strings. SIAM Journal on Computing, 6(2), 323–350. https://doi.org/10.1137/0206024

 Oracle. (2019). Code Tools: jmh. Retrieved June 1, 2019, from https://openjdk.java.net/projects/code-tools/jmh/

 Rahim, R., Zulkarnain, I., & Jaya, H. (2017). A review: search visualization with Knuth Morris Pratt algorithm. {IOP} Conference Series: Materials Science and Engineering, 237, 12026. https://doi.org/10.1088/1757-899x/237/1/012026

 Sarhan, Q. I., & Gawdan, I. S. (2017). Java Message Service Based Performance Comparison of Apache ActiveMQ and Apache Apollo Brokers. Science Journal of University of Zakho, 5(4), 307–312. https://doi.org/10.25271/2017.5.4.376

 Sunday, D. M. (1990). A Very Fast Substring Search Algorithm. Commun. ACM, 33(8), 132–142. https://doi.org/10.1145/79173.79184

 Tsarev, R., Chernigovskiy, A., A Tsareva, E., V Brezitskaya, V., Yu Nikiforov, A., & A Smirnov, N. (2016). Combined string searching algorithm based on knuth-morris- pratt and boyer-moore algorithms. IOP Conference Series: Materials Science and Engineering, 122, 12034. https://doi.org/10.1088/1757-899X/122/1/012034

 Wahlström, S. (2013). Evaluation of String Searching Algorithms. Retrieved from https://www.semanticscholar.org/paper/Evaluation-of-String-Searching-Algorithms-Wahlström/8afc6c601aa4ae2e0878c943735e75935e995b58

Published
2020-09-12
How to Cite
DAWOOD, S. S., & BARAKAT, S. A. (2020). EMPIRICAL PERFORMANCE EVALUATION OF KNUTH MORRIS PRATT AND BOYER MOORE STRING MATCHING ALGORITHMS. Journal of Duhok University, 23(1), 134-143. https://doi.org/10.26682/sjuod.2020.23.1.14
Section
Pure and Engineering Sciences