Control Systems and Computers

https://doi.org/10.15407/csc.2024.03.045

Control Systems and Computers, 2024, Issue 3 (307), pp. 45-52.

UDC 004.04.043; 004.912; 004.62

K.K. DUKHNOVSKA, Ph.D. in Technical Sciences, Associate Professor at the Department of Software Systems and Technologies, Faculty of Information Technologies, Taras Shevchenko National University of Kyiv, Ukraine, Bohdana Khmelnytskyi Street, 24, Kyiv, Ukraine, 02000, ORCID: https://orcid.org/0000-0002-4539-159X, kseniia.dukhnovska@knu.ua

I.L. MYSHKO, student at the Department of Software Systems and Technologies, Faculty of Information Technologies, Taras Shevchenko National University of Kyiv, Ukraine, Bohdana Khmelnytskyi Street, 24, Kyiv, Ukraine, 02000, ORCID: https://orcid.org/0009-0003-6018-6521, ivan.mishko21@gmail.com

A COMPARATIVE ANALYSIS OF FULL-TEXT SEARCH ALGORITHMS

The exponential growth of electronically stored textual data poses a significant challenge for search engine developers. This paper is dedicated to a detailed study and comparison of three classical full-text search algorithms: Knuth-Morris-Pratt (KMP), Boyer-Moore (BM), and Rabin-Karp (RK). These algorithms are widely used in computer science for efficient substring searching in textual data. The research results allowed us to identify the strengths and weaknesses of each algorithm and to determine the conditions under which each algorithm is most efficient.

Download full text! (On English)

Keywords: full-text search, substring search algorithms, Knuth-Maurice-Pratt algorithm, Boyer-Moore algorithm, Rabin-Karp algorithm.

1. Zhang, Z. (2022). “Review on String-Matching Algorithm”. In SHS Web of Conferences, Vol. 144, p. 03018. EDP Sciences. https://doaj.org/article/c78bdfe402274e139c26295b12694388
   https://doi.org/10.1051/shsconf/202214403018
2. Abikoye, O.C., Abubakar, A., Dokoro, A.H., Akande, O.N., & Kayode, A.A. (2020). “A novel technique to prevent SQL injection and cross-site scripting attacks using Knuth-Morris-Pratt string match algorithm”. EURASIP Journal on Information Security, pp. 1-14. https://doaj.org/article/27372f01abe34aea9ad7f516f9739556
   https://doi.org/10.1186/s13635-020-00113-y
3. Sulaiman, H.E. (2019). “Use the Brute_Force Pattern Matching Algorithm for Misuse Intrusion Detection System”. AL-Rafidain Journal of Computer Sciences and Mathematics, 13 (1), pp. 68-85. https://doaj.org/article/6c40c705b1fd4263955b4fc066b9155d
   https://doi.org/10.33899/csmj.2020.163510
4. Hendrian, D., Ueki, Y., Narisawa, K., Yoshinaka, R., & Shinohara, A. (2019). “Permuted pattern matching algorithms on multi-track strings. Algorithms, 12(4), pp. 73. https://doaj.org/article/4a62dbb11cc14fd0ba9e2be7fa549cc2
   https://doi.org/10.3390/a12040073
5. Shapira, D., & Daptardar, A. (2006). “Adapting the Knuth-Morris-Pratt algorithm for pattern matching in Huffman encoded texts”. Information processing & management, 42(2), pp. 429-439. https://www.sciencedirect.com/science/article/abs/pii/S0306457305000191
   https://doi.org/10.1016/j.ipm.2005.02.003
6. Rytter, W. (2003). “On maximal suffixes and constant-space linear-time versions of KMP algorithm”. Theoretical computer science, 299 (1-3), pp. 763-774. https://www.sciencedirect.com/science/article/pii/S030439750200590X
   https://doi.org/10.1016/S0304-3975(02)00590-X

Received 15.04.2024