Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Метод Бойера-Мура на Python
Сегодня рассматриваем метод Бойера-Мура. Хороший метод и не слишком сложный. Вообще основные попытки улучшить (оптимизировать) поиск подстроки в строке, это поиск алгоритма позволяющего передвигаться по строке быстрее, увеличивать шаг. И данный подход не исключение. Мне лично решение нравится.
Ниже представлена программа, осуществляющая поиск по методу Бойера-Мура.
Пояснения к программе
- В программе поиск осуществляет функция search(). Важным является список ml. Структура очень интересна. Элемент списка либо -1, либо значение самого правого индекса символа. А индексация в ml осуществляется с помощью кодов символа. Т.е. по коду символа мы может определить индекс данного символа в крайне правом положении. Например 'qwerewr' для символа 'e' код которого равен 101, в списке с индексом 101 будет стоять 4.
- Следует отметить размер списка ml. Всё зависит какие символы есть обеих строках. Соответственно наибольший код символа, который там встречается может быть взят за размер ml. Я же взял размер списка 2048, а мог бы и 256, так как представлены только символы латиницы. Но если иметь в виду, что могут быть и кириллические символы, то размера вполне хватает. Вот данный список и даёт возможность в некоторых случаях передвигаться не на 1, а на большее количество шагов.
- Внешний цикл while представляет передвижение подстроки по строке. Тут важно какое значение принимает i. Если оно будет увеличивать каждый раз на 1, то мы получим тривиальный поиск по строке. Внутренний цикл это проверка в обратном порядке есть ли совпадение подстроки с соответствующим отрезком строки. Если j < 0 то подтверждено совпадение, т.е. подстрока найдена.
- Ну, а далее две формулы увеличения i. Если мы попадаем на -1 в списке ml, то приращение будет равно 1. В формуле max(1, j - ml[ord(ss[i + j])]) единица может получиться если разность меньше 1. Шаг больше единицы получается, когда при сдвиге совмещаются два одинаковых символа в большой строке и в подстроке. При чем для подстроки имеется в виду последний символ, если их несколько. Это не значит что подстрока найдена, это значит что искать совпадение при меньшем шаге не нужно.
Как и в других методах поиска, для разных строк скорость поиска может быть разной. Есть разновидности данного алгоритма. Возможно в следующих статьях я о них расскажу.
Ну, пока всё!
Продолжение следует...
Пишите свои предложения и замечания, и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.
