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, 144, p. 03018. EDP Sciences. https://doaj.org/article/c78bdfe402274e139c26295b12694388.
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, 1-14. https://doaj.org/article/27372f01abe34aea9ad7f516f9739556.
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), 68-85. https://doaj.org/article/6c40c705b1fd4263955b4fc066b9155d.
4. Hendrian, D., Ueki, Y., Narisawa, K., Yoshinaka, R., & Shinohara, A. (2019). “Permuted pattern matching algorithms on multi-track strings. Algorithms, 12(4), 73. https://doaj.org/article/4a62dbb11cc14fd0ba9e2be7fa549cc2.
5. Shapira, D., & Daptardar, A. (2006). “Adapting the Knuth–Morris–Pratt algorithm for pattern matching in Huffman encoded texts”. Information processing & management, 42(2), 429-439. https://www.sciencedirect.com/science/article/abs/pii/S0306457305000191.
6. Rytter, W. (2003). “On maximal suffixes and constant-space linear-time versions of KMP algorithm”. Theoretical computer science, 299(1-3), 763-774. https://www.sciencedirect.com/science/article/pii/S030439750200590X.

Received 15.04.2024