Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Алгоритм Карпа-Рабина при поиске подстроки в строке на Python
Не хотелось бы формально излагать алгоритм, а подвести к нему понятными рассуждениями. Попробую.
Одним из вариантов поиска подстроки в строке ранее был изложен простой подход. Проходя по строке проверяем совпадение части строки, которую мы ищем, с соответствующим срезом в строке, где мы ищем. Если есть совпадение, то сравниваем всю строку. По сути две проверки. Но этими двумя проверками мы пытаемся оптимизировать алгоритм. Ведь второй проверки может и не понадобиться.
Сегодня что-то подобное, но не совсем. Как говорится, есть нюансы.
В общем случае идея очень проста. В качестве первичного поиска вместо среза попробуем взять число, которое характеризует строку. Это так называемое хеш-функция (hash-функция) строки. Общая идея заключается в том, что сравнивать числа быстрее и удобнее.
Что такое хеш-функция строки? Если совсем упрощённо, то это число, которое вычисляется по какому-либо алгоритму на основе данной строки. Если хеши двух строк не совпадают, то это гарантия, что строки разные. Обратное в общем случае не верно. Тут правда можно говорить о вероятности того, что у двух разных строк одинаковые хеши. Но оставим это математикам.
А как вычислять хеш? Да по-разному. Придумаем пока свой примитивный вариант. Например, сумма кодов (функция ord()) всех символов строки. Для нашего начального эксперимента вполне себе подойдёт.
Функция hash() (см. Рис. 1) как раз вычисляет хеш строки, т.е. является хеш-функцией. Если хеш подстроки и среза строки, такой же длины совпадают, то далее мы проверяем уже точное совпадение.
Всё вроде бы хорошо, только сумма кодов символов строки вычисляется как-то неуклюже. Согласен. Сумму кодов строки s можно вычислить просто так sum(map(ord, s)).
На рис. 2 hash-функция вычисляется более оптимально.
Что ещё нас должно волновать? А вот что. Многократный вызов функции вычисления хеша. При чём, если длина строки, где ищется другая строка, велика, мы можем получить ситуацию, когда вычисления производятся десятки тысяч раз. Не очень хороший фактор для алгоритма.
Попробуем применить приём скользящего окна. Идея заключается в том, что если мы вычислили функцию для конкретного среза, то хеш для следующего среза можно получить из данного хеша путём простых действий. Вот наш примитивный хеш как раз удовлетворяет такому механизму. Нужно вычесть значение ord() для первого символа отрезка и прибавить ord() для символа, следующего сразу за концом среза.
На рис. 3 реализован механизм скользящего окна. Вот строка
(hs1 - ord(s[i])) + ord(s[i + l2]) как раз и осуществляет сдвиг хеша в строке.
Наконец обратимся к программе (см. рис. 4), где реализован более сложный хеш. Его называют полиномиальный или хеш Горнера, по имени британского математика, занимавшегося полиномами. Он похож на наш простой хеш, но в нём член умножается на степень некоторого числа (число k). Данный алгоритм вычисления обладает тем свойством "скольжения".
Разобранный в статье механизм поиска всех подстрок в строке и называют алгоритма Карпа-Рабина.
Ну, пока всё!
Пишите свои предложения и замечания, и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.