Алгоритм Рабина-Карпа

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

Основная идея

Основная идея алгоритма Рабина-Карпа заключается в использовании хеш-функции для быстрого сравнения подстрок. Вместо прямого сравнения каждой подстроки текста с образцом, алгоритм сначала вычисляет хеш-значения и только при совпадении хешей выполняет непосредственное сравнение строк.

Принцип работы

Хеширование образца и начальной подстроки текста:
- Вычисляем хеш-значение образца длиной $m$ .
- Вычисляем хеш-значение первой подстроки текста такой же длины.
Сравнение хеш-значений:
- Сравниваем хеш-значения образца и текущей подстроки. Если они совпадают, то выполняем прямое сравнение строк.
- Если строки совпадают, значит, найдено вхождение образца в текст.
Скользящее окно:
- Используем технику “скользящего окна” для вычисления хеша следующей подстроки, избегая полного пересчета.
- Обновляем хеш-значение, удаляя влияние первого символа предыдущей подстроки и добавляя влияние нового символа.

Вычисление хеш-функции

Для вычисления хеша часто используется метод полиномиального хеширования. Предположим, что мы имеем строку $S = s_{0} s_{1} s_{2} ... s_{m - 1}$ , где $s_{i}$ — это ASCII-код i-го символа. Хеш-значение может быть вычислено как:

$h (S) = (s_{0} \cdot p^{m - 1} + s_{1} \cdot p^{m - 2} + ... + s_{m - 1} \cdot p^{0}) mod q$

где $p$ и $q$ — некоторые простые числа.

Пример реализации на Python

Рассмотрим реализацию алгоритма на Python:

def rabin_karp(text, pattern):
    n = len(text)
    m = len(pattern)
    p = 31  # Простое число для хеширования
    q = 10**9 + 7  # Большое простое число для предотвращения переполнения
 
    # Вычисляем хеш-значение образца
    pattern_hash = 0
    text_hash = 0
    p_power = 1
 
    for i in range(m):
        pattern_hash = (pattern_hash + ord(pattern[i]) * p_power) % q
        text_hash = (text_hash + ord(text[i]) * p_power) % q
        if i != m - 1:
            p_power = (p_power * p) % q
 
    results = []
 
    # Сравнение хеш-значений и поиск совпадений
    for i in range(n - m + 1):
        if pattern_hash == text_hash:
            if text[i:i + m] == pattern:
                results.append(i)
 
        if i < n - m:
            text_hash = (text_hash - ord(text[i]) + q) % q
            text_hash = (text_hash * p) % q
            text_hash = (text_hash + ord(text[i + m]) * p_power) % q
 
    return results
 
# Пример использования
text = "ababbaba"
pattern = "aba"
positions = rabin_karp(text, pattern)
print("Позиции вхождения образца:", positions)

Преимущества алгоритма Рабина-Карпа

Эффективность при множественных поисках:
- Алгоритм хорошо работает, когда требуется найти несколько образцов в одном тексте.
- Использование хеширования ускоряет процесс поиска.
Обновление хеша:
- Метод скользящего окна позволяет обновлять хеш-значение за $O (1)$ времени, что делает алгоритм эффективным для длинных текстов.

Заключение

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

m4lvx

Explorer