Realizaciya-algoritma-Rabina-Karpa-i-postroenie-konechnogo-avtomata-dlya-poiska-podstroki

1.

Реализация алгоритма
Рабина-Карпа и построение
конечного автомата для
поиска подстроки

2.

Что такое алгоритм Рабина-Карпа?
Алгоритм Рабина-Карпа — это мощный инструмент для эффективного поиска заданной подстроки (шаблона) в более длинном
тексте. Он был разработан в 1987 году Михаэлем Рабином и Ричардом Карпом, предложившими инновационный подход,
основанный на хешировании.
Хеширование
Разработчики
Эффективность
Использует хеширование для быстрого
Создан Михаэлем Рабином и Ричардом
В среднем работает за линейное время
сравнения подстрок, значительно
Карпом, чьи имена и носит алгоритм.
O(n), где n — длина текста, что делает
ускоряя процесс поиска.
его очень быстрым.
В отличие от наивных алгоритмов, которые сравнивают каждый символ по отдельности, Рабин-Карп преобразует подстроки в
числовые хеш-значения, что позволяет проводить предварительную проверку на равенство гораздо быстрее.

3.

Ключевая идея: хеширование подстрок
Центральная концепция алгоритма Рабина-Карпа заключается в использовании хеш-функций для представления подстрок. Это позволяет быстро определить потенциальные совпадения.
Преобразование в хеш
Каждая подстрока текста, имеющая длину искомого шаблона, преобразуется в уникальное
(или почти уникальное) числовое хеш-значение.
Сравнение хешей
Алгоритм сравнивает хеш-значение искомого шаблона с хеш-значениями всех подстрок
текста. Если хеши совпадают, это указывает на возможное совпадение.
Проверка при коллизии
Поскольку хеш-коллизии (разные строки имеют одинаковый хеш) возможны, при совпадении
хешей проводится посимвольная проверка, чтобы подтвердить, что подстроки
действительно идентичны.
Такой подход значительно сокращает количество прямых посимвольных сравнений, которые являются наиболее затратными операциями в алгоритмах поиска подстрок.

4.

Пример хеш-функции и скользящего
хеша
Для достижения высокой эффективности Рабин-Карп часто использует полиномиальную хешфункцию, которая позволяет реализовать "скользящее" хеширование.
1
2
Полиномиальный хеш
Скользящее хеширование
Формула h(s) = (s[0]*p^(m-1) +
Вместо того чтобы пересчитывать хеш
s[1]*p^(m-2) + ... + s[m-1]*p^0) mod M
каждой новой подстроки с нуля,
используется для вычисления хеша
скользящее хеширование позволяет
подстроки длины m. Здесь p — простое
обновить хеш-значение текущей
число, а M — большое простое число
подстроки до хеша следующей подстроки
(модуль).
за константное время O(1). Это делается
путем вычитания вклада первого символа и
добавления вклада нового последнего
символа.
3
Ускорение поиска
Благодаря скользящему хешу, алгоритм Рабина-Карпа способен обрабатывать весь текст
гораздо быстрее, чем наивный перебор, который потребовал бы O(m) операций для каждой
подстроки.

5.

Ограничения и особенности алгоритма
Несмотря на свою эффективность, алгоритм Рабина-Карпа имеет определенные особенности и потенциальные ограничения, которые
важно учитывать при его применении.
Эффективность при поиске
нескольких шаблонов
Возможные коллизии хешей
Худшее время работы: O(nm)
Хеш-функции не идеальны, и всегда
В худшем случае, если все подстроки
существует вероятность того, что две
дают одинаковый хеш (например, из-за
Алгоритм Рабина-Карпа особенно
разные подстроки будут иметь
неудачно выбранной хеш-функции или
эффективен, когда нужно найти
одинаковое хеш-значение. Это
специально подобранного текста),
несколько шаблонов одинаковой длины в
называется коллизией. Для их обработки
алгоритму придется выполнять
одном тексте. В этом случае хеши всех
необходима дополнительная
посимвольную проверку для каждой
шаблонов можно вычислить заранее, а
посимвольная проверка.
позиции. Это приводит к сложности
затем сравнивать их с хешами подстрок
O(nm), где n — длина текста, а m — длина
текста за один проход.
шаблона. Однако на практике такое
случается редко.
Правильный выбор хеш-функции и модуля M имеет решающее значение для минимизации коллизий и обеспечения хорошей
производительности алгоритма.

6.

Переход к конечному автомату для поиска подстроки
Другой мощный подход к поиску подстрок — использование конечного автомата. Он предлагает детерминированный и эффективный метод, который обрабатывает текст за один проход.
Что такое конечный автомат?
Это математическая модель вычислений, которая может быть в одном из нескольких состояний
в любой момент времени. Автомат последовательно обрабатывает входные символы.
Посимвольная обработка
Автомат принимает символы текста по одному, и каждый символ вызывает переход автомата из
текущего состояния в новое.
Отслеживание прогресса
Каждое состояние автомата кодирует информацию о том, насколько далеко мы продвинулись в
совпадении с искомым шаблоном.
Конечное состояние
Когда автомат достигает специального "конечного" состояния, это сигнализирует о том, что
шаблон успешно найден в тексте.

7.

Построение автомата: состояния и переходы
Построение конечного автомата для поиска подстроки — это систематический процесс, который гарантирует правильную
реакцию на каждый входной символ.
01
02
03
Состояния автомата
Переходы по символу
Префикс-функция (KMP)
Каждое состояние автомата
Если текущий символ текста
Для эффективного вычисления переходов
представляет собой длину самого
соответствует следующему символу
при несовпадении часто используется
длинного префикса шаблона, который
шаблона, автомат переходит в состояние,
концепция префикс-функции из
является суффиксом уже прочитанной
соответствующее более длинному
алгоритма Кнута-Морриса-Пратта (КМП).
части текста. Например, состояние 0
совпавшему префиксу (расширение
Она определяет, насколько нужно
означает отсутствие совпадений,
совпадения). Если нет совпадения,
"откатиться" в шаблоне, чтобы найти
состояние 1 — совпал первый символ
автомат должен найти самый длинный
следующий максимально длинный
шаблона и т.д.
префикс шаблона, который является
префикс, который также является
суффиксом текущей уже прочитанной
суффиксом текущего совпадения.
строки, чтобы не "потерять" часть
совпадения, которое может быть
префиксом шаблона.
Этот механизм позволяет автомату избегать повторного сканирования текста и двигаться только вперед.

8.

Пример автомата для шаблона "abab"
Рассмотрим, как будет выглядеть конечный автомат для поиска шаблона "abab". Это поможет лучше понять концепцию состояний и переходов.
State 2
After 'ab': continues to next on 'a'.
State 0
Initial: on 'a' → state 1.
State 4
Final: 'b' loops, 'a' → state 3.

9.

Как автомат ускоряет поиск подстроки
Основное преимущество конечного автомата — его способность обрабатывать текст непрерывно, без необходимости "отступать" или повторно
сканировать уже пройденные символы.
Однопроходная обработка
1
Автомат просматривает текст только один раз, переходя из состояния в состояние. Это значительно сокращает общее
время выполнения по сравнению с алгоритмами, которые могут требовать повторного анализа уже обработанных данных.
Движение только вперед
Каждый символ текста обрабатывается за константное время, так как автомат просто смотрит на
текущее состояние и текущий символ, чтобы определить следующий переход. Это обеспечивает
линейную временную сложность O(n) для всего текста.
Отсутствие повторных сравнений
В отличие от наивных методов, автомат никогда не "отступает" в тексте.
Все необходимые сравнения символов и определение дальнейших
действий уже "закодированы" в его таблице переходов, что позволяет
ему всегда двигаться вперед.
Таким образом, конечный автомат является одним из наиболее эффективных способов для поиска подстрок, особенно когда шаблон достаточно
длинный или требуется многократный поиск.

10.

Итоги и применение
И алгоритм Рабина-Карпа, и методы, основанные на конечных автоматах, предоставляют мощные решения для задачи поиска подстрок, каждое со своими уникальными преимуществами.
Алгоритм Рабина-Карпа
Хеширование: Использует хеш-функции для быстрого сравнения подстрок.
Скользящий хеш: Позволяет пересчитывать хеш за O(1).
Применимость: Особенно хорош для поиска множества шаблонов одинаковой длины.
Время: Среднее O(n), худшее O(nm) (редко).
Конечный автомат
Линейное время: Всегда обрабатывает текст за O(n) проходов.
Однопроходный: Не требует возвратов по тексту.
Детерминированность: Состояния и переходы строго определены.