Порівняльний аналіз часової ефективності алгоритмів пошуку підрядка
| dc.contributor.author | Клименко, Іван Вікторович | uk_UA |
| dc.contributor.author | Лебідь, Є. А. | uk_UA |
| dc.date.accessioned | 2025-05-28T08:03:05Z | |
| dc.date.available | 2025-05-28T08:03:05Z | |
| dc.date.issued | 2025 | |
| dc.description | І. Клименко: ORCID 0000-0001-5149-3974 | uk_UA |
| dc.description.abstract | UKR: У статті проведено порівняльний аналіз часової ефективності чотирьох класичних алгоритмів пошуку підрядка (string searching algorithms), що намагаються знайти позицію, де один або декілька текстових рядків (зразків) входять у довший рядок або текст. Порівнювались наступні алгоритми: наївного пошуку (перебору, або ж брут-форс), Кнута-Морріса-Пратта (КМП), Боєра-Мура та Рабіна-Карпа. Дослідження проводилось на трьох різних архітектурах процесорів та з трьома наборами вхідних даних різного обсягу. Алгоритми тестувались за умов як холодного, так і прогрітого кешу. Для зниження впливу сторонніх чинників було реалізовано запуск на одному процесорному ядрі та примусове очищення пам’яті після кожного тесту. Результати експериментів проаналізовано за допомогою розрахунків S- та R-показників ефективності, надано рекомендації щодо доцільності застосування кожного окремого алгоритму в різних умовах. | uk_UA |
| dc.description.abstract | ENG: This paper presents a comparative analysis of the time efficiency of four classical string searching algorithms that attempt to identify the position where one or more pattern strings occur within a longer string or text. The evaluated algorithms include the naive (brute-force) method, Knuth–Morris–Pratt (KMP), Boyer–Moore, and Rabin–Karp. The experiments were conducted on three different processor architectures using three datasets of varying sizes. Each algorithm was tested under both cold and warm cache conditions. To reduce external influence, the benchmarking was limited to a single CPU core, and memory was forcibly cleaned after each run. The experimental results were analyzed using S- and R-indicators of efficiency, and practical recommendations are provided regarding the applicability of each algorithm under different operating conditions. | en |
| dc.identifier.citation | Клименко І. В., Лебідь Є. А. Порівняльний аналіз часової ефективності алгоритмів пошуку підрядка. Інформаційні технології в металургії та машинобудуванні – ІТММ’2025 : тези доп. Міжнародної наук.-техн. конф. (м. Дніпро, 23-24 березня 2025 р.). Дніпро, 2025. C. 256–261. DOI: 10.34185/1991-7848.itmm.2025.01.045. | uk_UA |
| dc.identifier.doi | 10.34185/1991-7848.itmm.2025.01.045 | |
| dc.identifier.issn | 2708-0102 (Online) | |
| dc.identifier.uri | https://journals.nmetau.edu.ua/index.php/itmm/article/view/2107 | en |
| dc.identifier.uri | https://crust.ust.edu.ua/handle/123456789/20388 | en |
| dc.language.iso | uk | |
| dc.publisher | Український державний університет науки і технологій, ІВК «Системні технології», Дніпро | uk_UA |
| dc.subject | інформаційна технологія | uk_UA |
| dc.subject | машинний експеримент | uk_UA |
| dc.subject | S- та R-показники | uk_UA |
| dc.subject | алгоритм пошуку підрядка | uk_UA |
| dc.subject | часова ефективність алгоритму | uk_UA |
| dc.subject | information technology | en |
| dc.subject | machine-based benchmarking | en |
| dc.subject | S- and R-metrics | en |
| dc.subject | substring search algorithm | en |
| dc.subject | time efficiency of algorithms | en |
| dc.subject | КІТ | uk_UA |
| dc.subject.classification | TECHNOLOGY::Information technology | en |
| dc.title | Порівняльний аналіз часової ефективності алгоритмів пошуку підрядка | uk_UA |
| dc.title.alternative | Comparative Analysis of Time Efficiency of Substring Search Algorithms | en |
| dc.type | Thesis | en |