Control Systems and Computers, N3, 2024, Стаття 4
Dukhnovska K.K., Myshko I.L. Analysis and Comparison of Full-Text Search Algorithms. Сontrol Systems and Computers. 2024. № 3. C.
УДК 004.04.043; 004.912; 004.62
К.К. Духновська, кандидат технічних наук, доцент, кафедра програмних систем і технологій, факультет інформаційних технологій, Київський національний університет імені Тараса Шевченка, вул. Богдана Гаврилишина, 24, м. Київ, Україна, 02000, ORCID: https://orcid.org/0000-0002-4539-159X, kseniia.dukhnovska@knu.ua
І.Л. Мишко, студент, кафедра програмних систем і технологій, факультет інформаційних технологій, Київський національний університет імені Тараса Шевченка, вул. Богдана Гаврилишина, 24, м. Київ, Україна, 02000, ORCID: https://orcid.org/0009-0003-6018-6521,
ivan.mishko21@gmail.com
ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ПОВНОТЕКСТОВОГО ПОШУКУ
Вступ. Ця робота була спрямована на всебічне дослідження та порівняння ефективності різних алгоритмів повнотекстового пошуку, зокрема алгоритмів Кнута-Морріса-Пратта та Боєра-Мура, з метою визначення оптимального алгоритму для повнотекстового пошуку. Крім того, дослідження оцінило вплив паралельного обчислення на швидкість пошуку та виявило обмеження наявних підходів.
Мета. Метою дослідження є підвищення ефективності алгоритмів у контексті пошуку текстових шаблонів у великих обсягах даних.
Методи. Алгоритми повнотекстового пошуку.
Результати. Аналізуючи результати дослідження, можна зробити висновок, що алгоритм Бойєра-Мура виявився найефективнішим за швидкістю пошуку для обох тестових запитів. Його удосконалена евристика “поганого символу” дає змогу значно прискорити процес, пропускаючи непотрібні порівняння символів. Попри те, що алгоритм Кнута-Моріса-Пратта вважався найкращим у попередніх дослідженнях, в даному випадку він посів друге місце за швидкістю роботи.
Проте для коротких пошукових шаблонів алгоритм Кнута-Моріса-Пратта все ще може мати перевагу завдяки своїй оптимізованій структурі та здатності уникати повторних порівнянь символів. Алгоритми Бітап та Рабіна-Карпа продемонстрували гірші результати щодо швидкості пошуку порівняно з алгоритмами Бойєра-Мура та Кнута-Моріса-Пратта.
Щодо якості пошуку, всі алгоритми показали однакову кількість знайдених збігів для обох запитів, що свідчить про їх рівноцінну здатність знаходити релевантні документи.
Використання паралельних потоків значно покращило швидкість пошуку для всіх алгоритмів, особливо для довших текстів. Прискорення сягало від 70% до 81% залежно від алгоритму та запиту. Хоча паралелізм вимагав додаткових витрат на синхронізацію потоків, загальний виграш часу виявився вартим цих зусиль.
Висновки. Перспективними напрямками подальших досліджень є розширення набору тестових даних, детальний аналіз впливу різних параметрів алгоритмів на їхню ефективність, а також розробка адаптивних та інтелектуальних методів пошуку з використанням машинного навчання.
Результати цього дослідження мають практичне значення для розробки ефективних пошукових систем, систем керування базами даних та інших програмних продуктів, які використовують повнотекстовий пошук.
Завантажити повний текст! (англійською)
Ключові слова: повнотекстовий пошук, алгоритми пошуку підрядків, алгоритм Кнута-Моріса-Пратта, алгоритм Боєра-Мура, алгоритм Рабіна-Карпа.
- Zhang, Z. (2022). “Review on String-Matching Algorithm”. In SHS Web of Conferences, 144, p. 03018. EDP Sciences. https://doaj.org/article/c78bdfe402274e139c26295b12694388.
- 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.
- 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.
- 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.
- 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.
- 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.
Надійшла 15.04.2024
