Порівняльний аналіз алгоритмів пошуку підрядків у великих текстових даних

Abstract

Об'єкт дослідження – алгоритми пошуку підрядків у текстових даних великого обсягу. Предмет дослідження – часова та просторова складність алгоритмів пошуку підрядків, їх практична ефективність при обробці текстів різного характеру, зокрема багатобайтових Unicode-текстів у кодуванні UTF-8. Мета роботи – провести порівняльний аналіз класичних алгоритмів пошуку одиночного підрядка (наївний метод, Кнута–Морріса–Пратта, Боєра–Мура, Рабіна–Карпа) та алгоритму Ахо–Корасік для множинного пошуку; дослідити вплив багатобайтового кодування UTF-8 на продуктивність алгоритмів. Методи дослідження: теоретичний аналіз обчислювальної складності, експериментальне порівняння на основі бенчмаркінг-тестів мовою Python. У роботі здійснено систематичний огляд алгоритмів пошуку підрядків, надано математичне обґрунтування їх часової та просторової складності. Реалізовано програмний стенд для бенчмаркінгу, проведено шість серій експериментів із текстами різного обсягу, алфавіту та кодування. Досліджено вплив кодування UTF-8 на продуктивність алгоритмів на прикладі кириличного тексту: встановлено, що побайтовий пошук повільніший за посимвольний на 21–61% через збільшення обсягу даних удвічі, а нерівномірний розподіл байтів кирилиці знижує ефективність евристики поганого символу алгоритму Боєра–Мура. Показано, що алгоритм Ахо–Корасік забезпечує прискорення у 295.7 рази при 1000 шаблонах порівняно з послідовним пошуком. Сформульовано практичні рекомендації щодо вибору алгоритму залежно від характеристик вхідних даних.

The research object is substring search algorithms applied to large-scale text data. The subject of the study is the time and space complexity of these algorithms and their practical performance on texts of varying structure and size, including multibyte Unicode texts encoded in UTF-8. The purpose of the thesis is to conduct a comparative analysis of classical single-pattern search algorithms (naive, Knuth–Morris–Pratt, Boyer–Moore, Rabin–Karp) and the Aho–Corasick multi-pattern algorithm, and to investigate the impact of UTF-8 multibyte encoding on algorithm performance. Research methods: theoretical analysis of computational complexity, experimental comparison using benchmarking tests implemented in Python. The thesis presents a systematic review of substring search algorithms with mathematical justification of their complexity. A benchmarking framework was implemented, and six series of experiments were conducted with texts of different volumes, alphabets, and encodings. The impact of UTF-8 encoding on algorithm performance was investigated using Cyrillic text: byte-level search was found to be 21–61% slower than character-level search due to doubled data volume, and the uneven distribution of Cyrillic bytes reduces the effectiveness of the Boyer–Moore bad character heuristic. The Aho–Corasick algorithm was shown to provide a 295.7-fold speedup with 1000 patterns compared to sequential search. Practical recommendations for algorithm selection based on input data characteristics are formulated.