Об алгоритмах поиска компьютерной информации

Жаркова, Анастасия Владимировна; Мусугалиева, Альбина Геннадьевна

Об алгоритмах поиска компьютерной информации

Жаркова, Анастасия Владимировна, Мусугалиева, Альбина Геннадьевна

Дата публикации: 2023

Дата публикации в реестре: 2023-12-05T16:03:34Z

Аннотация:

Исследованы алгоритмы поиска подстроки в строке: наивный, Бойера — Мура, Кнута — Морриса — Пратта, Рабина — Карпа, а также применимые для них джокеры (символы подстановки, «совпадающие» с любым символом или их последовательностью). Реализована программа на языке СД для поиска файлов по различным параметрам, которая позволяет также сканировать заданную директорию с целью поиска вредоносных объектов. Проведены вычислительные эксперименты. Общее лучшее время поиска файлов (достаточно найти первое вхождение) оказалось с помощью алгоритма Бойера — Мура, худшее — с помощью алгоритма Рабина — Карпа. Для поиска файлов по небольшим заданным данным и параметрам можно использовать наивный поиск, для средних и больших данных и параметров при малых образцах лучше использовать алгоритм Кнута — Морриса— Пратта, при больших — Бойера — Мура.

Ключевые слова:
Бойера-Мура алгоритм, Кнута-Морриса-Пратта алгоритм, Рабина-Карма алгоритм, кибербезопасность, поиск подстроки в строке, поиск файла, сканирование

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2023. № 16. С. 126-129