Отчет по алгоритмам поиска подстроки в строке
Соколков Алексей, ФТ-103, email: [email protected]
Задача - реализовать несколько методов поиска подстроки в строке, сравнить их по времени выполнения и используемой памяти.
- Поиск грубой силой (Bruteforce)
- Алгоритм Боэра-Мура
- Алгоритм Ахо-Корасика
- Алгоритм Рабина-Карпа
- Алгоритм Кнут-Моррис-Пратт (оригинальная и модифицированная версии)
В алгоритмах при нажатии на заголовок Алгоритм вы перейдете по ссылке в источник, где была взята информация (если он был).
Поиск грубой силой (Bruteforce)
Полный перебор (метод грубой силы) — перебор всевозможных вариантов из списка.
Находится первое вхождение искомой строки.
Алгоритм
Сравниваем i-ые символы искомой строки и текста, если они равны, то берем i+=1. Так до того момента, пока не закончатся символы искомой строки – в таком случае номер вхождения найден. Как только символы не равны – начинаем поиск заново, но уже не берем первый элемент текста (потом второй и т. д.).
Сложность
n – количество символов в тексте, m – количество символов искомой строки
Алгоритм Боэра-Мура
Находится первое вхождение искомой строки.
Алгоритм
Сканирование слева направо, сравнение справа налево. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и выполняется поиск следующего вхождения подстроки.
Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.
«Несколько» символов – количество символов, которое вычисляется перед выполнением алгоритма с помощью таблицы суффиксов, в которой вычисляется, на сколько будет сдвинут шаблон относительно текста.
Сложность
На непериодических шаблонах - O(|n|+|m|+|Σ|)
На периодических - O(|n|*|m|+|Σ|)
n – количество символов в тексте, m – количество символов искомой строки, Σ — алфавит, на котором проводится сравнение
Алгоритм Рабина-Карпа
Алгоритм ищет строку в тексте с помощью хеширования.
Находятся все вхождения искомой строки.
Алгоритм
Вычисляется хеш шаблона строки.
Вычисляется хеш подстроки в тексте строки.
Сравнивается хеш подстроки текста с хешем шаблона.
Если они совпадают, то сравниваются отдельные символы для выявления точного совпадения двух строк.
Если они не совпадают, то окно подстроки сдвигается путём увеличения индекса и повторяется третий пункт для вычисления хеша следующих m символов, пока не будут пройдены все n символов.
Сложность
n – количество символов в тексте, m – количество символов искомой строки
Алгоритм Кнута-Морриса-Пратта
Находится первое вхождение искомой строки.
Алгоритм
Формируем массив (префикс-функцию), который будет использоваться при сдвиге образа вдоль строки.
При несовпадении, сдвигаем весь образ на то количество символов, которое было вычислено в префикс-функции.
Сложность
n – количество символов в тексте, m – количество символов искомой строки
Модифицированный алгоритм Кнута-Морриса-Праттаотличается лишь тем, что после нахождения искомой строки поиск не останавливается. Таким образом, находятся все вхождения искомой строки.
Алгоритм Ахо-Корасика
Находятся все вхождения искомого массива строк.
Алгоритм
Алгоритм строит конечный автомат, которому затем передаёт строку поиска. Автомат получает по очереди все символы строки и переходит по соответствующим рёбрам. Если автомат пришёл в конечное состояние, соответствующая строка словаря присутствует в строке поиска.
Несколько строк поиска можно объединить в дерево поиска, так называемый бор (префиксное дерево). Бор является конечным автоматом, распознающим одну строку из m — но при условии, что начало строки известно.
Первая задача в алгоритме — научить автомат «самовосстанавливаться», если подстрока не совпала. При этом перевод автомата в начальное состояние при любой неподходящей букве не подходит, так как это может привести к пропуску подстроки (например, при поиске строки aabab, попадается aabaabab, после считывания пятого символа перевод автомата в исходное состояние приведёт к пропуску подстроки — верно было бы перейти в состояние a, а потом снова обработать пятый символ). Чтобы автомат самовосстанавливался, к нему добавляются суффиксные ссылки, нагруженные пустым символом ⌀ (так что детерминированный автомат превращается в недетерминированный). Например, если разобрана строка aaba, то бору предлагаются суффиксы aba, ba, a. Суффиксная ссылка — это ссылка на узел, соответствующий самому длинному суффиксу, который не заводит бор в тупик (в данном случае a).
Для корневого узла суффиксная ссылка — петля. Для остальных правило таково: если последний распознанный символ — c , то осуществляется обход по суффиксной ссылке родителя, если оттуда есть дуга, нагруженная символом c, суффиксная ссылка направляется в тот узел, куда эта дуга ведёт. Иначе — алгоритм проходит по суффиксной ссылке ещё и ещё раз, пока либо не пройдёт по корневой ссылке-петле, либо не найдёт дугу, нагруженную символом.
Сложность
Если быть точным и учитывать вычисления автомата и суф. ссылок, то алгоритм работает O(M*k+N+t), где M=bohr.size().
Параметры компьютера, на котором проводилось тестирование
- Операционная система: Windows 10 Home
- Процессор: AMD Ryzen 5 3500U with Radeon Vega Mobile Gfx 2.10 GHz
- Оперативная память: 8,00 ГБ
Методика тестирований на время
При тестировании алгоритмов на время, используется модуль timeit. Он позволяет измерить время выполнения выбранного участка кода выбранное количество раз (в нашем случае за это отвечает переменная it в main.py).
Считается минимальное время выполнения, максимальное и среднее. Среднее высчитывается путем сложения всех посчитанных времен для одного текста и деления на их количество. Потом с помощью формулы высчитывается стандартное отклонение. Оно добавляется и вычитается к среднему времени, так мы получаем диапазон, в которые попадает значительная часть экспериментальных данных.
Время будет указано на вертикальной оси в графике в секундах.
При тестировании каждый случай будет запускаться 50 раз.
Методика тестирований на используемую память
В случае тестирования алгоритмов на потребляемую память, используется memory_usage() из модуля memory_profiler(). Он позволяет посчитать используемую алгоритмом память.
Считается минимальная используемая память, максимальная и средняя. Средняя высчитывается путем сложения всей памяти для одного текста и деления на их количество.
Память будет указана на вертикальной оси в графике в МБ.
При тестировании каждый случай будет запускаться 50 раз.
Тестирование времени выполнения
Лучший вариант
Под лучшим вариантом подразумевается текст, в котором искомая строка стоит в самом начале. Например: искомая строка A, тогда лучшим вариантом будет называться текст – A0000000.
Проведем тестирование с искомой строкой A и найдем минимальное, максимальное и среднее (с учетом отклонения) время соответственно (далее всегда будут приводиться по 3 графика, даже если не будет упоминания об этом).
Выводы
Начнем с того, что на графиках не видно алгоритма Кнутта-Морриса-Пратта, потому что его перекрывает результат алгоритма поиска грубой силой. Скорость их выполнения равна, так как они находят первое вхождение искомой строки и выходят, чего нельзя сказать о модифицированном алгоритме Кнутта-Морриса-Пратта. После первого вхождения искомой строки он продолжает искать как и алгоритм Ахо-Корасика, поэтому их графики похожи. Небольшие различия вызваны разными реализациями поиска.
Различия алгоритма Бойера-Мура и алгоритмов Брутфорса с Кнуттом-Моррисом-Праттом также обусловлены разными реализациями поиска.
Что касается алгоритма Рабина-Карпа, такое долгое выполнение связано с тем, что алгоритм постоянно считает хеши строки и текста и идет до самого конца, чтобы найти все вхождения.
Также, стоит заметить, что на последнем графике не видно отклонений. Однако на самом деле они есть, но очень маленькие, и их можно заметить только под сильным приближением (черные полосы).
Средний вариант
Под средним вариантом подразумевается текст, в котором искомая строка стоит в самом конце. Например: искомая строка A, тогда средним вариантом будет называться текст – 0000000A.
Проведем тестирование с искомой строкой A.
Выводы
В тестировании лучшего варианта искомая строка была в самом начале, из-за чего некоторым алгоритмом не нужно было продолжать поиск. В данном случаем видно, что время выполнения тех алгоритмов, которые всегда проходят весь текст, практически не изменилось, относительно тестирования лучшего варианта. Однако у остальных алгоритмов время выполнения поднялось достаточно сильно.
Худший вариант
Под худшим вариантом подразумевается текст, в котором искомая строка стоит в самом конце и перед ней есть похожие строки. Например: искомая строка ABCD, тогда худшим вариантом будет называться текст – ABCABCABCABCD.
Проведем тестирование с искомой строкой ABCD.
Выводы
Как видно, относительно тестирования средних вариантов, в данном случае увеличилось время выполнения алгоритмов, которые делают сдвиг более чем на 1 символ.
Случайные тексты
Выводы
Под каждый текст есть свой алгоритм, который справиться быстрее всех, но если не известно в каком виде будет текст – лучше (среди проверенных в отчете алгоритмов) использовать алгоритм поиска грубой силы и Кнутта-Морриса-Пратта, так как по статистике, они в среднем справляются быстрее всех.
Тестирование потребляемой памяти
Тестирование памяти проводилось на тех же типах текстов (min, max, average) и в вариантах использовались те же шаблоны (например, ABCD и текст ABCABCABCD).
Лучший вариант
Средний вариант
Худший вариант
Случайные тексты
Выводы
В отличие от измерений времени, использованная память имела настолько маленькие различия в типах min, max и average, что не было смысла их включать в отчет.
Среди тех, что есть можно с легкостью выделить сходства соотношений времени выполнения и затрачиваемой памяти - в "хороших" текстах памяти затрачивается меньше, чем в "средних".
Среди результатов памяти лишь выделяется "худший" вариант с ростом алгоритма Ахо-Корасика. Это происходит из-за поиска множества строк в тексте и сложности самого текста, так как он состоит из множества слов, которые нужно найти без последнего символа, поэтому приходится делать большое количество проверок.
Заключение
Итак, мы провели достаточно широкий анализ некоторых алгоритмов поиска вхождений подстроки в строку, объяснили полученные результаты и обнаружили некоторые интересные факты, связанные с особым подбором текстов.
Также мы сделали тестирующие пакеты для наших реализаций алгоритмов.
Теперь мы опишем структуру папки с проектом, в которой находятся все реализации, тесты и дополнительные материалы:
- ak.py – реализация алгоритма Ахо-Корасика
- bm.py - реализация алгоритма Бойера-Мура
- bruteforce.py - реализация алгоритма поиска грубой силой
- kmp.py – реализации алгоритмов Кнутта-Морриса-Пратта и его модифицированной версии
- rk.py - реализация алгоритма Рабина-Карпа
- tests.py – тесты к реализациям алгоритмов
- main.py – реализация подсчета затрачиваемого алгоритмами времени
- extensions.py – генерация случайных текстов, создание пустого листа (для записи результатов) и чтение командной строки
- time_calculation.py – методы, использующиеся в подсчете времени выполнения
- memory_calculation.py – методы, использующиеся в подсчете затрачиваемой памяти
- files.py – метод записи результатов в файл