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

Из этого туториала Вы узнаете, что такое алгоритм рабин-карп. Также вы найдете рабочие примеры алгоритма рабина-карпа на языках C, C ++, Java и Python.

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

Хеш-функция - это инструмент для сопоставления большего входного значения меньшему выходному значению. Это выходное значение называется хеш-значением.

Как работает алгоритм Рабина-Карпа?

Берется последовательность символов и проверяется возможность наличия искомой строки. Если возможность найдена, выполняется сопоставление символов.

Давайте разберемся с алгоритмом со следующими шагами:

  1. Пусть текст будет: Текст
    И строка, которую нужно искать в приведенном выше тексте, будет: Шаблон
  2. Назначим numerical value(v)/weightсимволам, которые мы будем использовать в задаче. Здесь мы взяли только первые десять алфавитов (то есть от A до J). Текстовые веса
  3. m - длина шаблона, а n - длина текста. Здесь m = 10 and n = 3.
    Пусть d будет количеством символов во входном наборе. Здесь мы взяли набор входных данных (A, B, C,…, J). Так, d = 10. Вы можете принять любое подходящее значение для d.
  4. Рассчитаем хеш-значение паттерна. Хеш-значение текста
хэш-значение для шаблона (p) = Σ (v * dm-1) mod 13 = ((3 * 10 2 ) + (4 * 10 1 ) + (4 * 10 0 )) mod 13 = 344 mod 13 = 6

В приведенном выше вычислении выберите простое число (здесь 13) таким образом, чтобы мы могли выполнять все вычисления с арифметикой с одинарной точностью.

Причина расчета модуля приведена ниже.

  1. Вычислить хеш-значение для текстового окна размером m.
Для первого окна ABC хэш-значение для текста (t) = Σ (v * dn-1) mod 13 = ((1 * 10 2 ) + (2 * 10 1 ) + (3 * 10 0 )) mod 13 = 123 мод 13 = 6
  1. Сравните хеш-значение шаблона с хеш-значением текста. Если они совпадают, то выполняется сопоставление символов.
    В приведенных выше примерах хэш-значение первого окна (т.е. t) совпадает с p, поэтому выберите соответствие символов между ABC и CDD. Поскольку они не совпадают, перейдите в следующее окно.
  2. Мы вычисляем хеш-значение следующего окна, вычитая первый член и добавляя следующий член, как показано ниже.
t = ((1 * 10 2 ) + ((2 * 10 1 ) + (3 * 10 0 )) * 10 + (3 * 10 0 )) mod 13 = 233 mod 13 = 12

Чтобы оптимизировать этот процесс, мы используем предыдущее значение хеш-функции следующим образом.

t = ((d * (t - v (символ, который нужно удалить) * h) + v (символ, который нужно добавить)) mod 13 = ((10 * (6-1 * 9) + 3) mod 13 = 12 Где , h = d м-1 = 10 3-1 = 100.
  1. Для BCC, т = 12 ( ≠ 6). Поэтому переходите к следующему окну.
    После нескольких поисков мы получим совпадение с окном CDA в тексте. Хеш-значение разных окон

Алгоритм

 n = t.length m = p.length h = dm-1 mod qp = 0 t0 = 0 для i = 1 до mp = (dp + p (i)) mod q t0 = (dt0 + t (i)) mod q для s = от 0 до n - m, если p = ts, если p (1… m) = t (s + 1… s + m), вывести «образец найден в позиции» s Если s <nm ts + 1 = (d ( ts - t (s + 1) h) + t (s + m + 1)) mod q

Примеры Python, Java и C / C ++

Python Java C C ++ 
 # Rabin-Karp algorithm in python d = 10 def search(pattern, text, q): m = len(pattern) n = len(text) p = 0 t = 0 h = 1 i = 0 j = 0 for i in range(m-1): h = (h*d) % q # Calculate hash value for pattern and text for i in range(m): p = (d*p + ord(pattern(i))) % q t = (d*t + ord(text(i))) % q # Find the match for i in range(n-m+1): if p == t: for j in range(m): if text(i+j) != pattern(j): break j += 1 if j == m: print("Pattern is found at position: " + str(i+1)) if i < n-m: t = (d*(t-ord(text(i))*h) + ord(text(i+m))) % q if t < 0: t = t+q text = "ABCCDDAEFG" pattern = "CDD" q = 13 search(pattern, text, q)
 // Rabin-Karp algorithm in Java public class RabinKarp ( public final static int d = 10; static void search(String pattern, String txt, int q) ( int m = pattern.length(); int n = txt.length(); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern.charAt(i)) % q; t = (d * t + txt.charAt(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (txt.charAt(i + j) != pattern.charAt(j)) break; ) if (j == m) System.out.println("Pattern is found at position: " + (i + 1)); ) if (i < n - m) ( t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q; if (t < 0) t = (t + q); ) ) ) public static void main(String() args) ( String txt = "ABCCDDAEFG"; String pattern = "CDD"; int q = 13; search(pattern, txt, q); ) )
 // Rabin-Karp algorithm in C #include #include #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) printf("Pattern is found at position: %d ", i + 1); ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )
 // Rabin-Karp algorithm in C++ #include #include using namespace std; #define d 10 void rabinKarp(char pattern(), char text(), int q) ( int m = strlen(pattern); int n = strlen(text); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < m - 1; i++) h = (h * d) % q; // Calculate hash value for pattern and text for (i = 0; i < m; i++) ( p = (d * p + pattern(i)) % q; t = (d * t + text(i)) % q; ) // Find the match for (i = 0; i <= n - m; i++) ( if (p == t) ( for (j = 0; j < m; j++) ( if (text(i + j) != pattern(j)) break; ) if (j == m) cout << "Pattern is found at position: " << i + 1 << endl; ) if (i < n - m) ( t = (d * (t - text(i) * h) + text(i + m)) % q; if (t < 0) t = (t + q); ) ) ) int main() ( char text() = "ABCCDDAEFG"; char pattern() = "CDD"; int q = 13; rabinKarp(pattern, text, q); )

Ограничения алгоритма Рабина-Карпа

Ложный удар

Когда хеш-значение шаблона совпадает с хеш-значением окна текста, но окно не является фактическим шаблоном, это называется ложным совпадением.

Ложное попадание увеличивает временную сложность алгоритма. Чтобы минимизировать ложное попадание, мы используем модуль. Это значительно снижает ложное попадание.

Сложность алгоритма Рабина-Карпа

В среднем и лучшем случае сложность алгоритма Рабина-Карпа равна, O(m + n)а сложность худшего случая - O (mn).

Сложность наихудшего случая возникает, когда ложные попадания происходят во всех окнах.

Приложения алгоритма Рабина-Карпа

  • Для сопоставления с образцом
  • Для поиска строки в большом тексте

Интересные статьи...