Алгоритм Рабина-Карпа — это алгоритм сопоставления строк, который эффективно ищет шаблон в тексте с помощью хеширования. Он работает, сначала создавая хэш-значение для заданного шаблона, перемещая окно той же длины по тексту, а затем создавая хэш-значения для каждой подстроки текста, равной по длине шаблону. Алгоритм определяет, действительно ли подстрока равна шаблону, если хеш-значение подстроки совпадает с хеш-значением шаблона.
Это очень простая реализация, которую нам нужно понять, чтобы понять фактический алгоритм Рабина-Карпа, который обсуждается ниже в статье. Здесь хеш-значение для шаблона «AV» равно 4 + 5 = 9, поэтому хеш-значение сравнивается с каждыми двумя символами из данной текстовой строки. Если хеш-значение совпадает, мы только что нашли шаблон. Если нет, то мы перемещаемся на 1 индекс в текстовой строке и снова сравниваем хеш-значение из 2 символов. В приведенном выше gif значение каждой 2 пары текста отображается красным цветом, поскольку оно не соответствует значению данного шаблона, пока оно не соответствует шаблону в последних 2 парах, где значение отображается зеленым цветом.
Фундаментальной идеей алгоритма Рабина-Карпа является скользящая хеш-функция, которая позволяет нам быстро вычислять хэш-значения для каждой подстроки текста и сравнивать их с хэш-значением шаблона.
Скользящая хэш-функция использует хеш-значение предыдущей подстроки длиной m-1, а также символ, добавляемый в конец подстроки, для вычисления хэш-значения подстрока длины m. В результате удаления первого символа из предыдущей подстроки и добавления нового символа хеш-значение текущей подстроки «скатывается» от значения предыдущей подстроки, что приводит к появлению термина «скользящая хеш-функция».
Алгоритм Рабина-Карпа: ложные совпадения
При использовании простой хеш-функции, даже если шаблон не равен, хеш-значение может быть таким же, как в приведенном выше примере. Здесь мы получаем хэш-код из текста, совпадающего с хэш-кодом нашего шаблона. Таким образом, если мы возьмем такую простую хеш-функцию, которая дает простые значения, существует возможность столкновения с другим шаблоном, имеющим такое же значение хеш-функции, хотя они не являются одними и теми же шаблонами. Это так называемые ложные попадания. Как избежать ложных попаданий? Просто возьмите сильную хэш-функцию. Итак, вот идея хэш-функции, чтобы избежать ложных попаданий Рабина Карпа.
Рабин-Карп: Актуальный алгоритм
Вместо использования простой хэш-функции используйте приведенную выше формулу, предложенную Рабином Карпом для расчета хеш-функции. Почему мы использовали 10? Это просто потому, что мне было бы легче продемонстрировать, а вам легче понять. Это общая идея, данная Рабином Карпом в случае струн. Хеш-функция означает, что мы можем определить собственную функцию в зависимости от шаблона данных, с которыми мы работаем. Например, если мы работаем только с заглавными буквами, то мы можем использовать 26 в качестве основы вместо 10. Если мы включаем как прописные, так и строчные буквы, мы можем использовать базу как 56. Аналогично, разные символы могут быть представлены в ASCII. Если мы включим все строчные и прописные буквы, цифры, знаки препинания и контрольные характеристики, мы можем взять 128 в качестве основы в качестве 7-битной схемы окончания символов. Если мы возьмем 1 бит со знаком, то в качестве расширенного 8-битного ASCII он может удвоиться до 256. Таким образом, мы можем взять 256 в качестве базового значения. Это полностью зависит от языка и типа данных, с которыми мы работаем.
Рабин-Карп: Использование мода
С помощью приведенной выше формулы для хеш-функции мы можем получить очень длинное значение, которое слишком велико для хранения в памяти. Мы устанавливаем значение режима в большое простое число, чтобы уменьшить вероятность коллизий хэшей и иметь дело со значениями хэша, которые слишком велики для хранения в памяти. Это связано с тем, что операция модуля уменьшает размер хэш-значения до меньшего значения, которое может быть сохранено в памяти. Кроме того, использование простого числа в качестве значения режима помогает работать с хеш-значениями, экономя место. Используя простое число в качестве значения режима, мы можем гарантировать, что результирующие хеш-значения по-прежнему уникальны и могут использоваться для эффективного определения совпадений между шаблоном и подстроками в тексте.
Внедрив эту хеш-функцию, мы просто уменьшили шансы получить спиритические удары. Что уменьшит временную сложность по сравнению с ранее использовавшейся простой хэш-функцией. Эффективность алгоритма сопоставления шаблонов на основе хэшей зависит от того, насколько хорошо реализована хеш-функция. Ниже приведены характеристики, которыми должна обладать хорошая хэш-функция:
- Единообразие. Функция должна создавать хэш-значения, равномерно распределенные по всему диапазону возможных хэш-значений. Делая это, мы гарантируем, что вероятность ложных попаданий (столкновений) сведена к минимуму.
- Скорость. Хеш-функция должна быть быстрой и эффективной в своих операциях, чтобы она могла быстро определить хеш-значение строки, это также уменьшит временную сложность.
- Детерминизм. Для заданной входной строки хеш-функция всегда должна возвращать одно и то же хэш-значение.
// Rabin-Karp algorithm with hash function of base 10
int rabin_karp(string text, string pattern) {
int n = text.length();
int m = pattern.length();
int p = 0;
int t = 0;
int h = 1;
// Calculate hash multiplier h = 10^(m-1)
for (int i = 0; i < m - 1; i++) {
h = (h * 10) % MOD;
}
// Calculate hash value of pattern and first substring of text
for (int i = 0; i < m; i++) {
p = (p * 10 + pattern[i] - '0') % MOD;
t = (t * 10 + text[i] - '0') % MOD;
}
// Search for pattern in text
for (int i = 0; i <= n - m; i++) {
// If hash values match, compare substring and pattern
if (t == p) {
bool match = true;
for (int j = 0; j < m; j++) {
if (text[i+j] != pattern[j]) {
match = false;
break;
}
}
if (match) {
return i; // pattern found at index i
}
}
// Calculate hash value of next substring
if (i < n - m) {
t = ((t - (text[i] - '0') * h) * 10 + (text[i+m] - '0')) % MOD;
if (t < 0) {
t += MOD;
}
}
}
return -1; //if not found
}
В этой статье мы углубимся в мир алгоритмов сопоставления строк, исследуя два наиболее часто используемых метода — наивный алгоритм и алгоритм Рабина-Карпа. Сначала мы представим основную идею наивного алгоритма, который включает сравнение каждой возможной подстроки текста с шаблоном. Однако мы также выделяем главный недостаток этого подхода — алгоритм сравнивает множество ненужных подстрок, что приводит к значительной временной сложности. Затем мы переключаем наше внимание на алгоритм Рабина-Карпа, который устраняет ограничения наивного алгоритма, используя хеш-функцию для сравнения шаблона с текстом. Мы объясняем ключевые компоненты этого алгоритма, включая значение хеш-функции и модуль, используемые в вычислениях. Кроме того, мы обсудим скользящую хэш-функцию, используемую в алгоритме Рабина-Карпа, которая позволяет эффективно обновлять хэш-значение подстроки.
Все изображения, использованные в этой статье, ниже на @learnwithutsav
Теперь вы хотите прочитать этот наивный алгоритм сопоставления строк 👇 и узнать его недостатки.
Повышение уровня кодирования
Спасибо, что являетесь частью нашего сообщества! Перед тем, как ты уйдешь:
- 👏 Хлопайте за историю и подписывайтесь на автора 👉 Utsav Poudel
- 📰 Смотрите больше контента в публикации Level Up Coding
- 💰 Бесплатный курс собеседования по программированию ⇒ Просмотреть курс
- 🔔 Подписывайтесь на нас: Twitter | ЛинкедИн | "Новостная рассылка"
🚀👉 Присоединяйтесь к коллективу талантов Level Up и найдите прекрасную работу
