EMPIRICAL PERFORMANCE EVALUATION OF KNUTH MORRIS PRATT AND BOYER MOORE STRING MATCHING ALGORITHMS
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
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
It is the policy of the Journal of Duhok University to own the copyright of the technical contributions. It publishes and facilitates the appropriate re-utilize of the published materials by others. Photocopying is permitted with credit and referring to the source for individuals use.
Copyright © 2017. All Rights Reserved.